¿Cuáles son algunos ejemplos de contraejemplos no triviales o difíciles a conjeturas matemáticas?

Oh esto va a ser divertido.

Primero, un punto de terminología: no hay “contraejemplos a las teorías matemáticas”, porque una teoría no es una afirmación única que pueda ser refutada con un contraejemplo. Tampoco hay contraejemplos a los teoremas matemáticos, porque los teoremas son verdaderos.

Existen contraejemplos interesantes, no triviales y, a veces, complicados, a afirmaciones matemáticas que, por supuesto, no son teoremas. Muchas de esas afirmaciones se mantuvieron como conjeturas por un tiempo, hasta que alguien encontró un contraejemplo.

Algunos de los siguientes contraejemplos son profundos, otros mundanos. Algunos son fáciles de verificar, otros no. Algunos están en Teoría de números, otros en Teoría de la computación, otros en lógica y otros en topología (y quizás algunos otros campos, veremos).


Reclamo : Cada número de la forma [math] 2 ^ {2 ^ n} +1 [/ math] es primo. (¡Falso!)

Esta fue una conjetura genuina hecha por Pierre de Fermat, quien verificó que [math] 2 ^ 2 + 1 = 5 [/ math], [math] 2 ^ 4 + 1 = 17 [/ math], [math] 2 ^ 8 + 1 = 257 [/ math] y [math] 2 ^ {16} + 1 = 65537 [/ math] son ​​de hecho números primos.

El contraejemplo viene precisamente en el siguiente número, [math] 2 ^ {32} + 1 = 4294967297 = 641 \ times 6700417 [/ math]. Esto puede parecer trivial para los estándares de hoy, pero cuando Euler encontró esta factorización, fue una hazaña muy inteligente (hizo esto reconociendo que [math] 641 = 2 ^ 9 + 2 ^ 7 + 1 [/ math] debe dividir ese número) .

De hecho, Fermat estaba tan equivocado con respecto a esto como puede ser: por lo que podemos decir, pasado [math] n \ geq 5 [/ math] ninguno de los números [math] 2 ^ {2 ^ n} +1 [ / math] es primo. Aunque no lo sabemos con seguridad. Sabemos que [math] 2 ^ {2 ^ {32}} + 1 [/ math] es compuesto (como todos los números más pequeños de esta forma), pero nadie sabe con seguridad si [math] 2 ^ {2 ^ {33 }} + 1 [/ math] es o no es primo.


Reclamación (Conjetura de Tait) : Cada gráfica cúbica plana con 3 conexiones tiene un ciclo hamiltoniano. (¡Falso!)

PG Tait propuso esto en 1884 como una forma de probar el famoso teorema de los 4 colores: Tait demostró (con bastante facilidad) que el teorema de los cuatro colores se desprende de esta afirmación. Bill Tutte tardó más de 60 años en encontrar este contraejemplo:

Este gráfico es obviamente plano, obviamente es cúbico (cada vértice tiene exactamente tres vecinos), es un poco menos obvio conectado a 3 (no se puede separar eliminando uno o dos vértices), y no es Hamiltoniano (no hay manera de visitar) todos los vértices en una trayectoria continua sin bucles). Esta última parte no es del todo obvia, pero tampoco es muy difícil de probar. Es encontrar este gráfico que es el desafío.


Reclamo : si sumas algunos poderes [matemáticos] k [/ matemáticos] para obtener un poder [matemático] k [/ matemáticos] , debes haber agregado al menos los números [matemáticos] k [/ matemáticos] . (¡Falso!)

Esta conjetura fue hecha por Leonhard Euler, como una cierta extensión del Último Teorema de Fermat.

Euler observó que es fácil sumar dos cuadrados para obtener un cuadrado, como en [math] 3 ^ 2 + 4 ^ 2 = 5 ^ 2 [/ math], pero no puedes agregar dos cubos para obtener un cubo: [ math] a ^ 3 + b ^ 3 = c ^ 3 [/ math] no tiene solución en enteros positivos (este es el caso [math] n = 3 [/ math] del último teorema de Fermat, en el que Euler fue el primero en llegar probar.) Sin embargo, puede agregar tres cubos para obtener un cubo, por ejemplo [math] 3 ^ 3 + 4 ^ 3 + 5 ^ 3 = 6 ^ 3 [/ math]. Bueno, pensó Euler, hay un patrón aquí: puedes sumar [math] k [/ math] [math] k [/ math] th para obtener un [math] k [/ math] th, pero puedes ‘ Salgo con menos de [math] k [/ math] de ellos.

Esto no es cierto, pero llevó casi 200 años encontrar un contraejemplo.

El primer contraejemplo fue encontrado en 1966 por Lander y Parkin, utilizando una búsqueda por computadora. Descubrieron que

[math] 27 ^ 5 + 84 ^ 5 + 110 ^ 5 + 133 ^ 5 = 144 ^ 5 [/ math].

