Prueba constructiva

Método de prueba en matemáticas

En matemáticas , una prueba constructiva es un método de prueba que demuestra la existencia de un objeto matemático mediante la creación o el suministro de 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 demuestra la existencia de un tipo particular de objeto sin proporcionar un ejemplo. Para evitar confusiones con el concepto más fuerte que sigue, a este tipo de prueba constructiva a veces se la denomina 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 involucran la existencia de objetos que no están explícitamente construidos. Esto excluye, en particular, el uso de la ley del medio excluido , el axioma de infinito y el axioma de elección , e induce un significado diferente para cierta terminología (por ejemplo, el término "o" tiene un significado más fuerte en matemáticas constructivas que en matemáticas clásicas). ^[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 las matemáticas constructivas, incluido el intuicionismo .

Las pruebas constructivas pueden considerarse como la definición de 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 pruebas y programas, y sistemas lógicos como la teoría de tipos intuicionista de Per Martin-Löf y el cálculo de construcciones de Thierry Coquand y Gérard Huet .

Un ejemplo histórico

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 los números reales .

El primer uso de pruebas no constructivas para resolver problemas considerados previamente parece ser el teorema de la base y el teorema de Nullstellensatz 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 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.}$

Un teorema de existencia tan no constructivo fue una sorpresa tan grande para los matemáticos de aquella época que uno de ellos, Paul Gordan , escribió: "esto no son matemáticas, es teología ". ^[2]

Veinticinco años después, Grete Hermann proporcionó un algoritmo para realizar cálculos que no es una prueba constructiva en sentido estricto, ya que utilizó el resultado de Hilbert. Demostró que, si existen, se pueden encontrar con grados menores que . ^[3] ${\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

Pruebas no constructivas

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, solo hay un número finito de ellos, en cuyo caso hay uno más grande, denotado n . Luego considere el número n ! + 1 (1 + el producto de los primeros n números). O bien 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 que es mayor que n , contrariamente al postulado original.

Consideremos ahora el teorema "existen números irracionales y tales que son racionales ". Este teorema se puede demostrar utilizando tanto una prueba constructiva como una prueba no constructiva. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a^{b}}$

La siguiente prueba de Dov Jarden de 1953 se ha utilizado ampliamente como ejemplo de una prueba no constructiva desde al menos 1970: ^{[4] [5]}

