Jerarquia aritmètica

Archiu:Arithmetic hierarchy.svg

Una ilustració de cóm els nivells de la jerarquia aritmètica es relacionen entre sí i a on es mostren la posició en la jerarquia.

La jerarquia aritmètica, o jerarquia de Kleene classifica certs conjunts basant-se en la complexitat de les fòrmules que els definixen. Tot conjunt que rep una classificació és cridat aritmètic. La jerarquia aritmètica és important en la teoria de recursión, teoria de conjunts descriptivos eficients, i l'estudi de teories formals tals com aritmètica de Peano. l'algoritme de Tarski-Kuratowski dona una forma fàcil d'obtindre un llímit superior sobre les classificacions que s'assignen a una fòrmula i al conjunt que la mateixa definix.

La jerarquia hiperaritmética i la jerarquia analítica estenen la jerarquia aritmètica classificant fòrmules i conjunts adicionals.

Jerarquia aritmètica de fòrmules

La jerarquia aritmètica assigna classificacions a les fòrmules en el llenguage d'axioma de Peano (aritmètica de primer orde). Les classificacions són identificades com $Σ_{n}^{0}$ i $Π_{n}^{0}$ per a número natural n. Les lletres gregues són ací símbols sense resaltar, que indica que les fòrmules no contenen paràmetros de conjunt.

Les classificacions $Σ_{n}^{0}$ i $Π_{n}^{0}$ es definixen en forma inductiva per a tot número natural n utilisant les següents regles:

Si $ϕ$ és llògicament equivalent a una fòrmula sense quantificadors, se li assigna la classificació $Σ_{0}^{0} = Π_{0}^{0}$ .
Si $ϕ$ és llògicament equivalent a una fòrmula del tipo $\exists n_{1} \dots \exists n_{k} ψ$ , a on $ψ$ és $Π_{n}^{0}$ , llavors a $ϕ$ se li assigna la classificació $Σ_{n + 1}^{0}$ .
Si $ϕ$ és llògicament equivalent a una fòrmula del tipo $\forall n_{l} \dots \forall n_{k} ψ$ , a on $ψ$ és $Σ_{n}^{0}$ , llavors a $ϕ$ se li assigna la classificació $Π_{n + 1}^{0}$ .

Jerarquia aritmètica de conjunts d'número natural

Siga un conjunt X definit per la fòrmula φ(n) en el llenguage d'aritmètica de Peano si $n \in X \leftrightarrow ℕ ⊨ ϕ (n)$ . Lo que significa que els elements de X són exactament els números que satisfan φ. Un conjunt és definible per mig d'aritmètica de primer orde si el mateix és definit per alguna fòrmula en el llenguage de l'aritmètica de Peano.

A cada conjunt X de número natural que és definible per mig d'aritmètica de primer orde se'ls assignen classificacions del tipo $Σ_{n}^{0}$ , $Π_{n}^{0}$ , i $Δ_{n}^{0}$ , a on $n$ és un número natural, segons s'indica a continuació. Si X és definible per una fòrmula $Σ_{n}^{0}$ llavors a $X$ se li assigna la classificació $Σ_{n}^{0}$ . Si X és definible per una fòrmula $Π_{n}^{0}$ llavors a $X$ se li assigna la classificació $Π_{n}^{0}$ . Si $X$ és $Σ_{n}^{0}$ i $Π_{n}^{0}$ llavors a $X$ se li assigna la classificació adicional $Δ_{n}^{0}$ .

Notar que casi no té sentit referir-se a fòrmules del tipo $Δ_{n}^{0}$ ; el primer quantificador d'una fòrmula és o ben existencial o universal. Per lo tant un conjunt $Δ_{n}^{0}$ no es troba definit per una fòrmula del tipo $Δ_{n}^{0}$ ; més be, són les fòrmules $Σ_{n}^{0}$ i $Π_{n}^{0}$ les que definixen el conjunt.
S'utilisa una definició paralela per a definir la jerarquia aritmètica en potències finitas cartesianas d'número natural. En lloc de fòrmules en una variable lliure, s'utilisen fòrmules en k variables lliures per a definir la jerarquia aritmètica sobre conjunts de k-tuplos d'número natural.
Jerarquia aritmètiques relativizadas

De la mateixa manera com es pot definir que és lo que significa que un conjunt X siga recursivo con relación a un atre conjunt I permetent que el càlcul que definix a X consulte a I com si fora un oràcul, podem estendre este concepte a tota la jerarquia aritmètica i definir lo que significa que X siga $Σ_{n}^{0}$ , $Δ_{n}^{0}$ o $Π_{n}^{0}$ en I, lo que s'indica respectivament com $Σ_{n}^{0, Y}$ $Δ_{n}^{0, Y}$ i $Π_{n}^{0, Y}$ . Per a fer açò fixem un conjunt de sancers I i vàrem sumar un predicat de pertinença en I al llenguage de l'aritmètica de Peano. Després afirmem que X es troba en $Σ_{n}^{0, Y}$ si està definit per una fòrmula $Σ_{n}^{0}$ en este llenguage expandit. És dir, X és $Σ_{n}^{0, Y}$ si es troba definit per una fòrmula $Σ_{n}^{0}$ que està habilitada a formular preguntes sobre pertinença en I. Alternativament, es poden interpretar els conjunts $Σ_{n}^{0, Y}$ com aquells conjunts que poden ser construïts començant a partir de conjunts recursivos en I i alternativament proyectant i prenent complements d'estos conjunts fins a n voltes.
Per eixemple siga I un conjunt de sancers. I siga X el conjunt d'número entero divisibles per un element de Y. Llavors X queda definida per la fòrmula $ϕ (n) = \exists m \exists t (Y (m) \land m \times t = n)$ per lo que X es troba en $Σ_{1}^{0, Y}$ (en realitat es troba també en $Δ_{0}^{0, Y}$ ya que podem acotar abdós quantificadors en n).

Reducibilidad i graus de l'aritmètica

La reducibilidad aritmètica és un concepte intermig entre la reducibilidad de Turing i la reducibilidad hiperaritmética. Un conjunt és aritmètic (o definible aritméticamente) si és definit per alguna fòrmula en el llenguage d'aritmètica de Peano. En forma equivalent es diu que X és aritmètic si X és $Σ_{n}^{0}$ o $Π_{n}^{0}$ per a algun sancer n. Un conjunt X és aritmètic en un conjunt I, lo que s'expressa com $X \leq_{A} Y$ , si X és definible per alguna fòrmula en el llenguage d'aritmètica de Peano estés per un predicat de pertinença en I. En forma equivalent, X és aritmètic en I si X es troba en $Σ_{n}^{0, Y}$ o $Π_{n}^{0, Y}$ per a algun sancer n. Un sinònim de $X \leq_{A} Y$ és: X és aritméticamente reducible a I

La relació $X \leq_{A} Y$ és reflexiva i transitiva, i per lo tant la relació $\equiv_{A}$ definida per la regla

X \equiv_{A} Y \Leftrightarrow X \leq_{A} Y \land Y \leq_{A} X

és una relació d'equivalència. Les classes d'equivalència d'esta relació són cridades els graus aritmètics; els mateixos es troben parcialment ordenats en $\leq_{A}$ .

Vore també

Referències

G.Japaridze, "The logic of the arithmetical hierarchy", Annals of Pure and Applied Logic 66 (1994), pp.89-112.
Moschovakis, Yiannis N. (1980). Descriptive Set Theory, North Holland. ISBN 0-444-70199-0.

Este artícul conté una traducció derivada de «Jerarquía aritmética» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.