Skip to main content

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.

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\)
Table 5.3.1. Inference Rules for Quantified Statements

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.

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.

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.

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))\)

.

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:

    • \(1 = 1^2 + 0^2 + 0^2\)

    • \(2 = 1^2 + 1^2 + 0^2\)

    • \(3 = 1^2 + 1^2 + 1^2\)

    • \(4 = 2^2 + 0^2 + 0^2\)

    • \(5 = 2^2 + 1^2 + 0^2\)

    • \(6 = 2^2 + 1^2 + 1^2\)

    • \(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.

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. \((\forall x) (p(x) \lor q(x))\)

  2. \((\exists x) (\neg q(x))\)

  3. \((\forall x) (\neg p(x) \lor r(x))\)

  4. \((\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.

login