Eliminación de la doble negación en lógica constructiva

Question

¿Cómo puedo demostrar que la eliminación de la doble negación no es demostrable en lógica constructiva?
Para aclarar, la eliminación de la doble negación es lo siguiente:

$$\neg\neg q \rightarrow q$$

Answer 1

Hay dos maneras de ir sobre esto:

1. Prueba de la teoría. Vamos a analizar las pruebas en el sistema de inferencia dado, y mostrar que no puede haber ninguna prueba formal de la doble negación de la eliminación. Esto es difícil y depende mucho de los detalles del sistema de inferencia.

2. Modelo de la teoría. Se construye un modelo de intuitionistic lógica proposicional en la que la doble negación eliminación es visiblemente falsa. Esto es mucho más fácil y menos sensible a los detalles, pero es conceptualmente más difícil.

Primero de todo, ¿qué es un modelo de intuitionistic lógica proposicional? Es una estructura algebraica $\mathfrak{A}$ equipada con constantes $\top$ $\bot$ así como operaciones binarias $\land$, $\lor$, $\to$, además de un orden parcial $\le$, de tal manera que el siguiente solidez regla es válida: teniendo en cuenta las fórmulas de $\phi$ $\psi$ en el idioma de intuitionistic lógica proposicional con proposicional variables $x, y, z, \ldots$, si el secuente $\phi \vdash \psi$ es demostrable, entonces $\phi \le \psi$ $\mathfrak{A}$ para todas las opciones de $x, y, z, \ldots$$\mathfrak{A}$.

Por ejemplo, $\mathfrak{A}$ podría ser un álgebra de Heyting, que es una estructura algebraica satisfacer algunas de axiomas. La primera de todas las $\mathfrak{A}$ es un (limitado) de celosía:

• La unidad de las leyes: \begin{align} \top \land x & = x & \bot \lor x & = x \\ x \land \top & = x & x \lor \bot & = x \end{align}
• La asociatividad, conmutatividad, y idempotence: \begin{align} (x \land y) \land z & = x \land (y \land z) & (x \lor y) \lor z & = x \lor (y \lor z) \\ x \land y & = y \land x & x \lor y & = y \lor x \\ x \land x & = x & x \lor x & = x \\ \end{align}
• Ley de la absorción: \begin{align} x \land (x \lor y) & = x & x \lor (x \land y) & = x \end{align}

Uno puede entonces verificar que $x \le y$ definido por $x \land y = x$ es un orden parcial en $\mathfrak{A}$ y que $\top$, $\bot$, $\land$, $\lor$ tienen su orden habitual de la teoría de los significados. A continuación, agregamos algunos axiomas para $\to$:

• Distributiva de la ley: $$x \to (y \land z) = (x \to y) \land (x \to z)$$
• Interno de la tautología: $$x \to \top = \top$$
• Debilitamiento interno: $$y \to (x \land y) = y$$
• Interna modus ponens: $$x \land (x \to y) = x \land y$$

Ejercicio. Mostrar que $y \le z$ implica $(x \to y) \le (x \to z)$, e $x \le ((x \land y) \to y)$$((x \to y) \land y) \le x$, y de ahí o de lo contrario ese $x \land y \le z$ si y sólo si $x \le (y \to z)$.

Ejercicio. Verificar la bondad de la regla para la interpretación de intuitionistic lógica proposicional en un álgebra de Heyting.

La proposición. Doble negación eliminación no es válido en intuitionistic lógica proposicional.

Prueba. Construimos un tres elementos de álgebra de Heyting falsificar la doble negación de la eliminación. Deje $\mathfrak{A} = \{ \bot, \omega, \top \}$ y definir las operaciones binarias de la siguiente manera: \begin{align} \begin{array}{|r|ccc|} \hline \land & \bot & \omega & \top \\ \hline \bot & \bot & \bot & \bot \\ \omega & \bot & \omega & \omega \\ \top & \bot & \omega & \top \\ \hline \end{array} && \begin{array}{|r|ccc|} \hline \lor & \bot & \omega & \top \\ \hline \bot & \bot & \omega & \top \\ \omega & \omega & \omega & \top \\ \top & \top & \top & \top \\ \hline \end{array} && \begin{array}{|r|ccc|} \hline \to & \bot & \omega & \top \\ \hline \bot & \top & \top & \top \\ \omega & \bot & \top & \top \\ \top & \bot & \omega & \top \\ \hline \end{array} \end{align} A continuación, se observa que la $((\omega \to \bot) \to \bot) = \top$, pero $\top \nleq \omega$. Por lo tanto, $(x \to \bot) \to \bot$ no puede ser un axioma de la intuitionistic lógica proposicional.

