Teoria Tipogràfica dels Nombres

Teoria Tipogràfica de Nombres (en anglès Typographical Number Theory - TNT) és un sistema axiomàtic formal que descriu els nombres naturals que apareixen en el llibre de Douglas Hofstadter Gödel, Escher, Bach. Es tracta d'una aplicació de l'aritmètica de Peano que Hofstadter fa servir per ajudar a explicar els teoremes d'incompletesa de Kurt Gödel i també fa una analogia amb l'ADN.

Igual que qualsevol sistema d'aplicació dels axiomes de Peano, TNT és capaç de referir-se a si mateix (és autoreferencial).

Numerals

TNT no utilitza un símbol diferent per a cada nombre natural. En el seu lloc, fa ús d'una manera simple i uniforme de donar un símbol compost a cada nombre natural, de la següent manera:

zero	0
u	S0
dos	SS0
tres	SSS0
quatre	SSSS0
cinc	SSSSS0

El símbol S es pot interpretar com "el successor de", o "el nombre després de". Ambdues són interpretacions possibles, però no estrictes. No es pot afirmar que, pel fet que quatre és el successor de tres, quatre és SSSS0, sinó més aviat que, ja que tres és el successor de dos, que és el successor d'un, que és el successor de zero, el que hem descrit com a 0, es pot "demostrar" que quatre és SSSS0. TNT està dissenyat de tal manera que qualsevol proposició ha de ser provada abans que pugui dir-se que sigui vertadera. Aquesta és la utilitat i rellevància d'aquesta construcció matemàtica.

Variables

Per tal de referir-se als termes no especificats, TNT fa ús de cinc variables. Aquestes són:

a, b, c, d, e.

Es poden construir més variables mitjançant l'addició del símbol prima després d'ells, per exemple,

a’, b’, c’, a’’, a’’’

En la versió més rígida de TNT, conegut com a TNT "auster", només s'utilitzen les següents variables:

a’, a’’, a’’’, etc.

Operadors

La suma i la multiplicació de nombres

En la teoria tipogràfica de nombres, s'utilitzen els símbols habituals de "+" per a les addicions i "·" per multiplicacions. Així, per escriure "b més c", s'escriu

(b + c)

i "a multiplicat per d " s'escriu com

(a·d)

Els parèntesis són obligatoris. Qualsevol laxitud violaria el sistema de formació de TNT (encara que és trivial demostrar que aquest formalisme no és necessari per a les operacions associativa i commutativa). Una altra norma és que només dos termes poden ser operats a la vegada. Per tant, per escriure "a més b més c", cal escriure bé

((a + b) + c) o bé, (a + (b + c))

L'equivalència

L'operador "equival a" s'utilitza per referir-se a l'equivalència. Es defineix pel símbol "=", i té aproximadament el mateix significat que ho fa normalment en matemàtiques. Per exemple,

(SSS0 + SSS0) = SSSSSS0

és una declaració veritable en TNT, amb la interpretació "3 més 3 és igual a 6".

La negació

En la teoria tipogràfica de nombres, la negació, és a dir, la conversió d'una declaració al seu contrari, es denota per l'operador "~". Per exemple,

~ (SSS0 + SSS0) = SSSSSSS0

és una declaració veritable en TNT, interpretat com a "3 + 3 no és igual a 7".

La negació en TNT és equivalent a la negació de la lògica de Boole (negació lògica), en comptes de ser el contrari. Per exemple, la negació de "menjar una poma" és "no menjar una poma", en lloc de "menjar una cosa diferent d'una poma". De la mateixa manera la negació de "la televisió està encesa" és "La televisió no està encesa" més que "la televisió està apagada". Aquesta és una diferència subtil, però important.

La conjunció

Per indicar la conjunció "i" amb els símbols

<, al principi de la cadena

∧, per referir-se a la "i"

>, al final de la cadena.

Per tant la proposició "0 més un és igual a un i un més un és igual a dos" s'escriu com:

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

La disjunció

Per indicar la disjunció "o", utilitzant els símbols

<, al principi de la cadena

∨, per indicar la "o"

>, al final de la cadena.

Així, la frase "0 més un és igual a un o un més un és igual a dos" s'escriu com:

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

La implicació

Per indicar la implicació lògica "si ... llavors ...", s'utilitzen els següents símbols:

<,al principi de la cadena

⊃, a la premissa i la conclusió per separat

>, al final de la cadena.

Per tant la proposició "si un és igual a zero, el zero és igual a un" s'escriu d'aquesta manera:

<S0=0⊃0=S0>.

Àtoms i els símbols proposicionals

Tots els símbols proposicionals que s'utilitzen en la teoria tipogràfica de nombres són els mateixos que els que s'utilitzen en càlcul proposicional i conserven el seu significat. Per àtoms s'entén aquelles cadenes que contenen igualtats, com per exemple:

¬S0 = SS0, "1 no és igual a 2",

(SS0 + SSS0) = SSSS0,"2 més 3 igual a 4",

¬(SS0 +SS0) = SSS0; "2 més 2 no és igual a 3",

<S0=0⊃0=S0>; "Si un és igual a 0, llavors 0 és igual a 1".

Quantificadors

TNT utilitza dos quantificadors: ∀ i ∃.

