Aritmetická sada

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 26. května 2021; ověření vyžaduje 1 úpravu .

Aritmetická množina je množina přirozených čísel , která lze definovat vzorcem v jazyce aritmetiky prvního řádu , tedy pokud existuje takový vzorec s jednou volnou proměnnou , která . Podobně se množina n-tic přirozených čísel nazývá aritmetika, pokud existuje vzorec takový, že . Můžete také mluvit o aritmetických množinách n-tic přirozených čísel, konečných posloupnostech přirozených čísel, vzorcích (pro jakékoli jejich pevné Gödelovo číslování ) a obecně o aritmetických množinách libovolných objektů kódovaných přirozenými čísly. $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})$

Související definice

Funkce se nazývá aritmetika , pokud je jejím grafem aritmetická množina. Podobně lze hovořit o aritmetické povaze funkcí a obecně funkcí definovaných na množinách jakýchkoliv konstruktivních objektů. $\N \do \N$ $\N^n \to \N$

Aritmetický vzorec je vzorec v jazyce aritmetiky prvního řádu.

Predikát (vlastnost) se nazývá aritmetika , pokud jej lze specifikovat pomocí aritmetického vzorce. Pojmy predikát, vlastnost a množina jsou často identifikovány, a proto jsou pro ně také identifikovány pojmy aritmetiky.

Reálné číslo je považováno za aritmetické , pokud je aritmetický soubor menších než je aritmetický (nebo ekvivalentně, je-li aritmetický soubor). Komplexní číslo se nazývá aritmetika, pokud je aritmetická jeho skutečná i imaginární část.

Vlastnosti

Podmnožina aritmetické množiny nemusí být nutně aritmetická.
Množina všech aritmetických množin přirozených čísel je spočetná množina a množina všech nearitmetických množin je nespočetná .
Množina komplexních aritmetických čísel tvoří algebraicky uzavřené pole .
Jakékoli vyčíslitelné číslo je aritmetické.
Množina aritmetických čísel (stejně jako její doplněk) je hustá dovnitř a dovnitř $\mathbb {R}$ $\mathbb {C} .$
Pořadí na množině reálných aritmetických čísel je izomorfní s pořadím na množině racionálních čísel.

Příklady

Prázdná množina je aritmetická.
Jakákoli spočetná množina (zejména jakákoli rozhoditelná množina a jakákoli konečná množina ) jsou aritmetické.
Sčítání a projekce jakékoli aritmetické množiny jsou aritmetické.
Sjednocení a průnik konečného počtu aritmetických množin je také aritmetické.
Množina čísel, od kterých posloupnost definovaná v Collatzově domněnce končí jedničkou, je aritmetická, a pokud je tato hypotéza pravdivá, je dokonce triviálně řešitelná (celá množina přirozených čísel).
Množina racionálních čísel větších než Khaitinova konstanta Ω je aritmetická, ale nevyčíslitelná.
Množina čísel Turingových strojů , které se nezastaví na prázdném vstupu, je aritmetická (ačkoli nevyčíslitelná ).
Ale množina čísel Turingových strojů , které implementují operaci porovnávání přirozených čísel, nějakým způsobem zcela uspořádávají množinu, je nearitmetická. $\N$
Sada prohlášení, která nejsou prokazatelná v ZFC , je aritmetická, ale s výhradou konzistence ZFC je nevyčíslitelná.
Ale soubor pravdivých výroků v aritmetice prvního řádu není aritmetický (což představuje tvrzení Tarského věty o nevyjádřitelnosti pravdy v aritmetice), ačkoli soubor dokazatelných výroků je aritmetický a dokonce i spočetný.

Aritmetická hierarchie

Zvažte aritmetický jazyk prvního řádu obsahující symbol porovnání predikátových čísel ( nebo ). Pro takový jazyk je definován koncept ohraničených kvantifikátorů: $<$ $\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

