¿La decidibilidad implica inconsistencia?

Question

Siempre he pensado que, según Gödel de la incompletitud de los problemas, cada inconsistente teoría sería decidable. Este es el indicado, aquí por ejemplo: https://en.wikipedia.org/wiki/Decidability_(lógica)

Hay varios resultados básicos sobre decidability de teorías. Cada teoría es inconsistente decidable, como cada fórmula en la firma de la teoría será una consecuencia lógica, y por lo tanto un miembro de la teoría.

Pero yo estaba teniendo una conversación con un matemático y él me dijo todo lo contrario.

Estábamos teniendo una discusión y me mencionó que inconsistentes teorías sería decidable. Él dijo:

Undecidability requiere de la lógica de primer orden, y eso es todo. No Paraconsistent lógica, Trivialism, o incluso Desviadas de la lógica. Simplemente de la lógica de primer orden.
Creo que son una especie de clase de en el derecho de barrio, pero hay un par de problemas técnicos que necesitamos como un requisito previo para seguir hablando. Por ejemplo, usted dice que "decidability implica la incoherencia". En realidad, decidability implica exactamente lo contrario, implica consistencia

Pensé que realmente incoherente teoría sería completamente decidable, como todo iba a ser comprobable. Pero ahora estoy dudando...

Pero esto es correcto? Estoy completamente equivocado? No puede no ser incoherente y decidable teorías? Y no puede ser incoherente y indecidible teorías?

Answer 1

Parece que el matemático consiguió llevar un poco al final, porque, por supuesto, decidability no implica consistencia. Como usted señala, una teoría es inconsistente decidable porque demuestra todo. (Si desea hacer referencia a Gödel para eso, es la integridad teorema quieres, aunque). Y la inconsistencia de las teorías, ciertamente, existe.

Por otro lado, podemos tener una coherente teoría de que es decidable como en la lógica de primer orden con igualdad, pero no otros lógico símbolo de la teoría con el único axioma $$ \forall x\forall y(x=y) $$

Es coherente porque tiene un modelo (con un solo objeto); es decidable porque este es el único modelo y es fácil de evaluar cualquier wff a un valor de verdad en ese modelo.

También podemos tener una coherente teoría de que es indecidible , al menos tenemos la esperanza de PA y de ZFC son tales teorías.

Así que el único que no trivial de implicación entre estas propiedades y su negación es la suya: la inconsistencia implica decidability (o contraposed: undecidability implica consistencia).

Answer 2

Tienes razón en que cada teoría es inconsistente decidable. De hecho, este es el procedimiento de decisión para cualquier inconsistente teoría:

Entrada: [cualquier declaración]

Salida: "Sí, es un teorema!"

Así, la inconsistencia implica decidablity

Pero esto es lo contrario de lo que su profesor de reclamaciones usted está diciendo:

Por ejemplo, usted dice que "decidability implica la incoherencia".

??Eh? Usted no está diciendo que en todos los

y cuando el maestro dice:

En realidad, decidability implica exactamente lo contrario, implica consistencia

Bueno, eso es simplemente malo, porque eso significaría que la inconsistencia implica undecidability y, como hemos visto, la inconsistencia en lugar implica decidability