En matemáticas , una prueba constructiva es un método de prueba que demuestra la existencia de un objeto matemático creando o proporcionando un método para crear el objeto. Esto contrasta con una prueba no constructiva (también conocida como prueba de existencia o teorema de existencia pura ), que prueba la existencia de un tipo particular de objeto sin proporcionar un ejemplo. Para evitar confusión con el concepto más fuerte que sigue, esta prueba constructiva a veces se denomina prueba efectiva .
Una prueba constructiva también puede referirse al concepto más fuerte de prueba que es válido en matemáticas constructivas . El constructivismo es una filosofía matemática que rechaza todos los métodos de prueba que implican la existencia de objetos que no están construidos explícitamente. Esto excluye, en particular, el uso de la ley del tercero excluido , el axioma del infinito y el axioma de elección , e induce un significado diferente para alguna terminología (por ejemplo, el término "o" tiene un significado más fuerte en términos constructivos). matemáticas que en clásica). [1]
Algunas pruebas no constructivas muestran que si una determinada proposición es falsa, se produce una contradicción; en consecuencia la proposición debe ser verdadera ( prueba por contradicción ). Sin embargo, el principio de explosión ( ex falso quodlibet ) ha sido aceptado en algunas variedades de matemáticas constructivas, incluido el intuicionismo .
Se puede considerar que las pruebas constructivas definen algoritmos matemáticos certificados : esta idea se explora en la interpretación de la lógica constructiva de Brouwer-Heyting-Kolmogorov , la correspondencia Curry-Howard entre pruebas y programas, y sistemas lógicos como el tipo intuicionista de Per Martin-Löf. teoría , y el cálculo de construcciones de Thierry Coquand y Gérard Huet .
Hasta finales del siglo XIX, todas las demostraciones matemáticas eran esencialmente constructivas. Las primeras construcciones no constructivas aparecieron con la teoría de los conjuntos infinitos de Georg Cantor , y la definición formal de los números reales .
El primer uso de pruebas no constructivas para resolver problemas previamente considerados parece ser el Nullstellensatz de Hilbert y el teorema de base de Hilbert . Desde un punto de vista filosófico, el primero es especialmente interesante, ya que implica la existencia de un objeto bien especificado.
El Nullstellensatz puede enunciarse de la siguiente manera: Si hay polinomios en n indeterminados con coeficientes complejos , que no tienen ceros complejos comunes , entonces existen polinomios tales que
Un teorema de existencia tan no constructivo fue tal sorpresa para los matemáticos de aquella época que uno de ellos, Paul Gordan , escribió: "esto no es matemática, es teología ". [2]
Veinticinco años después, Grete Hermann proporcionó un algoritmo para computación que no es una prueba constructiva en el sentido estricto, ya que utilizó el resultado de Hilbert. Demostró que, si existen, se pueden encontrar con grados inferiores a . [3]
Esto proporciona un algoritmo, ya que el problema se reduce a resolver un sistema de ecuaciones lineales , considerando como incógnitas el número finito de coeficientes de la
Consideremos primero el teorema de que hay una infinidad de números primos . La prueba de Euclides es constructiva. Pero una forma común de simplificar la prueba de Euclides postula que, contrariamente a la afirmación del teorema, sólo hay un número finito de ellos, en cuyo caso hay uno más grande, denotado n . Entonces considere el número n ! + 1 (1 + el producto de los primeros n números). O este número es primo o todos sus factores primos son mayores que n . Sin establecer un número primo específico, esto prueba que existe uno mayor que n , contrariamente al postulado original.
Consideremos ahora el teorema "existen números irracionales y aquellos que son racionales ". Este teorema se puede demostrar utilizando tanto una prueba constructiva como una prueba no constructiva.
La siguiente prueba de 1953 de Dov Jarden se ha utilizado ampliamente como ejemplo de prueba no constructiva desde al menos 1970: [4] [5]
CURIOSA
339. Una prueba sencilla de que una potencia de un número irracional a un exponente irracional puede ser racional. es racional o irracional. Si es racional, nuestra afirmación queda probada. Si es irracional, lo prueba nuestra afirmación. Dov Jardín Jerusalén
Con un poco más de detalle:
En esencia, esta prueba no es constructiva porque se basa en la afirmación "O q es racional o es irracional", un ejemplo de la ley del tercero excluido , que no es válida dentro de una prueba constructiva. La prueba no constructiva no construye un ejemplo a y b ; simplemente ofrece una serie de posibilidades (en este caso, dos posibilidades mutuamente excluyentes) y muestra que una de ellas (pero no muestra cuál ) debe producir el ejemplo deseado.
Resulta que es irracional debido al teorema de Gelfond-Schneider , pero este hecho es irrelevante para la exactitud de la demostración no constructiva.
Una prueba constructiva del teorema de que una potencia de un número irracional a un exponente irracional puede ser racional ofrece un ejemplo real, como por ejemplo:
La raíz cuadrada de 2 es irracional y 3 es racional. también es irracional: si fuera igual a , entonces, según las propiedades de los logaritmos , 9 n sería igual a 2 m , pero el primero es impar y el segundo es par.
Un ejemplo más sustancial es el teorema menor del grafo . Una consecuencia de este teorema es que se puede dibujar un grafo sobre el toroide si, y sólo si, ninguno de sus menores pertenece a un determinado conjunto finito de " menores prohibidos ". Sin embargo, la prueba de la existencia de este conjunto finito no es constructiva y en realidad no se especifican los menores prohibidos. [6] Aún son desconocidos.
En matemáticas constructivas , una afirmación puede ser refutada dando un contraejemplo , como en matemáticas clásicas. Sin embargo, también es posible dar un contraejemplo brouweriano para demostrar que la afirmación no es constructiva. [7] Este tipo de contraejemplo muestra que la afirmación implica algún principio que se sabe que no es constructivo. Si se puede demostrar constructivamente que el enunciado implica algún principio que no es demostrable constructivamente, entonces el enunciado en sí no puede ser demostrable constructivamente.
Por ejemplo, se puede demostrar que un enunciado particular implica la ley del tercero excluido. Un ejemplo de un contraejemplo brouweriano de este tipo es el teorema de Diaconescu , que muestra que el axioma completo de elección no es constructivo en sistemas de teoría constructiva de conjuntos , ya que el axioma de elección implica la ley del tercero excluido en tales sistemas. El campo de las matemáticas inversas constructivas desarrolla aún más esta idea al clasificar varios principios en términos de "cuán no constructivos" son, mostrando que son equivalentes a varios fragmentos de la ley del tercero excluido.
Brouwer también proporcionó contraejemplos "débiles". [8] Sin embargo, tales contraejemplos no refutan una afirmación; sólo demuestran que, por el momento, no se conoce ninguna prueba constructiva de la afirmación. Un contraejemplo débil comienza tomando algún problema matemático no resuelto, como la conjetura de Goldbach , que pregunta si todo número natural par mayor que 4 es la suma de dos primos. Defina una secuencia a ( n ) de números racionales de la siguiente manera: [9]
Para cada n , el valor de a ( n ) se puede determinar mediante una búsqueda exhaustiva, por lo que a es una secuencia bien definida, constructivamente. Además, debido a que a es una secuencia de Cauchy con una tasa de convergencia fija, a converge a algún número real α, de acuerdo con el tratamiento habitual de los números reales en matemática constructiva.
Se pueden demostrar constructivamente varios hechos sobre el número real α. Sin embargo, basándose en el diferente significado de las palabras en matemáticas constructivas, si hay una prueba constructiva de que "α = 0 o α ≠ 0", entonces esto significaría que hay una prueba constructiva de la conjetura de Goldbach (en el primer caso) o una prueba constructiva de que la conjetura de Goldbach es falsa (en el último caso). Debido a que no se conoce tal prueba, la declaración citada tampoco debe tener una prueba constructiva conocida. Sin embargo, es completamente posible que la conjetura de Goldbach pueda tener una prueba constructiva (y en este momento no sabemos si la tiene), en cuyo caso la afirmación citada también tendría una prueba constructiva, aunque una que se desconoce en este momento. El principal uso práctico de los contraejemplos débiles es identificar la "dureza" de un problema. Por ejemplo, el contraejemplo que acabamos de mostrar muestra que la afirmación citada es "al menos tan difícil de probar" como la conjetura de Goldbach. Los contraejemplos débiles de este tipo suelen estar relacionados con el principio limitado de omnisciencia .