(nebo , pro jazyky s přísným srovnáním). Takové kvantifikátory lze zavést jako zkratku pro vzorce zobrazené vpravo nebo jako rozšíření jazyka. zde může být jakýkoli termín zdrojového jazyka, který neobsahuje volný výskyt symbolu , a je to jakýkoli vzorec. "Obyčejné" kvantifikátory pro zdůraznění rozdílu od omezených se někdy nazývají neomezené. $\forall (x<t)\varphi$ $\exists (x<t)\varphi$ $t$ $X$ $\varphi$

Vzorec se nazývá omezený nebo -vzorec , pokud neobsahuje neomezené kvantifikátory; jakkoli omezeně může obsahovat. Jsou také zavedeny dva synonymní pojmy: -vzorec a -vzorec , které znamenají totéž jako -vzorec. $\Delta _{0}$ ${\displaystyle \Sigma _{0))$ ${\displaystyle \Pi _{0))$ $\Delta _{0}$

Aritmetická hierarchie vzorců je hierarchií tříd – vzorců a – vzorců . Jsou definovány induktivně: $\Sigma _{n}$ $\Pi _{n}$

vzorec ve tvaru , kde je -vzorec, se nazývá -vzorec;

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

\varphi

\Pi _{n-1}

\Sigma _{n}

vzorec ve tvaru , kde je -vzorec, se nazývá -vzorec.

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

\varphi

\Sigma _{n-1}

\Pi _{n}

Omezená formule, které předcházejí skupiny alternujících kvantifikátorů, je tedy -formulí, pokud začínají existenční kvantifikátory, a -formulí, pokud začínají univerzální kvantifikátory. $n$ $\Sigma _{n}$ $\Sigma _{n}$

Samozřejmě ne každý aritmetický vzorec má tento tvar. Jak je však známo z logiky predikátů, jakýkoli vzorec lze redukovat na prenexovou normální formu. To nám umožňuje zavést pojmy - a -formule v širokém slova smyslu: formule se nazývá - ( -) formule v širokém smyslu, pokud je v logice predikátů ekvivalentní nějaké - ( -) formuli v úzký smysl (je povoleno také rozšiřování a skládání omezených kvantifikátorů). Taková definice však umožňuje, aby stejný vzorec patřil do několika tříd aritmetické hierarchie v závislosti na pořadí, ve kterém jsou kvantifikátory vyjímány, když jsou redukovány na prenexový normální vzorec. Proto problém nejjednodušší třídy aritmetické hierarchie, do které vzorec v nejširším slova smyslu patří, dává smysl. $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$

Aritmetická hierarchie může být také uvažována pro množiny. Řekneme, že množina patří do třídy ( ), pokud ji lze specifikovat pomocí vzorců - ( -). Průnik tříd a nazývá se také třída -set. Je snadné vidět, že aritmetická hierarchie vyčerpává všechny aritmetické množiny. $A$ $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$ $\Delta _{n}$

Třídy aritmetické hierarchie mají souvislost s teorií vyčíslitelnosti. Třída jsou přesně všechny vyčíslitelné množiny, třída je ko-spočetná a třída je rozhodnoutelná. Zbytek tříd v aritmetické hierarchii jsou Turingovy skoky předchozích: třída je přesně všechny -spočetné množiny, třída je -spočítatelná a třída je -rozložitelná. Aritmetické množiny jsou tedy přesně všechny množiny, které lze získat z rozhoditelných Turingových mocnin. $\Sigma_1$ $\Pi_{1}$ $\Delta_1$ $\Sigma _{n}$ ${\displaystyle 0^{(n-1)))$ $\Pi _{n}$ ${\displaystyle 0^{(n-1)))$ $\Delta _{n}$ ${\displaystyle 0^{(n-1)))$

Viz také

aritmetická hierarchie
Hyperaritmetická hierarchie
Analytická hierarchie
Projektivní hierarchie
borelská hierarchie

Literatura

N. K. Vereščagin, A. Šen. Část 2. Jazyky a počet // Přednášky o matematické logice a teorii algoritmů. - 2. vyd. - M .: MTSNMO , 2002.