Mulțime aritmetică

În logica matematică o mulțime aritmetică este o mulțime de numere naturale care pot fi definite printr-o formulă bine formată de ordinul întâi în aritmetica Peano. Mulțimile aritmetice sunt clasificate de ierarhia aritmetică.

Definiția poate fi extinsă la o mulțime numărabilă arbitrară A, (de exemplu mulțimile n-uple de numere întregi, mulțimea numerelor raționale, mulțimea formulelor din unele limbaje formale etc.) folosind numere Gödel pentru a reprezenta elemente ale mulțimii și declarând un subset din A ca fiind aritmetic dacă setul numerelor Gödel corespunzătoare este aritmetic.

O funcție $f:\subseteq \mathbb {N} ^{k}\to \mathbb {N}$ se numește definibilă aritmetic dacă graficul lui f este o mulțime aritmetică.

Un număr real se numește aritmetic dacă toată mulțimea numerelor raționale mai mici ca el este aritmetică. Un număr complex se numește aritmetic dacă părțile sare reale și imaginare sunt ambele aritmetice.

Definiție formală

O mulțime de numere naturale, X, este aritmetică sau definibilă aritmetic dacă există o formulă φ(n) în limbajul aritmeticii Peano astfel încât n să fie în X dacă și numai dacă φ(n) respectă modelul aritmetic standard. Similar, o relație de ordinul k $R(n_{1},\ldots ,n_{k})$ este aritmetică dacă există o formulă $\psi (n_{1},\ldots ,n_{k})$ astfel încât $R(n_{1},\ldots ,n_{k})\iff \psi (n_{1},\ldots ,n_{k})$ este valabilă pentru toate k-uplurile $(n_{1},\ldots ,n_{k})$ numerelor naturale.

O funcție finitară pe numerele naturale se numește aritmetică dacă graficul său este o relație binară aritmetică.

O mulțime A se spune că este aritmetică pe o mulțime B dacă A este definibilă printr-o formulă aritmetică care are pe B ca parametru al mulțimii.

Exemple

• Mulțimea numerelor prime este aritmetică.
• Orice mulțime numărabilă recursiv este aritmetică.
• Orice funcție calculabilă este definibilă aritmetic.
• Mulțimea pentru codarea problemei Halting este aritmetică.
• Constanta Chaitin este un număr real aritmetic.
• Teorema Tarski arată că setul de formule adevărate ale aritmeticii de ordinul întâi nu este definibil aritmetic.

Proprietăți

• Complementul unei mulțimi aritmetice este o mulțime aritmetică.
• Saltul Turing pe o mulțime aritmetică este o mulțime aritmetică.
• Colecția de mulțimi aritmetice este numărabilă, dar secvența mulțimilor aritmetice nu este definibilă aritmetic. Astfel, nu există o formulă aritmetică φ(n,m) care să fie adevărată dacă și numai dacă m este un membru al predicatelor aritmetice de ordinul n.

De fapt, o astfel de formulă ar descrie o problemă de decizie pentru toate salturile Turing, prin urmare, aparține lui 0^(ω), care nu poate fi formalizat în aritmetica de ordinul întâi, nu aparține ierarhiei aritmetice de ordinul întâi.

• Mulțimea numerelor aritmetice reale este numărabilă, densă și ordonată izomorf cu mulțimea numerelor raționale.

Mulțimi aritmetice implicite

Fiecare mulțime aritmetică are o formulă aritmetică care spune dacă anumite numere sunt în ea. O noțiune alternativă de definibilitate permite o formulă care nu spune dacă anumite numere sunt în ea, dar spune dacă mulțimea în sine are o anumită proprietate aritmetică.

O mulțime Y de numere naturale este implicit aritmetică sau implicit definibilă aritmetic dacă este definibilă cu o formulă aritmetică care este capabilă să utilizeze Y ca parametru. Adică, dacă există o formulă $\theta (Z)$ în limbajul aritmeticii Peano fără variabile numerice libere și un nou parametru, mulțimeaZ, iar relația de apartenență a mulțimii $\in$ să fie astfel încât Y să fie unica mulțime Z pentru care $\theta (Z)$ să fie valabilă.

Orice mulțime aritmetică este implicit aritmetică; dacă X este definită aritmetic prin φ(n) atunci este definită implicit prin formula

$\forall n[n\in Z\iff \phi (n)]$.

Totuși, nu orice mulțime implicită aritmetic este aritmetică. În special, mulțimea valorilor de adevăr ale aritmeticii de ordinul întâi este o mulțime implicit aritmetică, dar nu și o mulțime aritmetică.

Lectură suplimentară

• en Rogers, H. (1967). Theory of recursive functions and effective computability. McGraw-Hill. OCLC 527706