# What is the negation of “Subset”?

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 Tamaroff Apr 7 '13 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? –  Mariano Suárez-Alvarez Apr 7 '13 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! –  Tom Oldfield Apr 7 '13 at 19:29

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$.

-

$$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] \\ \\ & \equiv \exists x [\lnot\lnot(x \in A) \land \lnot (x \in B)] \\ \\ & \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 +) –  Babak S. Aug 23 '13 at 7:04

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 Apr 7 '13 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. –  Babak S. Apr 8 '13 at 6:00
Deserves a thumbs up my friend! +1 –  Amzoti Apr 22 '13 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$.

-