# Negating $(\forall a \in A)(\exists b \in B)(a \in C \leftrightarrow b\in C)$?

I'm not quite sure how to go about doing this. When negating I know the quantifiers themselves will be negated meaning that $\forall$ would become $\exists$ and vice-versa. Also I know that $\leftrightarrow$ can be written for example as $(\lnot a\in C \lor b \in C)\land(\not b \in C \lor a \in C)$. And this can be negated using De Morgan's laws. However what about the $\in$ would I have to negate those too? Can you please show me how that's done.

• You may also note that $\neg(p\leftrightarrow q)\iff (\neg p)\leftrightarrow q$ – Hagen von Eitzen Oct 16 '13 at 18:09
• $\neg a\in A$ is the negation of $a\in A$. It is also written as $a\notin A$ – drhab Oct 16 '13 at 18:09

$$\lnot(x \in X) \equiv x \notin X$$

$$\lnot\Big((\forall a \in A)(\exists b \in B)(a \in C \leftrightarrow b\in C)\Big)\tag{1}$$

$$\equiv \lnot \Big[(\forall a \in A)(\exists b \in B)\Big((a \notin C \lor b \in C)\land( b \notin C \lor a \in C)\Big)\Big]\tag{2}$$

$$\equiv (\exists a \in A)(\forall b \in B) \Big( \lnot(a\notin C \lor b \in C) \lor \lnot(b\notin C \lor a\in C)\Big)\tag{3}$$

$$\equiv (\exists a \in A)(\forall b \in B) \Big((a\in C \land b \notin C) \lor (b\in C \land a\notin C)\Big)\tag{4}$$

$(1)$ is the negation of the given proposition.

$(2)$ is equivalent to the negated proposition, as you note.

$(3)$ Negation moves inward, changing the quantifiers, respectively, finally negating the quantified expression, and applies DeMorgan's Rule.

$(4)$ By DeMorgan's.

• Oh, I see. Also just wondering when negating the expression $(\forall a \in A)$ would I only negate the $\forall$ or would I have to negate the $\in$ as well? What I mean is would the negation be $\exists a\in A$ or would it be $\exists a\notin A$ – JustAnotherUser Oct 16 '13 at 18:22
• You can simply remove that negation by moving it progressively inward. – amWhy Oct 16 '13 at 18:32
• @amWhy: Nice write up +1 – Amzoti Oct 18 '13 at 0:40