Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 11 down vote accepted

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

share|cite|improve this answer
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

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

share|cite|improve this answer
Nice and straightforward +) – Babak S. Aug 23 '13 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$.

share|cite|improve this answer

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

share|cite|improve this answer
$\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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.