24 votos

¿Qué hacer si usted cree que un problema es indecidible?

Mientras que el título de esta pregunta es subjetiva, espero que para hacer lo que yo estoy buscando algo bastante concreto. La primera y principal pregunta es esta: Si usted cree que un problema que se está trabajando es formalmente indecidible, pero usted no es lógico, ¿cuáles son algunas maneras para empezar a aprender las herramientas necesarias para que usted intente demostrar undecidability? Donde debería empezar?

Ahora, para un ejemplo claro. En el anillo de la teoría de uno de los grandes problemas abiertos se llama Koethe de la conjetura. Hay muchas formas equivalentes de estado de la conjetura, tales como "La suma de dos nil izquierda ideales aún es nula". Permítanme darles otro equivalente descripción.

Deje $R=\mathbb{Z}\langle a,b\rangle$ ser el libre anillo de dos no de desplazamientos de los generadores. Supongamos que $I$ es una izquierda ideal de $R$, que contiene algunas de alimentación de $b$, y que contiene algunos de potencia de cada elemento de $Ra$. Entonces la conjetura afirma $I$ contiene algún poder de $a+b$. Tenga en cuenta que $R$ es contable, y de hecho podemos enumerar fácilmente los elementos de $Ra$ as $f_1,f_2,\ldots$.

Así, dada una secuencia de enteros positivos $\vec{n}=\{n_0,n_1,n_2,\ldots\}$, la hipótesis se afirma que la izquierda ideal que contenga $b^{n_0},f_1^{n_1},f_2^{n_2},\ldots$ también contiene un poder de $a+b$.

Para algunas secuencias $\vec{n}$ (tales como eventualmente constante secuencias), no es difícil calcular que la conjetura es verdadera. Pero, en general, los cálculos se hacen muy difíciles. Lam dice en su "Primer Curso en no conmutativa Anillos" p. 171, que ha habido un

(de larga data) la sospecha de que la Conjetura es falsa.

Si es así, entonces es falsa por lo suficientemente rápido crecimiento de la secuencia de $\vec{n}$.

Sin embargo, uno de los problemas aquí es que nadie sabe cómo controlar el comportamiento de $I$ para el rápido crecimiento de las secuencias de $\vec{n}$, y también hay formas de modificar $I$ solo un poco, y seguramente no producir un contra-ejemplo.

Mi corazonada es que la conjetura es falsa, pero para ver esto tenemos herramientas para afirmar (de rápido crecimiento vectores $\vec{n}$) el ideal de la $I$ se queda complicado. No estoy seguro de que el regular de las herramientas de ZFC son suficientes para la tarea; pero no tienen idea de a dónde ir desde aquí.

Un último comentario: siempre Existe el peligro de que el temor de que un problema que está trabajando es formalmente indecidible, sólo porque usted no puede resolver inmediatamente de ella. Debido a esto no he perdido la esperanza de que existe una solución. Sin embargo, también existe la posibilidad de que algunos de los más fuertes de la teoría de conjuntos puede proporcionar herramientas para buscar en el problema de manera diferente, y realmente eso es lo que yo busco.

37voto

thedeeno Puntos 12553

La primera cosa a decir es que para que una norma para ser independiente de algunos axiomas significa realmente dos cosas, es decir, que es consistente con los axiomas, y también que la negación de la la declaración es consistente con los axiomas. Y normalmente, el las pruebas de estas dos cosas son esencialmente ajenos. Así que en su caso, en donde la pregunta parece ser abierto, me atrevería a decir que es un poco prematuro especular sobre la independencia plena, cuando en lugar usted debe especular acerca de la coherencia de la declaración, o la consistencia de la negación de la declaración. La independencia se produce sólo cuando estas dos situaciones son las caso.

La segunda cosa a decir es que por supuesto casi todos los que no son triviales la instrucción es independiente de algunos muy débil conjunto de axiomas; que no especificar que sistema axiomático que estaban considerando para la independencia, pero la naturaleza de la independencia de las pruebas varía mucho dependiendo del sistema que uno está considerando. A menudo, las declaraciones que resultó ser independiente de la PA o algunos otros débil sistema se puede demostrar en ZFC, y de manera similar a una declaración de que es independiente de ZFC puede ser comprobable de ZFC más grandes cardenales o algún otro sistema fuerte. Ninguna de las afirmaciones es independiente de cualquier sentido absoluto, ya que en la teoría de la toma de una posición en la que declaración, queda resuelto. Por lo que la propiedad de una declaración ser independiente es lógico, pues, relativo a un determinado axiomática del sistema.

