0
$\begingroup$

I am trying to understand the use of quantifiers within the definition of a subset. The definition of a subset is:

$$ A \subseteq B \equiv \forall x(x \in A \rightarrow x \in B) $$

I am confused about, when you negate the statement of a subset, to an existential quantifier:

$$ \forall x(x \in A \rightarrow x \in B) \equiv \exists x(x \in A \land x \notin B) $$

How do these two have the same meaning? I am struggling to get to grips with the negated version.

To clarify, I understand the conversion and can do that applying the relevant laws but in idiomatic English it makes no sense. For Universal Quantifier, it means For all $x$, if $x$ is a member of $A$, then $x$ is a member of $B$. However, for a Existential Quantifier: There exists some value of such that $x$ is a member of $A$ but is not a member of $B$? That surely goes against the principle of a subset?

$\endgroup$
6
  • 1
    $\begingroup$ Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. $\endgroup$ Jul 18 '20 at 12:57
  • 1
    $\begingroup$ Don't forget that you've negated the definition of subset. "There exists an $x$ that is in $A$ but not in $B$" precisely means "$A$ is not a subset of $B$". A classical equivalent to the definition of subset is "There does not exist an $x$ that is in $A$ but not in $B$". $\endgroup$ Jul 18 '20 at 12:57
  • $\begingroup$ Oh, so, correct me if wrong. I thought that when you negated an entire statement it turned it from a positive into a negative but still maintained the original meaning. I think my understanding has been wrong on the negation of quantifiers then and when negated it means the opposite of what was originally said. $\endgroup$
    – Blue Sky
    Jul 18 '20 at 13:00
  • $\begingroup$ Yes, the whole point of negating is that it changes what the statement means. It makes it mean the opposite, in fact. Classically, if you negate it twice, you get back the original meaning, though. For instance, if $x \in \Bbb Z$, the negation of "$x$ is even" is "$x$ is odd". $\endgroup$ Jul 18 '20 at 13:01
  • 1
    $\begingroup$ Yp, double negation law. I've really screwed up here. This makes a lot of sense; trying to understand proofs and logic has always been two steps forward and one step back for me. $\endgroup$
    – Blue Sky
    Jul 18 '20 at 13:03
1
$\begingroup$

Answer: My understanding was incorrect. When you negate a statement that has a quantifier, you look to say the opposite of the original meaning. Quite surprise how I forgot about this. Please refer to the comments below.

$\endgroup$
0
$\begingroup$

Well, the general representation of an all-quantified statement is $\forall x (P(x)\Rightarrow Q(x))$, i.e. $\forall$ combined with $\Rightarrow$, while the general representation of an existential quantified statement is $\exists x (P(x)\wedge Q(x))$, i.e., $\exists$ and $\wedge$.

The above negation is perfectly fine.

$\endgroup$
2
  • $\begingroup$ I am not disputing that the negation I spoke off is incorrect. I am struggling to understand the concept. An explanation of the Existential Quantifier solution in idiomatic English would hopefully help me to understand it. All you have done is removed the truth sets and returned to representing them as P and Q, which is not helpful $\endgroup$
    – Blue Sky
    Jul 18 '20 at 12:43
  • 1
    $\begingroup$ Apologies, made a mistake with my understanding. $\endgroup$
    – Blue Sky
    Jul 18 '20 at 13:05
0
$\begingroup$

Here is used 2 formula: $$(A \Rightarrow B)= (\neg A \lor B)$$ $$\neg \forall x(R(x))= \exists x (\neg R(x))$$ Joining these formulas with negation $\neg (C \lor D)= (\neg C) \land (\neg D)$ gives answer: $$\neg \forall x (x \in A \Rightarrow x \in B)=\\= \exists x (\neg (x \in A \Rightarrow x \in B)) =\\= \exists x (\neg (x \notin A \lor x \in B )) =\\= \exists x(x \in A \land x \notin B)$$

By words: exist x such that it is in A and(but) it is not in B.

$\endgroup$
7
  • $\begingroup$ I already understood the conversion between the two and applying the relevant laws; the conditional law and the Quantifier Negation law. My issue is understanding in idiomatic English the meaning of the Existential Quantifier version of a subset? $\endgroup$
    – Blue Sky
    Jul 18 '20 at 12:49
  • $\begingroup$ For Universal Quantifier, it means For all x, if x is a member of A, then x is a member of B. However, for a Existential Quantifier: There exists some value of such that x is a member of A but is not a member of B? That surely goes against the principle of a subset? $\endgroup$
    – Blue Sky
    Jul 18 '20 at 12:50
  • $\begingroup$ The edit you made I already understand. The version in spoken English I do not. $\endgroup$
    – Blue Sky
    Jul 18 '20 at 12:53
  • $\begingroup$ Let me repeat your sentence in following way: exist $x$ such that it is in $A$, but it is not in $B$. Now it agreed with intuition of subset - no? $\endgroup$
    – zkutch
    Jul 18 '20 at 12:55
  • $\begingroup$ Yes, I understand that but how is that an alternative definition of a subset. What you have just said goes against the terminology of a subset: if x is in A, then x is in B $\endgroup$
    – Blue Sky
    Jul 18 '20 at 12:57

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.