Аритметичка хијерархија

У математичкој логици, аритметичка хијерархија, аритметичка хијерархија или Клин-Мостовскова хијерархија класификује одређене скупове на основу сложености формула које их дефинишу. Било који скупи који добија класификацију се зове аритметички.

Рачунска хијерархија је важна у теорији рекурзије и ефективне теорије описног скупа, и студија формалних теорија као што је Пеано аритметика.

Тарски-Куратовски алгоритам пружа једноставан начин да добијете горњу границу класификације одређене за формулу и сет који га дефинише.

Хипераритметичка хијерархија и аналитичка хијерархија продужују аритметичку хијерархију како би класификовали додатне формуле и скупове.

Аритметичка хијерархија формула

Рачунска хијерархија додељује класификације формулама у језику првог реда аритметике. Класификације су означене као ${\mathrm{\Sigma }}_n^0$ и ${\mathrm{\Pi }}_n^0$ за природне бројеве n (укључујући 0). Грчка писма су кључни симболи, што указује да формуле не садрже постављене параметре.

Ако  је формула $\varphi$ логички еквивалентна формули са само ограниченим кватификаторима онда $\varphi$ су додељене класификације ${\mathrm{\Sigma }}_0^0$ и ${\mathrm{\Pi }}_0^0$.

Класификације ${\mathrm{\Sigma }}_n^0$ и ${\mathrm{\Pi }}_n^0$ се индуктивно дефинишу за сваки природан број n користећи следећа правила:

• Ако је $\varphi$ логички еквивалентна формули форме$\mathrm{\exists }{n}_1\mathrm{\exists }{n}_2\cdots \mathrm{\exists }{n}_k\psi$, где $\psi$ је ${\mathrm{\Pi }}_n^0$, онда $\varphi$ је додељена класификација ${\mathrm{\Sigma }}_{n+1}^0$.
• Ако је $\varphi$ логички еквивалентна формули форме $\mathrm{\forall }{n}_1\mathrm{\forall }{n}_2\cdots \mathrm{\forall }{n}_k\psi$, где $\psi$ је ${\mathrm{\Sigma }}_n^0$, онда $\varphi$ је додељена класификација ${\mathrm{\Pi }}_{n+1}^0$.

Такође, ${\mathrm{\Sigma }}_n^0$ формула је еквивалентна формули која почиње са неким егзистенцијалним квантификаторима и алтернативи $n-1$ пута између низа егзистенцијалних и универзалних квантификатора; док ${\mathrm{\Pi }}_n^0$ формула је еквивалентна формули која почиње са неким универзалним квантификаторима и алтернативама на сличан начин.

Зато што је свака формула еквивалентна формули у Пренекс нормалном облику, свакој формули без постављених квантификатора је додељена најмање једна класификација. Будући редудантни квантификатори се могу додати било којој формули, једанпут када је формула додељена класификација ${\mathrm{\Sigma }}_n^0$ или ${\mathrm{\Pi }}_n^0$ биће додељене класификације ${\mathrm{\Sigma }}_m^0$ и ${\mathrm{\Pi }}_m^0$ за свако m веће од n. Најважнија класификација која се додељује формули је она са најмање n, јер је то довољно да се утврде све остале класификације.

Аритметичка хијерархија скупова природних бројева

Скуп природних бројева X је дефинисан формулом φ језиком Пеано аритметике (језик првог реда са симболима "0" за нула, "S" за функцију наслеђивања, "+" за збир, "×" за множење и "=" за једнакост), ако су елементи X  тачно бројеви који задовољавају φ. То је, за све природне бројеве n,

где је $\underset{\_}{n}$ је цифра на језику аритметике која одговара $n$. Скуп је дефинисан у првом реду аритметике ако је то дефинисано на основу неке формуле на језику Пеано аритметике.

Сваком скупу природних бројева X који је дефинисан првим редом аритметике су додељене класификације форме  ${\mathrm{\Sigma }}_n^0$, ${\mathrm{\Pi }}_n^0$, и ${\mathrm{\Delta }}_n^0$, где је $n$ природан број, како следи. Ако је X дефинисан са ${\mathrm{\Sigma }}_n^0$ формулом онда је X додељена класификација ${\mathrm{\Sigma }}_n^0$. Ако је X дефинисан са ${\mathrm{\Pi }}_n^0$ формулом онда је X додељена класификација ${\mathrm{\Pi }}_n^0$. Ако је X и ${\mathrm{\Sigma }}_n^0$ и ${\mathrm{\Pi }}_n^0$ онда је $X$ додељена додатна класификација ${\mathrm{\Delta }}_n^0$.

