using quantifiers for predicates, prenex normal form

55 Views Asked by At

Say we have $A=B$

iff $\forall x (x \in A \Rightarrow x \in B$) and $\forall y (y \in B \Rightarrow y \in A$)

can we write the above as: $\forall x [(x \in A \Rightarrow x \in B$) and $(x \in B \Rightarrow x \in A$)] if so, why? I don't really understand equivalent formulations of these statements.

1

There are 1 best solutions below

4
On

See rules for prenex operations.

But for the question above, we have to use the rules for "distributing" quantifiers :

$∀x(P(x) ∧ Q(x))$ is equivalent to $(∀xP(x) ∧ ∀xQ(x))$.

Thus, $∀x(x∈A \Rightarrow x∈B) \land ∀y(y∈B \Rightarrow y∈A)$ is equivalent to :

$∀x \ [(x∈A \Rightarrow x∈B) \land (x∈B \Rightarrow x∈A)]$,

and this, in turn, is equivalent to :

$∀x(x∈A \Leftrightarrow x∈B)$.