Skip to main content

Discrete Mathematics for Computer Science: An open educational resource.

Ken Levasseur, Al Doerr, Michiel Smid, Oscar Levin, Charles M. Grinstead, J. Laurie Snell, Eric Lehman, F. Thomson Leighton, Albert R Meyer, Jeff Erickson, Kenneth P. Bogart, Carol Chritchlow, David Eck, OpenDSA Project, L.J. Miller

Section 5.3 Proofs of Quantified Statements

Formal proofs of quantified expressions can use all the techniques presented in sections Section 5.1 - Section 5.2 , plus some specialized forms.

Subsection 5.3.1 Proofs With Quantifiers

Proving quantified statements often requires invoking one or more the following inference rules.
Table 5.3.1. Inference Rules for Quantified Statements
Existential Instantiation \((\exists x)(p(x)) \Rightarrow p(c)\) \(c \in U\)
Existential Generalization \(p(c) \Rightarrow (\exists x)(p(x)) \) \(c \in U\)
Universal Instantiation \((\forall x)(p(x)) \Rightarrow p(c) \) \(c\) is any arbitrary element of \(U\)
Universal Generalization \(p(c) \Rightarrow (\forall x)(p(x)) \) \(c\) is any arbitrary element of \(U\)
The instantiation rules are used to fix a variable in a proposition over a universe to a single (but perhaps unspecified) value in order to apply the rules of propositional logic. The generalization rules are used to expand results from a fixed variable to the entire universe. Commonly in less formal proofs, such as those in mathematics, these are implied but not directly stated in the proof.

Definition 5.3.2. Constructive Proof.

Constructive proofs are used to prove theorems of the form: \((\exists n)(p(n))\text{.}\) All that is needed is to find one value \(c\) for which \(p(c)\) is true and then invoke the Existential Generalization Rule.

Example 5.3.3. A constructive proof.

Show that there is a positive integer that can be written as the sum of cubes of positive integers in two different ways:
\begin{equation*} 10^3 + 9^3 = 12^3 + 1^3 = 1729 \end{equation*}
Therefore by Existential Generalization it is true, there is a positive integer that can be written as the sum of cubes of positive integers in two different ways.

Definition 5.3.4. Non-Constructive Proof.

Non-constructive proofs are also used to prove theorems of the form: \((\exists n)(p(n))\text{.}\) Assume no \(c\) exists for which \(p(c)\) is true and show this leads to a contradiction.

Example 5.3.5. A non-constructive proof.

Show that there exist irrational numbers \(x\) and \(y\) such that \(x^y\) is rational.
  • Take the negation of the conclusion: no such \(x, y\) exist.
  • We know that \(\sqrt{2}\) is irrational.
  • Let both \(x, y = \sqrt{2}.\)
  • Then, \(x^y = \sqrt{2}^{\sqrt{2}}.\)
  • There are two possibilities, \(\sqrt{2}^{\sqrt{2}}\) is either rational or irrational.
  • If it is rational, we have two irrational numbers \(x\) and \(y\) with \(x^y\) rational.
  • If it is irrational:
    • Let \(x = \sqrt{2}^{\sqrt{2}}\) and \(y = \sqrt{2}\text{.}\)
    • Then
      \begin{equation*} x^y = (\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{2}^{(\sqrt{2}\sqrt{2})} = \sqrt{2}^{2} = 2 \end{equation*}
    • 2 is rational.
  • In either case, we have a rational result, which contradicts our negated conclusion.\(\square\)
.

Definition 5.3.6. Proof of Non-Existence.

Non-Existence proofs are used to prove theorems of the form: \(\neg (\exists n)(p(n))\text{.}\) Using the equivalent form \((\forall n) \neg(p(n)) )\) show that \((p(n))\) is never true.

Example 5.3.7. A non-existence proof..

