Aritmetica tipografică

În matematică , aritmetica tipografică sau AT (în engleză Typographic Number Theory , sau TNT ) este un sistem formal axiomatic care descrie numerele naturale care apare în cartea lui Douglas Hofstadter Gödel, Escher, Bach . Este o implementare a aritmeticii lui Peano .

Ca orice sistem care implementează axiomele lui Peano, aritmetica tipografică este capabilă să se refere la sine (este auto-referențială ).

Se utilizează un sistem restricționat, care se ocupă doar de numere întregi și numere pozitive, pentru a găsi configurația minimă în care pare posibilă exprimarea teoremei lui Gödel .

În versiunea sa minimă, TA utilizează 20 de simboluri, plus un simbol de sfârșit de linie. De asemenea, este definită asocierea fiecărui simbol cu un număr Gödel în care se utilizează numere din trei cifre (numite triplete prin analogie cu ADN ) compuse din cifrele 1, 2, 3 și 6.

Unele dintre simboluri și reguli derivă dintr-un sistem formal definit anterior, numit calcul propozițional care implementează calculul propozițional utilizat în mod obișnuit în logica matematică .

Prin traducerea formulelor în numere, Hofstadter arată cum teorema lui Gödel corespunde unui număr și cum acest număr face parte din TA.

Este definită și o versiune a TA care elimină unele simboluri, numită versiunea frugală a TA.

Numere

În aritmetica tipografică nu există niciun simbol care să exprime fiecare număr natural . În schimb, fiecare natural este asociat cu un șir format doar din cele două simboluri S și 0 :

zero	0
unu	S0
Două	SS0
Trei	SSS0
patru	SSSS0
cinci	SSSSS0

si asa mai departe.

Simbolul S poate fi interpretat ca „Succesorul lui”.

Variabile

De asemenea, trebuie să ne referim la numere sau variabile nespecificate. Există cinci variabile în TA:

a , b , c , d , e .

Alte variabile pot fi construite adăugând un supercript la dreapta lor, ca acesta

a ', b ', c ', a ' ', a ' ''

toate sunt variabile.

În versiunea frugală a Vechiului Testament, există doar simboluri

a ', a ' ', a ' '' etc.

Operatori

Adunarea și multiplicarea numerelor

În aritmetica tipografică, simbolurile obișnuite " + " sunt utilizate pentru adunare și " · " pentru multiplicare. Deci pentru a scrie „b plus c” scrii

(b + c)

și se scrie „a for d”

(a d) .

Rețineți că parantezele sunt necesare pentru ca șirurile să fie bine formate . Mai mult, operațiile sunt binare și, prin urmare, o operație poate fi efectuată numai între doi termeni. Pentru a scrie „a plus b plus c” trebuie să scrieți

((a + b) + c)

sau

(a + (b + c)) .

Egalitate

Pentru a indica egalitatea se folosește simbolul „ = ”, având același sens pe care îl are de obicei în matematică. De exemplu,

SSS0 + SSS0 = SSSSSS0

este o teoremă TA (corespunzătoare unei afirmații adevărate în aritmetică ), ceea ce înseamnă că „3 plus 3 este egal cu 6”.

Negare

În Vechiul Testament, negația , adică transformarea unei afirmații în opusul ei, este notată cu simbolul „¬”. De exemplu,

¬ ( SSS0 + SSS0 ) = SSSSSSS0

este o teoremă TA.

Conjuncție

Simbolurile sunt folosite pentru a indica conjuncția („și”)

< , la începutul șirului;

∧ , pentru a indica „e”;

> , la sfârșitul șirului.

Astfel, propoziția „0 plus unu este egal cu unu și unu plus unu este egal cu doi” este scrisă ca:

<(0 + S0) = S0∧ (S0 + S0) = SS0> .

Disjuncție

Simbolurile sunt folosite pentru a indica disjuncția („sau”)

< , la începutul șirului;

∨ , pentru a indica „o”;

> , la sfârșitul șirului.

Deci, propoziția „0 plus unu este egal cu unul sau unul plus unu este egal cu doi” este scrisă astfel:

<(0 + S0) = S0∨ (S0 + S0) = SS0> .

Implicare

Pentru a indica implicația logică („dacă ... atunci ...”), sunt utilizate următoarele simboluri:

< , la începutul șirului;

⊃ , pentru a separa premisa și concluzia;

> , la sfârșitul șirului.

Astfel, propoziția „dacă unul este egal cu zero, atunci zero este egal cu unul” este scrisă astfel:

<S0 = 0⊃0 = S0> .

Atomi și simboluri propoziționale

Toate simbolurile calculului propozițional sunt utilizate în aritmetica tipografică și își păstrează semnificația.

Pentru atomi ne referim la șiruri care atestă egalități, cum ar fi de exemplu

¬ S0 = SS0 .

În schimb, următoarele sunt formule compuse:

( SS0 + SSS0 ) = SSSS0 ; 2 plus 3 este egal cu 4,

¬ ( SS0 + SS0 ) = SSS0 ; 2 plus 2 nu este egal cu 3,

<S0 = 0⊃0 = S0> ; dacă 1 este egal cu 0, atunci 0 este egal cu 1.

Cuantificatoare

Se utilizează două cuantificatoare: ∀ și ∃ .

∃ înseamnă „există”, se numește cuantificator existențial
∀ înseamnă „pentru fiecare”, se numește cuantificatorul universal
Simbolul „ : ” este utilizat pentru a separa un cuantificator de un alt cuantificator sau de restul formulei.

De exemplu

∀a: ∀b: (a + b) = (b + a)

