Mulțime aritmetică

Format:Note de subsol2 Î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ă Format:Mvar, (de exemplu mulțimile Format:Mvar-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 Format:Mvar 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 Format:Mvar 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, Format:Mvar, este aritmetică sau definibilă aritmetic dacă există o formulă φ(n) în limbajul aritmeticii Peano astfel încât Format:Mvar să fie în Format:Mvar dacă și numai dacă φ(n) respectă modelul aritmetic standard. Similar, o relație de ordinul Format:Mvar $R(n_1,\dots ,n_k)$ este aritmetică dacă există o formulă $\psi (n_1,\dots ,n_k)$ astfel încât $R(n_1,\dots ,n_k)⟺\psi (n_1,\dots ,n_k)$ este valabilă pentru toate Format:Mvar-uplurile $(n_1,\dots ,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 Format:Mvar se spune că este aritmetică pe o mulțime Format:Mvar dacă Format:Mvar este definibilă printr-o formulă aritmetică care are pe Format:Mvar 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ă φ(Format:Mvar) care să fie adevărată dacă și numai dacă Format:Mvar este un membru al predicatelor aritmetice de ordinul Format:Mvar.

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

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

$\mathrm{\forall }n[n\in Z⟺\varphi (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ă

• Format:En icon Rogers, H. (1967). Theory of recursive functions and effective computability. McGraw-Hill. Format:Oclc