Aritmetica lui Peano

Aritmetica lui Peano , notată și de acronimul PA ( Peano Arithmetic ) în logica matematică este o teorie de prim ordin care are ca axiome o versiune a axiomelor lui Peano exprimată în limbajul de primul ordin .

Definiție

Limbajul PA este limbajul aritmeticii de ordinul întâi , adică constă din următoarele simboluri:

simboluri pentru variabile: $X$ ${\ displaystyle x}$ $X$ , $y$ ${\ displaystyle y}$ $y$ , $z$ ${\ displaystyle z}$ $z$ , $x_{1}$ ${\ displaystyle x_ {1}}$ $x_1$ , $x_{2}$ ${\ displaystyle x_ {2}}$ $x_2$ , $x_{3}$ ${\ displaystyle x_ {3}}$ $x_3$ , $x_{4}$ ${\ displaystyle x_ {4}}$ $x_ {4}$ , ...
constante individuale:
simboluri pentru funcții unare: $S.$ ${\ displaystyle S}$ $S.$
simboluri pentru funcții binare: $+$ ${\ displaystyle +}$ $+$ , $\times$ ${\ displaystyle \ times}$ $\ ori$
simboluri pentru relațiile binare: $=$ ${\ displaystyle =}$ $=$
simboluri pentru conectivități logice, cuantificatoare și paranteze

În sintaxa PA, înseamnă funcția binară $+$ ${\ displaystyle +}$ $+$ calculat pe termeni $t_{1}$ ${\ displaystyle t_ {1}}$ $t_1$ Și $t_{2}$ ${\ displaystyle t_ {2}}$ $t_2$ în loc să scrie $+(t_{1},t_{2})$ ${\ displaystyle + (t_ {1}, t_ {2})}$ $+ (t_ {1}, t_ {2})$ este obișnuit să scrii $t_{1}+t_{2}$ ${\ displaystyle t_ {1} + t_ {2}}$ $t_ {1} + t_ {2}$ . O convenție similară se aplică funcției binare $\times$ ${\ displaystyle \ times}$ $\ ori$ .

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

(PA1)

\forall x\neg (S(x)=0)

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

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

(PA2)

\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)}

(PA3)

\forall x(x+0=x)

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

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

(PA4)

\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))}

(PA5)

\forall x(x\times 0=0)

{\ displaystyle \ forall x (x \ times 0 = 0)}

{\ displaystyle \ forall x (x \ times 0 = 0)}

(PA6)

\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)}

(PA7) închiderea universală a

\varphi (0,x_{1},...x_{n})\land (\forall x(\varphi (x,x_{1},...,x_{n})\rightarrow \varphi (S(x),x_{1},...,x_{n})))\rightarrow \forall x\varphi (x,x_{1},...,x_{n})

{\ displaystyle \ varphi (0, x_ {1}, ... x_ {n}) \ land (\ forall x (\ varphi (x, x_ {1}, ..., x_ {n}) \ rightarrow \ varphi (S (x), x_ {1}, ..., x_ {n}))) \ rightarrow \ forall x \ varphi (x, x_ {1}, ..., x_ {n})}

{\ displaystyle \ varphi (0, x_ {1}, ... x_ {n}) \ land (\ forall x (\ varphi (x, x_ {1}, ..., x_ {n}) \ rightarrow \ varphi (S (x), x_ {1}, ..., x_ {n}))) \ rightarrow \ forall x \ varphi (x, x_ {1}, ..., x_ {n})}

pentru fiecare wff

\varphi (x,x_{1},...,x_{n})

{\ displaystyle \ varphi (x, x_ {1}, ..., x_ {n})}

{\ displaystyle \ varphi (x, x_ {1}, ..., x_ {n})}

in care

x,x_{1},...,x_{n}

{\ displaystyle x, x_ {1}, ..., x_ {n}}

{\ displaystyle x, x_ {1}, ..., x_ {n}}

