Aritmeettinen joukko

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 26.5.2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Aritmeettinen joukko on luonnollisten lukujen joukko , joka voidaan määrittää kaavalla ensimmäisen kertaluvun aritmeettisen kielellä , eli jos on olemassa sellainen kaava , jossa on yksi vapaa muuttuja , että . Vastaavasti luonnollisten lukujen joukkoa kutsutaan aritmeettiseksi, jos on olemassa sellainen kaava , että . Voit myös puhua luonnollisten lukujen monikoiden aritmeettisista sarjoista, luonnollisten lukujen äärellisistä sarjoista, kaavoista (joille tahansa niiden kiinteälle Gödel-numerointille ) ja yleensä kaikkien luonnollisten lukujen koodaamien objektien aritmeettisista joukoista. $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})$

Aiheeseen liittyvät määritelmät

Funktiota kutsutaan aritmeettiseksi , jos sen kuvaaja on aritmeettinen joukko. Vastaavasti voidaan puhua funktioiden aritmeettisesta luonteesta ja yleisesti ottaen minkä tahansa konstruktiivisen objektin joukoille määriteltyjen funktioiden aritmeettisuudesta. $\N \to \N$ $\N^n \to \N$

Aritmeettinen kaava on ensimmäisen asteen aritmeettisen kielen kaava.

Predikaattia (ominaisuutta) kutsutaan aritmeettiseksi , jos se voidaan määrittää aritmeettisella kaavalla. Predikaatin, ominaisuuden ja joukon käsitteet tunnistetaan usein, minkä vuoksi myös niiden aritmeettiset käsitteet tunnistetaan.

Reaaliluvun sanotaan olevan aritmeettinen , jos sitä pienempi rationaalien joukko on aritmeettinen (tai vastaavasti, jos sitä suurempi rationaalien joukko on aritmeettinen). Kompleksilukua kutsutaan aritmeettiseksi, jos sen reaali- ja imaginaariosa ovat aritmeettisia.

Ominaisuudet

Aritmeettisen joukon osajoukko ei välttämättä ole aritmeettinen.
Kaikkien luonnollisten lukujen aritmeettisten joukkojen joukko on laskettava joukko ja kaikkien ei-aritmeettisten joukkojen joukko on laskematon .
Kompleksisten aritmeettisten lukujen joukko muodostaa algebrallisesti suljetun kentän .
Mikä tahansa laskettavissa oleva luku on aritmeettinen.
Aritmeettisten lukujen joukko (sekä sen komplementti) on tiheä sisään ja sisään $\mathbb {R}$ $\mathbb {C} .$
Aritmeettisten todellisten lukujen järjestys on isomorfinen rationaalisten lukujen joukon järjestyksen kanssa.

Esimerkkejä

Tyhjä joukko on aritmeettinen.
Mikä tahansa numeroitava joukko (erityisesti mikä tahansa ratkeava joukko ja mikä tahansa äärellinen joukko ) ovat aritmeettisia.
Minkä tahansa aritmeettisen joukon yhteenlasku ja projektio ovat aritmeettisia.
Äärillisen määrän aritmeettisten joukkojen liitto ja leikkauspiste ovat myös aritmeettisia.
Lukujoukko, josta alkaen Collatzin arvelussa määritetty sekvenssi päättyy yhteen, on aritmeettinen, ja jos tämä hypoteesi pitää paikkansa, se on jopa triviaalisti ratkaistavissa (koko luonnollisten lukujen joukko).
Khaitinin vakiota Ω suurempi rationaalilukujen joukko on aritmeettinen, mutta ei-numeroitavissa.
Joukko Turingin koneita , jotka eivät pysähdy tyhjään syötteeseen, on aritmeettinen (vaikka ei numeroitava ) .
Mutta Turingin koneiden lukujoukko , joka toteuttaa luonnollisten lukujen vertailun ja järjestää joukon jollakin tavalla täysin, on ei-aritmeettinen. $\N$
Lauseet, jotka eivät ole todistettavissa ZFC :ssä , ovat aritmeettisia, mutta ZFC:n johdonmukaisuudesta riippuen niitä ei voi lukea.
Mutta ensimmäisen asteen aritmetiikassa tosilauseiden joukko ei ole aritmeettinen (joka muodostaa Tarskin lauseen väitteen totuuden sanoittamattomuudesta aritmetiikassa), vaikka todennettavissa olevien väitteiden joukko on aritmeettinen ja jopa luettavissa.

Aritmeettinen hierarkia

Tarkastellaan ensimmäisen asteen aritmeettista kieltä, joka sisältää predikaattilukuvertailusymbolin ( tai ). Tällaiselle kielelle rajattujen kvantorien käsite määritellään: $<$ $\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

