Aritmetisk sæt

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 26. maj 2021; verifikation kræver 1 redigering .

Et aritmetisk sæt er et sæt naturlige tal , der kan defineres af en formel på sproget for førsteordens aritmetik , det vil sige, hvis der er sådan en formel med én fri variabel , der . Tilsvarende kaldes et sæt tupler af naturlige tal aritmetik, hvis der findes en formel sådan, at . Du kan også tale om aritmetiske sæt af tupler af naturlige tal, endelige sekvenser af naturlige tal, formler (for enhver af deres faste Gödel-nummerering ) og generelt om aritmetiske mængder af alle objekter kodet af naturlige tal. $S\subseteq \mathbb {N}$ $\varphi(x)$ $x$ $x\in S\Leftrightarrow \varphi (x)$ $S\subseteq \mathbb {N} ^{n}$ $\varphi (x_{1},\ldots ,x_{n})$ $(x_{1},\ldots ,x_{n})\in S\Leftrightarrow \varphi (x_{1},\ldots,x_{n})$

Relaterede definitioner

En funktion kaldes aritmetisk , hvis dens graf er et aritmetisk sæt. På samme måde kan man tale om den aritmetiske karakter af funktioner og generelt funktioner defineret på sæt af konstruktive objekter. $\N \til \N$ $\N^n \til \N$

En aritmetisk formel er en formel på sproget i førsteordens aritmetik.

Et prædikat (egenskab) kaldes aritmetik , hvis det kan specificeres ved hjælp af en aritmetisk formel. Begreberne prædikat, egenskab og mængde identificeres ofte, hvorfor regnebegreberne for dem også identificeres.

Et reelt tal siges at være aritmetisk , hvis mængden af rationaler er mindre end det er aritmetiske (eller tilsvarende hvis mængden af rationaler større end det er aritmetiske). Et komplekst tal kaldes aritmetisk, hvis både dets reelle og imaginære dele er aritmetiske.

Egenskaber

En delmængde af et aritmetisk sæt er ikke nødvendigvis aritmetisk.
Mættet af alle aritmetiske sæt af naturlige tal er et tælleligt sæt , og sættet af alle ikke-aritmetiske mængder er utælleligt .
Sættet af komplekse aritmetiske tal danner et algebraisk lukket felt .
Ethvert beregneligt tal er aritmetiske.
Sættet af aritmetiske tal (såvel som dets komplement) er tæt ind og ind $\mathbb {R}$ $\mathbb {C} .$
Rækkefølgen på mængden af reelle aritmetiske tal er isomorf med rækkefølgen på mængden af rationelle tal.

Eksempler

Det tomme sæt er aritmetisk.
Enhver optallig mængde (især enhver afgørbar mængde og enhver finit mængde ) er aritmetiske.
Tilføjelsen og projektionen af ethvert aritmetisk sæt er aritmetiske.
Foreningen og skæringen af et endeligt antal aritmetiske mængder er også aritmetiske.
Det sæt af tal, der starter, hvorfra sekvensen defineret i Collatz-formodningen slutter med et, er aritmetisk, og hvis denne hypotese er sand, er den endda trivielt løselig (hele sættet af naturlige tal).
Sættet af rationelle tal, der er større end Khaitins konstant Ω , er aritmetisk, men kan ikke tælles.
Sættet af numre af Turing-maskiner , der ikke stopper ved et tomt input, er aritmetisk (selv om det ikke kan tælles ).
Men det sæt af tal på Turing-maskiner , der implementerer operationen med at sammenligne naturlige tal, og som fuldstændig bestiller sættet på en eller anden måde, er ikke-aritmetisk. $\N$
Sættet af udsagn, der ikke kan bevises i ZFC , er aritmetiske, men, afhængigt af ZFC's konsistens , kan de ikke tælles.
Men mængden af sande udsagn i førsteordens aritmetik er ikke aritmetik (hvilket udgør påstanden i Tarskis sætning om uudsigelig sandhed i aritmetik), selvom sættet af bevisbare udsagn er aritmetiske og endda talløse.

Aritmetisk hierarki

Overvej et førsteordens aritmetisk sprog, der indeholder et prædikattalssammenligningssymbol ( eller ). For et sådant sprog er begrebet afgrænsede kvantifikatorer defineret: $<$ $\leq$

\forall (x\leq t)\varphi \ {\overset {\mathrm {def} }{\leftrightarrow }}\ \forall x\ x\leq t\rightarrow \varphi

