Hispanopedia Wiki
Articulo de referencia

Prueba constructiva

En matemáticas , una demostración constructiva es un método que prueba la existencia de un objeto matemático creándolo o proporcionando un método para crearlo. Esto contrasta co...

Hispanopedia WikiContenido en espanolLectura gratuita

En matemáticas , una demostración constructiva es un método que prueba la existencia de un objeto matemático creándolo o proporcionando un método para crearlo. Esto contrasta con una demostración 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 confusiones con el concepto más general que se menciona a continuación, a este tipo de demostración constructiva se la denomina a veces demostración efectiva .

Una demostración constructiva también puede referirse al concepto más fuerte de una demostración válida en matemáticas constructivas . El constructivismo es una filosofía matemática que rechaza todos los métodos de demostración que implican la existencia de objetos que no se construyen explícitamente. Esto excluye, en particular, el uso del principio del tercero excluido , el axioma del infinito y el axioma de elección . El constructivismo también 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 demostraciones no constructivas muestran que si una proposición es falsa, se produce una contradicción; por consiguiente, la proposición debe ser verdadera ( demostración por contradicción ). Sin embargo, el principio de explosión ( ex falso quodlibet ) ha sido aceptado en algunas variantes de las matemáticas constructivas, incluido el intuicionismo .

Las demostraciones 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 demostraciones 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 demostraciones no constructivas para resolver problemas previamente considerados parece ser el Nullstellensatz de Hilbert y el teorema de la base de Hilbert . Desde un punto de vista filosófico, el primero es especialmente interesante, ya que implica la existencia de un objeto bien definido.

El Nullstellensatz puede enunciarse de la siguiente manera: SiF1,…,Fk{\displaystyle f_{1},\ldots ,f_{k}}son polinomios en n indeterminadas con coeficientes complejos , que no tienen raíces complejas comunes , entonces hay polinomiosgramo1,…,gramok{\displaystyle g_{1},\ldots ,g_{k}}de tal manera que

F1gramo1+…+Fkgramok=1.{\displaystyle f_{1}g_{1}+\ldots +f_{k}g_{k}=1.}

Un teorema de existencia no constructivo como este fue una sorpresa tan grande para los matemáticos de la época que uno de ellos, Paul Gordon , escribió: "Esto no es matemáticas, es teología ". [ 2 ]

