1 votos

Ejemplo de lógica en la que una prueba por contradicción no implica una prueba directa.

Tiene sentido que para cualquier lógica que tenga axiomas, una regla de inferencia y un enunciado que quieras demostrar P, puedas tomar una demostración directa de P y convertirla en una demostración por contradicción (ya has demostrado P y asumido que no es P. ¡Una reducción cont!) ¿Hay algún ejemplo de lógicas (no triviales) en las que lo contrario no sea cierto? ¿Dada una prueba por contradicción que demuestre p, no se puede construir una prueba directa que demuestre p?

Por prueba directa me refiero únicamente a generar enunciados a partir de los axiomas la regla de inferencia y los hijos de dicha regla.

Gracias

1voto

DanteAlighieri Puntos 16

La pregunta no me queda muy clara, así que hablaré de un par de interpretaciones de la misma y espero que las respuestas sean útiles.

La lógica intuicionista es básicamente lógica clásica sin medio excluido ( $P \vee \neg P$ ). Podemos recuperar la lógica clásica habitual a partir de la lógica intuicionista bien añadiendo el medio excluido, bien añadiendo el principio de eliminación de la doble negación , $\neg \neg P \rightarrow P$ . Si definimos una prueba directa como aquella que es válida en lógica intuicionista, entonces la pregunta es: ¿es la lógica intuicionista diferente de la lógica clásica?

La respuesta a esta pregunta es sí. Resulta que el medio excluido no es demostrable en lógica intuicionista.

Alternativamente, por prueba directa se puede entender una prueba sin cortes. Esto no está realmente relacionado con la prueba por contradicción como tal, pero podría estar más cerca de lo que quieres decir. La regla del corte es una de las reglas de el cálculo secuencial y afirma que a partir de $\Gamma \vdash \Delta,A$ y $A, \Sigma \vdash \Pi$ podemos deducir $\Gamma,\Sigma \vdash \Delta,\Pi$ . Observe que $A$ aparece en el antecedente pero no en el consecuente. El proceso de convertir una prueba en una prueba sin cortes se conoce como eliminación de cortes .

En este caso, la respuesta a la pregunta es que la eliminación de cortes puede realizarse normalmente para la lógica por sí sola (esto es cierto tanto para la lógica clásica como para la lógica intuicionista) pero no en general cuando se añaden axiomas al sistema. En $PA$ (y si no recuerdo mal incluso en $HA$ la contrapartida intuicionista de $PA$ ) es posible realizar la eliminación de cortes, pero sólo pasando a pruebas infinitas. Hay teoremas en $PA$ que no tienen una prueba sin cortes (finita).

0voto

CallMeLaNN Puntos 111

La resolución de la paradoja de Russell es probablemente la prueba por contradicción más famosa de la teoría de conjuntos:

Supongamos que $\exists x \forall y (y\in x\leftrightarrow y\notin y)$

Sea $r$ (el conjunto Russell) sea tal que $\forall y (y\in r\leftrightarrow y\notin y)$ por especificación existencial.

Aplicando esta definición de $r$ a $r$ obtenemos la contradicción $r\in r\leftrightarrow r\notin r$ .

Concluimos $\neg\exists x \forall y (y\in x\leftrightarrow y\notin y)$ .

No veo cómo se puede convertir esto en una prueba directa. (Cambiar " $\in$ " a cualquier otro predicado lógico si tu teoría de conjuntos no permite la autopertenencia. La lógica de la prueba seguiría funcionando).

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