sunt variabile libere .

(PA7) este o schemă de axiome numită schemă de inducție , există o axiomă distinctă pentru fiecare wff $\varphi$ ${\ displaystyle \ varphi}$ $\ varphi$ .

Ideea din spatele axiomelor este următoarea:

(PA1) traduce în mod formal afirmația „zero nu este succesorul niciunui număr” (a patra dintre axiomele lui Peano ),
(PA2) traduce în mod formal afirmația „numerele diferite au succesori diferiți” (al treilea din axiomele lui Peano ),
(PA3) și (PA4) oferă împreună o definiție recursivă a operației de adunare pornind de la funcția succesor,
(PA5) și (PA6) definesc recursiv multiplicarea pornind de la adunare,
(PA7) conține formulările tuturor instanțelor posibile ale principiului inducției (a cincea din axiomele lui Peano ) pe toate formulele posibile.

Modelul „standard”

Axiomele PA au fost elaborate având în vedere un model precis:

setul de referință pentru variabile este setul de numere naturale
simbolul ar dori să reprezinte numărul natural 0
simbolul $S.$ ${\ displaystyle S}$ $S.$ reprezintă „succesor“ funcția care asociază numărul n + 1 la un număr n
simbolurile $+,\times$ ${\ displaystyle +, \ times}$ $+, \ ori$ reprezintă operațiile binare de adunare și multiplicare
simbolul $=$ ${\ displaystyle =}$ $=$ reprezintă relația de egalitate

Primele două axiome (PA1) și (PA2) sunt traducerile în limbajul formal al primelor două axiome ale lui Peano , ele exprimă faptul că 0 nu este succesorul niciunui număr și funcția „succesor” este o funcție injectivă . Axiomele (PA3), (PA4), (PA5) și (PA6) definesc inductiv operațiile de adunare și multiplicare, a doua în ceea ce privește prima și prima în ceea ce privește „succesorul”. Ne-am putea întreba de ce nu au fost introduse axiomele pentru putere , în realitate se arată că axiomele date sunt suficiente pentru a reprezenta operația de exponențiere. (PA7) este o modalitate de a traduce principiul inducției într-o teorie de ordinul întâi prin intermediul unei scheme de axiome . Principiul inducției afirmă că orice subset de numere naturale care are proprietățile de a conține 0 și de a conține succesorii elementelor sale coincide cu mulțimea numerelor naturale, în mod formal ar trebui să scriem:

\forall U[((0\in U)\land \forall x((x\in U)\to (S(x)\in U)))\to \forall x(x\in U)]

{\ displaystyle \ forall U [((0 \ in U) \ land \ forall x ((x \ in U) \ to (S (x) \ in U))) \ to \ forall x (x \ in U) ]}

{\ displaystyle \ forall U [((0 \ in U) \ land \ forall x ((x \ in U) \ to (S (x) \ in U))) \ to \ forall x (x \ in U) ]}

cu toate acestea, această formulă nu este exprimată în limbajul primului ordin, deoarece conține cuantificatori pe seturi, precum și pe elemente. Ideea de a ocoli acest obstacol este de a reprezenta seturi de numere naturale prin wff-uri cu o variabilă liberă . În loc să scrie asta $x\in U$ ${\ displaystyle x \ în U}$ $x \ în U$ noi scriem $\varphi (x)$ ${\ displaystyle \ varphi (x)}$ $\ varphi (x)$ unde este $\varphi$ ${\ displaystyle \ varphi}$ $\ varphi$ este un wff care exprimă proprietățile pe care trebuie să le aibă un număr pentru a aparține setului $U$ ${\ displaystyle U}$ $U$ . Apoi devine traducerea formulei de mai sus

pentru fiecare wff

\varphi (x)

{\ displaystyle \ varphi (x)}

\ varphi (x)

cu o variabilă gratuită

