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. [1] 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). [2]
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 .
Las demostraciones constructivas pueden verse 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 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 establecerse de la siguiente manera: Si son polinomios en n indeterminados con coeficientes complejos , que no tienen ceros complejos comunes , entonces hay polinomios tal que
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 ". [3]
Veinticinco años después, Grete Hermann proporcionó un algoritmo para la informáticalo cual no es una prueba constructiva en el sentido fuerte, ya que usó el resultado de Hilbert. Ella demostró que, si existen, se pueden encontrar con grados inferiores a . [4]
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
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.
La siguiente prueba de 1953 de Dov Jarden se ha utilizado ampliamente como ejemplo de prueba no constructiva desde al menos 1970: [5] [6]
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 irracionalprueba nuestra afirmación.
Dov Jarden Jerusalén
Con un poco más de detalle:
- Recordar que es irracional y 2 es racional. Considere el número. O es racional o es irracional.
- Si es racional, entonces el teorema es verdadero, con y ambos siendo .
- Si es irracional, entonces el teorema es verdadero, con ser y ser , desde
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.
Como resulta, es irracional debido al teorema de Gelfond-Schneider , pero este hecho es irrelevante para la corrección de la prueba no constructiva.
Pruebas constructivas
Una prueba constructiva del teorema anterior sobre los poderes irracionales de los irracionales daría un ejemplo real, como:
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 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 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. [7] 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. [8] Este tipo de contraejemplo muestra que la declaración 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". [9] Sin embargo, tales contraejemplos no refutan una declaració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: [10]
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 α, según el tratamiento habitual de los números reales en matemáticas constructivas.
Se pueden probar de manera constructiva varios hechos sobre el número real α. Sin embargo, según 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 la actualidad 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
- ^ "El glosario definitivo de jerga matemática superior - prueba constructiva" . Bóveda de matemáticas . 2019-08-01 . Consultado el 25 de octubre de 2019 .
- ^ Bridges, Douglas; Palmgren, Erik (2018), "Constructive Mathematics" , en Zalta, Edward N. (ed.), The Stanford Encyclopedia of Philosophy (verano de 2018 ed.), Metaphysics Research Lab, Universidad de Stanford , consultado el 25 de octubre de 2019
- ^ 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 .
- ^ 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 .
- ^ 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 deoctubre de 2014en la Wayback Machine.
- ^ 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)
- ^ Becarios, Michael R .; Langston, Michael A. (1 de junio de 1988). "Herramientas no constructivas para probar la decidibilidad en tiempo polinomial" (PDF) . Revista de la ACM . 35 (3): 727–739. doi : 10.1145 / 44483.44491 .
- ^ Mandelkern, Mark (1989). "Contraejemplos brouwerianos". Revista de Matemáticas . 62 (1): 3-27. doi : 10.2307 / 2689939 . ISSN 0025-570X . JSTOR 2689939 .
- ^ AS Troelstra, Principios del intuicionismo , Notas de la conferencia en matemáticas 95, 1969, p. 102
- ^ 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 los 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