Puedes encontrar su papel original aquí. En 1966, esto fue toda una hazaña. Hoy en día, puede encontrar este ejemplo en solo unos minutos de codificación y ejecución de su código en una computadora portátil estándar, o incluso en un teléfono inteligente (¡Pruébelo!).

Esto muestra que Euler estaba equivocado cuando [math] k = 5 [/ math]. Él ya sabía que era correcto para [math] k = 3 [/ math]. ¿Qué hay de [math] k = 4 [/ math]?

Eso tomó considerablemente más ingenio que una simple búsqueda por computadora. En 1986, Noam Elkies, de 20 años de edad, usó la teoría de las curvas elípticas (más algunos trabajos de computadora) para encontrar infinidad de contraejemplos a la conjetura de Euler para las cuatro potencias. El mas pequeño es

[math] 2682440 ^ 4 + 15365639 ^ 4 + 18796760 ^ 4 = 20615673 ^ 4 [/ math].

Finalmente, para [math] k \ geq 6 [/ math], la situación aún es desconocida. Es posible, aunque en mi opinión poco probable, que la conjetura de Euler sea válida para los sextos poderes y más allá.

Sin embargo, no hemos terminado con Euler.


Reclamo : No hay cuadrados ortogonales de orden par que no sean divisibles por 4 . (¡Falso!)

Mira la siguiente serie de tarjetas.

A ♠ K ♥ Q ♦ J ♣
Q ♣ J ♦ A ♥ K ♠
J ♥ Q ♠ K ♣ A ♦
K ♦ A ♣ J ♠ Q ♥

Vea lo inteligente que es esto: cada fila contiene cada rango (J, Q, K, A) exactamente una vez, al igual que cada columna. Además, cada fila contiene cada palo (♠, ♥, ♦, ♣) exactamente una vez, al igual que cada columna. Pero, además, los dos arreglos de rango y palos están tan mezclados que ninguna carta aparece dos veces en toda la gama: el Gato de corazones aparece solo una vez, al igual que la Reina de Picas, y así sucesivamente para todas las combinaciones posibles.

Sin esta última condición de “ortogonalidad”, lo que tendrías aquí son solo dos rompecabezas de Sudoku de orden 4 superpuestos. Pero el requisito de que ninguno de los pares aparezca dos veces hace que sea un rompecabezas muy difícil, lo suficientemente difícil como para interesar al gran Euler. Usó letras latinas y griegas para construir esos arreglos, ganándolos y luego llamándolos cuadrado greco-latino. Aquí hay una gran variedad de órdenes 3.

Euler pudo construir dichas matrices para cada orden impar y para cada orden divisible por 4. Es fácil ver que no existe tal matriz para la orden 2 (¡ejercicio!), Y Euler no pudo construir una de orden 6, por lo que propuso que las órdenes 2, 6, 10, 14, … son imposibles. Esos son los números pares que no son divisibles por 4.

Euler también estaba equivocado al respecto, y una vez más se demoraron más de 150 años en refutar esta conjetura (en este punto, probablemente debería mencionar que Euler fue uno de los matemáticos más profundos y creativos de todos los tiempos, y esos problemas conjeturales eran bastante poco característicos de él.)

Euler tenía razón sobre la orden 6, aunque fue solo en 1901 que esto fue comprobado. Pero en 1959, Raj Chandra Bose y Sharadchandra Shankar Shrikhande construyeron una matriz ortogonal de orden 22. ET Parker encontró un ejemplo de orden 10, y más tarde los tres demostraron que tales matrices existen para cada [math] n [/ math] excepto las brechas en [math] n = 2 [/ math] y [math] n = 6 [/ math].

Aquí hay una matriz ortogonal de orden 10: cada combinación de 2 dígitos aparece exactamente una vez, y cada fila y cada columna contienen cada dígito en el primer y segundo lugar.



Reclamo : No hay grados de Turing entre 0 y 0 ′ . (Falso)!

La teoría de los grados de Turing es una idea verdaderamente hermosa. Estudia los aspectos computacionales de los conjuntos de números y revela una estructura sorprendentemente compleja a partir de unas pocas definiciones simples. Aquí están los fundamentos mínimos que necesitamos.

Un conjunto de números naturales se llama computable si puede escribir un programa de computadora que verifique la membresía en el conjunto. Como puede escribir un programa de computadora que verifique si un número es primo, el conjunto de números primos es computable. Ya que puede escribir un programa de computadora que verifique si un número dado es par y es la suma de dos números primos, el conjunto de números pares que es la suma de dos números primos es computable (No sabemos si este grupo contiene todos los números pares). mayor que 2, que es la conjetura de Goldbach; sin embargo, el conjunto es computable). La familia de todos los conjuntos computables se llama 0 .

