I am trying to prove that equisatisfiability is an equivalence relation and I have to name the number of equivalence classes.
I know I have to prove that it is reflexive, symmetric and transitive. This is what i have so far:
(φ ≈ ψ) if φ is satisfiable ⇐⇒ ψ is satisfiable
- Reflexive: φ ≈ φ is true because when φ is satisfiable <--> φ is satisfiable
- Symmetric: φ ≈ ψ implies ψ ≈ φ? Yes, coz φ ⇐⇒ ψ is the same as ψ ⇐⇒ φ
- Transitive: When φ ≈ ψ and ψ ≈ χ it implies that φ ≈ χ
Is my way of thinking correct? I am not really sure if this is enough for to prove it.
When it comes to the equivalence classes I am totally stuck. Maybe someone can help me here a little bit? Thank you.