Resolucion ej 13.d

[Luciana Benotti]

Hola chicos,

Les envio la resolucion del ejercicio 13d, ya que varios lo
consultaron y es un ejercicio dificil (si a alguien se le ocurre una
demo mas facil mandenla a la lista por favor :)).

Mi estrategia fue primero transformar el enunciado para avecharse de
las simetrias que
presenta. O dicho de otra manera reescribir el enunciado
∀x : : T.x ≡ ¬S.x ⇒ ( ∃x : : T.x ≡ ¬ ∀x : : S.x )  de la siguiente
forma (usando la definicion de equivalencia como una doble
implicacion):
(1) (∀x : : T.x ⇒ ¬S.x) ∧ (∀x : : ¬S.x ⇒ T.x) ⇒ ( ∃x : : T.x ⇒  ∃x : :
¬ S.x ) ∧ ( ∃x : : ¬ S.x ⇒ ∃x : : T.x )

Ahora, (1) se puede escribir como (A ∧ B ⇒ C ∧ D) donde:
- A es (∀x : : T.x ⇒ ¬S.x)
- B es (∀x : : ¬S.x ⇒ T.x)
- C es ( ∃x : : T.x ⇒  ∃x : : ¬ S.x )
- D es ( ∃x : : ¬ S.x ⇒ ∃x : : T.x )

Dado que ((A ⇒ C) ∧ (B ⇒ D) ⇒ (A ∧ B ⇒ C ∧ D) es valido vamos a
demostrar (A ⇒ C) ∧ (B ⇒ D) en lugar de demostrar (A ∧ B ⇒ C ∧ D). Si
demostrarmos que (A ⇒ C) ∧ (B ⇒ D) es un teorema, entonces (A ∧ B ⇒ C
∧ D) es un teorema.

Para demostrar (A ⇒ C) ∧ (B ⇒ D) vamos a demostrar primero (A ⇒ C).
(A ⇒ C) es (∀x : : T.x ⇒ ¬S.x) ⇒ ( ∃x : : T.x ⇒  ∃x : : ¬ S.x )

(∀x : : T.x ⇒ ¬S.x) ⇒ ( ∃x : : T.x ⇒  ∃x : : ¬ S.x ) se puede
transformar usando currificacion y despues la demstracion sale usando
distributiva del ∃ con ∧, instanciacion y modus ponens (ademas de
monotonia).

Una vez que terminen con (A ⇒ C), fijense que (B ⇒ D):  (∀x : : ¬S.x ⇒
T.x) ⇒  ( ∃x : : ¬ S.x ⇒ ∃x : : T.x )
es muy parecida (es simplemente una sustitucion).

Si quedan dudas respondan a este email o nos pueden preguntar en el
horario de consulta.

Saludos, Luciana.