Skip to main content
Mathematics LibreTexts

4.3: Negations

  • Page ID
    23901
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Recall part of the symbolization key of Section \(4.1\):

    \(\mathcal{U}\): The set of all people.

    \(A\): The set of all angry people.

    \(H(x)\): The set of all happy people.

    Consider these further assertions:

    1. No one is angry.
    2. Not everyone is happy.

    Assertion 15. can be paraphrased as, “It is not the case that someone is angry.” (In other words, “It is not the case that there exists a person who is angry.”) This is the negation of the assertion that there exists an angry person, so it can be translated using “not” and “there exists”: \(\neg \exists x,(x \in A)\).

    It is important to notice that Assertion 15. is equivalent to the assertion that “Everyone is nonangry.” This assertion can be translated using “for all” and “not”: \(\forall x, \neg (x \in A)\), or, in other words, \(\forall x, (x \notin A)\). In general: \[\neg \exists x, \mathcal{A} \text { is logically equivalent to } \forall x, \neg \mathcal{A} \text {. }\]
    This means that the negation of a “\(\exists\)” assertion is a “\(\forall\)” assertion.

    Assertion 16. says it is not true that everyone is happy. This is the negation of the assertion that everyone is happy, so it can be translated using “not” and “\(\forall\)”: \(\neg\forall x,(x \in H)\).

    Moreover, saying that not everyone is happy is the same as saying that someone is not happy. This latter assertion translates to \(\exists x, (x \notin H)\). In general: \[\neg \forall x, \mathcal{A} \text { is logically equivalent to } \exists x, \neg \mathcal{A} \text {. }\]
    This means that the negation of a “\(\forall\)” assertion is a “\(\exists\)” assertion.

    Just as for “\(\forall x\)” and “\(\exists x\),” the bounded quantifiers “\(\forall x \in X\)” and “\(\exists x \in X\)” are interchanged under negation:

    \(\neg \forall x \in X, \mathcal{A} \text { is logically equivalent to " } \exists x \in X, \neg \mathcal{A} \text {. }\)
    \(\neg \exists x \in X, \mathcal{A} \text { is logically equivalent to } " \forall x \in X, \neg \mathcal{A} \text {. }\)

    There is no fundamental difference between this and the previous examples; we have simply replaced \(\mathcal{U}\) with the set \(X\).

    In summary: if you need to negate an assertion that starts with a quantifier, switch the quantifier to the other one (from \(\exists\) to \(\forall\) or vice-versa), and then continue, negating the remainder of the assertion.

    To perform the additional negations, you will want to remember the following rules from Exercise \(1.7.5\):

    Rules of Negation

    \(\neg(A \vee B) \text { is logically equivalent to } \neg A \& \neg B \text {. }\)
    \(\neg(A \& B) \text { is logically equivalent to } \neg A \vee \neg B \text {. }\)
    \(\neg(A \Rightarrow B) \text { is logically equivalent to } A \& \neg B \text {. }\)
    \(\neg \neg A \text { is logically equivalent to } A \text {. }\)

    Example \(4.3.1\).

    Let us simplify the Assertion (*) \[\neg \forall s \in S,(((s \in A) \vee(s \in B)) \&((s \in C) \Rightarrow(s \notin D))) .\]
    We bring \(\neg\) inside the quantifier, switching from \(\forall\) to \(\exists\): \[\exists s \in S, \neg(((s \in A) \vee(s \in B)) \&((s \in C) \Rightarrow(s \notin D))) .\]
    Now, we switch \(\&\) to \(\vee\), and apply \(\neg\) to each of the two terms: \[\exists s \in S,(\neg((s \in A) \vee(s \in B)) \vee \neg((s \in C) \Rightarrow(s \notin D))) .\]
    Next, the connective \(\vee\) in the left term is changed to \(\&\) (and \(\neg\) is applied to the subterms), and the rule for negating \(\Rightarrow\) is implied to the right term: \[\exists s \in S,((\neg(s \in A) \& \neg(s \in B)) \vee((s \in C) \& \neg(s \notin D))) .\]
    Finally, we use the abbreviation \(\notin\) in the first two terms, and eliminate the double negative in the final term: \[\exists s \in S,(((s \notin A) \&(s \notin B)) \vee((s \in C) \&(s \in D))) .\]
    This final result is logically equivalent to Assertion (*) above.

    Solution

    Add text here.

    The same principles apply to negating assertions in English.

    Example \(4.3.2\).

    Suppose that we want to negate

    “Every umbrella either needs a new handle or is not big enough.”

    We create a symbolization key:

    \(U\): The set of all umbrellas.

    \(H\): The set of all umbrellas that need a new handle.

    \(B\): The set of all umbrellas that are big enough.

    Now we can translate the assertion as \(\forall u \in U, \bigl( (u \in H) \vee (u \notin B)\bigr).\) Negating this, we have \[\neg\forall u \in U, \bigl( (u \in H) \vee (u \notin B)\bigr).\]
    We have just learned that this is equivalent to \[\exists u \in U, \neg\bigl( (u \in H) \vee (u \notin B)\bigr),\]
    which can be simplified to \[\exists u \in U, \bigl((u \notin H) \& \neg(u \notin B)\bigr),\]
    and finally, eliminating the double negative, this is equivalent to \[\exists u \in U, \bigl((u \notin H) \& (u \in B)\bigr).\]
    Now we translate back to English:

    “There is some umbrella that does not need a new handle and is big enough.”

    Applying these rules systematically will enable you to simplify the negation of any assertion (no matter whether it is expressed in English or in ).

    English is more open to interpretation and inexactitude than . Therefore, when we need to negate an English assertion in this chapter, we translate it into , perform the negation, and translate back. You will also be expected to do this. Later, when you are doing proofs, you might be able to work directly with the English version, although you may find it helpful to keep the version in mind.

    Warning.

    To make an assertion, quantifiers must be applied to predicates — they cannot stand by themselves. That is, an assertion must be of the form \(\exists x \in X, P(x)\) or \(\forall x\in X, P(x)\), not just \(\exists x\in X\) or \(\forall x \in X\). For example, some students erroneously try to translate the assertion “there exists an umbrella” as but that is not an assertion. The problem is that it is not a complete sentence: it would translate into English as “there exists an umbrella, such that.” (Notice the “such that” left dangling at the end.)

    One way to obtain a correct symbolization is to rephrase the original assertion as: “there exists something that is an umbrella.” This translates to \(\exists x, (x \in U)\), which is a correct symbolization. Its negation simplifies to \(\forall x, (x \notin U)\), which means “every thing that exists is not an umbrella.”

    If \(\exists u \in U\) were an assertion, then, by applying the rules for negation, its negation would be “\(\forall u \in U, \neg\),” which is not a complete sentence: its English translation is “for all \(u\) in \(U\), it is not true that.” To avoid such mistakes, remember that every quantifier must always be followed by a predicate.

    Exercise \(4.3.3\).

    Negate each of the assertions in Exercise \(4.2.4\). Express your answer both in the language of and in English (after simplifying).

    Exercise \(4.3.4\).

    Negate each of the following assertions of (and simplify, so that \(\neg\) is not applied to anything but predicates or assertion variables). Show your work!

    1. \((L \Rightarrow \neg M) \& (M \vee N)\)
    2. \(\bigl( (a \in A) \& (b \in B) \bigr) \vee (c \in C)\)
    3. \(\forall a \in A, \Bigl( \bigl( (a \in P) \vee (a \in Q) \bigr) \& (a \notin R) \Bigr)\)
    4. \(\forall a \in A, \Bigl( (a \in T) \Rightarrow \exists c \in C, \bigl( (c \in Q) \& ( c \mathrel{R} a) \bigr) \Bigr)\)
    5. \(\forall x, \biggl( (x \in A) \& \Bigl( \exists \ell \in L, \bigl( (x \mathrel{B} \ell ) \vee (\ell \in C) \bigr) \Bigr) \biggr)\)
    6. \(A \Rightarrow \Bigl( \bigl( \exists x \in X, (x \in B) \bigr) \vee \bigl( \forall e \in E, \exists d \in D, (e \mathrel{C} d) \bigr) \Bigr)\)
    7. \(\forall a \in A, \exists b \in B, \exists c \in C, \forall d \in D, \Bigl( (a \mathrel{K} b) \& \bigl( (a \mathrel{Z} c) \vee (b > d) \bigr) \Bigr)\)
    Exercise \(4.3.5\).

    Simplify each assertion. Show your work!

    1. \(\neg \forall a \in A, \bigl( (a \in P) \vee (a \in Q) \bigr)\)
    2. \(\neg \exists a \in A, \bigl( (a \in P) \& (a \in Q) \bigr)\)
    3. \(\neg \forall x \in X, \exists y \in Y, \bigl( (x \in A) \& (x \mathrel{C} y) \bigr)\)
    4. \(\neg \forall s \in S, \biggl( (s \in R) \Rightarrow \Bigl( \exists t \in T, \bigl( (s \neq t) \& (s \mathrel{M} t) \bigr) \Bigr) \biggr)\)
    Answer

    Add texts here. Do not delete this text first.

    Remark \(4.3.6\).

    Unfortunately, there is no nice, compact way of negating assertions involving uniqueness. For example, if we want to say “It is not the case that there is a unique person who owes Hikaru money,” we need to say that “Either no one owes Hikaru money, or more than one person owes Hikaru money.” This translates to \[(H = \emptyset) \vee \bigl(\exists h_1 \in H, (\exists h_2 \in H, h_2 \neq h_1)\bigr).\]
    In general, if you come across a situation where you want to negate an assertion that involves uniqueness, it is a good idea to rewrite the assertion without using “\(\exists!\).” You should have no difficulty negating this rephrased assertion.

    4.3A. Vacuous Truth.

    Note that if the assertion \[\exists x \in A, \neg P(x)\]
    is true (where \(A\) is any set and \(P(x)\) is any unary predicate), then there must exist an element \(a\) of \(A\), such that \(P(a)\) is false. Ignoring the last condition (about \(P(a)\)), we know that \(a \in A\), so \(A \neq \emptyset\). That is, we know: \[\text { If the assertion } \exists x \in A, \neg P(x) \text { is true, then } A \neq \varnothing \text {. }\]
    So the contrapositive is also true: \[\text { If } A=\varnothing, \text { then the assertion } \exists x \in A, \exists P(x) \text { is false. }\]
    Therefore, the assertion \(\exists x \in \emptyset, \neg P(x)\) is false, so its negation is true: \[\text { The assertion } \forall x \in \varnothing, P(x) \text { is true. }\]
    Since \(P(x)\) is an arbitrary predicate, this means that any assertion about all of the elements of the empty set is true; we say it is vacuously true. The point is that there is nothing in the empty set to contradict whatever assertion you care to make about all of the elements.

    Example \(4.3.7\).

    If you say, “All of the people on Mars have purple skin,” and there are not any people on Mars, then you have spoken the truth — otherwise, there would have to be some person on Mars (whose skin is not purple) to provide a counterexample.

    In summary:

    any assertion about all of the elements of the empty set is vacuously true.

    Exercise \(4.3.8\).

    Which of the following English assertions are vacuously true (in the real world)?

    1. All quintuplets are sickly.
    2. All standard playing cards that are numbered fifteen, are green.
    3. All prime numbers that are divisible by 12, have 5 digits.
    4. All people who have been to the moon are men.
    5. All people who do not breathe are dead.
    Answer

    Add texts here. Do not delete this text first.


    This page titled 4.3: Negations is shared under a CC BY-NC-SA 2.0 license and was authored, remixed, and/or curated by Dave Witte Morris & Joy Morris.