Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
8  
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
add comment

5 Answers 5

up vote 10 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|improve this answer
6  
Why unfortunately? –  Mariano Suárez-Alvarez Apr 7 '13 at 19:27
7  
@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
add comment

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|improve this answer
add comment

$$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|improve this answer
    
Nice and straightforward +) –  B. S. Aug 23 '13 at 7:04
add comment

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

share|improve this answer
1  
$\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. –  B. S. Apr 8 '13 at 6:00
    
Deserves a thumbs up my friend! +1 –  Amzoti Apr 22 '13 at 1:26
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.