Feeds:
Entradas
Comentarios

Archive for 24 julio 2017

Giuseppe Peano había observado que la adición de números naturales se puede definir recursivamente así:

x + 0 = x

x + Sy = S(x + y)

Otras funciones numéricas \mathbf{N}^{k} \rightarrow \mathbf{N} que se pueden definir con la ayuda de un esquema de recursión (y con la ayuda de 0, S y sustitución) se denominan primitivas recursivas. Gödel usó este concepto para precisar lo que él quería decir con “efectivamente enumerable”. Se dice que un conjunto de números naturales es recursivamente enumerable si consta de todos los f(n) con n\in\mathbf{N}, donde f:\mathbf{N}\rightarrow\mathbf{N} es una función primitiva recursiva.

Giuseppe Peano

Esta noción se puede extender fácilmente a subconjuntos de \mathbf{N}^{k} y, mediante un simple truco llamado aritmetización, a conjuntos de cadenas de palabras en un lenguaje. Así, Gödel pudo afirmar que el conjunto de teoremas de la matemática es recursivamente enumerable y, más recientemente, el lingüista americano Noam Chomsky (1928-) pudo decir que el conjunto de oraciones gramaticales de un lenguaje natural, como el inglés, es recursivamente enumerable.

No es difícil demostrar que todas las funciones primitivas recursivas pueden ser calculadas. Por ejemplo, para calcular x + y cuando x = 3 e y = 2, haciendo uso de la definición recursiva de Peano de x + y y de las definiciones 1 = S0, 2 = S1, etc., se procede de la siguiente manera:

3+2=S2+S1=S(S2+1)=S(S2+S0)

=SS(S2+0)=SSS2=SS3=S4=5.

Pero las funciones recursivas primitivas no son las únicas funciones numéricas que se pueden calcular. Más generales son las funciones recursivas, donde f:N\rightarrow N se dice que es recursiva si su grafo es recursivamente eumerable, es decir, si existen funciones recursivas primitivas u, v:N\rightarrow N tales que, para todos los números naturales x e y, y = f(x) si y sólo si, para un cierto z\in N, x = u (z) y y = v (z).

Todas las funciones recursivas se pueden calcular con lápiz y papel o, aún más primitivamente, moviendo piedrecillas(calculi en latín) de un lugar a otro, usando un conjunto finito de instrucciones, hoy llamado programa. Por el contrario, sólo las funciones recursivas se pueden calcular así, o computar por una máquina teórica introducida por el matemático inglés Alan Turing (1912-1954), o por una computadora moderna, para el caso. La tesis de Church-Turing afirma que la noción informal de calculabilidad es completamente capturada por la noción formal de funciones recursivas y por lo tanto, en teoría, replicable por una máquina.

Alan Turing

Alonzo Church

El teorema de incompletitud de Gödel había demostrado que cualquier sistema matemático formal útil contendría proposiciones indecidibles, proposiciones que no pueden ser probadas ni refutadas. Church y Turing, al tiempo que buscaban una prueba algorítmica (mecánica) para decidir la teoría y, por tanto, eliminar potencialmente los no-teoremas, demostraron independientemente, en 1936, que tal método algorítmico era imposible para la lógica de predicados de primer orden. El teorema Church-Turing de la indecidibilidad, combinado con el resultado relacionado del matemático estadounidense, nacido en Polonia, Alfred Tarski (1902-1983) sobre la indecidibilidad de la verdad, eliminó la posibilidad de que un dispositivo puramente mecánico reemplazara a los matemáticos.

Alfred Tarski

 

 

 

Read Full Post »

En el programa de Hilbert estaba implícita la esperanza de que la noción sintáctica de la demostración captara la noción semántica de la verdad. Kurt Gödel se topó con el sorprendente descubrimiento de que este no era el caso de la teoría de tipos y lenguas relacionadas adecuadas para la aritmética, siempre que se insistan en las siguientes suposiciones:

  1. El conjunto de teoremas (enunciados probables) es efectivamente enumerable, en virtud de la noción de la prueba que es decidible.
  2. El conjunto de afirmaciones verdaderas de la matemática es ω-completo en el siguiente sentido: dada cualquier fórmula φ(x), que contiene una variable libre x de tipo N, la sentencia universal ∀x ε N, φ(x) será verdadera si φ(n) Es verdadera para cada número n.
  3. El lenguaje es consistente.

