Aritmetica lui Robinson

Aritmetica lui Robinson , de obicei notată cu Q în logica matematică , este o teorie de primul ordin, definită pentru prima dată de Raphael M. Robinson în 1950 ^[1] care are ca axiome proprii o versiune redusă a axiomelor lui Peano în care principiul inducției este absent și există adăugarea unei axiome care afirmă că fiecare număr natural, altul decât zero, este succesorul unui alt număr (care în aritmetica lui Peano este demonstrabilă prin inducție). Interesul aritmeticii lui Robinson pentru logică constă în faptul că este cea mai slabă teorie în care este posibil să se reprezinte toate funcțiile recursive primitive și, în consecință, este, de asemenea, cea mai slabă teorie la care se referă prima dintre teoremele incompletitudinii lui Gödel .

Definiție

Limbajul lui Q este limbajul aritmeticii de ordinul întâi .

Axiomele lui Q constau din axiomele logice , axiomele pentru egalitate și următoarele axiome proprii :

(Q1) $\forall x\neg (S(x)=0)$ ${\ displaystyle \ forall x \ neg (S (x) = 0)}$ ${\ displaystyle \ forall x \ neg (S (x) = 0)}$

Exprimă faptul că 0 nu este succesorul unui număr

(Q2) $\forall x\forall y(S(x)=S(y)\rightarrow x=y)$ ${\ displaystyle \ forall x \ forall y (S (x) = S (y) \ rightarrow x = y)}$ ${\ displaystyle \ forall x \ forall y (S (x) = S (y) \ rightarrow x = y)}$

Exprimă faptul că numerele diferite au succesori diferiți, adică funcția succesor este o funcție injectivă

(Q3) $\forall x(\neg (x=0)\to \exists y(x=S(y)))$ ${\ displaystyle \ forall x (\ neg (x = 0) \ to \ există y (x = S (y)))}$ ${\ displaystyle \ forall x (\ neg (x = 0) \ to \ există y (x = S (y)))}$

Exprimă faptul că orice număr, altul decât 0, este succesorul unui alt număr

(Q4) $\forall x(x+0=x)$ ${\ displaystyle \ forall x (x + 0 = x)}$ ${\ displaystyle \ forall x (x + 0 = x)}$
(Q5) $\forall x\forall y(x+S(y)=S(x+y))$ ${\ displaystyle \ forall x \ forall y (x + S (y) = S (x + y))}$ ${\ displaystyle \ forall x \ forall y (x + S (y) = S (x + y))}$

Această pereche de axiome definește recursiv adăugarea

(Q6) $\forall x(x\times 0=0)$ ${\ displaystyle \ forall x (x \ times 0 = 0)}$ ${\ displaystyle \ forall x (x \ times 0 = 0)}$
(Q7) $\forall x\forall y(x\times S(y)=(x\times y)+x)$ ${\ displaystyle \ forall x \ forall y (x \ times S (y) = (x \ times y) + x)}$ ${\ displaystyle \ forall x \ forall y (x \ times S (y) = (x \ times y) + x)}$

Această pereche de axiome definește recursiv multiplicarea

Incompletitatea Q

După cum sa menționat, Q este o teorie incompletă . Acest fapt poate fi văzut fără a fi necesar să invocăm teoremele lui Gödel : o afirmație simplă indecidabilă în Q este cea care afirmă proprietatea comutativă a adunării

\forall x\forall y(x+y=y+x)

{\ displaystyle \ forall x \ forall y (x + y = y + x)}

{\ displaystyle \ forall x \ forall y (x + y = y + x)}

.

Pentru a arăta că este indecidabil, construim un model non-standard de Q care nu respectă proprietatea comutativă a adunării : de exemplu, să considerăm un model compus din uniunea mulțimii numerelor naturale N cu un set de două „străine” „elemente { a , b }. Definim funcția „succesor” pentru a și b ca

S ( a ): = a

S ( b ): = b

este ușor să verificați dacă S respectă axiomele (Q1), (Q2) și (Q3); apoi extindem operația + pe setul N ∪ { a , b } prin setarea:

a + n : = a pentru toate n din N

b + n : = b pentru toate n din N

n + a : = b pentru toate n din N

n + b : = a pentru toate n din N

a + a : = b

b + b : = a

a + b : = a

b + a : = b

se poate verifica dacă operația definită respectă axiomele (Q4) și (Q5). De asemenea, este posibil să se extindă înmulțirea în N ∪ { a , b } pentru a verifica axiomele (Q6) și (Q7) ^[2] : ceea ce este în schimb relevant este că operația „+” tocmai definită nu comută: a + b = a în timp ce b + a = b . Deducem că în Q nu este posibil să se demonstreze formula care afirmă proprietatea comutativă a sumei. Pe de altă parte, în Q nu este nici măcar posibil să-i dovedim negarea, deoarece afirmația este adevărată în modelul standard al numerelor naturale. Concluzionăm că afirmația care exprimă proprietatea comutativă este indecidabilă în Q.

Notă

^ RM Robinson, An Essentially Undecidable Axiom System , în Proceedings of the International Congress of Mathematics , 1950, pp. 729-730.
^ Peter Smith, capitolul 10.5 , în O introducere la teoremele lui Gödel , ediția a II-a, Pp. 69-70.

Elemente conexe

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] RM Robinson, An Essentially Undecidable Axiom System , în Proceedings of the International Congress of Mathematics , 1950, pp. 729-730.

[2] Peter Smith, capitolul 10.5 , în O introducere la teoremele lui Gödel , ediția a II-a, Pp. 69-70.

[1]

[2]