Имајте на уму да ретко има смисла говорити о ${\mathrm{\Delta }}_n^0$ формулама; први квантификатор формуле је било егзистенцијалан или универзалан. Онда ${\mathrm{\Delta }}_n^0$ скуп није дефинисан са ${\mathrm{\Delta }}_n^0$ формулом; пре него, где су и ${\mathrm{\Sigma }}_n^0$ и ${\mathrm{\Pi }}_n^0$  формуле које дефинишу скуп.

Паралелна дефиниција се користи за дефинисање рачунске хијерархије на коначан Декартов производ природних бројева. Уместо формула са једном слободном променљивом, формуле са k слободним бројем променљивих се користе за дефинисање рачунске хијерархије скуповима од k-торки природних бројева.

Релативизиране аритметичке хијерархије

Као што можемо дефинисати шта то значи за скуп X да буде рекурзиван у односу на други скуп Y дозвољавајући израчунавања дефинисањем X да се консултује са Y и можемо да продужимо овај појам на целу аритметичку хијерархију и дефинисати шта то значи за X да буде ${\mathrm{\Sigma }}_n^0$, ${\mathrm{\Delta }}_n^0$ или ${\mathrm{\Pi }}_n^0$ у Y, означавају редом ${\mathrm{\Sigma }}_n^{0,Y}$ ${\mathrm{\Delta }}_n^{0,Y}$ и ${\mathrm{\Pi }}_n^{0,Y}$. Да би се то урадило, треба поправити низ целих бројева Y и да се дода предикат за чланство у Y на језику Пеано аритметике. Тада смо рекли да је X у ${\mathrm{\Sigma }}_n^{0,Y}$ ако је дефинисано са ${\mathrm{\Sigma }}_n^0$ формула у овом проширеном језику. Другим речима X је ${\mathrm{\Sigma }}_n^{0,Y}$ ако је дефинисан са ${\mathrm{\Sigma }}_n^0$ формулом којој је дозвољено да поставља питања у вези чланства у Y. Алтернативно може се погледати ${\mathrm{\Sigma }}_n^{0,Y}$ скупова као и оне који могу да се граде почев од скупова рекурзивних у Y и наизменично узимање унија и пресека ових скупова до n пута.

Ако је на пример Y скуп целих бројева. Нека X буде скуп бројева дељивих неким елементом из Y. Онда је X дефинисано формулом $\varphi (n)=\mathrm{\exists }m\mathrm{\exists }t(Y(m)\wedge m\times t=n)$ тако да је X у ${\mathrm{\Sigma }}_1^{0,Y}$ (у ствари је у ${\mathrm{\Delta }}_0^{0,Y}$ као и јер смо могли да ограничимо обе стране квантификатора n).

Аритметичко смањење и степени

Аритметичко смањење је средњи појам између Тјуринговог смањења и хипераритметичког смањења.

Скуп је аритметички (такође аритметика и аритметички дефинисан) ако је то дефинисано на основу неке формуле на језику Пеано аритметике. Еквивалентно X је аритметички ако је X  ${\mathrm{\Sigma }}_n^0$ или ${\mathrm{\Pi }}_n^0$ за неки цео број n. Скуп X је аритметички у скупу Y, који је означен као $X{\le }_{A}Y$, ако је X дефинисано неком формулом на језику Пеано аритметике друге стране предиката за чланство у Y. Еквивалентно, X је аритметичко у Y ако је X у ${\mathrm{\Sigma }}_n^{0,Y}$ или ${\mathrm{\Pi }}_n^{0,Y}$ за неки цео број n. Синоним за $X{\le }_{A}Y$ је: X је аритметички смањено на Y.

Релација $X{\le }_{A}Y$ је рефлексивна и прелазна, а тиме и однос ${\equiv }_A$ дефинисан правилом

је релација еквиваленције. Еквивалентне класе ове релације се називају аритметички степени; они су делимично наређени под ${\le }_A$.

Аритметичка хијерархија подскупова Канторовог и Беровог простора

