[escepticos] cuantificadores

["Miguel A. Lerma" <mlerma@...>]

 > ...[suprimido] sustituyase *disyunción * por conjuncion y por otra parte
 > ponme un contraejemplo en el que un cuantificador no es una generalización
 > de una conectiva.

La existencia de sistemas formales consistentes que no son 
omega-consistentes es una buena prueba de hasta que punto 
cuantificadores y conectivas son conceptos diferentes. 

De un sistema formal se dice que es consistente si en el no es 
posible deducir contradicciones, es decir, proposiciones de la 
forma "A y no A".  De un sistema formal se dice que es omega-
consistente si no contiene un predicado numerico de la forma P(n) 
tal que:

1. Todas las formulas P(0), P(1), P(2),... son deducibles. 

2. La formula "no para todo n, P(n)" es tambien deducible. 

Es decir, en un sistema que no es omega-consistente, a pesar de 
verificarse P(n) para cada n=0,1,2,..., la formula que afirma 
lo contrario seria deducible. Esto no es una contradiccion, 
porque no hay ninguna regla de inferencia logica (en la logica 
de predicados de primer orden) que permita pasar de una coleccion 
infinita de formulas de la forma P(0), P(1), P(2),..., a la 
correspondiente formula "para todo n, P(n)".

Un ejemplo "natural" de sistema formal consistente que no es 
omega-consistente es la Aritmetica de Peano (AP) con la negacion 
de la sentencia de Paris-Harrington (PH). Debido al teorema 
de incompletitud de Godel es imposible demostrar la consistencia 
de la aritmetica en terminos puramente aritmeticos, pero si 
es posible hacerlo con el auxilio de herramientas extra-aritmeticas, 
como la teoria de ordinales (Gentzen, 1936). Por otro lado, 
la sentencia de Paris-Harrington es un enunciado de la forma 
PH = "para todo n,k,r, existe un m tal que H(n,k,r,m)" donde 
H(n,k,r,m) es cierta propiedad sobre coloracion de grafos 
estudiada en la teoria de Ramsey (v. Graham, Rothschild, 
Spencer: "Ramsey Theory").  Usando teoria de conjuntos
es posible probar PH, por lo cual la sentencia P(n,k,r) = 
"existe m tal que H(n,k,r,m)" es en efecto cierta cualesquiera 
que sean los numeros naturales n,k,r. Mas aun, para n,k,r dados, 
es posible demostrar P(n,k,r) en AP, porque H(n,k,r,m) es una 
afirmacion finitista sobre grafos que se puede comprobar en un 
numero finito de pasos. Sin embargo sucede que PH es una proposicion 
indecidible en AP (teorema de Paris-Harrington) - en AP no es posible 
fundir las distintas pruebas de P(n,k,r) para cada n,k,r dados 
en una unica prueba que valga para todo n,k,r. Por lo tanto
ni PH ni su negacion son demostrables en AP. En consecuencia 
podemos a~nadir la negacion de PH a AP, y obtener el sistema 
formal AP + no PH, que sera consistente, pero no omega-consistente.

Si la sentencia de Paris-Harrington parece un poco retorcida, 
es posible sustituirla por otras, como la del teorema de Goodstein. 
El libro de Roger Penrose: "The Large, The Small and the Human Mind",
el cual por cierto defiende numerosas tesis con las que discrepo, 
contiene sin embargo una clara exposicion del teorema de Goodstein 
en su apendice numero 1. La propiedad alli involucrada es puramente 
numerica y de la forma P(n) = cierta serie de transformaciones 
realizadas comenzando con el numero 'n' termina en un numero 
finito de pasos. Para cada n dado es posible comprobar que P(n) 
es en efecto cierta, pero la proposicion "para todo n, P(n)"
es indemostrable en AP. Por lo tanto, AP + "no para todo n, P(n)"
constituye otro ejemplo simple de sistema consistente que no es 
omega-consistente.


Miguel A. Lerma