Además, yo diría que la importancia filosófica de un la independencia resultado puede variar un poco dependiendo de la fondo para el sistema que se establezca. A mi modo de el pensamiento, el hecho de que el PA no prueba, dicen, que $\epsilon_0$ es fundado es menos preocupante filosóficamente que el hecho de que CH y muchas otras declaraciones parece ser perturbado por ZFC más cualquiera de los conocidos grandes cardenal axiomas, que son la coherencia sabio la más fuerte de las teorías que sabemos, ya que en el primer caso se podría mirarlo simplemente como una debilidad de la PA, pero en el último caso que nos aparecen a la izquierda con un poco de angustia acerca de lo que es el verdadero la verdad de la cuestión de CH.

Así que permítanme hablar de la forma en que un conjunto teórico de los enfoques de la posibilidad de la independencia. Estas son algunas de las preguntas que vienen a la mente cuando se considera la posibilidad de la independencia.

Es la afirmación de algo que podría ser cambiado por forzar? La inmensa mayoría de los más conocidos de la independencia de los resultados en las matemáticas son ZFC independencia de los resultados establecidos por el método de forzamiento. Casi todos los naturales no trivial declaración de infinito la combinatoria ha demostrado ser independiente de ZFC, obligando, y tenemos un número enorme de los que ocurren naturalmente en declaraciones las matemáticas que se sabe que son independientes de ZFC.

Sin embargo, en algunos casos, podemos decir que un enunciado puede definitivamente no se muestra independiente por medio de forzar, simplemente debido a su complejidad lógica. Específicamente, el Shoenfield absolutismo teorema muestra que cualquier $\Sigma^1_2$ declaración es invariante por forzar.

Por ejemplo, en el caso de tu ejemplo, parece haber la complejidad de la $\Pi^1_1$, y esto significa que su declaración es invariante por forzar. Por lo tanto, no será posible para demostrar su declaración independiente de ZFC por medio de forzar. Esto no quiere decir que no es independiente de ZFC, pero no va a ser probado independiente de ZFC en la forma en que la mayoría de las instrucciones se sabe para ser independiente de ZFC han demostrado ser independiente de ZFC.

Es la afirmación de algo que se convierten establecido, si un cierto conjunto iban a ser contables? Cualquier conjunto dado puede convertirse en contable en un forzando la extensión, y esta situación a menudo se asienta muchos declaraciones específicas.

Es la declaración resuelto por la hipótesis continua, o por Martin Axioma? Muchas declaraciones se puede demostrar la coherencia de las ser una consecuencia ya sea de la hipótesis continua o la generalizada hipótesis continua o por el axioma de Martin o de otros los axiomas que son conocidos por ser relativamente consistente con ZFC. Este es una forma muy común para los no-set-teóricos para establecer la consistencia de los resultados, demostrando que la declaración de la considerando son simplemente una consecuencia de las declaraciones acerca de que la consistencia de los resultados ya son conocidos.

Es la declaración de una consecuencia de la existencia de grandes los cardenales? Implica la existencia o consistencia de los grandes los cardenales? A veces sucede que la existencia de grandes cardenales puede implicar la verdad o la consistencia de una instrucción determinada, o una determinada declaración implica la verdad o la consistencia de menor grandes cardenales, y de esta manera la consistencia de la declaración de encaja en el gran cardenal de la jerarquía. Esto tiene consecuencias para la de la independencia. Por ejemplo, si cada conjunto de los reales es Lebesgue medir,, $\omega_1$ es inaccesible a los reales, y por lo que el la consistencia de esa situación con ZF implica la consistencia de un cardinal inaccesible con ZFC. De ello se sigue que no podemos demostrar incluso en Con(ZFC) sí (si esto es consistente) que ZF no demostrar la existencia de un Lebesgue no medible conjunto. Hay muchas situaciones similares, donde una sentencia dada $\varphi$ podría implica la existencia de un interior modelo con un gran cardenal, y por lo que se deduce que la consistencia de la declaración no puede ser resultó sin asumiendo que al menos la consistencia de que los grandes el cardenal hipótesis.

Para la independencia más que la más débil de los sistemas, tales como los habituales sistemas de de segundo orden de la teoría de números, hay toda una lista de preguntas que uno debe hacerse, y yo esperaría que algunos otros MO los usuarios pueden elaborar sobre esto. Por ejemplo, Es la declaración de algo que se resuelva en el mundo en el que todo es computable? Si no, la declaración tiene la esperanza de ser independiente de $\text{RCA}_0$, que es el universo de de segundo orden de la teoría de números que consiste esencialmente de computable sólo fija.

Finalmente, para probar que la declaración de $\varphi$ es independiente de la teoría de la $T$ significa para comprobar que $T+\varphi$ es consistente y también se $T+\neg\varphi$, y así que uno necesita para apreciar la profundidad y la sutileza de la consistencia de las pruebas de las diversas teorías de la $T$ que podría ser objeto de consideración.