Канторов простор, означен $2^{\omega }$, је скуп свих бесконачних секвенци 0s и 1s; Беров простор, означен ${\omega }^{\omega }$ или $𝒩$, је скуп свих бесконачних секвенци природних бројева. Имајте на уму да елементи Канторовог простора могу да се идентификују са комплета целих бројева и елемената Беровог простора са функцијама природних бројева до целих бројева.

Обична аксиоматизација од другог реда аритметике користи језик сета са седиштем у којима су постављени квантификатори који се природно могу сматрати квантификовањем преко Канторовог простора. Подскуп Канторовог простора је додељен класификацији ${\mathrm{\Sigma }}_n^0$ ако је дефинисан са ${\mathrm{\Sigma }}_n^0$ формулом. Скупу је додељена класификација ${\mathrm{\Pi }}_n^0$ ако је дефинисан са формулом ${\mathrm{\Pi }}_n^0$. Ако је скуп и ${\mathrm{\Sigma }}_n^0$ и ${\mathrm{\Pi }}_n^0$ онда му се додељује додатна класификација ${\mathrm{\Delta }}_n^0$. На пример ако је $O\subset 2^{\omega }$ скуп свих бесконачних бинарних низова где нису сви 0 (или еквивалентно скуп свих непразних скупова целих бројева). Као $O=\{X\in 2^{\omega }|\mathrm{\exists }n(X(n)=1)\}$ видимо да је $O$ дефинисано формулом ${\mathrm{\Sigma }}_1^0$ и стога је ${\mathrm{\Sigma }}_1^0$ скуп.

Имајте на уму да, иако су оба елемента Канторовог простора (сматра се скупом целих бројева) и подскупова у Канторовом простору су класификовани у аритметичке хијерархије, то нису исте хијерархије. У ствари, однос између две хијерархије је занимљив и нетривијалан. На пример ${\mathrm{\Pi }}_n^0$ елементи Канторовог простора нису (генерално) исти као елемнти из $X$ Канторовог простора тако да је $\{X\}$  ${\mathrm{\Pi }}_n^0$ подскуп Канторовог простора. Међутим, многи занимљиви резултати се односе на две хијерархије.

Постоје два начина да се подскуп Беровог простора може сврстати у аритметичке хијерархије.

• Подскуп Беровог простора има одговарајући подскуп Канторовог простора која се односи на сваку функцију из $\omega$ у $\omega$ на карактеристику функције њеног графа. Подскуп Беровог простора има класификацију ${\mathrm{\Sigma }}_n^1$, ${\mathrm{\Pi }}_n^1$, или ${\mathrm{\Delta }}_n^1$ ако и само ако одговарајући подскуп Канторовог простора има исту класификацију.
• Еквивалентна дефиниција аналитичке хијерархије Беровог простора даје дефинисање аналитичке хијерархије формула помоћу функционалне верзије другог реда аритметике; онда аналитичка хијерархија подгрупе Канторовог простора може бити дефинисана од хијерархије на Беровом простору. Ова дефиниција алтернативно даје управо исте класификације као за прву дефиницију.

Паралелне дефиниције се користе за дефинисање рачунске хијерархије на коначна картезијанска овлашћења Беровог простора или Канторовог простора, користећи формуле са неколико слободних променљивих. Рачунска хијерархија се може дефинисати на било који ефикасни пољски простор; дефиниција је посебно једноставна за Канторов простор и Беров простор јер се уклапа са језиком обичног другог реда аритметике.

Имајте на уму да можемо дефинисати аритметичку хијерархију подскупова Канторовог и Беровог простора у односу на неки скуп природних бројева. У ствари подебљана ${\mathrm{\Sigma }}_n^0$ је само унија ${\mathrm{\Sigma }}_n^{0,Y}$ за све скупове целих бројева Y. Имајте на уму да је подебљана хијерархија само стандардна хијерархија Борелове хијерархије.

Екстензије и варијације

Могуће је дефинисати аритметичку хијерархију формула коришћењем језика продуженог са симболом за сваку примитивну рекурзивну функцију. Ова варијација мало мења класификацију неких скупова.

Многе семантичке варијације хијерархије могу се дефинисати на свим финитарним односима природних бројева; следећа дефиниција се користи. Сваки израчунљив однос се дефинише као ${\mathrm{\Sigma }}_0^0$ и ${\mathrm{\Pi }}_0^0$. Класификације ${\mathrm{\Sigma }}_n^0$ и ${\mathrm{\Pi }}_n^0$ се индуктивно дефинишу са следећим правилима.