Show that there is no number \(x\) such that \(x^2 + 1 \lt 0\text{.}\)
  • Let \(p(x)\) be \(x^2 + 1 \lt 0\)
  • Then the whole statement can be written as: \(\neg (\exists x)(p(x))\)
  • Equivalently: \((\forall x) (\neg(p(x)))\)
  • We have three cases:
    1. Case 1: \(x \lt 0\text{.}\) Since multiplying two negatives, gives a positive, \(x^2\) is positive. Thus, \(x^2 + 1\) is also positive. Hence \(\neg(p(x))\) holds.
    2. Case 2: \(x = 0\text{.}\) Here \(x^2 = 0 \text{.}\) Thus, \(x^2 + 1 = 1\) is also positive. Hence \(\neg(p(x))\) holds.
    3. Case 3: \(x \gt 0\text{.}\) Since multiplying two positives, gives a positive, \(x^2\) is positive.. Thus, \(x^2 + 1\) is also positive. Hence \(\neg(p(x))\) holds.
  • Therefore, by Universal Instantiation \((\forall x) \neg(p(x)) )\square\)

Definition 5.3.8. Proof by Counterexample.

Counterexamples are used to show theorems of the form \((\forall n)(p(n))\) are false. All that is needed is to find one value \(c\) for which \(p(c)\) is false. That value is called a counterexample. \((\forall n)(p(n))\) is then false by Universal Instantiation. Counterexamples can also be used to prove statements with a negated universal quantifier \(\neg (\forall n)(p(n))\) are true. This is done using the counterexample in a proof by contradiction on \((\forall n)(p(n))\)
.

Example 5.3.9. A counterexample proof..

Show that every positive integer is the sum of the squares of 3 integers.
  • This can be rewritten as \((\forall x)(p(x))\text{,}\) where \(p(x)\) is the statement "\(x\) is the sum of the squares of 3 integers" and \(x \in \mathbb{P}\text{.}\)
  • Enumerating out from 1, we see that 7 cannot be made in this way:
    • \(\displaystyle 1 = 1^2 + 0^2 + 0^2\)
    • \(\displaystyle 2 = 1^2 + 1^2 + 0^2\)
    • \(\displaystyle 3 = 1^2 + 1^2 + 1^2\)
    • \(\displaystyle 4 = 2^2 + 0^2 + 0^2\)
    • \(\displaystyle 5 = 2^2 + 1^2 + 0^2\)
    • \(\displaystyle 6 = 2^2 + 1^2 + 1^2\)
    • \(\displaystyle 8 = 2^2 + 2^2 + 0^2\)
  • Therefore, 7 is a counterexample and \((\forall x)(p(x))\) is false.

Definition 5.3.10. Proof by Universal Generalization.

Universal Generalization is used for many proofs of mathematical formulas, but most less formal proofs don’t state that it is used. In a proof using Universal Generalization, we pick an arbitrary value from the universe and show that the statement is true. The catch is the value must be arbitrary, showing a formula works for a particular value cannot be generalized to all values in the universe.

Example 5.3.11. A proof using Universal Generalization..

Prove if an integer \(x\) is even then \(x^2\) is even.
The statement to be proven can be rewritten more formally as \((\forall x)(p(x) \rightarrow p(x^2))\text{,}\) where \(p(x)\) is the statement \(x\) is even. A formal proof would proceed as follows:
  1. \((\forall x)(p(x) \rightarrow p(x^2)) \) Premise
  2. \((p(c) \rightarrow p(c^2))\) Universal Instantiation to arbitrary integer \(c\)
  3. \(p(c)\) Assume hypothesis is true.
  4. \(c = 2k\text{,}\) for some integer \(k\text{.}\) Definition of even integer.
  5. \(c^2 = (2k)^2 = 2(2k^2)\) \(c^2\) is also even.
  6. \(p(c^2)\) is true.
  7. \(\therefore (\forall x)(p(x) \rightarrow p(x^2))\) Universal Generalization.

