Aritmetika aro

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

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[redakti | redakti fonton]

  • 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[redakti | redakti fonton]

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

Vidu ankaŭ[redakti | redakti fonton]