• Ако релација $R(n_1,\dots ,n_l,m_1,\dots ,m_k)$ је ${\mathrm{\Sigma }}_n^0$ онда је релација$S(n_1,\dots ,n_l)=\mathrm{\forall }{m}_1\cdots \mathrm{\forall }{m}_{k}R(n_1,\dots ,n_l,m_1,\dots ,m_k)$ дефинисана да буде ${\mathrm{\Pi }}_{n+1}^0$
• Ако релација $R(n_1,\dots ,n_l,m_1,\dots ,m_k)$ је ${\mathrm{\Pi }}_n^0$ онда је релација$S(n_1,\dots ,n_l)=\mathrm{\exists }{m}_1\cdots \mathrm{\exists }{m}_{k}R(n_1,\dots ,n_l,m_1,\dots ,m_k)$ дефинисана да буде ${\mathrm{\Sigma }}_{n+1}^0$

Ова варијација мало мења класификацију неких скупова. То се може проширити да покрије финитарне односе на природне бројеве, Беровог простора, и Канторовог простора.

Значење ознаке

Следећа значења, се могу прикључити нотацији за аритметички редослед формула.

Ознака $n$ у симболима ${\mathrm{\Sigma }}_n^0$ и ${\mathrm{\Pi }}_n^0$ указује на број промена блокова универзалног и егзистенцијалног броја квантификатора који се користе у формули. Штавише, спољни блок је егзистенцијалан у ${\mathrm{\Sigma }}_n^0$ формуле и универзални у ${\mathrm{\Pi }}_n^0$ формулама.

Ознака $0$ у симболима ${\mathrm{\Sigma }}_n^0$, ${\mathrm{\Pi }}_n^0$, и ${\mathrm{\Delta }}_n^0$ означава тип предмета који се квантификују готови. Тип 0 објекти су природни бројеви, и објекти типа $i+1$ су функције које мапирају скуп објеката типа $i$ на природне бројеве. Квантификација над већим објектима типа, као што је функција природних бројева до природних бројева, описана од стране суперскрипту већа од 0, као у аналитичкој хијерархији. Суперскрипт 0 указује на квантификаторе преко бројева, експонент 1 указује на квантификацију над функцијама од бројева до броја (тип 1 предмет), суперскрипт 2 би одговарао квантификацији преко функција које узимају тип 1 објекат и враћају број, и тако даље.

Примери

• ${\mathrm{\Sigma }}_1^0$ скупови бројева су они дефинисани по формули форме $\mathrm{\exists }{n}_1\cdots \mathrm{\exists }{n}_k\psi (n_1,\dots ,n_k,m)$ где $\psi$ има само ограничене квантификаторе. То су управо рекурзивно бројиви скупови.
• Скуп природних бројева који су индекси за Тјурингове машине које рачунају укупан број функција у ${\mathrm{\Pi }}_2^0$. Интуитивно, индекс $e$ спада у овом скупу ако и само ако за сваки $m$ "постоји неко $s$ тако да се Тјурингова машина са индексом $e$ зауставља на улазу $m$ после $s$ корака”. Комплетан доказ би показао да је имовина приказана у наводницима у претходној реченици и дефинише се на језику Пеано аритметике од стране ${\mathrm{\Sigma }}_1^0$ формула.
• Сваки ${\mathrm{\Sigma }}_1^0$ подскуп Беровог простора или Канторовог простора је отворен скуп у уобичајеној топологији простора. Осим тога, за сваки такав скуп постоји израчунљиво набрајање Геделових бројева основних отворених скупова чија је унија оригиналан скуп. Из тог разлога, ${\mathrm{\Sigma }}_1^0$ скупови се понекад називају ефикасно отвореним. Слично томе, сваки ${\mathrm{\Pi }}_1^0$ скуп је затворен и ${\mathrm{\Pi }}_1^0$ скупови се понекад називају затвореним.
• Сваки аритметичка подскуп Канторовог простора или Беровог простора је Борелов скуп. Борелова хијерархија проширује аритметичку хијерархију да укључи додатни Борелов скуп. На пример, сваки ${\mathrm{\Pi }}_2^0$ подскуп Канторовог или Беровог простора је $G_{\delta }$ скуп (то јест, што је једнако скупу пресека бројивих отворених скупова). Осим тога, сваки од ових отворених скупова је ${\mathrm{\Sigma }}_1^0$ и листа Геделових бројева отворених скупова има израчунљиву вредност. Ako $\varphi (X,n,m)$ је ${\mathrm{\Sigma }}_0^0$ формула са слободним скупом променљиве X и слободним бројем променљивих $n,m$ онда ${\mathrm{\Pi }}_2^0$ скуп $\{X\mid \mathrm{\forall }n\mathrm{\exists }m\varphi (X,n,m)\}$ је пресек ${\mathrm{\Sigma }}_1^0$ скупова форме $\{X\mid \mathrm{\exists }m\varphi (X,n,m)\}$ како n креће преко скупа природних бројева.  

