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

estas nomita kiel aritmetike difinebla se la grafikaĵo de  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  sur la aritmetika formuloj de logiko de la unua ordo. Tiam la aro , kie  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

Kategorio:Teorio de efikaj priskribaj aroj