Î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 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ă

modificare

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   este aritmetică dacă există o formulă   astfel încât   este valabilă pentru toate k-uplurile   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.

Proprietăți

modificare
  • 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

modificare

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ă   în limbajul aritmeticii Peano fără variabile numerice libere și un nou parametru, mulțimeaZ, iar relația de apartenență a mulțimii   să fie astfel încât Y să fie unica mulțime Z pentru care   să fie valabilă.

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

 .

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ă

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