Web Analytics Made Easy - Statcounter

[HOME PAGE] [STORES] [CLASSICISTRANIERI.COM] [FOTO] [YOUTUBE CHANNEL]

Jerarquia aritm??tica - Viquip??dia

Jerarquia aritm??tica

De Viquip??dia

En l??gica matem??tica, la jerarquia aritm??tica o jerarquia de Kleene ??s una classificaci?? de conjunts de nombres naturals (i per extensi?? de qualsevol tipus d'elements que es codifiquin en nombres naturals) segons la complexitat de les f??rmules que els defineixen. Els conjunts classificats s'anomenen aritm??tics.

La jerarquia aritm??tica ??s important en la teoria de la recursi??, en la teoria descriptiva de conjunts efectiva, i en l'estudi de teories formals (com per exemple l'aritm??tica de Peano).

L'algorisme de Tarski-Kuratowski permet obtenir f??cilment una fita superior per a la classificaci?? dels conjunts aritm??tics.

La jerarquia hiperaritm??tica i la jerarquia anal??tica s??n extensions de la jerarquia aritm??tica que permeten classificar m??s conjunts.

Taula de continguts

[edita] La jerarquia aritm??tica per f??rmules

La jerarquia aritm??tica classifica en primer lloc les f??rmules (sense par??metres) del llenguatge de l'aritm??tica de primer ordre. Les classes de f??rmules es denoten \Sigma^0_n i \Pi^0_n per cada natural n.

Si una f??rmula ?? ??s l??gicament equivalent a una f??rmula que nom??s t?? quantificadors fitats aleshores ?? pertany a \Sigma^0_0 i a \Pi^0_0.

Les classes \Sigma^0_n i \Pi^0_n es defineixen inductivament per cada nombre natural n de la seg??ent manera:

  • Si ?? ??s l??gicament equivalent a una f??rmula del tipus \exists n_1 \cdots \exists n_k \psi, on ?? ??s \Pi^0_n, llavors ?? ??s \Sigma^0_{n+1}.
  • Si ?? ??s l??gicament equivalent a una f??rmula del tipus \forall n_l \cdots \forall n_k \psi, on ?? ??s \Sigma^0_n, llavors ?? ??s \Pi^0_{n+1}.

Com que tota f??rmula ??s equivalent a una f??rmula en forma normal prennexa, tota f??rmula pertany a alguna classe de la jerarquia. D'altra banda, com que a tota f??rmula se li poden afegir quantificadors banals (??s a dir, que no lliguin cap variable lliure), si una f??rmula pertany a \Sigma^0_n o a \Pi^0_n, tamb?? pertany a \Sigma^0_m o a \Pi^0_m per cada m m??s gran que n. Ara b??, la classe m??s significativa per cada f??rmula ??s la que t?? el m??nim ??ndex n.

[edita] La jerarquia aritm??tica per conjunts de nombres naturals

Diem que un conjunt X de nombres naturals ??s definible per una f??rmula ??(n) del llenguatge de l'aritm??tica de Peano si n \in X \leftrightarrow \mathbb{N} \models \phi(n), ??s a dir, si els elements de X s??n exactament els nombres que verifiquen ??. Un conjunt ??s definible en l'aritm??tica de primer ordre si ??s definible per alguna f??rmula del llenguatge de l'aritm??tica de Peano.

A cada conjunt X de nombres naturals definible en l'aritm??tica de primer ordre es classifica en una classe \Sigma^0_n, \Pi^0_n, o \Delta^0_n, per algun n natural de la manera seg??ent. Si X ??s definible per una f??rmula \Sigma^0_n, llavors X pertany a \Sigma^0_n. Si X ??s definible per una f??rmula \Pi^0_n, llavors X pertany a \Pi^0_n. Si X pertany a la vegada a \Sigma^0_n i a \Pi^0_n, llavors pertany a \Delta^0_n.

Observem que no tindria gaire sentit parlar de f??rmules \Delta^0_n car el primer quantificador d'una f??rmula prennexa ??s universal o b?? existencial. Per tant, no diem que un conjunt de \Delta^0_n ??s definible per una f??rmula \Delta^0_n, sin?? que ??s definible per una f??rmula \Sigma^0_n i per una f??rmula \Pi^0_n. Fixem-nos que els conjunts de \Delta^0_n s??n exactament els conjunts recursius.

De manera an??loga es pot fer una classificaci?? de conjunts de k-tuples de naturals. Simplement en lloc d'usar f??rmules amb una variable lliure cal usar f??rmules amb k variables lliures.

[edita] Jerarquies aritm??tiques relativitzades

De la mateixa manera que es pot definir que un conjunt X sigui recursiu relativament a un altre conjunt Y tot permetent que la computaci?? de X consulti Y com a oracle, podem estendre aquesta noci?? a tota la jerarquia aritm??tica i definir qu?? significa que un conjunt X sigui \Sigma^0_n, \Delta^0_n o \Pi^0_n relativament a Y, i ho denotem respectivament amb \Sigma^{0,Y}_n \Delta^{0,Y}_n i \Pi^{0,Y}_n. A tal efecte fixem un conjunt de naturals Y i afegim al llenguatge un predicate unari per a la pertinen??a a Y. Diem que X ??s a \Sigma^{0,Y}_n si ??s definible per una f??rmula \Sigma^0_n d'aquest llenguatge expandit. Per dir-ho m??s intu??tivament, X ??s \Sigma^{0,Y}_n si ??s definible per una f??rmula \Sigma^{0}_n que pot consultar Y. Tamb?? podem veure els conjunts de \Sigma^{0,Y}_n com aquells que es construeixen a partir de conjunts recursius relativament a Y tot projectant-los i agafant complements fins a n vegades.

Per exemple, sigui Y un conjunt de naturals i sigui X el conjunt dels nombres divisibles per algun element de Y. Llavors X ??s definible per la f??rmula \phi(n)=\exists m \exists t (Y(m)\and m\times t = n) i per tant X ??s a \Sigma^{0,Y}_1 (de fet ??s a \Delta^{0,Y}_0 ja que podr??em fitar ambd??s quantificadors per n).

[edita] Reductibilitat aritm??tica i graus

La reductibilitat aritm??tica ??s una noci?? intermitja entre la reductibilitat de Turing i la reductibilitat hiperarim??tica.

Un conjunt ??s aritm??tic (o aritm??ticament definible) si ??s definible per alguna f??rmula del llenguatge de l'aritm??tica de Peano, ??s a dir, si pertany a \Sigma^0_n o a \Pi^0_n per algun natural n. Un conjunt X ??s aritm??tic relativament a un altre conjunt Y, i es denota X \leq_A Y, si X ??s definible alguna f??rmula del llenguatge de l'aritm??tica de Peano expandit amb un predicat unari per a la pertinen??a a Y, ??s a dir, si X pertany a \Sigma^{0,Y}_n o a \Pi^{0,Y}_n per algun natural n. En aquest cas tamb?? es diu que X ??s aritm??ticament reductible a Y.

La relaci?? \leq_A ??s reflexiva i transitiva, i per tant la seva simetritzaci?? \equiv_A definida aix??

X \equiv_A Y \Leftrightarrow X \leq_A Y \and Y \leq_A X

??s una relaci?? d'equival??ncia. Les classes d'equival??ncia d'aquesta relaci?? s??n els graus aritm??tics i tenen un ordre parcial indu??t per \leq_A.