Reprezentabilitate

În logica matematică conceptul de reprezentabilitate a unei funcții sau a unui predicat este legat de teoriile formale aritmetice, și anume teoriile de ordinul întâi care au ca limbaj limbajul aritmetic de ordinul întâi și apoi admit ca model structura naturii numere cu operații de adunare și multiplicare. Exemple de astfel de teorii sunt aritmetica lui Peano și aritmetica lui Robinson .

Ideea unei mulțimi care poate fi reprezentată de o teorie aritmetică T este cea a unei mulțimi pentru care

există o formulă care exprimă întregul în limbajul lui T
având în vedere orice număr este posibil să „ni se spună” prin teoria T dacă aparține sau nu mulțimii.

Un discurs analog este valabil pentru funcțiile reprezentabile.

Definiție

În limbajul aritmeticii de prim ordin există termeni „standard” pentru a desemna numere naturale numite numere :

0 este cifra numărului zero

S (0) este numărul numărului 1

S (S (0)) este cifra numărului 2

...si asa mai departe...

Dacă notăm cu S ⁿ (0) termenul S (S (S (... S (S (0))) ...))) în care simbolul S apare de n ori putem spune că S ⁿ (0 ) este numeralul numărului n .

Acum putem da următoarea definiție:

Având în vedere un subset $U$ ${\ displaystyle U}$ $U$ din mulțimea N de numere naturale vom spune că $U$ ${\ displaystyle U}$ $U$ este reprezentabil în T dacă

există o formulă bine formată φ (x) cu o variabilă liberă care o exprimă ;
pentru orice număr natural $n$ {\ displaystyle n} $n$ avem asta
- de sine $n\in U$ ${\ displaystyle n \ în U}$ ${\ displaystyle n \ în U}$ atunci φ (S ⁿ (0)) este demonstrabil în T
- de sine $n\notin U$ ${\ displaystyle n \ notin U}$ ${\ displaystyle n \ notin U}$ asa de $\neg$ ${\ displaystyle \ neg}$ $\ neg$ φ (S ⁿ (0)) este demonstrabil în T

Noțiunea de reprezentabilitate poate fi extinsă și la subseturi de N ^k și deci la relațiile cu k argumente. În acest caz, formula care le reprezintă trebuie să aibă k variabile libere.

Exemple

Setul U = { 0 } format doar din numărul 0 poate fi exprimat prin intermediul formulei
$\varphi (x):\equiv (x=0)$ ${\ displaystyle \ varphi (x): \ equiv (x = 0)}$ ${\ displaystyle \ varphi (x): \ equiv (x = 0)}$

și prin intermediul acestei formule poate fi reprezentat și în aritmetica lui Robinson , de fapt dacă n ∈ U adică n = 0 atunci formula

\varphi (0)\equiv (0=0)

{\ displaystyle \ varphi (0) \ equiv (0 = 0)}

{\ displaystyle \ varphi (0) \ equiv (0 = 0)}

este demonstrabil fiind o instanță a axiomelor pentru egalitate , dacă în schimb n ≠ 0 atunci formula

\neg \varphi (S^{n}(0))\equiv \neg (S^{n}(0)=0)\equiv \neg (S(S(...S(0)...))=0)

{\ displaystyle \ neg \ varphi (S ^ {n} (0)) \ equiv \ neg (S ^ {n} (0) = 0) \ equiv \ neg (S (S (... S (0). ..)) = 0)}

{\ displaystyle \ neg \ varphi (S ^ {n} (0)) \ equiv \ neg (S ^ {n} (0) = 0) \ equiv \ neg (S (S (... S (0). ..)) = 0)}

este demonstrabil prin exploatarea axiomei (Q1) (din axiomele aritmeticii lui Robinson ), axioma (L5) axiomelor logice și modus ponens . Prin urmare, pentru U se verifică definiția setului reprezentabil în aritmetica lui Robinson.

Mulțimea U = N poate fi reprezentată în orice teorie care include axiomele logice printre axiomele sale. Pentru a exprima și reprezenta mulțimea N orice tautologie este suficientă, de fapt tautologiile sunt toate demonstrabile a doar prin intermediul axiomelor logice.

Mulțimea goală este reprezentabilă în orice teorie care include axiomele logice printre axiomele sale. Orice contradicție este suficientă pentru a exprima și reprezenta setul gol, de fapt tautologiile sunt toate demonstrabile doar prin intermediul axiomelor logice.

Se poate arăta că orice set recursiv este reprezentabil în aritmetica lui Robinson și, prin urmare, și în aritmetica lui Peano .

Reprezentați funcții

Pentru o funcție

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

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

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

există două noțiuni de reprezentabilitate :

Se spune că funcția f este slab reprezentabilă în teoria aritmetică T se

există o formulă bine formată φ (y, x) cu 2 variabile libere care exprimă relația y = f ( x );
pentru fiecare pereche de numere naturale n și m avem asta
- dacă n = f ( m ) atunci φ (S ⁿ (0), S ^m (0)) este demonstrabil în T
- dacă n ≠ f ( m ) atunci $\neg$ ${\ displaystyle \ neg}$ $\ neg$ φ (S ⁿ (0), S ^m (0)) este demonstrabil în T.

Prin urmare, o funcție f este slab reprezentabilă dacă graficul său este reprezentabil ca un set.

Se spune că funcția f este puternic reprezentabilă în T sau reprezentabilă ca funcție dacă, împreună cu condițiile anterioare, este valabilă și condiția suplimentară:

pentru fiecare număr natural m formula poate fi dovedită în T

\exists y(\varphi (y,S^{m}(0))\land \forall z(\varphi (y,S^{m}(0))\to (z=y)))

{\ displaystyle \ există y (\ varphi (y, S ^ {m} (0)) \ land \ forall z (\ varphi (y, S ^ {m} (0)) \ to (z = y))) }

{\ displaystyle \ există y (\ varphi (y, S ^ {m} (0)) \ land \ forall z (\ varphi (y, S ^ {m} (0)) \ to (z = y))) }

Această formulă traduce faptul că relația y = f (x) exprimată prin formula φ (y, x) se comportă asupra numărului m ca o funcție , adică având în vedere elementul m al domeniului există un singur element y din gama care este în relație cu m .

Noțiunile de reprezentabilitate descrise mai sus sunt ușor generalizate la funcțiile definite pe N ^k mai degrabă decât pe N.

Elemente conexe