En primer lugar necesitamos una sucesión infinita de signos a los que llamaremos variables:
\( x_0, x_1, x_2,\ldots \)
Pedimos que sea infinita porque un matemático, después de haber llenado 20 pizarras con una demostración, siempre tiene que tener derecho a escribir una línea más en la que aparezca una variable nueva que no haya aparecido hasta entonces. Un matemático nunca usará más de una cantidad finita de variables, pero siempre puede ir añadiendo más según le vaya haciendo falta.
Poniéndolo de ese modo, la verdad es que las pizarras están hechas de átomos, y ningún matemático puede escribir más variables que el número de átomos del Universo.
Si el Universo fuese finito en número de átomos (hasta ahora sólo hay evidencia empírica que apoye la finitud),
basta considerar N variables, con N igual al número de partículas del Universo.
La cuestión es si el Teorema de Godel depende o no del hecho de disponer de una cantidad fija N de variables.
Es decir, si para poder probarlo hacen falta infinitas variables.
No lo recuerdo ahora, pero me parece que no, siempre que haya un número de variables bastante grande como para expresar las sentencias de Godel.
Además de las variables necesitamos dos conectores lógicos \( \lnot \) y \( \rightarrow \) y un cuantificador universal \( \forall \).
Se puede ser aún más económico, usando un único signo para representar operaciones tipo NAND o NOR.
Por último, necesitaremos dos signos que llamaremos relatores: \( = \) y \( \in \).
En este caso se puede pensar en hacer un poco de economía también,
aunque de una manera poco ortodoxa, introduciendo un símbolo \( \underline\in \),
con el sentido de: "pertenece o es igual a".
De modo que si \( X \underline\in Y \) y \( Y \underline\in X \) entonces \( X= Y \).
Este deseo de ahorrar en signos seguramente repercutirá con costos en alguna otra parte.
En resumen, los signos del lenguaje de la teoría de conjuntos son
\( \begin{array}{ccccccccc}
\lnot&\rightarrow&\forall&=&\in&x_0&x_1&x_2&\cdots
\end{array}
\)
y ninguno más.
\( \begin{array}{ccccccccc}
\bar\vee&\forall&\underline\in&x_0&x_1&x_2&\cdots& x_N
\end{array}
\)
Adoptamos el convenio de que los relatores van delante de las variables,
Sabio convenio.
No sólo por el teorema "fundamental de la aritmética (de fórmulas)" que enunciás luego,
sino que también es más simple el trabajo de una computadora al reconocer fórmulas de un tipo u otro,
al evitarse todo el trabajo de analizar paréntesis bien nivelados.
Ahora definimos una sucesión generadora de fórmulas como una sucesión finita de cadenas de signos, digamos \( \alpha_1,\ldots, \alpha_n \), con la propiedad de que cada término de la sucesión esté en uno de los casos siguientes:
- Sea una fórmula atómica.
- Sea de la forma \( \lnot\alpha \), donde \( \alpha \) es una cadena previa en la sucesión.
- Sea de la forma \( \rightarrow \alpha\beta \), donde \( \alpha \) y \( \beta \) son cadenas previas en la sucesión.
En la práctica, en lugar de \( \rightarrow\alpha\beta \) escribiremos \( \alpha\rightarrow \beta \).
- Sea de la forma \( \forall x \alpha \), donde \( x \) es una variable y \( \alpha \) es una cadena previa en la sucesión.
Usando NOR, se acorta la lista anterior en un ítem,
lo cual presumo que también reducirá la complejidad al programar un reconocer de fórmulas.
Podemos pensar que la notación de "alto nivel" es como un lenguaje de programación (tipo C o Java, etc.) mientras que la notación de "bajo nivel" es el lenguaje máquina que, en último extremo, no es más que una sucesión de ceros y unos, que es lo que realmente se guarda en la memoria del ordenador. Cualquier afirmación de un lenguaje de programación sólo es aceptable en la medida en que el ordenador sepa transformarla en instrucciones de lenguaje máquina, que es lo único que realmente tiene sentido para él y sabe ejecutar. Del mismo modo, somos libres de nombrar a las fórmulas con los convenios que juzguemos convenientes siempre y cuando esté claro en todo momento a qué cadena de signos estamos haciendo referencia con nuestros criterios de notación.
Aquí se habla de un "ordenador" como algo capaz de interpretar el lenguaje de máquina.
Ocurre que el lenguaje de máquina es, simplemente, un lenguaje como cualquier otro.
Lo que hace distintivo a la máquina es su "capacidad de ejecución de tareas".
Aunque en el contexto de lenguajes formales matemáticos se introduce la semántica aparte del lenguaje,
en la especificación del lenguaje C, por ejemplo, no se hace alusión alguna al lenguaje de máquina,
sino al "comportamiento esperado" en un entorno de ejecución determinado.
O sea que si una computadora pudiera, de alguna forma, "leer C", sin pasar por un lenguaje de máquina intermedio, el mismo C sería el lenguaje de esa computadora, y así sería de "bajo nivel".
En realidad, lo que me llama la atención acá es el hecho de que el "lenguaje C" no sólo se especifica en términos sintácticos, sino también en términos de una máquina abstracta subyacente junto con los lineamientos esperados del comportamiento observable de un programa. Por ejemplo, se describe en la especificación del lenguaje cómo ha de ser la representación de datos de tipo entero sin signo en forma interna en la computadora.
En otro lenguaje de programación cualquiera, dicha representación interna de los enteros no tendría por qué especificarse, y los números representarse internamente con un criterio cualquiera.
