Aritmetisk uppsättning

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 26 maj 2021; verifiering kräver 1 redigering .

En aritmetisk mängd är en uppsättning naturliga tal som kan definieras av en formel på språket för första ordningens aritmetik , det vill säga om det finns en sådan formel med en fri variabel som . På liknande sätt kallas en uppsättning tuplar av naturliga tal aritmetik om det finns en formel sådan att . Du kan också prata om aritmetiska uppsättningar av tuplar av naturliga tal, ändliga sekvenser av naturliga tal, formler (för vilken som helst av deras fasta Gödel-numrering ), och i allmänhet om aritmetiska uppsättningar av alla objekt som kodas av naturliga 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})$

Relaterade definitioner

En funktion kallas aritmetik om dess graf är en aritmetisk mängd. På liknande sätt kan man tala om den aritmetiska karaktären hos funktioner och i allmänhet funktioner definierade på uppsättningar av alla konstruktiva objekt. $\N \till \N$ $\N^n \till \N$

En aritmetisk formel är en formel på språket för första ordningens aritmetik.

Ett predikat (egenskap) kallas aritmetik om det kan specificeras med en aritmetisk formel. Begreppen predikat, egenskap och mängd identifieras ofta, varför även aritmetikbegreppen för dem identifieras.

Ett reellt tal sägs vara aritmetiskt om mängden rationaler är mindre än den är aritmetiska (eller på motsvarande sätt om mängden rationaler som är större än den är aritmetiska). Ett komplext tal kallas aritmetiskt om både dess reella och imaginära delar är aritmetiska.

Egenskaper

En delmängd av en aritmetisk uppsättning är inte nödvändigtvis aritmetisk.
Uppsättningen av alla aritmetiska uppsättningar av naturliga tal är en räknebar uppsättning , och uppsättningen av alla icke-aritmetiska uppsättningar är oräkneliga .
Uppsättningen av komplexa aritmetiska tal bildar ett algebraiskt slutet fält .
Alla beräkningsbara tal är aritmetiska.
Uppsättningen av aritmetiska tal (liksom dess komplement) är tät in och in $\mathbb {R}$ $\mathbb {C} .$
Ordningen på mängden reella aritmetiska tal är isomorf med ordningen på mängden rationella tal.

Exempel

Den tomma mängden är aritmetisk.
Varje uppräknad mängd (i synnerhet vilken som helst avgörbar mängd och vilken finit mängd som helst ) är aritmetiska.
Adderingen och projektionen av alla aritmetiska mängder är aritmetiska.
Unionen och skärningspunkten mellan ett ändligt antal aritmetiska mängder är också aritmetiska.
Den uppsättning tal som börjar från vilken sekvensen som definieras i Collatz-förmodan slutar med ett är aritmetisk, och om denna hypotes är sann är den till och med trivialt lösbar (hela uppsättningen naturliga tal).
Mängden rationella tal som är större än Khaitins konstant Ω är aritmetiska men kan inte räknas upp.
Uppsättningen av antalet Turing-maskiner som inte stannar vid en tom ingång är aritmetisk (även om den inte kan räknas upp ).
Men uppsättningen av siffror för Turing-maskiner som implementerar operationen att jämföra naturliga tal, helt ordnar uppsättningen på något sätt, är icke-aritmetisk. $\N$
Uppsättningen av påståenden som inte är bevisbara i ZFC är aritmetiska, men, med förbehåll för ZFC:s konsistens , kan den inte räknas upp.
Men mängden sanna påståenden i första ordningens aritmetik är inte aritmetik (vilket utgör påståendet i Tarskis teorem om sanningens outsäglighet i aritmetiken), även om mängden bevisbara påståenden är aritmetiska och till och med uppräknbara.

Aritmetisk hierarki

