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?
$\begingroup$
$\endgroup$
1
-
12$\begingroup$ 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$. $\endgroup$– Pedro ♦Commented Apr 7, 2013 at 19:29
Add a comment
|
6 Answers
$\begingroup$
$\endgroup$
2
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$).
answered Apr 7, 2013 at 19:26
-
7$\begingroup$ Why unfortunately? $\endgroup$ Commented Apr 7, 2013 at 19:27
-
9$\begingroup$ @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! $\endgroup$ Commented Apr 7, 2013 at 19:29
$\begingroup$
$\endgroup$
1
$$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}$$
$\begingroup$
$\endgroup$
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$.
$\begingroup$
$\endgroup$
3
Hint: Use $$A\subseteq B\equiv \forall x(x\in A\Longrightarrow x\in B)$$ to see it is not as you stated.
-
3$\begingroup$ $\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$? $\endgroup$– user50407Commented Apr 7, 2013 at 20:25
-
$\begingroup$ @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. $\endgroup$– MikasaCommented Apr 8, 2013 at 6:00
-
$\begingroup$ Deserves a thumbs up my friend! +1 $\endgroup$– AmzotiCommented Apr 22, 2013 at 1:26
$\begingroup$
$\endgroup$
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$.
$\begingroup$
$\endgroup$
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.
