Prueba constructiva - Constructive proof

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 la confusión con el concepto más fuerte que sigue, tal prueba constructiva a veces se llama prueba efectiva .

Una prueba constructiva también puede referirse al concepto más fuerte de una prueba que es válida 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 se construyen explícitamente. Esto excluye, en particular, el uso de la ley del medio 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 constructivo matemáticas que en la clásica).

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 demostraciones constructivas definen algoritmos matemáticos certificados : esta idea se explora en la interpretación de Brouwer-Heyting-Kolmogorov de la lógica constructiva , la correspondencia de Curry-Howard entre demostraciones y programas, y sistemas lógicos como el tipo intuicionista de Per Martin-Löf . teoría , y Thierry Coquand y Gérard Huet 's cálculo de las construcciones .

Un ejemplo historico

Hasta finales del siglo XIX, todas las demostraciones matemáticas eran esencialmente constructivas. Las primeras construcciones no constructivas aparecieron con la teoría de conjuntos infinitos de Georg Cantor y la definición formal de números reales .

El primer uso de demostraciones no constructivas para resolver problemas previamente considerados parece ser el teorema de base de Hilbert Nullstellensatz y 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 expresarse de la siguiente manera: si son polinomios en n indeterminados con coeficientes complejos , que no tienen ceros complejos comunes , entonces hay polinomios tales que ${\ Displaystyle f_ {1}, \ ldots, f_ {k}}$${\ Displaystyle g_ {1}, \ ldots, g_ {k}}$

${\ Displaystyle f_ {1} g_ {1} + \ ldots + f_ {k} g_ {k} = 1.}$

Tal teorema de existencia no constructiva fue una sorpresa para los matemáticos de la época que uno de ellos, Paul Gordan , escribió: "esto no es matemática, es teología ".

Veinticinco años después, Grete Hermann proporcionó un algoritmo para la computación que no es una prueba constructiva en el sentido estricto, ya que utilizó el resultado de Hilbert. Demostró que, de existir, se pueden encontrar con grados inferiores a . ${\ Displaystyle g_ {1}, \ ldots, g_ {k},}$${\ Displaystyle g_ {1}, \ ldots, g_ {k}}$${\ Displaystyle 2 ^ {2 ^ {n}}}$

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 ${\ Displaystyle g_ {i}.}$

Ejemplos de

Pruebas no constructivas

Primero, considere el teorema de que hay una infinidad de números primos . La demostración de Euclides es constructiva. Pero una forma común de simplificar la demostración de Euclides postula que, contrariamente a la afirmación del teorema, solo 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 , contrario al postulado original.

Ahora considere el teorema "existen números irracionales y tal que es racional ". Este teorema se puede probar utilizando tanto una prueba constructiva como una prueba no constructiva. ${\ Displaystyle a}$${\ Displaystyle b}$${\ Displaystyle a ^ {b}}$

La siguiente prueba de 1953 de Dov Jarden se ha utilizado ampliamente como ejemplo de prueba no constructiva desde al menos 1970:

CURIOSA
339. Una simple prueba 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 está probada. Si es irracional, prueba nuestra afirmación.      Dov Jarden Jerusalén
${\ Displaystyle {\ sqrt {2}} ^ {\ sqrt {2}}}$${\ Displaystyle ({\ sqrt {2}} ^ {\ sqrt {2}}) ^ {\ sqrt {2}} = 2}$

Con un poco más de detalle:

• Recuerde que es irracional y 2 es racional. Considere el número . O es racional o es irracional. ${\ Displaystyle {\ sqrt {2}}}$ ${\ Displaystyle q = {\ sqrt {2}} ^ {\ sqrt {2}}}$
• Si es racional, entonces el teorema es cierto, con y tanto bienestar . ${\ Displaystyle q}$${\ Displaystyle a}$${\ Displaystyle b}$${\ Displaystyle {\ sqrt {2}}}$
• Si es irracional, entonces el teorema es verdadero, con ser y ser , ya que ${\ Displaystyle q}$${\ Displaystyle a}$${\ Displaystyle {\ sqrt {2}} ^ {\ sqrt {2}}}$${\ Displaystyle b}$${\ Displaystyle {\ sqrt {2}}}$

${\ Displaystyle \ left ({\ sqrt {2}} ^ {\ sqrt {2}} \ right) ^ {\ sqrt {2}} = {\ sqrt {2}} ^ {({\ sqrt {2}} \ cdot {\ sqrt {2}})} = {\ sqrt {2}} ^ {2} = 2.}$