∃ significa "existeix", s'anomena quantificador existencial

∀ significa "per a tots",s'anomena quantificador universal

":" s'utilitza per a separar un quantificador d'un altre quantificador o de la resta de la fórmula.

per exemple:

∀ a: ∀ b: (a + b) = (b + a) "Per a tot nombre a i per a tot nombre b, a més b es igual a b més a" o "la addició és commutativa".

¬ ∃ c: Sc = 0 "No existeix un nombre c tal que c més un és igual a zero", o "zero no és el successor de qualsevol nombre natural".

Una variable que està en l'àmbit d'un quantificador es diu variable quantificada, aquesta variable és lliure. Una fórmula que conté almenys una variable lliure es diu oberta, en cas contrari s'anomena tancada o enunciat.

Regles de formació

Numeració

0 és un nombre. Un nombre precedit per S és també un nombre.

Exemples:

0, S0, SS0.

Variables

a, b, c, són variables. Una variable seguida per una prima és també una variable.

Exemples:

a, b ', c.

Termes

Tots els nombres i les variables són termes. Un terme precedit per S és també un terme. Si els conjunts són termes, aleshores també ho són (s + t) i (s · t).

Exemples:

S0, b, SSa', (S0·(SS0+c)), S(Sa·(Sb·Sc)).

Els termes es divideixen en dues categories:

els termes definits (que no contenen variables), per exemple: 0, (S0 + S0).
els termes indefinits (que contenen variables), per exemple: b, (((S0+S0)+S0)+e)..

Àtoms

Si s i t són termes, llavors s = t és un àtom.

Exemple:

S0=0, S(b+c)=((c·d)·e).

Negació

Una fórmula ben formada precedida per un símbol de negació (¬) està ben formada. Exemple:

¬S0=0, ¬<0=0⊃S0=0>.

Composició

Si x i y són fórmules ben formades, i cap de les variables lliures d'una es quantifica en l'altre, a continuació, les següents fórmules són ben formades:

<x∧y>, <x∨y>, <x⊃y>.

Exemple:

<0=0∧¬0=0>, <S0=0⊃∀c:¬∃b:(b+b)=c>.

Mètrica

Si u és una variable i x és una fórmula lliure ben formada, llavors les següents cadenes són fórmules ben formades:

∃ o: x, ∀ o: x.

Exemple:

∀ A: <a=a∨¬∃c:c=a>, ~ ∃ c: c = d.

Fórmules obertes

Si conté almenys una variable lliure.

Exemple:

¬ c = c, <∀ b: b = b ∧ ¬ c = c>.

Fórmules tancades (oracions)

No contenen variables lliures.

Exemples:

S0 = 0, ¬ ∀ D: D = 0.

Axiomes

∀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)

Regles

Regla de la particularització

Sigui o una variable que apareix a la cadena x. Si la cadena ∀ o: x és un teorema, llavors x és, igual que totes les cadenes que s'obtenen mitjançant la substitució de o x, en cada aparició, amb un terme fix. El terme que substitueix o no ha de contenir una variable que es quantifica en x.

Exemple:

axioma 1, substituint 0 en lloc d'una x, s'obté ¬ S0 = 0.

Regla de generalització

x és un teorema que apareix a la variable o lliure. Llavors ∀ o: x és un teorema.

Canvi d'estat

Si u és una variable, llavors la cadena ∀u:¬ i ¬∃u: són intercanviables dins d'un teorema. Exemple: Mitjançant l'aplicació d'aquesta norma amb l'axioma 1, obtenim ¬∃a:Sa=0(és a dir: zero no és el successor de qualsevol nombre natural).

Regla de l'existència

Si un terme (que pot contenir variables, sempre que estiguin lliures) apareix en una o més vegades en un teorema, llavors es pot substituir aquest terme en una, en totes o algunes de les seves ocurrències amb una variable que no és ja apareix en el teorema, per tot el que precedeix la rellevant des del quantificador existencial.

Exemple:

Mitjançant l'aplicació d'aquesta norma amb l'axioma 1, s'obté∃b:∀a:¬Sa=b.

Regla de simetria

Si r = s és un teorema, aleshores també ho és r = s.

Regla de la transitivitat de la igualtat

Si r = s i s= t són teoremes, llavors també ho és r = t.

Regla per al successor

Si r = t és un teorema, aleshores Sr = St és un teorema.

Regla de l'eliminació per al successor

Si Sr = St és un teorema, aleshores r = t és un teorema.

En la següent regla usant aquesta notació: una fórmula ben formada en el qual la variable està lliure s'abreuja pel símbol X {a}. Però amb el símbol X {SA / A} denota la X mateixa cadena però en què cada aparició d'un ha estat reemplaçat amb Sa. De manera similar, amb X {0/1} denota la cadena inicial en què cada aparició d'un ha estat substituït per 0.

Regla d'inducció

Sigui o una variable X i {u} una fórmula ben formada en el qual no apareix lliure. Si ∀u:<X{u}⊃X{Su/u}> e X{0/u} són ambdós teoremes, llavors ∀ u: X {u} també és un teorema.

Referències

Hofstadter, Douglas R. (1999) [1979], Gödel, Escher, Bach: An Eternal Golden Braid, Basic Books, ISBN 0-465-02656-7, (anglès).