... Î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 sun...
 

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

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.

Exemple

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

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




  Go to top  

This article is issued from web site Wikipedia. The original article may be a bit shortened or modified. Some links may have been modified. The text is licensed under "Creative Commons - Attribution - Sharealike" [1] and some of the text can also be licensed under the terms of the "GNU Free Documentation License" [2]. Additional terms may apply for the media files. By using this site, you agree to our Legal pages [3] [4] [5] [6] [7]. Web links: [1] [2]