30

§7 Dos metateoremas

Existen varios resultados potentes que permiten simplificar mucho las prue-

bas de la logica proposicional. En el sentido estricto no son teoremas del

CPC sino teorema sobre deducciones, o en particular, teoremas sobre teo-

remas (con precision, teoremas matematicos sobre teoremas del CPC). El

primer resultado de esta seccion codifica la practica matematica de “suponer

el antecedente y deducir el consecuente” cuando se quiere demostrar una

implicacion.

Teorema 7.1 (Teorema de la Deduccion). Sea Σ ⊆ F(L) un conjunto de

formulas, posiblemente vacıo, y sean α, β ∈ F(L) formulas.

Si Σ, α ` β entonces Σ ` α→ β.

Las referencias al teorema de la deduccion se abrevian TD. En realidad se

trata de una equivalencia, la otra implicacion es inmediata por MP.

Demostracion. Si β1, β2, β3, . . . , βn = β es una deduccion de β a partir de

Σ∪{α}, se demuestra por induccion (matematica completa) que Σ ` α→ βi

para cada i (1 ≤ i ≤ n). En particular, para i = n resulta Σ ` α→ β.

Paso inicial. La formula β1 no puede deducirse de formulas anteriores luego

es un axioma o una premisa. En el primer caso se tiene lo siguiente.

1. β1 Ax

2. β1 → (α→ β1) Ax 1

3. α→ β1 MP/1, 2

Ası α→ β1 es un teorema del CPC, luego tambien Σ ` α→ β1.

En el caso en que β1 es una premisa, de nuevo hay dos posibilidades. Si

β1 ∈ Σ entonces basta sustituir Ax por P en la deduccion anterior, y se

31

obtiene Σ ` α→ β1 de manera directa. Si β1 = α entonces α→ β1 = α→ α

que es un teorema por el ejemplo 5.5, de manera que de nuevo Σ ` α→ β1.

Paso inductivo. Sea k > 1 y supongase que Σ ` α → βi para cada i con

1 ≤ i < k. Si βk es un axioma o una premisa entonces Σ ` α → βk como

en el paso inicial. Si se obtiene por MP entonces existen formulas anteriores

de la forma βj, βj → βk y por hipotesis de induccion se tiene Σ ` α → βj,

Σ ` α → (βj → βk). Supongase que la primera deduccion requiere M pasos

y la segunda N −M pasos, entonces a la yuxtaposicion de las dos sucesiones

se anaden las lıneas siguientes.

N + 1. (α→ (βj → βk))→ ((α→ βj)→ (α→ βk)) Ax 2

N + 2. (α→ βj)→ (α→ βk) MP/N,N + 1

N + 3. α→ βk MP/M,N + 2

De esta manera Σ ` α→ βk.

La prueba anterior es constructiva porque dada una deduccion de β, siguien-

do en cada renglon los pasos de la demostracion es posible elaborar una

deduccion de α→ β.

El teorema de la deduccion, aplicado de manera reiterada, permite ver cual-

quier deduccion con finitas premisas como un teorema del CPC.

Corolario 7.2. Sean α1, α2, . . . , αn, β ∈ F(L) formulas.

α1, . . . , αn ` β si y solo si ` α1 → (α2 → · · · (αn → β) · · · ).

Ejemplo 7.3. ` (α→ β)→ ((β → γ)→ (α→ γ))

Demostracion. Por TD, basta probar α → β ` (β → γ) → (α → γ) y, de

nuevo por TD, basta probar α → β, β → γ ` α → γ. Este es el ejemplo

6.4, sin embargo ahora la prueba puede simplificarse porque, por TD, basta

probar α → β, β → γ, α ` γ. Esta deduccion se prueba de manera sencilla

con dos aplicaciones de MP.

32

Ejemplo 7.4. ` ¬¬α→ α

Demostracion. Se obtiene por TD del ejemplo 6.9.

Ejemplo 7.5. ` α→ ¬¬α

Demostracion.

1. (¬¬¬α→ ¬α)→ (α→ ¬¬α) Ax 3

2. ¬¬¬α→ ¬α Teo 7.4

3. α→ ¬¬α MP/1, 2

