Aritmetikai halmaz

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. május 26-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Az aritmetikai halmaz természetes számok halmaza , amely egy képlettel definiálható az elsőrendű aritmetika nyelvén , vagyis ha van olyan képlet egy szabad változóval , amely . Hasonlóképpen a természetes számok sorait aritmetikának nevezzük, ha létezik olyan képlet , amelyre . Beszélhetünk természetes számok sorainak számtani halmazairól, természetes számok véges sorozatairól, képletekről (bármelyik rögzített Gödel-számozáshoz ), és általában bármely természetes számok által kódolt objektum aritmetikai halmazáról. $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})$

Kapcsolódó definíciók

Egy függvényt aritmetikainak nevezünk, ha a grafikonja egy aritmetikai halmaz. Hasonlóképpen beszélhetünk a függvények aritmetikai természetéről, és általában bármely konstruktív objektum halmazán definiált függvényekről. $\N \ to \N$ $\N^n \to \N$

Az aritmetikai képlet egy képlet az elsőrendű aritmetika nyelvében.

Egy predikátumot (tulajdonságot) aritmetikának nevezünk, ha egy aritmetikai képlettel megadható. Az állítmány, a tulajdonság és a halmaz fogalmát gyakran azonosítják, ezért az ezekre vonatkozó aritmetikai fogalmakat is azonosítják.

Egy valós számot aritmetikainak nevezünk , ha a nála kisebb racionális okok halmaza aritmetikus (vagy ezzel egyenértékű, ha a nála nagyobb racionális számok halmaza aritmetikai). Egy komplex számot aritmetikainak nevezünk, ha valós és képzetes része is aritmetikus.

Tulajdonságok

Egy aritmetikai halmaz részhalmaza nem feltétlenül aritmetikai.
A természetes számok összes aritmetikai halmaza megszámlálható , a nem aritmetikai halmaz pedig megszámlálhatatlan .
A komplex számtani számok halmaza algebrailag zárt mezőt alkot .
Bármely kiszámítható szám aritmetikai.
Az aritmetikai számok halmaza (valamint komplementere) sűrűn és belül $\mathbb {R}$ $\mathbb {C} .$
A valós számtani számok halmazának sorrendje izomorf a racionális számok halmazának sorrendjével.

Példák

Az üres halmaz aritmetikai.
Bármely felsorolható halmaz (különösen minden eldönthető halmaz és minden véges halmaz ) aritmetikai.
Bármely számtani halmaz összeadása és vetítése aritmetikai.
Véges számú aritmetikai halmaz egyesülése és metszéspontja is aritmetikai.
Az a számhalmaz, amelyből a Collatz -sejtésben meghatározott sorozat eggyel végződik, aritmetikai, és ha ez a hipotézis igaz, akkor akár triviálisan is megoldható (a természetes számok teljes halmaza).
A Khaitin-féle Ω állandónál nagyobb racionális számok halmaza aritmetikai, de nem megszámlálható.
Azon Turing-gépek számkészlete , amelyek nem állnak meg egy üres bemenetnél, aritmetikai (bár nem felsorolható ).
De a Turing-gépek számkészlete , amely a természetes számok összehasonlításának műveletét valósítja meg, valamilyen módon teljesen rendezve a halmazt, nem aritmetikus. $\N$
A ZFC -ben nem bizonyítható állítások halmaza aritmetikai, de a ZFC konzisztenciájától függően nem felsorolható.
De az igaz állítások halmaza az elsőrendű aritmetikában nem aritmetikai (ami Tarski tételének az igazság aritmetikában való kimondhatatlanságáról szóló állítása), bár a bizonyítható állítások halmaza aritmetikus, sőt felsorolható.

Aritmetikai hierarchia

Tekintsünk egy elsőrendű aritmetikai nyelvet, amely predikátumszám-összehasonlító szimbólumot ( vagy ) tartalmaz. Egy ilyen nyelv esetében a korlátos kvantorok fogalma a következő: $<$ $\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