(tai tiukasti vertailukelpoisille kielille). Tällaisia kvantisoijia voidaan ottaa käyttöön lyhenteenä oikealla esitettyihin kaavoihin tai kielen jatkeeksi. tässä voi olla mikä tahansa lähdekielen termi, joka ei sisällä symbolin vapaata esiintymistä ja on mikä tahansa kaava. "Tavallisia" kvantoreita, jotka korostavat eroa rajoitetuista, kutsutaan joskus rajoittamattomiksi. $\forall (x<t)\varphi$ $\exists (x<t)\varphi$ $t$ $x$ $\varphi$

Kaavaa kutsutaan rajoitetuksi tai -kaavaksi , jos se ei sisällä rajoittamatonta määrää kvantisoijia; kuinka rajoitetusti se voi sisältää. Lisäksi otetaan käyttöön kaksi synonyymiä termiä: -formula ja -formula , jotka tarkoittavat samaa kuin -kaava. $\Delta _{0}$ ${\displaystyle \Sigma _{0))$ ${\displaystyle \Pi _{0))$ $\Delta _{0}$

Kaavojen aritmeettinen hierarkia on luokkien -kaavat ja -kaavat hierarkia. Ne määritellään induktiivisesti: $\Sigma _{n}$ $\Pi _{n}$

kaavaa muodolla , jossa on -kaava, kutsutaan -kaavaksi;

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

\varphi

\Pi _{n-1}

\Sigma _{n}

muodon kaavaa , jossa on -kaava, kutsutaan -kaavaksi.

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

\varphi

\Sigma _{n-1}

\Pi _{n}

Siten rajoitettu kaava, jota edeltävät vuorottelevien kvantorien ryhmät, on -kaava, jos eksistentiaaliset kvantoijat alkavat, ja -kaava, jos yleiset kvantoijat alkavat. $n$ $\Sigma _{n}$ $\Sigma _{n}$

Tietenkään kaikilla aritmeettisilla kaavoilla ei ole tätä muotoa. Kuitenkin, kuten predikaattilogiikasta tiedetään, mikä tahansa kaava voidaan pelkistää prenex-normaalimuotoon. Tämä antaa meille mahdollisuuden esitellä käsitteet - ja -kaavat laajassa merkityksessä: kaavaa kutsutaan - ( -) kaavaksi laajassa merkityksessä, jos se predikaattilogiikassa vastaa jotakin - ( -) kaavaa suppeassa merkityksessä (rajoitettujen kvantorien laajentaminen ja taittaminen on myös sallittua). Tällainen määritelmä kuitenkin sallii saman kaavan kuulua useisiin aritmeettisen hierarkian luokkiin riippuen siitä, missä järjestyksessä kvantisoijat poistetaan, kun ne pelkistetään prenex-normaalikaavalle. Siksi aritmeettisen hierarkian yksinkertaisimman luokan ongelma, johon kaava kuuluu laajimmassa merkityksessä, on järkevä. $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$

Aritmeettinen hierarkia voidaan ottaa huomioon myös joukoille. Sanomme, että joukko kuuluu luokkaan ( ), jos se voidaan määrittää käyttämällä - ( -) kaavoja. Luokkien leikkauspiste ja kutsutaan myös -set-luokiksi. On helppo nähdä, että aritmeettinen hierarkia tyhjentää kaikki aritmeettiset joukot. $A$ $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$ $\Delta _{n}$

Aritmeettisen hierarkian luokilla on yhteys laskettavuusteoriaan. Luokka on täsmälleen kaikki numeroitavat joukot, luokka on rinnakkaisnumeroitavissa ja luokka on pääteltävissä. Loput aritmeettisen hierarkian luokat ovat aiempien Turing-hyppyjä: luokka on täsmälleen kaikki -numeroitavissa olevat joukot, luokka -koenumeroitava ja luokka -selvittävä. Aritmeettiset joukot ovat siis täsmälleen kaikkia joukkoja, jotka voidaan saada päätettävistä Turingin potenssien perusteella. $\Sigma_1$ $\Pi_{1}$ $\Delta_1$ $\Sigma _{n}$ ${\displaystyle 0^{(n-1)))$ $\Pi _{n}$ ${\displaystyle 0^{(n-1)))$ $\Delta _{n}$ ${\displaystyle 0^{(n-1)))$

Katso myös

Aritmeettinen hierarkia
Hyperaritmeettinen hierarkia
Analyyttinen hierarkia
Projektiivinen hierarkia
Borel hierarkia

Kirjallisuus

N. K. Vereshchagin, A. Shen. Osa 2. Kielet ja laskelma // Matemaattisen logiikan ja algoritmien teorian luentoja. - 2. painos - M .: MTSNMO , 2002.