Aritmetika aro

En matematika logiko aritmetika aro estas kalkulebla aro kiu povas esti difinita per formulo de aritmetiko de la unua ordo. La aritmetikaj aroj estas orditaj en la aritmetika hierarkio.

Funkcio

$f:\subseteq \mathbb {N} ^{k}\to \mathbb {N}$

estas nomita kiel aritmetike difinebla se la grafikaĵo de $f$ estas aritmetika aro.

Ekzemploj

• komputeblaj funkcioj estas aritmetike difineblaj
• Aro de ĉiuj primoj estas aritmetika
• rekursie numerigeblaj aroj estas aritmetikaj
• Teoremo de Tarski pri nedifinebleco: Se estas donita numerado $\nu _{\Sigma }$ sur la aritmetika formuloj de logiko de la unua ordo. Tiam la aro $\nu _{\Sigma }^{-1}[A]$, kie $A$ estas la ara variablo libera kaj veraj propozicioj, estas ne aritmetika. (???)

Propraĵoj

• La komplemento de aritmetika aro estas aritmetika aro
• La nombro de aritmetikaj aroj estas kalkulebla.

Vidu ankaŭ

• Aritmetika hierarkio