Computadoras

Jerarquía aritmética de conjuntos de números naturales
Sea un conjunto X definido por la fórmula φ(n) en el lenguaje de aritmética de Peano si . Lo que significa que loselementos de X son exactamente los números que satisfacen φ. Un conjunto es definible mediante aritmética de primer orden si el mismo es definido por alguna fórmula en el lenguajede la aritmética de Peano.
A cada conjunto X de números naturales que es definible mediante aritmética de primer orden se les asignan clasificaciones del tipo , , y , donde nes un número natural, según se indica a continuación. Si X es definible por una fórmula entonces a X se le asigna la clasificación . Si X es definible por una fórmula entoncesa X se le asigna la clasificación . Si X es y entonces a X se le asigna la clasificación adicional .
Notar que casi no tiene sentido referirse a fórmulas del tipo ; el primercuantificador de una fórmula es o bien existencial o universal. Por lo tanto un conjunto no se encuentra definido por una fórmula del tipo ; más bien, son las fórmulas y lasque definen el conjunto.
Se utiliza una definición paralela para definir la jerarquía aritmética en potencias finitas cartesianas de números naturales. En vez de fórmulas conuna variable libre, se utilizan fórmulas con k variables libres para definir la jerarquía aritmética sobre conjuntos de k-tuplos de números naturales.
La suma, la multiplicacióny la potenciación son operaciones DIRECTAS, porque en ellas, conociendo ciertos datos, se halla un resultado.

La resta, la división, la radicación y la logaritmación sonoperaciones INVERSAS, así:

-La resta es inversa de la suma.
-La división es inversa de la multiplicación.
-la radicación y la logaritmación son inversas de la potenciación.