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 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 .

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 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 ${\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 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] ${\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, 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. ${\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: ^{[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
${\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 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", 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. ${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$

Pruebas constructivas

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:

${\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, según 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 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.

Contraejemplos brouwerianos

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]

${\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, 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 .

Ver 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. Puentes, Douglas; Palmgren, Erik (2018), "Constructive Mathematics", en Zalta, Edward N. (ed.), The Stanford Encyclopedia of Philosophy (edición de verano de 2018), Metaphysics Research Lab, Universidad de Stanford , 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: Prensa de la Universidad de Princeton. 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 simple de que una potencia de un número irracional a un exponente irracional puede ser racional", Curiosa No. 339 en Scripta Mathematica 19 :229 (1953)
6. Becarios, 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 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. 102
9. Mark van Atten, 2015, "Contraejemplos débiles", Enciclopedia de Matemáticas de Stanford

Otras lecturas

• J. Franklin y A. Daoud (2011) Prueba en matemáticas: una introducción . Libros de Kew, 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). Prensa de la Universidad de Oxford. 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, Enciclopedia de Filosofía de Stanford