¿Cómo puedo demostrar que lo falso no es un teorema?

Question

Definiciones

Definamos nuestro cálculo proposicional como sigue:

Alfabeto $D := \{p_i:i\in \mathbb{N}\}$ .

Operadores $\Omega := \Omega_0 \cup \Omega_2$ donde $\Omega_0 := \{f\}$ y $\Omega_2 := \{\rightarrow\}$ .

Axiomas:

• AX1 : $A\rightarrow(B\rightarrow A)$
• AX2 : $(A\rightarrow(B\rightarrow C))\rightarrow((A\rightarrow B) \rightarrow (A\rightarrow C))$
• AX3 : $((A\rightarrow f)\rightarrow f) \rightarrow A$

donde $A$ , $B$ y $C$ pueden ser fórmulas arbitrarias.

El modus ponens es la única regla de inferencia. En concreto, una fórmula $A$ es un teorema (se denota $\vdash A$ ) si existe una secuencia de fórmulas $A_1, ..., A_n$ (llamado secuencia de inferencia ) tal que $A_n=A$ y para todos $i\in \{1,...,n\}$ se mantiene lo siguiente:

• $A_i$ es un axioma, o
• existe $j,k\in \{1,...,i-1\}$ tal que $A_k=A_j\rightarrow A_i$ .

Palabra y fórmula

A palabra es una secuencia no vacía y finita de símbolos del conjunto $D\cup \Omega \cup \{(,)\}$ .

Una palabra $A$ es un fórmula si existe una secuencia finita de palabras $A_1,...,A_m$ tal que $A_m=A$ y para todos $i \in \{1,...,m\}$ se mantiene lo siguiente:

• $A_i=p_n$ para algunos $n\in \mathbb{N}$ o
• $A_i=f$ o
• $A_i=(A_j\rightarrow A_k)$ para algunos $j,k \in \{1,...,i-1\}$ .

En aras de la brevedad, se pueden omitir los paréntesis exteriores, de modo que $(A \rightarrow B)$ es lo mismo que $A \rightarrow B$ .

Problema

Demostrar que $\not\vdash f$ .

Comentarios

Este problema parece difícil porque de alguna manera tengo que demostrar que existe ninguna secuencia de inferencia que demostraría $\vdash f$ . Intuitivamente, parece que para cualquier secuencia de inferencia $A_1,...,A_n$ la fórmula $A_i$ siempre contiene al menos un símbolo de flecha para todos los $i\in \{1,...,n\}$ pero no sé cómo probarlo.

(Creo que se supone que no debo utilizar los teoremas de solidez o integridad en la demostración, ya que se introducen mucho más tarde en las notas de la conferencia).

Answer 1

Dejemos que $V(E)$ para una expresión proposicional $E$ definirse como:

• $1$ si toda valoración bivalente de $E$ es cierto
• $0$ si cualquier valoración bivalente de $E$ es falso

dado que $'f'$ se valora como falso. Así, por ejemplo, $V(\ulcorner A \lor (A \to f) \urcorner)$ tiene 2 valoraciones: $\top \lor (\top \to \bot) = \top$ así como $\bot \lor (\bot \to \bot) = \top$ por lo que su valoración es $1$ .

Demostrar que la valoración de cada axioma es $1$ (tenga en cuenta que, por ejemplo, una instancia de AX1 podría ser $(X \to Y) \to ((M \to N) \to (X \to Y))$ , es decir, el $A$ y $B$ en el axioma son expresiones y no variables proposicionales).

Demostrar que el modus ponens preserva las valoraciones positivas: si $A \to B$ y $A$ tiene valoraciones positivas, entonces $B$ debe tener una valoración positiva. El mismo cavaet, $A$ y $B$ son expresiones y no variables proposicionales.

Si lo unimos, podemos argumentar de forma inductiva que ninguna expresión demostrable tiene una valoración de $0$ . Combine esto con la valoración de $\ulcorner f \urcorner$ .

Answer 2

1. Ninguno de los axiomas es f. Por lo tanto, f sólo podría deducirse mediante el uso de la separación (es decir, modus ponens).
2. Todo desprendimiento de una fórmula tiene una de las siguientes formas 1. (B→A) originada por el axioma 1. 2. A con origen en el axioma 1. 3. ((A→B)→(A→C)) con origen en el axioma 2. 4. (A→C) originado por el axioma 2. 5. C que se origina en el axioma 2. 6. A que se origina en el axioma 3.

Observaré que todos los axiomas son sólidos, en el sentido de que ninguno de ellos se evalúa a f para cualquier valoración de sus variables.

(B→A), ((A→B)→(A→C)), y (A→C) no tienen la misma forma de f. Por tanto, no es posible derivar f de forma que tenga la forma indicada por 1., 3. o 4.

Consideremos la posibilidad de que f tenga la forma A originada por el axioma 1, o por el axioma 3. En el primer caso, el esquema del axioma 1 se instanciará como el axioma (f→(B→f)). Pero, entonces nada podría desprenderse, ya que los axiomas son sólidos. Así, (B→f) no sería derivable, y tampoco f. Por tanto, f no puede derivarse así. En el segundo caso, el esquema axiomático 3 se instanciará como el axioma (((f→f)→f)→f). Pero, el antecedente de ese axioma es ((f→f)→f), que es falso. Dado que los axiomas son sólidos, eso no permite una deducción de f. Así, las dos posibilidades 2., y 6. consideradas aquí no pueden derivar f.

Finalmente, llegamos a la posibilidad de que f se haya derivado teniendo la forma C del axioma 2. Entonces el esquema del axioma 2 se instanciará como un axioma que tiene la forma ((A→(B→f))→((A→B)→(A→f)). Para llegar a f, como todos los axiomas son verdaderos, y la regla de deducción del modus ponens es sólida, se sigue que (A→(B→f)), (A→B), y A son verdaderos. Pero, si A es verdadero, y (A→B) es verdadero, también lo es B. Entonces, como B es verdadero, (B→f) es falso. Como (B→f) es falso, y A es verdadero, eso implicaría que (A→(B→f)) es falso. Pero, eso no es posible ya que los axiomas son sólidos.

Habiendo eliminado todos los casos posibles de cómo se podría deducir f según la definición de una prueba, concluimos que f no es demostrable.