4voto

Gerhard Paseman Puntos 2659

Joel David Hamkins ha dado una buena respuesta en el caso de (2), donde una cierta noción cuando se expresa formalmente en el lenguaje de una teoría de la $T$ (y también la negación de este concepto) puede no ser comprobable de $T$ mediante la correspondiente prueba de sistema. Me gustaría tocar en el otro caso (1), donde es posible mostrar no sólo que la conjetura es falsa, pero que puede ser falso en un noncomputable manera. Esta sería una buena resolución, desde el punto de vista del cartel original, porque podría arrojar luz sobre la naturaleza de algorítmica preguntas en general álgebra.

(Descargo de responsabilidad: a pesar de mi proximidad al tema, no soy experto en decidability. Recomiendo Algorítmica de Problemas en las Variedades por Sapir y Kharlampovich, y también en la sección 6 y versiones anteriores de Ross Willard "Una Visión general de la Moderna Álgebra Universal", ambos disponibles en la Web. Tuve el privilegio de ser uno de los primeros en ver McKenzie presentar su trabajo de Tarski Finito Base del Problema: que el trabajo influye en este post.)

Considerar la posibilidad de que Koethe la conjetura es falsa. Como el Ritmo de Nielsen señala en su pregunta, de una manera que podría ser falsa, es que existe un rápido crecimiento de la secuencia de $n_i$ y un (esperemos recursiva) enumeración $f_1,f_2, \ldots$ de % de $Ra$ tal que $a+b$ y todos sus poderes evita toda la izquierda-los ideales generados por un número finito de subsequence de $b^{n_0}, {f_1}^{n_1}, {f_2}^{n_2}, \ldots$ . (A menos que me he perdido algo, esto debe ser equivalente a su formulación.) Sería agradable ser capaz de caracterizar a los ideales que no la conjetura, o de una determinada anillo, para caracterizar las secuencias y las enumeraciones que conducen al fracaso.

Como se ha mencionado en los comentarios, para mostrar que no recursiva caracterización es posible, sería un método para reducir un problema indecidible a esta pregunta. En otras palabras, la construcción de un recursiva mapa de $\phi$, de modo que para cada instancia de $I$ a un problema conocido para ser indecidible, $\phi(I)$ es una secuencia de (digamos) de los exponentes $n_j$ de manera tal que una cierta enumeración de $Ra$ elevado a exponentes $n_j$ produce un ideal que contiene un poder de $a+b$ fib $I$ satisface la propiedad en el problema conocido para ser indecidible. Boone-Novikov resultado es bien conocido (un finitely presentado el grupo con indecidible problema de palabras), y el artículo de Sapir y Kharlampovich contiene muchos ejemplos más, y si el Koethe problema "ve" suficiente como uno de los indecidible problemas, entonces se podría construir un recursiva $\phi$ como se sugirió anteriormente.

Alternativamente, uno podría tener un dominio de la situación en la que uno podría tratar de construir una secuencia de ideales con tal propiedad que "codificado" máquina de Turing cálculos. En el caso de Tarski Finito Base del problema (hay un programa de ordenador que puede tomar como entrada de la función de las tablas de un número finito de álgebra Un finitos tipo, y la salida "sí" si la teoría ecuacional de V(A) es finitely-basado, y "no" en caso contrario), hubo una serie de problemas relacionados con el que McKenzie estaba trabajando en lo que le permitió expresar un programa de Turing como un álgebra de determinadas operaciones correspondiente al estado de transición de la tabla del programa, de tal forma que si el estado de reposo, la que correspondería a un cierto algebraica de la propiedad en un poder infinito de la base de álgebra, y no corresponden de otra manera. Las propiedades involucradas tenía que hacer con restos de pequeñez, y McKenzie me dijo que parte de su proceso de pensamiento fue para arreglar todas las propiedades que necesitaba en pequeños grupos, y hacer pequeños cambios en la expresión algebraica de la construcción, para obtener el grupo de propiedades que necesitaba (mi redacción basada en un mal recordar de un evento más de veinte años en el pasado).

Este es un intento para responder a la pregunta de una manera diferente: si usted sospecha que la respuesta no es sólo que no, pero no en un no-recursiva manera, tratan de dos enfoques: la reducción de algo en la Kharlampovich-Sapir (u otras fuentes), o comprender las propiedades de los ideales que satisfacer Koethe la conjetura así como los que no, y ver si esas propiedades son recursivamente inseparables (puede estar relacionado de alguna manera a los cálculos de detener o no).

Gerhard "Que es lo que Haría yo Inicio" Paseman, 2015.03.24

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X