Prueba no constructiva

Prueba no constructiva ( prueba ineficiente ): una clase de pruebas matemáticas que prueban solo la existencia en un conjunto dado (generalmente infinito) de un elemento que satisface las propiedades dadas, pero no proporciona ninguna información sobre las otras propiedades del elemento, es decir, no permite ni presentarlo ni describirlo aproximadamente. Las pruebas que prueban la existencia de un elemento presentando una forma de obtener ese elemento se denominan constructivas .

Si se prueba una fórmula en la demostración en la que una de las cantidades es una constante, pero su valor no se puede restaurar, entonces este número se llama constante ineficaz .

Esta noción no debe confundirse con el caso en que una constante (u otro objeto de interés) es simplemente muy difícil de expresar o queda fuera de las expectativas razonables. Por ejemplo, la demostración en la que aparece el número de Graham es constructiva porque el número de Graham, aunque es muy grande, puede describirse específicamente.

La naturaleza de las pruebas no constructivas

Las demostraciones no constructivas, por regla general, surgen cuando se utilizan algunas afirmaciones y técnicas típicas en el curso de la demostración, que no son constructivas en sí mismas. A menudo, las pruebas no constructivas se llevan a cabo por contradicción .

Principio de Dirichlet

Muchas de estas demostraciones se basan en diversas formas y generalizaciones del principio de Dirichlet. Por sí mismo, este principio

Si los elementos se encuentran en las celdas, entonces hay una celda con al menos dos elementos $n+1$ $norte$

afirma existencia, pero no permite encontrar el objeto deseado.

Este grupo también incluye la aplicación de la desigualdad de Markov y las desigualdades resultantes para sumas ordinarias. Por ejemplo, si se sabe que la suma es lo suficientemente grande y los elementos en ella están acotados por arriba ( ), entonces se puede demostrar que hay muchos elementos cuyo valor es relativamente grande y cercano a . Este "muchos" significa algún conjunto de elementos, y este , si él o sus elementos se usan más en la prueba, hará que la prueba no sea constructiva, ya que es imposible saber nada al respecto excepto que existe. $\sum \limits _{i=1}^{n}{a_{i}}$ $a_{i}<M$ $METRO$ $A$ $A$

Consideraciones similares al principio de Dirichlet subyacen en la base aritmética del método probabilístico , donde casi todas las pruebas resultan ser no constructivas.

También se puede utilizar el enunciado inverso del principio de Dirichlet para conjuntos infinitos:

Si hay un número finito de conejos en un número finito de cajas, entonces cada caja contiene un número finito de conejos.

Aquí no surge la afirmación de existencia, pero surgirá si, por ejemplo, en lugar de cajas discretas, consideramos un segmento y los valores de una función sobre él. Si converge, entonces converge en casi todas partes , es decir, el conjunto de puntos donde no converge tiene medida cero. Pero no podemos decir nada sobre este conjunto, lo que significa que no podemos decir nada sobre los puntos donde converge la serie. Hemos demostrado que la serie converge en casi todas partes, pero no está claro dónde exactamente. Aquí es donde radica la falta de construcción. ${\ estilo de visualización (0; 1)}$ $\int \limits _{0}^{1}\left({\sum \limits _{i=1}^{\infty}{f_{i}(x)))\right)dx$ ${\displaystyle \sum \limits _{i=1}^{\infty}{f_{i}(x)))$

Establecer diferencia de tamaño

Si , entonces . $|A|<|B|$ ${\ estilo de visualización \ existe x \ en B: \ x \ no \ en A}$

Si reformulamos esto en términos del principio de Dirichlet, obtenemos lo siguiente:

si algunos de los conejos están en una de las jaulas, pero hay como máximo un conejo en cada jaula, entonces al menos un conejo no está en ninguna jaula. $n+1$ $norte$

En el ejemplo descrito anteriormente con la integral de serie, solo se usó esta técnica, pero debe notarse que en esta técnica no importa si los conjuntos también eran constructivos antes. Incluso si estuvieran determinados de forma única, la existencia del elemento se demostraba de forma no constructiva (dentro del conjunto ). $A$ $B$ $X$ $B$

Uso de la existencia como requisito previo

La mayoría de los teoremas matemáticos se formulan de acuerdo con el principio “Si […], entonces […]”. Si la primera parte de esta oración (premisa) contiene algunas condiciones relacionadas solo con la existencia de elementos con ciertas propiedades, entonces la prueba de tal afirmación puede ser constructiva solo en el sentido de indicar claramente la dependencia del objeto deseado (la existencia del que se prueba) del objeto, cuya existencia se supone. Sin embargo, el carácter constructivo de la prueba en este sentido todavía no garantiza el carácter constructivo de los enunciados más amplios para cuya prueba se utilizará; para garantizar su carácter constructivo, también es necesario garantizar el carácter constructivo de la prueba de la propiedad de existencia asumida aquí.

Por ejemplo, probemos algún enunciado para cualquier función continua y algún punto (tal que ). Por definición de continuidad, . Es fácil deducir de esto que . La prueba de esto puede considerarse constructiva, ya que podemos evaluar en términos de dependencia . Sin embargo, si luego usamos el corolario probado para alguna función , sobre la cual sabemos que es continua, pero no conocemos una dependencia clara (es decir, la continuidad se prueba de manera no constructiva), entonces obtendremos una no- prueba constructiva, ya que no podemos restaurar y . $F$ $x_{0}$ ${\ estilo de visualización f (x_ {0})> 0}$ $\forall \varepsilon >0\existe \delta =\delta (\varepsilon)>0:\forall x:|x-x_{0}|<\delta \Rightarrow |f(x)-f(x_{ 0})|<\varepsilon$ $\existe \mu >0:\int \limits _{x_{0}}^{x_{0}+\mu }f(x)dx\leq 1.001\mu f(x)$ $\mu$ ${\ estilo de visualización \ delta (\ varepsilon)}$ $F$ ${\ estilo de visualización \ delta (\ varepsilon)}$ $F$ $\mu$