Својства

Следеће особине стају за аритметичке хијерархије скупова природних бројева и аритметичке хијерархије подгрупа Канторовог или Беровог простора.

• Колекције ${\mathrm{\Pi }}_n^0$ и ${\mathrm{\Sigma }}_n^0$ су затворене под коначним унијама и коначним пресецима њихових елемената.
• Скуп је ${\mathrm{\Sigma }}_n^0$ ако и само ако је његова допуна ${\mathrm{\Pi }}_n^0$. Скуп је${\mathrm{\Delta }}_n^0$ ако и само ако је скуп и ${\mathrm{\Sigma }}_n^0$ и ${\mathrm{\Pi }}_n^0$, у ком случају ће његов комплемент такође бити ${\mathrm{\Delta }}_n^0$.
• Инклузије ${\mathrm{\Delta }}_n^0⊊{\mathrm{\Pi }}_n^0$ и ${\mathrm{\Delta }}_n^0⊊{\mathrm{\Sigma }}_n^0$ стају за $n\ge 1$.
• Инклузије ${\mathrm{\Pi }}_n^0⊊{\mathrm{\Pi }}_{n+1}^0$ и ${\mathrm{\Sigma }}_n^0⊊{\mathrm{\Sigma }}_{n+1}^0$ стају за свако $n$ и инклузију ${\mathrm{\Sigma }}_n^0\cup {\mathrm{\Pi }}_n^0⊊{\mathrm{\Delta }}_{n+1}^0$ стају за $n\ge 1$. Тако да хијерархија не пропадне.

Релација ка Тјуринговим машинама

Тјурингови израчунљиви скупови природних бројева су управо скупови на нивоу ${\mathrm{\Delta }}_1^0$ аритметичке хијерархије. У рекурсивно бројивим скуповима су управо скупови на нивоу ${\mathrm{\Sigma }}_1^0$.

Пророчка машина није у стању да реши свој проблем обуставе (варијација Тјуринга је доказ примене). Ограничени проблем за ${\mathrm{\Delta }}_n^{0,Y}$, у ствари, седи у ${\mathrm{\Sigma }}_{n+1}^{0,Y}$.

Постова теорема успоставља блиску везу између аритметичке хијерархије скупова природних бројева и Тјурингових степени. Конкретно, утврђује следеће чињенице за све n ≥ 1:

• Скуп ${\mathrm{\varnothing }}^{(n)}$ (енти Тјурингов скок празног скупа) се заврши у једном и сваком ${\mathrm{\Sigma }}_n^0$.
• Скуп $\mathbb{N}\setminus {\mathrm{\varnothing }}^{(n)}$ се заврши у једном и сваком  ${\mathrm{\Pi }}_n^0$.
• Скуп ${\mathrm{\varnothing }}^{(n-1)}$ се заврши Тјурингом у ${\mathrm{\Delta }}_n^0$.

Хијерархија полинома  је "изводљив ресурс ограничене" верзије аритметичке хијерархије у којој се дужина полинома граница ставља на бројеве који су укључени (или, еквивалентно, време полинома граница је постављено на Тјурингове машине које су укључене). То даје финију класификацију неких скупова природних бројева који су на нивоу ${\mathrm{\Delta }}_1^0$ аритметичке хијерархије.

Види још

• Интерпретеабилна логика
• Хијерархија (математика)
• Хијерархија полинома

Литература

• Шаблон:Cite journal
• Moschovakis, Yiannis N. (1980), Descriptive Set Theory, Studies in Logic and the Foundations of Mathematics 100, North Holland. Шаблон:Page, Zbl 0433.03025.
• Шаблон:Cite book
• Rogers, H., jr (1967), Theory of recursive functions and effective computability, Maidenhead: McGraw-Hill, Zbl 0183.01401.