CURIOSA
339. Una prueba sencilla de que una potencia de un número irracional elevada a un exponente irracional puede ser racional. es racional o irracional. Si es racional, nuestra afirmación queda demostrada. Si es irracional, nuestra afirmación queda demostrada.      Dov Jarden Jerusalem
${\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 verdadero, siendo y ambos . ${\displaystyle q}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle {\sqrt {2}}}$
• Si es irracional, entonces el teorema es verdadero, siendo y siendo , 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 la afirmación "o q es racional o es irracional", una instancia 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 da 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 corrección de la prueba no constructiva. ${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$

Pruebas constructivas

Una prueba constructiva del teorema de que una potencia de un número irracional elevada a un exponente irracional puede ser racional da 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 grafo menor . Una consecuencia de este teorema es que se puede dibujar un grafo sobre 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 están realmente especificados. ^[6] Todavía son desconocidos.

Contraejemplos brouwerianos

En matemáticas constructivas , una afirmación puede ser refutada dando un contraejemplo , como en las 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 demuestra que la afirmación implica algún principio que se sabe que no es constructivo. Si se puede demostrar de manera constructiva que la afirmación implica algún principio que no es demostrable de manera constructiva, entonces la afirmación en sí misma no puede ser demostrable de manera constructiva.

Por ejemplo, se puede demostrar que una determinada afirmación implica la ley del medio excluido. Un ejemplo de un contraejemplo brouweriano de este tipo es el teorema de Diaconescu , que demuestra que el axioma de elección completo no es constructivo en sistemas de teoría de conjuntos constructiva , puesto que el axioma de elección implica la ley del medio excluido en tales sistemas. El campo de las matemáticas inversas constructivas desarrolla esta idea aún más 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". ^[8] Sin embargo, estos contraejemplos no refutan una afirmación; sólo muestran que, en la actualidad, no se conoce ninguna prueba constructiva de la afirmación. Un contraejemplo débil comienza tomando algún problema no resuelto de matemáticas, 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]

${\displaystyle a(n)={\begin{cases}(1/2)^{n}&{\mbox{if every even natural number in the interval }}[4,n]{\mbox{ is the sum of two primes}},\\(1/2)^{k}&{\mbox{if }}k{\mbox{ is the least even natural number in the interval }}[4,n]{\mbox{ which is not the sum of two primes}}\end{cases}}}$

Para cada n , el valor de a ( n ) se puede determinar mediante una búsqueda exhaustiva, y por lo tanto 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 las matemáticas constructivas.

Varios hechos sobre el número real α pueden demostrarse de manera constructiva. Sin embargo, en base al diferente significado de las palabras en matemáticas constructivas, si hay una prueba constructiva de que "α = 0 o α ≠ 0", 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 segundo caso). Como no se conoce tal prueba, la afirmación citada tampoco debe tener una prueba constructiva conocida. Sin embargo, es completamente posible que la conjetura de Goldbach pueda tener una prueba constructiva (ya que no sabemos en este momento 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 "dificultad" de un problema. Por ejemplo, el contraejemplo que se acaba de mostrar muestra que la afirmación citada es "al menos tan difícil de demostrar" como la conjetura de Goldbach. Los contraejemplos débiles de este tipo suelen estar relacionados con el principio limitado de omnisciencia .

Véase también

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

Referencias

1. Bridges, Douglas; Palmgren, Erik (2018), "Matemáticas constructivas", en Zalta, Edward N. (ed.), The Stanford Encyclopedia of Philosophy (edición de verano de 2018), Metaphysics Research Lab, Stanford University , consultado el 25 de octubre de 2019
2. McLarty, Colin (15 de abril de 2008). Círculos perturbados: la interacción de las matemáticas y la narrativa — Capítulo 4. Hilbert sobre la teología y sus descontentos El mito del origen de las matemáticas modernas . Doxiadēs, Apostolos K., 1953-, Mazur, Barry. Princeton: Princeton University Press. doi :10.1515/9781400842681.105. ISBN 9781400842681. OCLC  775873004. S2CID  170826113.
3. Hermann, Grete (1926). "Die Frage der endlich vielen Schritte in der Theorie der Polynomideale: Unter Benutzung nachgelassener Sätze von K. Hentzelt". Mathematische Annalen (en alemán). 95 (1): 736–788. doi :10.1007/BF01206635. ISSN  0025-5831. S2CID  115897210.
4. J. Roger Hindley , "The Root-2 Proof as an Example of Non-constructivity", artículo inédito, septiembre de 2014, texto completo Archivado el 23 de octubre de 2014 en Wayback Machine.
5. Dov Jarden, "Una prueba sencilla de que una potencia de un número irracional elevada a un exponente irracional puede ser racional", Curiosa No. 339 en Scripta Mathematica 19 :229 (1953)
6. Fellows, Michael R.; Langston, Michael A. (1 de junio de 1988). "Herramientas no constructivas para demostrar la decidibilidad en tiempo polinomial" (PDF) . Revista de la ACM . 35 (3): 727–739. doi :10.1145/44483.44491. S2CID  16587284.
7. Mandelkern, Mark (1989). "Contraejemplos brouwerianos". Revista de Matemáticas . 62 (1): 3–27. doi :10.2307/2689939. ISSN  0025-570X. JSTOR  2689939.
8. AS Troelstra, Principios del intuicionismo , Lecture Notes in Mathematics 95, 1969, pág. 102
9. Mark van Atten, 2015, "Contraejemplos débiles", Enciclopedia de Matemáticas de Stanford

Lectura adicional

• J. Franklin y A. Daoud (2011) Demostración en matemáticas: una introducción . Kew Books, ISBN 0-646-54509-4 , cap. 4 
• Hardy, GH y Wright, EM (1979) Introducción a la teoría de números (quinta edición). Oxford University Press. ISBN 0-19-853171-0 
• Anne Sjerp Troelstra y Dirk van Dalen (1988) "Constructivismo en matemáticas: Volumen 1" Elsevier Science. ISBN 978-0-444-70506-8 

Enlaces externos

• Contraejemplos débiles de Mark van Atten, Stanford Encyclopedia of Philosophy