En realidad, Gödel también hizo una suposición algo más fuerte, que, como el matemático estadounidense John Barkley Rosser más tarde mostró, podía ser reemplazada asumiendo la consistencia. El ingenioso argumento de Gödel se basó en la observación de que las declaraciones sintácticas sobre el lenguaje de la matemática pueden traducirse en declaraciones de la aritmética, por lo tanto, en el lenguaje de la matemática. Fue inspirado en parte por un argumento que supuestamente se remonta a los antiguos griegos y que fue algo como esto: Epiménides dice que todos los cretenses son mentirosos; Epiménides es un cretense; por lo tanto Epiménides es un mentiroso. Bajo los supuestos 1 y 2, Gödel construyó una declaración matemática g que es verdadera pero no demostrable. Si se supone que todos los teoremas son verdaderos, se deduce que ni g ni ¬g es un teorema.

Ningún matemático duda de la suposición 1. Al mirar una supuesta prueba de un teorema, adecuadamente formalizado, es posible para un matemático, o incluso para un ordenador, decir si es una prueba. Al enumerar todas las pruebas en, digamos, orden alfabético, se obtiene una enumeración efectiva de todos los teoremas. Los matemáticos clásicos también aceptan la suposición 2 y, por tanto, de mala gana acuerdan con Gödel que, contrariamente a la expectativa de Hilbert, hay verdaderas declaraciones matemáticas que no son demostrables.

Sin embargo, los intuicionistas moderados podrían sacar una conclusión diferente, porque no están comprometidos con la suposición 2. Para ellos, la verdad de la afirmación universal ∀x ε N, φ(x) sólo puede conocerse si se conoce la verdad de φ(n) para cada número natural n, de manera uniforme. Este no sería el caso, por ejemplo, si la prueba de φ(n) aumenta en dificultad, por lo tanto en longitud, con n. Por lo tanto, los intuicionistas moderados podrían identificar la verdad con la probabilidad y no sentirse molestados por el hecho de que ni g ni ¬g sean verdaderos, ya que en primer lugar no creerían en el principio del tercero excluido.

Los intuicionistas siempre han creído que, para que una declaración sea verdadera, su verdad debe ser cognoscible. Por otra parte, los intuicionistas moderados podrían conceder a los formalistas que decir que una afirmación se sabe que es verdadera es decir que se ha demostrado. Sin embargo, algunos intuicionistas no aceptan el argumento anterior. Al afirmar que la matemática es independiente del lenguaje, los intuicionistas afirmarían que en la demostración metamatemática de Gödel de su teorema de la incompletitud, citar la ω-completitud para establecer la verdad de una declaración universal produce después de todo una prueba uniforme de ésta última.

Gödel se consideraba un platónico, en la medida en que creía en una noción de verdad absoluta. Él tomó por hecho, como hacen muchos matemáticos, que el conjunto de afirmaciones verdaderas es ω-completo. Otros lógicos son más escépticos y quieren reemplazar la noción de verdad por la de la verdad en un modelo. De hecho, el propio Gödel, en su teoría de la integridad, había demostrado que para que un enunciado matemático fuera demostrable es necesario y suficiente que sea cierto en cada modelo. Su teorema de la incompletitud demostró ahora que la verdad en cada modelo ω-completo no es suficiente para la demostración.

Read Full Post »

El descubrimiento de Bertrand Russell de una contradicción oculta en el intento de Friedrich Frege de formalizar la teoría de conjuntos hizo que algunos matemáticos se preguntaran cómo podía asegurarse de que no existían otras contradicciones. El programa de Hilbert, llamado formalismo, debía concentrarse en el lenguaje formal de la matemática y estudiar su sintaxis. En particular, la consistencia de la matemática, que puede ser tomada, por ejemplo, como la afirmación metamatemática de que la afirmación matemática 0 = 1 no es demostrable, debía ser demostrable dentro de la sintaxis de la matemática. Este proyecto de formalización sólo tenía sentido si la sintaxis de la matemática era consistente, pues de lo contrario toda afirmación sintáctica sería demostrable, incluso aquella que afirma la consistencia de la matemática.

Desafortunadamente, una consecuencia del teorema de incompletitud de Gödel es que la consistencia de la matemática puede ser probada solamente en un lenguaje que es más fuerte que el lenguaje de la matemática misma. Sin embargo, el formalismo no está muerto -de hecho, la mayoría de los matemáticos puros son formalistas tácitos- pero el intento ingenuo de probar la consistencia de la matemática en un sistema más débil tuvo que ser abandonado.

Aunque nadie, excepto un intuicionista extremista, negará la importancia del lenguaje de la matemática, la mayoría de los matemáticos son también filosóficos realistas que creen que las palabras de este lenguaje denotan entidades en el mundo real. Siguiendo al matemático suizo Paul Bernays (1888-1977), esta posición también se llama platonismo, ya que Platón creía que las entidades matemáticas realmente existen.

Paul Isaac Bernays

 

Read Full Post »

Older Posts »