¿Son los dos Or-Elims equivalentes?

Question

Tenemos:

1. $\varphi \lor \psi, \neg \varphi \vdash \psi$
2. $\varphi \lor \psi, \varphi \to \chi, \psi \to \chi \vdash \chi$

El uso de $2$ y explosión (ex falso), uno puede demostrar que $1$:

1. $\varphi \lor \psi$ [premisa]
2. $\neg \varphi$ [premisa]
3. 1. $\varphi$ [asunción]
   2. $\bot$ [contradicción 2 3.1]
   3. $\psi$ [explosión]
4. $\varphi \to \psi$ [$\to$introducción 3.1-3.3]
5. 1. $\psi$ [asunción]
6. $\psi \to \psi$ [$\to$introducción 5.1-5.1]
7. $\psi$ [$\lor$elim 1 4 6]

Sin embargo, se puede demostrar $2$ $1$ el uso de otros intuitionist reglas?

Answer 1

No. Escribir $\triangledown$ para nuestros aspirantes a la disyunción, así que tenemos la regla de $\varphi\triangledown\psi,\neg\varphi\vdash\psi$ (y, presumiblemente, tenemos $\varphi_i\vdash\varphi_1\triangledown\varphi_2$). Entonces, para hacer uso de la $\varphi\triangledown\psi$ asunción en $\varphi\triangledown\psi,\varphi\to\chi,\psi\to\chi\vdash\chi$ tenemos que ser capaces de demostrar $\neg\varphi$. Simplemente no hay razón para que esto sería demostrable.

Esto es aún más evidente con una interpretación computacional. Aquí está lo que el comienzo de una prueba de intento se vería en Agda:

data ⊥ : Set where

¬_ : Set → Set
¬ A = A → ⊥

postulate WOr : Set → Set → Set
postulate Left : {φ ψ : Set} → φ → WOr φ ψ
postulate Right : {φ ψ : Set} → ψ → WOr φ ψ
postulate wOrElim : {φ ψ : Set} → WOr φ ψ → ¬ φ → ψ

orElim : {φ ψ χ : Set} → WOr φ ψ → (φ → χ) → (ψ → χ) → χ
orElim wor l r = r (wOrElim wor (λ x → ? (l x)))

No hay ninguna opción obvia de lo que para poner el ?. Computacionalmente, no hay manera de exfiltrate la $\chi$ l produce. En el computacionales interpretación de la lógica clásica, la de Peirce, la ley nos da esencialmente throw/catch mecanismo de modo que podríamos implementar orElim en un hecho, una versión clásica de Agda con algo como:

orElim : {φ ψ χ : Set} → WOr φ ψ → (φ → χ) → (ψ → χ) → χ
orElim wor l r = try {r (wOrElim wor (λ x → throw (l x)))} catch(c) { c }    

Esto no es una prueba de que es imposible, por supuesto. Tal vez hay un programa inteligente para hacer lo que yo no creo. En la práctica, sin embargo, la programación de experiencia, combinados con el cómputo de la interpretación, en particular, intuitionistic la lógica hace que sea bastante fácil de reconocer que no hay flujo de datos de rutas de acceso. Como tal, cosas que no son intuitionistically comprobable a ser relativamente auto-evidente.

Si va a demostrar que usted no puede derivar 2 en 1, que tendríamos que hacer algo así como una inducción sobre las derivaciones, o usted puede hacer una contra-modelo, por ejemplo, un modelo topológico.

Answer 2

Usted no puede de manera constructiva la Prueba Por Casos como el de la sugerencia O Elim regla. Considere las siguientes valoraciones (que se encuentra mi equipo):

$$\begin{array} {cc|c} A & B & A \to B \\ \hline 1 & 1 & 1 \\ 2 & 1 & 1 \\ 3 & 1 & 1 \\ 1 & 2 & 2 \\ 2 & 2 & 1 \\ 3 & 2 & 1 \\ 1 & 3 & 3 \\ 2 & 3 & 3 \\ 3 & 3 & 1 \\ \end{array}$$

$$\begin{array} {c|c} A & \lnot A \\ \hline 1 & 3 \\ 2 & 3 \\ 3 & 1 \\ \end{array}$$

$$\begin{array} {cc|c} A & B & A \lor B \\ \hline 1 & 1 & 1 \\ 2 & 1 & 1 \\ 3 & 1 & 1 \\ 1 & 2 & 1 \\ 2 & 2 & 1 \\ 3 & 2 & 2 \\ 1 & 3 & 1 \\ 2 & 3 & 2 \\ 3 & 3 & 3 \\ \end{array}$$

Y la siguiente lógica $L$:

$$\begin{array} {ll} \text{Axiom Schema:} & \\ \hline A \to B \to A & \text{Weakening} \\ (A \to B \to C) \to (A \to B) \to (A \to C) & \text{Conditional Modus Ponens} \\ \hline (A \to B) \to (A \to \lnot B) \to \lnot A & \text{Negation Propagation} \\ A \to \lnot A \to B & \text{Explosion} \\ \hline A \to (A \lor B) & \text{Or Intro 1} \\ A \to (B \lor A) & \text{Or Intro 2} \\ (A \lor B) \to \lnot A \to B & \text{Needs a Name 1} \\ (A \lor B) \to \lnot B \to A & \text{Needs a Name 2} \\ \hline \text{Inferences:} & \\ A, ~ (A \to B) \vdash B & \text{Modus Ponens} \\ \end{array}$$

Tomando $1$ como el valor de "true", cada axioma esquema es una tautología, y por modus ponens, implicación tiene la propiedad de que si $A = 1$$(A \to B) = 1$$B = 1$. Así que cada comprobable afirmación también es una tautología.

Sin embargo, la Prueba Por Casos, $P(A, B, C) = (A \lor B) \to (A \to C) \to (B \to C) \to C$, no es una tautología, específicamente $P(2, 2, 2)\ne 1$. Por lo que no es demostrable.

Sin embargo, sospecho que la sustitución de la negación de los esquemas con los clásicos esquemas $(\lnot A \to \lnot B) \to B \to A$ (o el equivalente de varias reglas para la cordura bien) conduce a la Prueba Por Casos de ser comprobable, ya lo he visto en varios lógica de publicaciones.

---

KennyLau encuentra la clásica prueba en un comentario:

$$\begin{array} {rll} 1 & X \lor Y & \text{Premise} \\ 2 & X \to Z & \text{Premise} \\ 3 & Y \to Z & \text{Premise} \\ % 4 & \quad \quad \lnot Z & \text{Assumption} \\ 5 & \quad \quad \quad \quad Y & \text{Assumption} \\ 6 & \quad \quad \quad \quad Z & \text{Imp-Elim 3,5} \\ 7 & \quad \quad \lnot Y & \text{Contradiction of assumption 5, with 4 and 6} \\ 8 & \quad \quad X & \text{Needs a name, from 1 and 7} \\ 9 & \quad \quad Z & \text{Imp-Elim 2 and 8} \\ 10 & \lnot \lnot Z & \text{Contradiction of assumption 4, with 4 and 9} \\ 11 & Z & \text{Double negation elimination of 10} \\ \end{array}$$