(vagy szigorú összehasonlítással rendelkező nyelvek esetén). Az ilyen kvantorok bevezethetők a jobb oldalon látható képletek rövidítéseként, vagy a nyelv kiterjesztéseként. itt lehet a forrásnyelv bármely olyan kifejezése, amely nem tartalmazza a szimbólum szabad előfordulását , és bármilyen képlet. A "közönséges" kvantorokat, amelyek a korlátozott és a korlátozott különbséget hangsúlyozzák, néha korlátlannak nevezik. $\forall (x<t)\varphi$ $\exists (x<t)\varphi$ $t$ $x$ $\varphi$

A képletet korlátozottnak vagy -formulának nevezzük , ha nem tartalmaz korlátlan kvantorokat; bármennyire is korlátozottan tartalmazhat. Két szinonim kifejezést is bevezetünk: -formula és -formula , amelyek ugyanazt jelentik, mint a -formula. $\Delta _{0}$ ${\displaystyle \Sigma _{0))$ ${\displaystyle \Pi _{0))$ $\Delta _{0}$

A képletek aritmetikai hierarchiája a -formulas és -formulas osztályok hierarchiája. Induktív módon határozzák meg: $\Sigma _{n}$ $\Pi _{n}$

a formájú képletet , ahol egy -képlet, -képletnek nevezzük ;

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

\varphi

\Pi _{n-1}

\Sigma _{n}

a formájú képletet , ahol egy -képlet, -képletnek nevezzük .

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

\varphi

\Sigma _{n-1}

\Pi _{n}

Így egy korlátozott képlet, amelyet váltakozó kvantorok csoportjai előznek meg, -formula, ha az egzisztenciális kvantorok kezdődnek, és -formula, ha az univerzális kvantorok kezdődnek. $n$ $\Sigma _{n}$ $\Sigma _{n}$

Természetesen nem minden számtani képletnek van ilyen formája. Azonban, amint az a predikátumok logikájából ismeretes, bármely formula redukálható prenex normál alakra. Ez lehetővé teszi, hogy bemutassuk a tág értelemben vett - és -képletek fogalmát: egy formulát - ( -) tág értelemben vett képletnek nevezünk, ha a predikátumok logikájában ekvivalens valamilyen - ( -) formulával a szűk értelemben (korlátozott kvantorok bővítése és hajtogatása is megengedett). Egy ilyen definíció azonban lehetővé teszi, hogy ugyanaz a képlet az aritmetikai hierarchia több osztályába tartozzon, attól függően, hogy a kvantorokat milyen sorrendben veszik ki, amikor prenex normál formulára redukálják. Ezért van értelme az aritmetikai hierarchia legegyszerűbb osztályának problémájának, amelyhez a képlet a legtágabb értelemben tartozik. $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$

Az aritmetikai hierarchia halmazoknál is figyelembe vehető. Azt mondjuk, hogy egy halmaz a ( ) osztályba tartozik, ha a - ( -) képletekkel megadható . Az és osztályok metszéspontja -halmaz osztálynak is nevezik . Könnyen belátható, hogy az aritmetikai hierarchia kimeríti az összes számtani halmazt. $A$ $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$ $\Delta _{n}$

Az aritmetikai hierarchia osztályai kapcsolatban állnak a kiszámíthatósági elmélettel. Egy osztály pontosan az összes felsorolható halmaz, egy osztály társ-számlálható, egy osztály pedig eldönthető. Az aritmetikai hierarchia többi osztálya az előzőek Turing-ugrása: egy osztály pontosan az összes -számlálható halmaz, egy osztály -egyszerszámozható, egy osztály pedig -feloldható . Így az aritmetikai halmazok pontosan mindazok a halmazok, amelyek meghatározható Turing-hatványokból nyerhetők. $\Sigma_1$ $\Pi_{1}$ $\Delta_1$ $\Sigma _{n}$ ${\displaystyle 0^{(n-1)))$ $\Pi _{n}$ ${\displaystyle 0^{(n-1)))$ $\Delta _{n}$ ${\displaystyle 0^{(n-1)))$

Lásd még

Aritmetikai hierarchia
Hiperaritmetikai hierarchia
Analitikai hierarchia
Projektív hierarchia
Borel hierarchia

Irodalom

N. K. Verescsagin, A. Shen. 2. rész. Nyelvek és kalkulus // Előadások a matematikai logikáról és az algoritmusok elméletéről. - 2. kiadás - M . : MTSNMO , 2002.