Exercises 5.3.2 Exercises for Section 5.3

1.

Translate the following argument and prove or disprove that it is valid.
  • Every student likes either soccer or basketball.
  • There is at least one student who does not like basketball.
  • For each student, the student does not like soccer or likes baseball.
  • All students who like volleyball do not like baseball.
  • Therefore, there exists a student who does not like volleyball.
Answer.
Assume that the universe of discourse is the set of all students. Let:
  • \(p(x)\) denote "A student x likes soccer".
  • \(q(x)\) denote "A student x likes basketball".
  • \(r(x)\) denote "A student x likes baseball".
  • \(s(x)\) denote "A student x likes volleyball".
The given argument is translated as follows.
  1. \(\displaystyle (\forall x) (p(x) \lor q(x))\)
  2. \(\displaystyle (\exists x) (\neg q(x))\)
  3. \(\displaystyle (\forall x) (\neg p(x) \lor r(x))\)
  4. \(\displaystyle (\forall x) (s(x) \rightarrow \neg r(x))\)
Therefore, \((\exists x) (\neg s(x))\)
Proof:
  1. \((\exists x) (\neg q(x))\) Premise 2
  2. \(\neg q(c)\) Existential Instantiation (1)
  3. \((\forall x) (p(x) \lor q(x))\) Premise 1
  4. \((p(c) \lor q(c))\) Universal Instantiation (3). Since UI we can let it be same element as (2)
  5. \(p(c) \) Disjunctive Syllogism (2,4)
  6. \((\forall x) (\neg p(x) \lor r(x))\) Premise 3
  7. \((\neg p(c) \lor r(c))\) UI (6)
  8. \(r(c)\) Disjunctive Syllogism (5,7)
  9. \((\forall x) (s(x) \rightarrow \neg r(x))\) Premise 4
  10. \((s(c) \rightarrow \neg r(c))\) UI (9)
  11. \(\neg s(c)\) Indirect Reasoning (8, 10)
  12. \(\therefore (\exists x) (\neg s(x))\) Existential Generalization (11)

2.

Prove that \((\exists x)(\forall y)(p(x, y)) \Rightarrow (\forall y)(\exists x)(p(x, y))\text{,}\) but that converse is not true.

3.

Given the following argument:
"If students study hard in courses, then they do well in them." "For students to do well in courses it is necessary that they do not skip classes for those courses." "Students doing well in discrete math follows from them studying hard in discrete math." "Therefore, students who do well in a discrete math course do not skip discrete math class."
Define propositional functions and the compound proposition for each statement over the universe of courses.
Answer.
First, define propositions over the universe of all courses:
  • Let \(W(x)\) be: Students do well in course \(x\text{.}\)
  • Let \(H(x)\) be: Students study hard in course \(x\text{.}\)
  • Let \(S(x)\) be: Students skip class for course \(x\text{.}\)
Now define the compound propositions given to us:
  • "If students study hard in courses, then they do well in them."
    \begin{equation*} \forall x H(x) \rightarrow W(x) \end{equation*}
  • "For students to do well in courses it is necessary that they do not skip classes for those courses."
    \begin{equation*} \forall x W(x) \rightarrow \neg S(x) \end{equation*}
  • "Students doing well in discrete math, follows from them studying hard in discrete math." translates to: "If students study hard in their discrete math course, then they do well in the course." from the List 4.1.11. So we have:
    \begin{equation*} H(\text{discrete math}) \rightarrow W(\text{discrete math}) \end{equation*}
  • We’re asked to show: "students who do well in a discrete math course do not skip discrete math class." This translates to: "If students do well in discrete math, then they do not skip discrete math class."
    \begin{equation*} W(\text{discrete math}) \rightarrow \neg S(\text{discrete math}) \end{equation*}

4.

Using the propositions from exercise 3 to prove the statement: "students who do well in a discrete math course do not skip discrete math class".
PrevTopNext