„pentru fiecare număr a și pentru fiecare număr b , un plus b este egal cu b plus a ” sau „adunarea este comutativă ”.

¬∃c: Sc = 0

„nu există un număr c astfel încât c plus unu să fie egal cu zero”, adică „zero nu este succesorul unui număr natural”.

O variabilă care se află în câmpul de acțiune al unui cuantificator se numește variabilă cuantificată, altfel se numește variabilă liberă . O formulă care conține cel puțin o variabilă gratuită se numește deschisă , altfel se numește închisă sau pronunțată .

Reguli de antrenament

Numere: 0 este o cifră.; Un numeral precedat de S este, de asemenea, un numeral.; Exemple: 0 , S0 , SS0 .

Variabile: a , b , c , d , e sunt variabile.; O variabilă urmată de un singur ghilimel este, de asemenea, o variabilă.; Exemple: a , b ' , c' '' .

Termeni: Toate numerele și toate variabilele sunt termeni.; Un termen precedat de S este, de asemenea, un termen.; Dacă s și t sunt termeni, atunci la fel sunt ( s + t ) și ( s · t ).; Exemple: 0 , b , SSa ' , (S0 · (SS0 + c)) , S (Sa · (Sb · Sc)) .

Termenii se împart în două categorii:

termeni definiți (care nu conțin variabile), de exemplu: 0 , (S0 + S0) .
termeni nedefiniti (care contin variabile), de exemplu: b , (((S0 + S0) + S0) + e) .

Atomi: Dacă s și t sunt termeni, atunci s = t este un atom.; Exemple: S0 = 0 , S (b + c) = ((c d) e) .

Negări: O formulă bine formată precedată de un simbol de negație ( ¬ ) este bine formată.; Exemple: ¬S0 = 0 , ¬ <0 = 0⊃S0 = 0> .

Compuși: Dacă x și y sunt formule bine formate și niciuna dintre variabilele libere ale uneia nu este cuantificată în cealaltă, atunci următoarele formule sunt bine formate:; < x ∧ y > , < x ∨ y > , < x ⊃ y > .; Exemple: <0 = 0∧¬0 = 0> , <S0 = 0⊃∀c: ¬∃b: (b + b) = c> .

Cuantificări: Dacă u este o variabilă și x este o formulă bine formată în care u este liber, atunci următoarele șiruri sunt formule bine formate:; ∃ u : x , ∀ u : x .; Exemple: ∀a : <a = a∨¬∃c: c = a> , ~ ∃c: Sc = d .

Formule deschise: Acestea conțin cel puțin o variabilă gratuită.; Exemple: ¬c = c , <∀b: b = b∧¬c = c> .

Formule închise (enunțuri): Nu conțin variabile libere.; Exemple: S0 = 0 , ¬∀d: d = 0 .

Axiome

∀a: ¬Sa = 0
∀a: (a + 0) = a
∀a: ∀b: (a + Sb) = S (a + b)
∀a: (a 0) = 0
∀a: ∀b: (a Sb) = ((a b) + a)

Reguli

Regula particularizării: Fie u o variabilă care apare în șirul x . Dacă șirul ∀ u : x este o teoremă, atunci x este și el, la fel și toate șirurile obținute din x prin înlocuirea lui u , în oricare dintre aparițiile sale, cu orice termen dat. Termenul care înlocuiește u nu trebuie să conțină o variabilă care este cuantificată în x .; Exemplu: din axioma 1, substituind 0 în loc de a , obținem ¬S0 = 0 .

Regula generalizării: Fie x o teoremă în care apare variabila liberă u . Atunci ∀ u : x este o teoremă.

Regula de schimb: Dacă u este o variabilă, atunci șirurile ∀u: ¬ și ¬∃u: sunt interschimbabile în cadrul oricărei teoreme.; Exemplu: aplicând această regulă axiomei 1, obținem ¬∃a: Sa = 0 (adică: zero nu este succesorul unui număr natural).

Regula existenței: Dacă un termen (care poate conține variabile, cu condiția să fie libere) apare de una sau mai multe ori într-o teoremă, atunci îl puteți înlocui într-unul, în unele sau în toate aparițiile sale, cu o variabilă care nu apare deja în teorema, precedând întregul cu cuantificatorul existențial corespunzător.; Exemplu: aplicând această regulă axiomei 1, obținem ∃b: ∀a: ¬Sa = b .

Regula de simetrie pentru egalitate: Dacă r = s este o teoremă, atunci r = s este .

Regula tranzitivității pentru egalitate: Dacă r = s și s = t sunt teoreme, atunci r = t este .

Regula de introducere pentru succesor: Dacă r = t este o teoremă, atunci S r = S t este o teoremă.

Regula eliminării pentru succesor: Dacă S r = S t este o teoremă, atunci r = t este o teoremă.

În următoarea regulă folosim această notație: o formulă bine formată în care variabila a este liberă este abreviată cu simbolul X { a }. In schimb, simbolul X {Sa / a} indică același șir X în care, totuși, fiecare apariție a unei a fost înlocuit cu Sa. In mod similar, X {0 / a} indică șirul inițial , în care fiecare apariție a unei a fost înlocuit cu 0.

Regula de inducție: Fie u o variabilă și X { u } o formulă bine formată în care u apare liber. Dacă ∀ u : < X { u } ⊃ X { S u / u } > și X { 0 / u } sunt ambele teoreme, atunci ∀ u : X { u } este, de asemenea, o teoremă.

Bibliografie

Hofstadter, Douglas , Gödel, Escher, Bach: o ghirlandă strălucitoare eternă , Adelphi , ISBN 8845907554

Elemente conexe

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