Mulțimea aritmetică

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 26 mai 2021; verificarea necesită 1 editare .

O mulțime aritmetică este o mulțime de numere naturale care pot fi definite printr-o formulă în limbajul aritmeticii de ordinul întâi , adică dacă există o astfel de formulă cu o variabilă liberă care . În mod similar, un set de tupluri de numere naturale se numește aritmetică dacă există o formulă astfel încât . Puteți vorbi, de asemenea, despre mulțimi aritmetice de tupluri de numere naturale, secvențe finite de numere naturale, formule (pentru oricare dintre numerotarea lor fixă Gödel ) și, în general, despre mulțimi aritmetice de orice obiecte codificate de numere naturale. $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})\în S\Leftrightarrow \varphi (x_{1},\ldots,x_{n})$

Definiții înrudite

O funcție se numește aritmetică dacă graficul ei este o mulțime aritmetică. În mod similar, se poate vorbi despre natura aritmetică a funcțiilor și, în general, a funcțiilor definite pe mulțimi de orice obiecte constructive. $\N \la \N$ $\N^n \la \N$

O formulă aritmetică este o formulă în limbajul aritmeticii de ordinul întâi.

Un predicat (proprietate) se numește aritmetică dacă poate fi specificat folosind o formulă aritmetică. Conceptele de predicat, proprietate și mulțime sunt adesea identificate, motiv pentru care sunt identificate și conceptele de aritmetică pentru ele.

Se spune că un număr real este aritmetic dacă mulțimea de raționale mai mică decât este aritmetică (sau, în mod echivalent, dacă mulțimea de raționale mai mare decât ea este aritmetică). Un număr complex se numește aritmetic dacă ambele părți reale și imaginare sunt aritmetice.

Proprietăți

O submulțime a unei mulțimi aritmetice nu este neapărat aritmetică.
Mulțimea tuturor mulțimilor aritmetice de numere naturale este o mulțime numărabilă , iar mulțimea tuturor mulțimilor nearitmetice este nenumărabilă .
Mulțimea numerelor aritmetice complexe formează un câmp închis algebric .
Orice număr calculat este aritmetic.
Mulțimea numerelor aritmetice (precum și complementul său) este dens în și în $\mathbb {R}$ $\mathbb {C} .$
Ordinea în mulțimea numerelor aritmetice reale este izomorfă cu ordinea în mulțimea numerelor raționale.

Exemple

Mulțimea goală este aritmetică.
Orice mulțime enumerabilă (în special, orice mulțime decidabilă și orice mulțime finită ) sunt aritmetice.
Adunarea și proiecția oricărei mulțimi aritmetice sunt aritmetice.
Unirea și intersecția unui număr finit de mulțimi aritmetice sunt de asemenea aritmetice.
Mulțimea numerelor pornind de la care șirul definit în conjectura Collatz se termină cu unu este aritmetică, iar dacă această ipoteză este adevărată, este chiar trivial rezolvabilă (întreaga mulțime de numere naturale).
Mulțimea numerelor raționale mai mare decât constanta lui Khaitin Ω este aritmetică, dar nenumerabilă.
Setul de numere de mașini Turing care nu se opresc la o intrare goală este aritmetic (deși nu este enumerabil ).
Dar setul de numere ale mașinilor Turing care implementează operația de comparare a numerelor naturale, ordonând complet mulțimea într-un fel, este non-aritmetică. $\N$
Setul de afirmații care nu sunt demonstrabile în ZFC este aritmetic, dar, în funcție de consistența ZFC, este nenumerabil.
Dar mulţimea enunţurilor adevărate din aritmetica de ordinul întâi nu este aritmetică (ceea ce constituie afirmaţia teoremei lui Tarski asupra inexprimabilităţii adevărului în aritmetică), deşi mulţimea enunţurilor demonstrabile este aritmetică şi chiar enumerabilă.

Ierarhie aritmetică

Luați în considerare un limbaj aritmetic de ordinul întâi care conține un simbol de comparare a numerelor predicate ( sau ). Pentru un astfel de limbaj, conceptul de cuantificatori mărginiți este definit: $<$ $\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