Observación. De Morgan leyes siguen siendo válidos en este álgebra de Heyting. Encontrar uno que falsifica parte de De Morgan leyes. (Ver esta pregunta.)

Answer 2

Una forma muy sencilla y eficiente árbol de la prueba método (es decir, un tableau método sin firmado fórmulas) para intuitionistic lógica ha sido publicado por la Campana, DeVidi y Salomón en "Opciones Lógicas: Una Introducción a la Clásica y Alternativa de la Lógica" http://books.google.fr/books/about/Logical_Options.html?id=zUVYx-bTLgMC&redir_esc=y

Aquí está el árbol de la contra-modelo para la fórmula $\neg \neg p \to p$, a la Campana de la $et{}~ al.$:

$$\underline{?(\neg \neg p \to p)}^{\surd}$$ $$ ? p $$ $$ \neg \neg p$$ $$ \underline{? \neg p }^{\surd}$$ $$ p $$ El árbol de mostrar un Kripke contra-modelo donde, en una localidad expresada por un espacio entre dos líneas horizontales, $p$ no se sabe para ser verdad (es decir, es falso en la localidad), mientras que $\neg \neg p$ está demostrado, es decir, se sabe para ser verdad. El símbolo $?$ dice que la fórmula no es conocido para ser verdad, y se pega la fórmula en la localidad. El símbolo $\surd$ dice que la fórmula está desactivada. Cada fórmula sin $\surd$ o sin $?$ puede pasar a través de cualquier línea horizontal (la verdad es persistente). Para más detalles, véase Bell et al.'s libro.

Esto es muy simple prueba método de echo a la muy agradable explicación dada por Zhen Lin. (Me gustaría agradecer a Zhen Lin de corazón por su puesto.)

Answer 3

Hay un intuitionistic idea que se convierte en más valiosa con la llegada de los computacional-matemáticas. A grandes rasgos constructivos de la lógica o las matemáticas, cuando dices "objeto" existe está diciendo: "sabemos de alguna forma, para construir Una". Esta posición implica la"tertio exclusoregla' $\neg(\neg q))\rightarrow q$ falla.

El ejemplo clásico pertenece a Brouwer (1925). Nos escribe el decimal de expansión de $\pi$, y es el número de $\rho=0.333\ldots$que cortamos cuando la secuencia de $012346789$ aparecen en $\pi$ el primer tiempo. Con la clásica lógica nos dice que $\rho$ es racional. Si la secuencia de $012346789$ no aparece $\rho$ será definido por $ \frac{1}{3}$. Con el enfoque constructivo no se puede probar $\rho$ es racional antes de encontrar la primera secuencia $0123456789$ $\pi$ o usted tiene una prueba de que esta secuencia no aparece nunca en la expansión decimal de $\pi$.

Pero constructiva en matemáticas se puede demostrar que es contradictorio que $\rho$ no es racional. Si nos digamos $\rho$ no es racional (lo que es equivalente, que tenemos una construcción de diferenciar $\rho$ de cualquier número racional), a continuación, $\rho=0.3333\ldots 3$ debe ser imposible, y la secuencia de $0123456789$ no aparece en $\pi$. Por lo tanto, $\rho=\frac{1}{3}$ lo cual es imposible. Entonces es contradictorio que $\rho$ no es racional, pero no tenemos una prueba de que $\rho$ es racional.

EDITAR:

Mi respuesta es complementaria a otras más formales respuestas. Se va a la principal punto de renunciar a la $\neg(\neg q))\rightarrow q$. Esencialmente, mi respuesta es intuitionistic, no un formalismo.