# What is the negation of "$A\subseteq B$"?

I'm trying to prove something using an indirect proof, so I need to know the negation of $A\subseteq B$. I'm assuming it's $A\nsubseteq B$, but what does this mean symantically? Is it $\forall x\in A,\ x\notin B$? Is it safe to say that $A$ and $B$ are disjoint at that point?

• Note that $A\subseteq B\iff A-B=\varnothing$. Then saying $\neg(A\subseteq B)$ is the same as saying $A-B\neq\varnothing$, that is, there exists an $a\in A$ such that $a\notin B$.
– Pedro
Commented Apr 7, 2013 at 19:29

Unfortunately not. $A \subset B$ means $\forall x \in A, x \in B$, so the negation is $\exists x \in A, x \not \in B$ i.e. there is some element of $A$ that is not in $B$.

Intuititively, since $A \subset B$ means that $A$ is "entirely contained in $B$". $A$ not being a subset of $B$ then means that $A$ is not entirely contained in $B$. This includes the situation that they are disjoint, but also includes the situation where some elements of $A$ are in $B$, but not all of them (i.e. $A$ is partially contained in $B$).

• Why unfortunately? Commented Apr 7, 2013 at 19:27
• @MarianoSuárez-Alvarez I don't like telling people they're wrong! I guess I mean unfortunately for the OP rather than unfortunately for maths, since for the latter it is certainly rather useful! Commented Apr 7, 2013 at 19:29

$$A \subseteq B \equiv \forall x( x \in A \rightarrow x \in B)\tag{1}$$

Negating $(1)$ gives us:

\begin{align} A \not\subseteq B & \equiv \lnot \forall x(x\in A \rightarrow x \in B) \\ \\ & \equiv \exists x \lnot(x\in A \rightarrow x \in B) \\ \\ & \equiv \exists x \lnot[\lnot(x \in A) \lor (x \in B)] \tag{p \to q \equiv \lnot p \lor q}\\ \\ & \equiv \exists x [\lnot\lnot(x \in A) \land \lnot (x \in B)] \tag{DeMorgan's}\\ \\ & \equiv \exists x [x \in A \land \lnot (x \in B)] \\ \\ & \equiv \exists x (x\in A \land x \notin B) \tag{A\not \subseteq B} \end{align}

• Nice and straightforward +) Commented Aug 23, 2013 at 7:04

Remember the the definition of subset: if $A \subseteq B$, then every element of A is an element of $B$. The negation of a statements like "every object is " or "all objects are" is the statement "at least one object is not." Thus, $A \not \subseteq B$ means that at least one element of A is not an element of $B$.

Hint: Use $$A\subseteq B\equiv \forall x(x\in A\Longrightarrow x\in B)$$ to see it is not as you stated.

• $\forall x\in A\implies x\in B$ does not seem correct to me. Presumably you mean $\forall x, x\in A\implies x\in B$?
– user50407
Commented Apr 7, 2013 at 20:25
• @MichaelCorleone: Yes exactly! It is obvious that we are speaking of elements in $A$ firstly. Thanks for noting me that. What you noted is definitely right. Commented Apr 8, 2013 at 6:00
• Deserves a thumbs up my friend! +1 Commented Apr 22, 2013 at 1:26

To address the last part, which wasn't your main question: The statement you have, "$\forall x\in A$, $x\notin B$" is indeed equivalent to $A$ and $B$ being disjoint. But quite clearly $A$ not being a subset of $B$ is much weaker than $A$ and $B$ being disjoint, for example $B$ could even be a proper subset of $A$.

We can use that

• $$A\subset B$$ is equivalent to $$A\cap B^c=\emptyset$$

so then if you negate it:

• $$A\not\subset B$$ is equivalent to $$A\cap B^c\neq \emptyset$$.

That is, there exist $$a\in A$$ such that $$a\not\in B$$, which is the definition of $$A\subset B$$ negated. For me, the later expression is more clear. Hope it helps someone else.