1
$\begingroup$

The quantified definition for a proper subset can be found here.

$A \subset B \leftrightarrow \forall x [x \in A \rightarrow x \in B] \land \exists x [x \notin A \land x \in B]$

I want to determine $A \not \subset B$ (A not proper subset B). Can I simply negate $A \subset B$ for $A \not \subset B$? $$\neg \Big(\forall x [x \in A \rightarrow x \in B] \land \exists x [x \notin A \land x \in B]\Big) \\ \leftrightarrow \neg \Big(\forall x [\neg (x \in A) \vee x \in B] \land \exists x [x \notin A \land x \in B]\Big) \\ \leftrightarrow \exists x [x \in A \wedge x \notin B] \vee \forall x [x \in A \vee x \notin B]$$ The part before the first $\vee$ looks correct, but I'm not so sure for the second part: $... \vee \forall x [x \in A \vee x \notin B]$

$\endgroup$
  • $\begingroup$ I prefer some x in A-B or A = B. $\endgroup$ – William Elliot Mar 12 '18 at 4:23
  • $\begingroup$ @wybkqqnob what do you mean "what do you mean?" William's comment says that a convenient equivalent expression to $A\not\subset B$ is $(A\setminus B\neq \emptyset\vee A=B)$. Note, the first half is exactly what you wrote, $(\exists x[x\in A\wedge x\notin B]$, but in a way that is more comfortable to most people. The second parts are not by themselves directly equivalent, but through some trickery one can see that the total statements are in fact equivalent. (to see this, consider restricting the second half of your attempt to the case where the first half is false) $\endgroup$ – JMoravitz Mar 12 '18 at 4:26
  • $\begingroup$ Remember that $P\vee Q \equiv P\vee (\neg P \wedge Q)$ $\endgroup$ – JMoravitz Mar 12 '18 at 4:32
  • $\begingroup$ @JMoravitz Aha! Now it makes sense $\endgroup$ – wybkqqnob Mar 12 '18 at 4:35
0
$\begingroup$

Yes, that's the correct negation, though you can take one more step and express the last universal as a quantified implication .

$$\begin{array}{rcl} &&\neg \Big(\big(\forall x~[x \in A \to x \in B]\big) ~\land~ \big(\exists x~[x \notin A \land x \in B]\big)\Big) \\ &\iff& \big(\exists x~[x \in A \wedge x \notin B]\big)~\vee~\big(\forall x~[x \in A \vee x \notin B]\big)\\&\iff&\big(\exists x~[x \in A \wedge x \notin B]\big)~\vee~\big(\forall x~[x\in B\to x \in A]\big)\end{array}$$

Which looks similar to the original, except that it is a disjunction.

$A$ is not a subset of $B$ iif there is an element in $A$ that is not in $B$, or every element in $B$ is in $A$.   That effectively says: "There are bits of $A$ outside $B$ or they are actually the same set".

$$\begin{array}{rcl} \neg(A\subset B) &\iff&\neg(A\subseteq B~\wedge~B\nsubseteq A ) \\ A\not\subset B&\iff& A\nsubseteq B~\vee~B\subseteq A\end{array}$$

$\endgroup$
0
$\begingroup$

The second quantifier is needed to handle cases where $A=B$ (i.e. the equivalence case that distinguishes $\subset$ from $\subseteq$). It is easy to check that in this case, the first quantifier is false but the second one is true.

$\endgroup$
  • $\begingroup$ So the expression on the last line is logically equivalent to $A \not \subset B$? $\endgroup$ – wybkqqnob Mar 12 '18 at 4:22
  • $\begingroup$ @wybkqqnob Yes. $\endgroup$ – Parcly Taxel Mar 12 '18 at 4:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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