Ejemplo 7.6 (Doble Negacion II). α ` ¬¬α

Demostracion. Se obtiene por MP del ejemplo anterior (7.5).

Otro importante metateorema codifica el metodo de reduccion al absurdo

(RA), tan querido en la practica matematica.

Teorema 7.7 (Reduccion al Absurdo). Sea Σ ⊆ F(L) un conjunto de for-

mulas, posiblemente vacıo, y sea ϕ ∈ F(L) una formula.

Si Σ,¬ϕ ` α y Σ,¬ϕ ` ¬α para alguna α ∈ F(L), entonces Σ ` ϕ.

Demostracion. Si τ es cualquier teorema (o axioma) entonces por las dedu-

cciones 6.5 y 6.10 se tiene α,¬α ` ¬τ luego por hipotesis Σ,¬ϕ ` ¬τ y por

TD resulta Σ ` ¬ϕ→ ¬τ . Supongase que esta deduccion requiere N pasos,

entonces a ella se anaden las lıneas siguientes.

N + 1. (¬ϕ→ ¬τ)→ (τ → ϕ) Ax 3

N + 2. τ → ϕ MP/N,N + 1

N + 3. τ Teo

N + 4. ϕ MP/N + 2, N + 3

De esta manera Σ ` ϕ.

33

Corolario 7.8. Sea Σ ⊆ F(L) un conjunto de formulas y sean ϕ, α ∈ F(L)

formulas.

1. Si Σ, ϕ ` α,¬α entonces Σ ` ¬ϕ

2. Si Σ,¬ϕ ` ϕ entonces Σ ` ϕ

Ejemplo 7.9 (No Contradiccion). ` ¬(α ∧ ¬α)

Demostracion. Por RA (caso (1 ) del corolario 7.8) basta probar α ∧ ¬α `α,¬α, lo cual es consecuencia inmediata de los axiomas 4 y 5.

Ejemplo 7.10 (Modus Tollendo Tollens). α→ β,¬β ` ¬α

Demostracion. Por RA ((1 ) del corolario 7.8) basta probar α → β,¬β, α `β,¬β. La primera deduccion es inmediata por MP ; la segunda es mas in-

mediata aun porque la conclusion esta entre las premisas.

El ejemplo siguiente se obtiene aplicando dos veces TD a Tollendo Tollens,

y en cierto modo es un “complemento” del axioma 3.

Ejemplo 7.11. ` (α→ β)→ (¬β → ¬α)

Ejemplo 7.12. α→ β,¬α→ β ` β

Demostracion. Por RA ((2 ) del corolario 7.8) basta ver α→ β,¬α→ β,¬β `β.

1. α→ β P

2. ¬β P

3. ¬α Ded 7.10/1, 2

4. ¬α→ β P

4. β MP/3, 4

34

En esta presentacion, el camino para llegar al proximo teorema es bastante

dispendioso.

Ejemplo 7.13 (Tercero Excluıdo). ` α ∨ ¬α

Demostracion. Resulta de inmediato aplicando el ejemplo 7.12 a los axiomas

α→ (α ∨ ¬α) y ¬α→ (α ∨ ¬α).

Ejercicios.

7.1. Demuestre el siguiente teorema del CPC.

(α→ β) ∨ (β → γ)

[Sugerencia: Use el resultado 7.12.]

7.2. Demuestre:

a) ¬(α ∧ β) ` ¬α ∨ ¬β

b) ¬(α ∨ β) ` ¬α ∧ ¬β

c) ¬(α→ β) ` α ∧ ¬β

d) ¬α ∨ ¬β ` ¬(α ∧ β)

e) ¬α ∧ ¬β ` ¬(α ∨ β)

f) α ∧ ¬β ` ¬(α→ β)

7.3. A partir del ejercicio anterior concluya:

a) ¬α ∨ β ` α→ β b) α→ β ` ¬α ∨ β

7.4. Demuestre el razonamiento presentado como ejemplo en el §1 y al

comienzo de la seccion 1.2.

7.5. Demuestre:

a) α ∨ β ` (α→ β)→ β

b) α→ (β → γ) ` (α ∧ β)→ γ

c) (α→ β)→ β ` α ∨ β

d) (α ∧ β)→ γ ` α→ (β → γ)

35

7.6. Demuestre:

a) α→ β, γ → δ ` (β → γ)→ (α→ δ)

b) α→ β, γ → δ ` (α ∧ γ)→ (β ∧ δ)

7.7. Demuestre:

a) (α→ β) ∧ ¬γ ` α→ ¬(β → γ) b) ¬α, γ → ¬β ` γ → ¬(α ∨ β)

7.8. Demuestre que si α ` β entonces ¬β ` ¬α.