No todos los conjuntos de números naturales son computables, porque hay demasiados conjuntos y muy pocos programas de computadora posibles para detectarlos. Como ejemplo concreto de un conjunto no computable, considere el conjunto de números que codifican (de alguna manera) los programas de computadora que se detienen. Ningún programa de computadora puede determinar correctamente si un número está o no en el conjunto.

Ahora, supongamos que te dan un dispositivo mágico que puede , en realidad, decirte si un programa se detiene o no. Al usar este dispositivo como “caja negra” (o, en el lenguaje más común, un “oráculo”), ahora puede hacerlo mejor y escribir programas de computadora que deciden la membresía en más conjuntos que solo los computables. Se dice que esos conjuntos son “computables usando un oráculo que se detiene”, y la familia de esos conjuntos se denota 0 ′ . También lleva el nombre cautivador “El salto de Turing de 0 “.

Emil Post hizo la pregunta: ¿hay conjuntos que son más difíciles de verificar que 0 pero más fáciles de verificar que 0 ′ ? Un poco más formal, ¿existe un conjunto que no sea computable pero sí computable con un oráculo que se detiene, y que no es lo suficientemente poderoso para servir como un oráculo que se detiene? Parece un poco difícil imaginar que existan tales problemas de nivel intermedio.

Pero lo hacen. Richard Friedberg y Albert Muchnik, independientemente, desarrollaron la idea conocida como el Método de Prioridad y construyeron conjuntos tan peculiares. Esto abrió un nuevo campo de estudio, explorando la rica estructura de los grados de Turing y su orden parcial.


Reclamo : No hay modelos de ZFC que violen la Hipótesis Continua . (¡Falso!)

Georg Cantor, el creador de la Teoría de los Conjuntos, se preguntó si hay un conjunto incontable de números reales que no pueden ponerse en correspondencia con los números reales. En otras palabras, ¿hay alguna cardinalidad entre [math] \ aleph_0 [/ math] y [math] 2 ^ {\ aleph_0} [/ math]?

Esta muy famosa conjetura se conoció como la Hipótesis Continua (CH). En 1938, Kurt Gödel demostró que esta hipótesis es consistente con ZFC, que es lo mismo que decir que hay un modelo de ZFC, un “universo de conjuntos”, en el que CH es verdadero. Algunas personas creyeron que esto era una indicación de que CH es, de hecho, verdadero, lo que significa que no hay modelos de ZFC en los que CH sea falso.

De hecho, las personas en general no tenían idea de cómo construir modelos de ZFC que no fueran los “naturales” como [math] L [/ math], que es el modelo creado por Gödel. Pero Paul Cohen logró hacer precisamente eso, inventando la técnica fundamental de Forcing en 1963. Por esto, recibió la medalla Fields.

La gente no suele pensar en un modelo de ZFC + [math] \ neg [/ math] CH es un “contraejemplo”, pero formalmente puede considerarse como uno: es un contraejemplo de la afirmación de que ZFC implica CH, es decir, que No hay modelos de ZFC donde CH es falso. De hecho, existen tales modelos, por lo que Cohen construyó lo que podría describirse como un contraejemplo.


Reclamo : Un grupo incontable debe tener un subgrupo apropiado incontable . (¡Falso!)

Es muy fácil construir grupos incontables: el círculo, el toro, el grupo de [math] n \ times n [/ math] matrices reales del determinante 1, y así sucesivamente. Hay toneladas de tales grupos, y si los miras, verás que todos insisten en contener subgrupos incontables. ¿Es posible crear un grupo incontable sin los subgrupos adecuados no contables?

Es posible, pero muy lejos de ser fácil. El primer contraejemplo, denominado “monstruo de Kuroš”, fue encontrado por Saharon Shelah y publicado aquí. Está más allá de mis habilidades incluso dibujar la construcción.


Reclamo : No hay libros dedicados exclusivamente a los contraejemplos . (¡Falso!)

La topología tiene tantos contraejemplos, hay un libro completo sobre ellos, y este libro es tan famoso, hay un artículo de Wikipedia al respecto. Tras su éxito, otros libros con títulos similares aparecieron en otros campos de las matemáticas.

Algunos de los contraejemplos estándar en topología son el conjunto de Cantor, la línea larga y el pendiente hawaiano. Un contraejemplo un poco más exótico es el espacio de “Pie pegajoso” construido por Bing como ejemplo de un espacio de Hausdorff conectado y contable. Es fácil suponer que un espacio de Hausdorff conectado debe ser incontable, porque todos los espacios conectados que todos sabemos son incontables, y claramente los finitos no son suficientes. Pero tales espacios extraños existen, y el espacio Sticky Foot es uno de ellos.


Reclamo : Esta lista está completa . (¡Falso!)

Esta afirmación no tiene sentido. Hay toneladas de otros contraejemplos en matemáticas, cada uno de los cuales sirve como contraejemplo de esa afirmación.