\exists (x\leq t)\varphi \ {\overset {\mathrm {def} }{\leftrightarrow }}\ \exists x\ x\leq t\wedge \varphi

(eller , for sprog med streng sammenligning). Sådanne kvantificerere kan introduceres som stenografi for formlerne vist til højre eller som en forlængelse af sproget. her kan være et hvilket som helst udtryk i kildesproget, der ikke indeholder en fri forekomst af symbolet og er en hvilken som helst formel. "Almindelige" kvantificerere for at understrege forskellen fra begrænset kaldes nogle gange ubegrænset. $\forall (x<t)\varphi$ $\exists (x<t)\varphi$ $t$ $x$ $\varphi$

Formlen kaldes begrænset eller -formel , hvis den ikke indeholder ubegrænsede kvantifiers; hvor begrænset den end kan indeholde. To synonyme udtryk introduceres også: -formel og -formel , som betyder det samme som -formel. $\Delta _{0}$ ${\displaystyle \Sigma _{0))$ $\Pi _{0}$ $\Delta _{0}$

Det aritmetiske hierarki af formler er et hierarki af klasser -formler og -formler. De er defineret induktivt: $\Sigma _{n}$ $\Pin}$

en formel for formen , hvor er en -formel, kaldes en -formel;

\exists x_{1}\ldots \exists x_{k}\ \varphi

\varphi

\Pi _{n-1}

\Sigma _{n}

en formel på formen , hvor er en -formel, kaldes en -formel.

\forall x_{1}\ldots \forall x_{k}\ \varphi

\varphi

\Sigma _{n-1}

\Pi _{n}

Således er en begrænset formel med grupper af alternerende kvantifikatorer foran en -formel, hvis de eksistentielle kvantifikatorer starter, og en -formel, hvis de universelle kvantifikatorer starter. $n$ $\Sigma _{n}$ $\Sigma _{n}$

Selvfølgelig har ikke alle aritmetiske formler denne form. Men som det er kendt fra prædikaternes logik, kan enhver formel reduceres til en prænex normal form. Dette giver os mulighed for at introducere begreberne - og -formler i bred forstand: en formel kaldes - ( -) en formel i bred forstand, hvis den i prædikaternes logik svarer til en - ( -) formel i snæver forstand (udvidelse og foldning af begrænsede kvantificerere er også tilladt). En sådan definition tillader imidlertid, at den samme formel hører til flere klasser i det aritmetiske hierarki, afhængigt af den rækkefølge, hvori kvantifikatorer tages ud, når de reduceres til en prænex normal formel. Derfor giver problemet med den simpleste klasse i det aritmetiske hierarki, som formlen hører til i bredeste forstand, mening. $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$

Det aritmetiske hierarki kan også overvejes for mængder. Vi vil sige, at et sæt hører til klassen ( ), hvis det kan specificeres ved hjælp af - ( -) formler. Skæringspunktet mellem klasserne og kaldes også -sæt-klassen. Det er let at se, at det aritmetiske hierarki udtømmer alle aritmetiske mængder. $EN$ $\Sigma _{n}$ $\Pin}$ $\Sigma _{n}$ $\Pin}$ $\Sigma _{n}$ $\Pin}$ $\Delta _{n}$

Det aritmetiske hierarkis klasser har en forbindelse med beregningsbarhedsteori. En klasse er præcis alle tællelige sæt, en klasse kan tælles sammen, og en klasse kan bestemmes. Resten af klasserne i det aritmetiske hierarki er Turing-hop af de foregående: en klasse er nøjagtig alle -optalbare sæt, en klasse er -samoptællig, og en klasse er -opløselig. Således er aritmetiske mængder præcis alle de mængder, der kan opnås fra afgørelige Turing-kræfter. $\Sigma_1$ $\Pi_{1}$ $\Delta_1$ $\Sigma _{n}$ ${\displaystyle 0^{(n-1)))$ $\Pin}$ ${\displaystyle 0^{(n-1)))$ $\Delta _{n}$ ${\displaystyle 0^{(n-1)))$

Se også

Aritmetisk hierarki
Hyperaritmetisk hierarki
Analytisk hierarki
Projektivt hierarki
Borel hierarki

Litteratur

N.K. Vereshchagin, A. Shen. Del 2. Sprog og regning // Forelæsninger om matematisk logik og teori om algoritmer. - 2. udgave - M . : MTSNMO , 2002.