(\varphi (0)\land \forall x(\varphi (x)\to \varphi (S(x)))\to \forall x\varphi (x)

{\ displaystyle (\ varphi (0) \ land \ forall x (\ varphi (x) \ to \ varphi (S (x))) \ to \ forall x \ varphi (x)}

{\ displaystyle (\ varphi (0) \ land \ forall x (\ varphi (x) \ to \ varphi (S (x))) \ to \ forall x \ varphi (x)}

(PA7) este o generalizare naturală a acestei scheme de axiome. Acum problema este că nu toate seturile de numere naturale pot fi reprezentate cu un wff adecvat, pentru a realiza acest lucru este suficient să observăm că setul de părți ale $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ N$ are cardinalitatea continuumului, în timp ce setul de formule bine formate este numărabil . Principala consecință a acestui fapt este existența modelelor reciproc neizomorfe , adică incapacitatea axiomelor PA de a caracteriza în mod unic o structură.

Modele nestandardizate

În plus față de modelul standard al numerelor naturale, există și alte modele în care se verifică toate axiomele (PA1) - (PA7) și care nu sunt izomorfe față de cel standard. Definirea explicită a unuia dintre aceste modele este ceva foarte complex, cu toate acestea existența modelelor non-standard este demonstrabilă de-a lungul multor căi diferite. Cea mai simplă dovadă este cea care folosește teorema compactității : un nou simbol al constantei individuale este adăugat limbajului $Și$ ${\ displaystyle e}$ $Și$ care ar indica un element „extern” mulțimii numerelor naturale și considerăm teoria PA * care pe lângă axiomele PA are următoarele axiome infinite:

(NS0)

e>0

{\ displaystyle e> 0}

{\ displaystyle e> 0}

(NS1)

e>S(0)

{\ displaystyle e> S (0)}

{\ displaystyle e> S (0)}

(NS2)

e>S(S(0))

{\ displaystyle e> S (S (0))}

{\ displaystyle e> S (S (0))}

...

prin urmare observăm că fiecare subset finit $\Phi$ ${\ displaystyle \ Phi}$ $\ Phi$ axiomelor PA ^* are un model: de fapt va exista un maxim k astfel încât axioma (NS i ) să nu fie în $\Phi$ ${\ displaystyle \ Phi}$ $\ Phi$ pentru i > k , prin urmare modelul standard al numerelor naturale poate fi considerat ca model prin asocierea simbolului $Și$ ${\ displaystyle e}$ $Și$ numărul natural k + 1 . În mod clar, alegerea lui k va depinde de set $\Phi$ ${\ displaystyle \ Phi}$ $\ Phi$ , prin urmare, această procedură nu ne oferă o metodă pentru a găsi un model verificat de toate axiomele PA ^* , totuși teorema de compactitate menționată mai sus în acest moment ne garantează că există un astfel de model. Este evident că acest model nu poate fi izomorf pentru modelul standard, deoarece conține un element ( e ) care, conform axiomelor, este mai mare decât orice număr natural. Încheiem observând că, deoarece modelul satisface toate axiomele PA ^*, va trebui să satisfacă toate axiomele PA , care sunt și axiomele PA ^* , de aceea am demonstrat existența unui model de PA care nu este izomorf pentru modelul standard.

Se poate arăta că toate modelele numărabile de PA sunt structural izomorfe pentru ansamblu $\mathbb {N} +\mathbb {Q} \times \mathbb {Z}$ ${\ displaystyle \ mathbb {N} + \ mathbb {Q} \ times \ mathbb {Z}}$ ${\ displaystyle \ mathbb {N} + \ mathbb {Q} \ times \ mathbb {Z}}$ . Se arată, de asemenea, că într-un model non-standard, operațiile de „adunare” și „multiplicare” (adică operațiile corespunzătoare simbolurilor respective) nu pot fi recursive .

Bibliografie

Giuseppe Peano , Arithmetices principia, nova methodo exposita , Turin, 1889.

Elemente conexe

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