Ejemplos de pruebas no constructivas

Teoría de la computabilidad

La existencia de un conjunto no computable es un ejemplo clásico de prueba no constructiva en términos de la diferencia en los tamaños de los conjuntos.

La formalización del concepto de algoritmo en un momento dio lugar a la pregunta: ¿existe un conjunto de números naturales para los que no existe un algoritmo (más estrictamente, una máquina de Turing ) que verifique que un número arbitrario pertenezca a este conjunto?

Según el teorema de Cantor , la cardinalidad del conjunto de todos los subconjuntos de números naturales es igual al continuo . Dado que cualquier máquina de Turing está dada por un número finito de símbolos, el conjunto de todas las máquinas de Turing es contable .

Como el continuo es mayor que un conjunto contable, y cada algoritmo corresponde a un determinado conjunto computable, entonces, además de un determinado conjunto contable de funciones, otras funciones resultan no computables. Sin embargo, sobre la base de estos argumentos, no se puede decir nada sobre cómo están dispuestos, por lo que tal prueba no es constructiva.

Cabe señalar que ninguna prueba no constructiva cancela la posibilidad de otra prueba constructiva . En particular, todavía se conocen algunos ejemplos de conjuntos y funciones no computables (así como problemas algorítmicamente indecidibles que pueden reducirse a ellos), ver:

Geometría de los números

Sea un cuerpo cerrado convexo de volumen , simétrico con respecto al origen de coordenadas . Si consideramos la función ${\displaystyle A\subconjunto {\mathbb {R} }^{n))$ ${\displaystyle V(A)>2^{n))$

f(x_{1},\dots,x_{n})=\#\left\lbrace {(c_{1},\dots,c_{n})\in {\mathbb {Z}_{ n}}:(2c_{1}+x_{1},\dots, 2c_{n}+x_{n})\en A}\right\rbrace

es obvio que por lo tanto $\int \limits _{0}^{2}\dots \int \limits _{0}^{2}{f(x_{1},\dots,x_{n})dx_{1}\ puntos dx_{n}}=V(A)>2^{n}$

\existe x_{1},\puntos,x_{n}:f(x_{1},\puntos,x_{n})\geq 2

entonces hay puntos cuya diferencia es un punto par de la red de enteros . A través de las propiedades de convexidad y simetría, es fácil deducir de esto que hay al menos un punto entero distinto de . Sin embargo, es imposible decir cuál es exactamente este punto. ${\overline {x}},{\overline {y}}\en A$ $A$ ${\ estilo de visualización (0, \ puntos, 0)}$

El enunciado probado se llama teorema de Minkowski [1] . La demostración descrita es no constructiva debido a que utiliza el principio de Dirichlet.

Geometría combinatoria

Algunas de las demostraciones relativas al problema de Danzer-Grünbaum no fueron constructivas debido a la aplicación del método probabilístico [2] [3] [4] .

Teoría de números

Usando el criterio de Weyl , se puede demostrar que para cualquier sucesión infinita de números, para casi todos los números , la sucesión se distribuye uniformemente módulo 1 , es decir, el conjunto de valores para los que este no es el caso tiene medida cero . Sin embargo, tal prueba no permite un conjunto de excepciones (obviamente depende de la secuencia ). es decir, es imposible comprender a partir de él si la secuencia se distribuye uniformemente para algún dato particular . [5] $a_{1}<a_{2}<\puntos <a_{n}<\puntos$ ${\ estilo de visualización \ xi \ en (0; 1)}$ ${\displaystyle {(a_{n}\xi )}_{n=1}^{\infty ))$ ${\displaystyle (a_{n})_{n=1}^{\infty))$ ${\displaystyle {(a_{n}\xi )}_{n=1}^{\infty ))$ $\xi$

Véase también

matemáticas constructivas

Notas

↑ Chandrasekharan, 1968 , pág. 136-137.
↑ P. Erdos, Z. Furedi. El mayor ángulo entre n puntos en el espacio euclidiano d-dimensional // Matemáticas combinatorias.--Marseille-Luminy, 1981.--P. 275-283; Matemáticas de Holanda Septentrional. Stud.--75.--North-Holland, Amsterdam, 1983 (enlace inaccesible) . Consultado el 31 de marzo de 2018. Archivado desde el original el 28 de agosto de 2018. (indefinido)
↑ D. Bevan, "Conjuntos de puntos que determinan solo ángulos agudos y algunos problemas de coloración relacionados", Electron. J. Combin., 13:1 (2006), 24 págs. . Consultado el 31 de marzo de 2018. Archivado desde el original el 2 de mayo de 2018. (indefinido)
↑ L. V. Buchok, "Sobre dos nuevos enfoques para obtener estimaciones en el problema de Danzer-Grunbaum", Mat. notas, 2010, volumen 87, número 4, páginas 519-527" . Consultado el 31 de marzo de 2018. Archivado desde el original el 12 de mayo de 2018. (indefinido)
↑ Kuipers, 1963 .

Literatura

K. Chandrasekharan. Una introducción a la teoría analítica de números . — Mundo, 1968.
Lawrence Kuipers, Harold Niederreiter. Distribución uniforme de secuencias. - Mir, 1963. - 407 págs.