En esencia, esta prueba no es constructiva porque se basa en el enunciado "O q es racional o es irracional", una instancia de la ley del medio excluido , que no es válida dentro de una prueba constructiva. La prueba no constructiva no construye un ejemplo un y b ; simplemente da un número de posibilidades (en este caso, dos posibilidades mutuamente excluyentes) y muestra que uno de ellos, pero no muestra que una sola debe ceder el ejemplo deseado.

Resulta que es irracional debido al teorema de Gelfond-Schneider , pero este hecho es irrelevante para la corrección de la prueba no constructiva. ${\ Displaystyle {\ sqrt {2}} ^ {\ sqrt {2}}}$

Pruebas constructivas

Una prueba constructiva del teorema anterior sobre los poderes irracionales de los irracionales daría un ejemplo real, como:

${\ Displaystyle a = {\ sqrt {2}} \ ,, \ quad b = \ log _ {2} 9 \ ,, \ quad a ^ {b} = 3 \ ,.}$

La raíz cuadrada de 2 es irracional y 3 es racional. también es irracional: si fuera igual a , entonces, por las propiedades de los logaritmos , 9 ⁿ sería igual a 2 ^m , pero el primero es impar y el segundo es par. ${\ Displaystyle \ log _ {2} 9}$${\ Displaystyle m \ over n}$

Un ejemplo más sustancial es el teorema del gráfico menor . Una consecuencia de este teorema es que se puede dibujar un gráfico en el toro si, y solo si, ninguno de sus menores pertenece a un cierto conjunto finito de " menores prohibidos ". Sin embargo, la prueba de la existencia de este conjunto finito no es constructiva y los menores prohibidos no se especifican realmente. Aún se desconocen.

Contraejemplos brouwerianos

En la matemática constructiva , una afirmación puede refutarse dando un contraejemplo , como en la matemática clásica. Sin embargo, también es posible dar un contraejemplo brouweriano para demostrar que la declaración no es constructiva. Este tipo de contraejemplo muestra que el enunciado implica algún principio que se sabe que no es constructivo. Si se puede probar de manera constructiva que un enunciado implica algún principio que no se puede demostrar de manera constructiva, entonces el enunciado en sí mismo no se puede probar de manera constructiva.

Por ejemplo, se puede mostrar que una declaración en particular implica la ley del medio 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 de conjuntos constructiva , ya que el axioma de elección implica la ley del centro excluido en tales sistemas. El campo de la matemática inversa constructiva desarrolla más esta idea al clasificar varios principios en términos de "cuán no constructivos" son, al mostrar que son equivalentes a varios fragmentos de la ley del medio excluido.

Brouwer también proporcionó contraejemplos "débiles". Sin embargo, tales contraejemplos no refutan una afirmación; solo muestran que, en la actualidad, no se conoce ninguna prueba constructiva del enunciado. Un contraejemplo débil comienza tomando algún problema matemático sin resolver, 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:

${\ displaystyle a (n) = {\ begin {cases} (1/2) ^ {n} & {\ mbox {si cada número natural par en el intervalo}} [4, n] {\ mbox {es la suma de dos primos}}, \\ (1/2) ^ {k} & {\ mbox {if}} k {\ mbox {es el número natural menos par en el intervalo}} [4, n] {\ mbox { que no es la suma de dos números primos}} \ end {cases}}}$

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, de manera constructiva. Además, debido a que a es una secuencia de Cauchy con una tasa fija de convergencia, a converge a algún número real α, de acuerdo con el tratamiento habitual de los números reales en matemáticas constructivas.

Varios hechos sobre el número real α pueden probarse de manera constructiva. Sin embargo, con base en el significado diferente 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 muy posible que la conjetura de Goldbach pueda tener una prueba constructiva (como no sabemos en este momento si la tiene), en cuyo caso la declaración citada tendría una prueba constructiva también, aunque una que se desconoce en la actualidad. El principal uso práctico de los contraejemplos débiles es identificar la "dureza" de un problema. Por ejemplo, el contraejemplo que se acaba de mostrar muestra que el enunciado citado es "al menos tan difícil de probar" como la conjetura de Goldbach. Los contraejemplos débiles de este tipo a menudo se relacionan con el principio limitado de omnisciencia .

Ver también

• Constructivismo (filosofía de las matemáticas)
• Errett Bishop - autor del libro "Fundamentos del análisis constructivo".
• Teorema de la existencia § Resultados de la existencia 'pura'
• Pruebas de existencia de algoritmos no constructivos
• Método probabilístico

Referencias

Otras lecturas

enlaces externos

• Contraejemplos débiles de Mark van Atten, Enciclopedia de Filosofía de Stanford