Tänk på ett första ordningens aritmetiskt språk som innehåller en predikatnummerjämförelsesymbol ( eller ). För ett sådant språk definieras begreppet avgränsade kvantifierare: $<$ $\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 , för språk med strikt jämförelse). Sådana kvantifierare kan introduceras som stenografi för formlerna som visas till höger, eller som en förlängning av språket. här kan vara vilken term som helst i källspråket som inte innehåller en fri förekomst av symbolen och är vilken formel som helst. "Vanliga" kvantifierare för att betona skillnaden från begränsad kallas ibland obegränsade. $\forall (x<t)\varphi$ $\exists (x<t)\varphi$ $t$ $x$ $\varphi$

Formeln kallas begränsad eller -formel om den inte innehåller obegränsade kvantifierare; hur begränsad den än kan innehålla. Två synonyma termer introduceras också: -formel och -formel , som betyder samma sak som -formel. $\Delta _{0}$ ${\displaystyle \Sigma _{0))$ $\Pi _{0}$ $\Delta _{0}$

Den aritmetiska hierarkin av formler är en hierarki av klasser -formler och -formler. De definieras induktivt: $\Sigma _{n}$ $\Pi _{n}$

en formel av formen , där är en -formel, kallas en -formel;

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

\varphi

\Pi _{n-1}

\Sigma _{n}

en formel av formen , där är en -formel, kallas en -formel.

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

\varphi

\Sigma _{n-1}

\Pi _{n}

Således är en begränsad formel som föregås av grupper av alternerande kvantifierare en -formel om de existentiella kvantifierarna startar, och en -formel om de universella kvantifierarna startar. $n$ $\Sigma _{n}$ $\Sigma _{n}$

Naturligtvis har inte varje aritmetisk formel denna form. Men som är känt från predikats logik kan vilken formel som helst reduceras till en prenex normal form. Detta tillåter oss att introducera begreppen - och -formler i vid mening: en formel kallas - ( -) en formel i vid mening, om den i predikats logik är ekvivalent med någon - ( -) formel i smal bemärkelse (expandering och vikning av begränsade kvantifierare är också tillåtna). En sådan definition tillåter emellertid att samma formel tillhör flera klasser i den aritmetiska hierarkin, beroende på i vilken ordning kvantifierare tas ut när de reduceras till en prenex-normalformel. Därför är problemet med den enklaste klassen i den aritmetiska hierarkin, till vilken formeln hör i vid mening, meningsfullt. $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$

Den aritmetiska hierarkin kan också beaktas för mängder. Vi kommer att säga att en mängd tillhör klassen ( ) om den kan specificeras med - ( -) formler. Skärningspunkten mellan klasserna och kallas även -set-klassen. Det är lätt att se att den aritmetiska hierarkin tömmer ut alla aritmetiska uppsättningar. $A$ $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$ $\Delta _{n}$

Den aritmetiska hierarkins klasser har ett samband med beräkningsbarhetsteori. En klass är exakt alla uppräknbara uppsättningar, en klass är medräknad och en klass kan avgöras. Resten av klasserna i den aritmetiska hierarkin är Turing-hopp av de tidigare: en klass är exakt alla -uppräknade uppsättningar, en klass är -samuppräknade och en klass är -upplösbar. Således är aritmetiska mängder exakt alla mängder som kan erhållas från avgörbara Turing-krafter. $\Sigma_1$ $\Pi_{1}$ $\Delta_1$ $\Sigma _{n}$ ${\displaystyle 0^{(n-1)))$ $\Pi _{n}$ ${\displaystyle 0^{(n-1)))$ $\Delta _{n}$ ${\displaystyle 0^{(n-1)))$

Se även

Aritmetisk hierarki
Hyperaritmetisk hierarki
Analytisk hierarki
Projektiv hierarki
Borel hierarki

Litteratur

N.K. Vereshchagin, A. Shen. Del 2. Språk och analys // Föreläsningar om matematisk logik och teori om algoritmer. - 2:a upplagan - M . : MTSNMO , 2002.