Buenas!, mi problema es que no logro encontrar un contraejemplo para el si solo si, cualquier tipo de sugerencia se agradece. Desde ya muchas gracias!
Hola Agustín:
Te paso algunas ideas de cómo encararlo:
Hay que probar que (1) y (2) no son equivalentes.
- (1) M ⊨ φ ↔ ψ
- (2) M ⊨ φ ⇔ M ⊨ ψ
Pista 1: Lo que se puede probar es que (2) no implica (1) (con lo cual ya no se cumple la doble implicancia)
Para eso debemos encontrar M, φ y ψ que cumplan (2) y no cumplan (1).
Pista 2: Alcanza con considerar una sola variable libre: {x} = FV(φ) = FV(ψ).
Entonces, nos queda:
- (1) M ⊨ ∀x (φ ↔ ψ)
- (2) M ⊨ ∀xφ ⇔ M ⊧ ∀xψ
Pista 3: Consideremos un caso en que (2) se cumpla porque ambos componentes de la doble implicancia son falsos (esta es la clave del contra ejemplo)
Resumiendo, buscamos M, ϕ y ψ tales que:
- {x} = FV(φ) = FV(ψ).
- M ⊭ φ ↔ ψ (no cumple 1)
- M ⊭ ∀xφ y M ⊭ ∀xψ (cumple 2)
Ultimas sugerencias:
- buscar ϕ y ψ lo más sencillo posible.
- buscar M con un universo binario, aunque también puede salir fácil con los naturales.