Limbajul aritmeticii de ordinul întâi

În logica matematică, limbajul aritmeticii de ordinul întâi este un limbaj de ordinul întâi cu care este posibil să se dezvolte teorii formale ale aritmeticii elementare, cum ar fi aritmetica lui Peano și aritmetica lui Robinson .

Alfabetul limbajului aritmetic de ordinul întâi constă din:

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}$ , ...
simboluri pentru constante individuale: $0$ ${\ displaystyle 0}$ ${\ displaystyle 0}$
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

Pentru a indica 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$ .

Model standard

Modelul standard al limbajului aritmeticii este modelul care este considerat ca universul discursului mulțimea N a numerelor naturale și interpretarea simbolului S ca funcție succesoră care asociază numărul n + 1 , simbolul 0 unui număr n cu numărul zero (și , în consecință, termenul S (0) cu succesorul 0, deci 1, S (S (0)) , cu numărul 2 și așa mai departe), interpretând simbolurile + și x ca adiție operațiuni și multiplicare , iar simbol = ca relație de egalitate .

Capacitate expresivă

Exprimarea seturilor, proprietăților și relațiilor

În limbajul aritmeticii de prim ordin nu există simboluri care să indice seturi de numere naturale, totuși un set poate fi identificat cu o formulă deschisă care, atunci când este interpretată în modelul standard, exprimă condiția necesară și suficientă care trebuie să satisfacă un număr natural pentru aparțin acelui număr. 'împreună. De exemplu, setul de numere pare poate fi exprimat prin proprietatea " x este multiplu de 2" care corespunde wff :

\varphi (x):=\exists y(x=y\times S(S(0)))

{\ displaystyle \ varphi (x): = \ există y (x = y \ ori S (S (0)))}

\ varphi (x): = \ există y (x = y \ ori S (S (0)))

care, interpretat în modelul standard, afirmă că x este astfel încât există un alt număr y care înmulțit cu 2 (pe care îl scriem ( S (S (0) )) dă rezultatul x .

Indicăm cu $S^{n}(0)$ ${\ displaystyle S ^ {n} (0)}$ $S ^ {n} (0)$ termenul $S(S(S(...(((0)))...)))$ ${\ displaystyle S (S (S (... (((0))) ...))))}$ $S (S (S (... (((0))) ...)))$ unde simbolul $S.$ ${\ displaystyle S}$ $S.$ apare $n$ ${\ displaystyle n}$ $n$ ori.

Vom spune că o formulă deschisă φ (x) exprimă un set de numere naturale $U$ ${\ displaystyle U}$ $U$ (sau echivalent o proprietate) dacă se întâmplă acest lucru

pentru fiecare $n\in U$ ${\ displaystyle n \ în U}$ $n \ în U$ formula $\varphi (S^{n}(0))$ ${\ displaystyle \ varphi (S ^ {n} (0))}$ $\ varphi (S ^ {n} (0))$ este adevărat în modelul standard
pentru fiecare $n\notin U$ ${\ displaystyle n \ notin U}$ $n \ notin U$ formula $\neg \varphi (S^{n}(0))$ ${\ displaystyle \ neg \ varphi (S ^ {n} (0))}$ $\ neg \ varphi (S ^ {n} (0))$ este adevărat în modelul standard

Prin urmare, vom spune că o mulțime (sau o proprietate) este exprimabilă în limbajul aritmeticii dacă există o formulă deschisă φ (x) care o exprimă .

Noțiunea de expresibilitate poate fi generalizată la subseturi de N ^k , caz în care va fi necesară o formulă deschisă cu k variabile libere φ (x ₁ , x ₂ , ..., x _k ) pentru a exprima un set.

Observăm că nu toate subseturile mulțimii N de numere naturale sau ale lui N ^k sunt exprimabile deoarece totalitatea subseturilor lui N (sau a lui N ^k ) are cardinalitatea continuumului în timp ce setul de formule este numărabil .

Se poate arăta că toate seturile recursive sunt exprimabile.

Relația ≤

O relație poate fi identificată cu setul de perechi ordonate de elemente care sunt legate între ele. Relația ≤, de exemplu, poate fi identificată cu setul de cupluri

\{(x,y)\in \mathbb {N} ^{2}:x\leq y\}

{\ displaystyle \ {(x, y) \ in \ mathbb {N} ^ {2}: x \ leq y \}}

\ {(x, y) \ in \ mathbb {N} ^ {2}: x \ leq y \}

Exprimarea relației ≤ este deci echivalentă cu găsirea unui wff care exprimă acest set. Cel mai simplu mod de a obține un wff de acest tip este cu formula

\varphi (x,y):=\exists z(y=x+z)

{\ displaystyle \ varphi (x, y): = \ există z (y = x + z)}

\ varphi (x, y): = \ există z (y = x + z)

.

Prin urmare, prezența simbolurilor + și = face adăugarea în limbaj a unui simbol pentru relația ≤ de prisos, deoarece există deja o formulă care îl exprimă.

Funcții expres

Vom spune că o funcție

f:\mathbb {N} ^{k}\to \mathbb {N}

{\ displaystyle f: \ mathbb {N} ^ {k} \ to \ mathbb {N}}

f: \ mathbb {N} ^ {k} \ to \ mathbb {N}

poate fi exprimat în limbajul aritmeticii atunci când graficul său sau întregul poate fi exprimat:

\{(x_{1},...,x_{k},y)\in \mathbb {N} ^{k+1}:y=f(x_{1},...,x_{k})\}

{\ displaystyle \ {(x_ {1}, ..., x_ {k}, y) \ in \ mathbb {N} ^ {k + 1}: y = f (x_ {1}, ..., x_ {k}) \}}

\ {(x_ {1}, ..., x_ {k}, y) \ în \ mathbb {N} ^ {{k + 1}}: y = f (x_ {1}, ..., x_ { k}) \}

.

Funcțiile care pot fi ușor exprimate sunt cele pentru care avem simboluri speciale:

funcția succesorală , exprimată prin formulă

y=S(x)

{\ displaystyle y = S (x)}

y = S (x)

adaos , care poate fi exprimat cu formula

y=x_{1}+x_{2}

{\ displaystyle y = x_ {1} + x_ {2}}

y = x_ {1} + x_ {2}

multiplicare , care se exprimă cu formula

y=x_{1}\times x_{2}

{\ displaystyle y = x_ {1} \ times x_ {2}}

y = x_ {1} \ times x_ {2}

.

Este mai puțin banal să înțelegem dacă pot fi exprimate alte funcții precum scăderea sau puterea . De fapt, se poate arăta că toate funcțiile recursive sunt exprimabile în limbajul aritmeticii. În special, puterea este și așa: acest lucru înseamnă că adăugarea de simboluri operaționale binare pentru puteri la limbaj nu i-ar fi mărit capacitatea expresivă. Dimpotrivă, dacă am fi renunțat la simbolul adunării sau multiplicării, nu ar fi existat nicio modalitate de a-l exprima prin intermediul celorlalte simboluri.

Elemente conexe

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