Veinticinco años después, Grete Hermann proporcionó un algoritmo para la computación.gramo1,…,gramok,{\displaystyle g_{1},\ldots ,g_{k},}lo cual no es una prueba constructiva en el sentido estricto, ya que utilizó el resultado de Hilbert. Ella demostró que, sigramo1,…,gramok{\displaystyle g_{1},\ldots ,g_{k}}existen, se pueden encontrar con grados menores que 22norte{\displaystyle 2^{2^{n}}}. [ 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 lagramoi.{\displaystyle g_{i}.}

Ejemplos

Pruebas no constructivas

Consideremos primero el teorema que afirma que existen infinitos números primos . La demostración de Euclides es constructiva. Sin embargo, una forma común de simplificar la demostración de Euclides postula que, contrariamente a lo que afirma el teorema, solo existe un número finito de ellos, en cuyo caso hay uno mayor, denotado por n . Consideremos entonces el número n ! + 1 (1 + el producto de los primeros n números). Este número es primo, o bien todos sus factores primos son mayores que n . Sin establecer un número primo específico, esto demuestra que existe uno mayor que n , contrariamente al postulado original.

Ahora consideremos el teorema "existen números irracionales ".a{\displaystyle a}yb{\displaystyle b}de tal manera queab{\displaystyle a^{b}}es racional ." Este teorema se puede demostrar utilizando tanto una demostración constructiva como una demostración no constructiva.

La siguiente demostración de 1953 de Dov Jarden se ha utilizado ampliamente como ejemplo de una demostración 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.22{\displaystyle {\sqrt {2}}^{\sqrt {2}}}es racional o irracional. Si es racional, nuestra afirmación queda demostrada. Si es irracional,(22)2=2{\displaystyle ({\sqrt {2}}^{\sqrt {2}})^{\sqrt {2}}=2}Esto demuestra nuestra afirmación. Dov Jarden Jerusalén           

Con un poco más de detalle:

  • Recuerda que2{\displaystyle {\sqrt {2}}}es irracional y 2 es racional. Consideremos el númeroq=22{\displaystyle q={\sqrt {2}}^{\sqrt {2}}}O es racional o es irracional.
  • Siq{\displaystyle q}es racional, entonces el teorema es verdadero, cona{\displaystyle a}yb{\displaystyle b}ambos siendo2{\displaystyle {\sqrt {2}}}.
  • Siq{\displaystyle q}es irracional, entonces el teorema es verdadero, cona{\displaystyle a}ser22{\displaystyle {\sqrt {2}}^{\sqrt {2}}}yb{\displaystyle b}ser2{\displaystyle {\sqrt {2}}}, desde
(22)2=2(2⋅2)=22=2.{\displaystyle \left({\sqrt {2}}^{\sqrt {2}}\right)^{\sqrt {2}}={\sqrt {2}}^{({\sqrt {2}}\cdot {\sqrt {2}})}={\sqrt {2}}^{2}=2.}

En esencia, esta demostración no es constructiva porque se basa en la afirmación "O q es racional o es irracional" , un ejemplo del principio del tercero excluido , que no es válido en una demostración constructiva. La demostración no constructiva no construye un ejemplo a y b ; simplemente presenta varias posibilidades (en este caso, dos mutuamente excluyentes) y muestra que una de ellas —pero no especifica cuál— debe dar como resultado el ejemplo deseado.

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

Pruebas constructivas

Una demostración constructiva del teorema que establece que una potencia de un número irracional elevada a un exponente irracional puede ser racional proporciona un ejemplo real, como por ejemplo:

a=2,b=registro2⁡9,ab=3.{\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.registro2⁡9{\displaystyle \log _{2}9}también es irracional: si fuera igual ametronorte{\displaystyle m \over n}, 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 menor de grafos . Una consecuencia de este teorema es que un grafo puede dibujarse en el toro si, y solo si, ninguno de sus menores pertenece a un cierto conjunto finito de " menores prohibidos ". Sin embargo, la demostración de la existencia de este conjunto finito no es constructiva, y los menores prohibidos no están realmente especificados. [ 6 ] Todavía se desconocen.

Contraejemplos brouwerianos

En matemáticas constructivas , una afirmación puede refutarse mediante un contraejemplo , al igual que 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 la afirmación implica algún principio que no es demostrable constructivamente, entonces la afirmación en sí misma no puede ser demostrable constructivamente.

Por ejemplo, se puede demostrar que una afirmación particular implica la ley del tercero excluido. Un ejemplo de 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 , ya que el axioma de elección implica la ley del tercero excluido en dichos sistemas. El campo de las matemáticas inversas constructivas desarrolla aún más esta idea clasificando diversos principios en función de su grado de no constructividad, demostrando que son equivalentes a diversos fragmentos de la ley del tercero excluido.

Brouwer también proporcionó contraejemplos "débiles". [ 8 ] Sin embargo, tales contraejemplos no refutan una afirmación; solo muestran que, en la actualidad, no se conoce ninguna prueba constructiva de la afirmación. 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. Definimos una sucesión a ( n ) de números racionales de la siguiente manera: [ 9 ]

a(norte)={(1/2)nortesi cada número natural par en el intervalo [4,norte] es la suma de dos números primos,(1/2)ksi k es el menor número natural par en el intervalo [4,norte] que no es la suma de dos números primos{\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 búsqueda exhaustiva, por lo que a es una sucesión bien definida, desde un punto de vista constructivo. Además, dado que a es una sucesión de Cauchy con una tasa de convergencia fija, a converge a algún número real α , según el tratamiento habitual de los números reales en matemáticas constructivas.

Se pueden demostrar constructivamente varios hechos sobre el número real α . Sin embargo, debido a los diferentes significados de los términos en matemáticas constructivas, si existe una demostración constructiva de que " α = 0 o α ≠ 0", esto implicaría una demostración constructiva de la conjetura de Goldbach (en el primer caso) o una demostración constructiva de que la conjetura de Goldbach es falsa (en el segundo caso). Dado que no se conoce tal demostración, la afirmación citada tampoco debe tener una demostración constructiva conocida. No obstante, es totalmente posible que la conjetura de Goldbach tenga una demostración constructiva (ya que actualmente desconocemos si la tiene), en cuyo caso la afirmación citada también tendría una demostración constructiva, aunque desconocida por el 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 demuestra 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

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, Universidad de Stanford , consultado el 25 de octubre de 2019.
  2. ↑ McLarty, Colin (15 de abril de 2008). Círculos perturbados: la interacción entre matemáticas y 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. , 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 , "La prueba de raíz cuadrada de 2 como ejemplo de no constructividad", 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. (1988-06-01). "Herramientas no constructivas para demostrar la decidibilidad en tiempo polinomial" (PDF) . Journal of the ACM . 35 (3): 727– 739. doi : 10.1145/44483.44491 . S2CID 16587284 . 
  7. ↑ Mandelkern, Mark (1989). "Contraejemplos brouwerianos". Mathematics Magazine . 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

Lecturas adicionales

  • Contraejemplos débiles, por Mark van Atten, Enciclopedia de Filosofía de Stanford.
Lecturas relacionadas
6 articulos
MatemáticasMatemáticasLas matemáticas son un campo de estudio que descubre y organiza métodos, teorías y teoremas que se desarrollan y prueban para las necesidades de la...Prueba matemáticaPrueba matemáticaP. Oxy. 29 , uno de los fragmentos más antiguos que se conservan de los Elementos de Euclides , un libro de texto utilizado durante milenios para e...Objeto matemáticoObjeto matemáticoUn teseracto o hipercubo de cuatro dimensiones es un ejemplo de objeto matemático. Un objeto matemático es un concepto abstracto que surge en matem...Teorema de existenciaTeorema de existenciaEn matemáticas , un teorema de existencia es un teorema que afirma la existencia de un determinado objeto. [1] Puede ser un enunciado que comience ...{\displaystyle \forall x,y,z,\ldots \in \mathbb {N} :p\vee \neg p}Constructivismo (filosofía de las matemáticas)En filosofía de las matemáticas , el constructivismo afirma que es necesario encontrar (o «construir») un ejemplo específico de un objeto matemátic...{\displaystyle \forall x,y,z,\ldots \in \mathbb {N} :p\vee \neg p}Constructivismo (filosofía de las matemáticas)En filosofía de las matemáticas , el constructivismo afirma que es necesario encontrar (o «construir») un ejemplo específico de un objeto matemátic...