(sau , pentru limbi cu comparație strictă). Astfel de cuantificatori pot fi introduși ca prescurtare pentru formulele afișate în dreapta sau ca o extensie a limbajului. aici poate fi orice termen din limba sursă care nu conține o apariție liberă a simbolului și este orice formulă. Cuantificatorii „obișnuiți” pentru a sublinia diferența față de limitat sunt uneori numiți nelimitați. $\forall (x<t)\varphi$ $\exists (x<t)\varphi$ $t$ $X$ $\varphi$

Formula se numește limitată sau -formulă dacă nu conține cuantificatori nelimitați; oricât de limitată ar putea conţine. Se introduc și doi termeni sinonimi: -formula și -formula , care înseamnă același lucru cu -formulă. $\Delta _{0}$ $\Sigma _{0)$ $\Pi _{0)$ $\Delta _{0}$

Ierarhia aritmetică a formulelor este o ierarhie a claselor -formule și -formule. Ele sunt definite inductiv: $\Sigma _{n}$ $\Pi _{n}$

o formulă de forma , unde este o formulă, se numește o formulă;

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

\varphi

\Pi _{n-1}

\Sigma _{n}

o formulă de forma , unde este o formulă, se numește o formulă.

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

\varphi

\Sigma _{n-1}

\Pi _{n}

Astfel, o formulă restrânsă precedată de grupuri de cuantificatori alternanți este o formulă - dacă încep cuantificatorii existențiali și o formulă - dacă încep cuantificatorii universali. $n$ $\Sigma _{n}$ $\Sigma _{n}$

Desigur, nu orice formulă aritmetică are această formă. Cu toate acestea, după cum se știe din logica predicatelor, orice formulă poate fi redusă la o formă normală preex. Acest lucru ne permite să introducem conceptele de - și - formule în sens larg: o formulă se numește - ( -) o formulă în sens larg, dacă în logica predicatelor este echivalentă cu o formulă - ( -) în sensul larg. sens îngust (este permisă și extinderea și plierea cuantificatorilor limitati). O astfel de definiție permite totuși ca aceeași formulă să aparțină mai multor clase ale ierarhiei aritmetice, în funcție de ordinea în care sunt scoși cuantificatorii atunci când sunt reduse la o formulă normală preex. Prin urmare, problema celei mai simple clase a ierarhiei aritmetice, căreia îi aparține formula în sensul cel mai larg, are sens. $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$

Ierarhia aritmetică poate fi luată în considerare și pentru mulțimi. Vom spune că o mulțime aparține clasei ( ) dacă poate fi specificată folosind formule - ( -). Intersecția claselor și este numită și clasa -set. Este ușor de observat că ierarhia aritmetică epuizează toate mulțimile aritmetice. $A$ $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$ $\Sigma _{n}$ $\Pi _{n}$ $\Delta _{n}$

Clasele ierarhiei aritmetice au o legătură cu teoria computabilității. O clasă este exact toate seturile enumerabile, o clasă este co-enumerabilă și o clasă este decidabilă. Restul claselor din ierarhia aritmetică sunt salturi Turing ale celor anterioare: o clasă este exact toate -seturile enumerabile, o clasă este -coenumerabilă și o clasă este -rezolvabilă. Astfel, mulțimile aritmetice sunt exact toate mulțimile care pot fi obținute din puterile Turing decidabile. $\Sigma_1$ $\Pi_{1}$ $\Delta_1$ $\Sigma _{n}$ ${\displaystyle 0^{(n-1)))$ $\Pi _{n}$ ${\displaystyle 0^{(n-1)))$ $\Delta _{n}$ ${\displaystyle 0^{(n-1)))$

Vezi și

Ierarhie aritmetică
Ierarhie hiperaritmetică
Ierarhie analitică
Ierarhie proiectivă
Ierarhia Borel

Literatură

N. K. Vereshchagin, A. Shen. Partea 2. Limbaje și calcul // Prelegeri despre logica matematică și teoria algoritmilor. - Ed. a II-a - M .: MTSNMO , 2002.