2-3_Proofs_Involving_Quantifiers(1)

2.3 Proofs Involving Quantifiers

Overview

  • This section covers methods to prove quantified statements involving universal ("\u2200") and existential ("\u2203") quantifiers.

Universal Statements

  • Definition: A universal statement is of the form "\u2200x \in S, P(x)" and asserts that property P holds for all elements x in the set S.

  • Proving Universal Statements

    • Method 2.3.1: To prove "\u2200x \in S, P(x)" directly:

      1. Let x be an arbitrary element in domain S.

      2. Prove that P(x) is true using appropriate proof techniques based on the logical form of P(x).

      3. Since x is arbitrary, conclude "\u2200x \in S, P(x)" is true.

Example of a Universal Proof

  • Example 2.3.2: Prove that for every odd integer x, x² = 8k + 1 for some k in Z.

    • Let x be an arbitrary odd integer. Odd integers can be represented as:

      • Case 1: x = 4m + 1 → x² = 16m² + 8m + 1 = 8(2m² + m) + 1.

      • Case 2: x = 4m + 3 → x² = 16m² + 24m + 9 = 8(2m² + 3m + 1) + 1.

Exercises on Universal Statements

  • Exercise 2.3.3: Prove that for all rational numbers x and y, x + y² is a rational number.

  • Exercise 2.3.4: Prove that if a | b and a | c, then a | (bx + cy) for all integers x and y.

Proofs Involving Sets

  • Set Definitions

    • If A is a subset of B (A ⊆ B), then every element of A is also an element of B.

    • A and B are equal (A = B) if A ⊆ B and B ⊆ A.

  • Method 2.3.4: To prove set relations:

    • A ⊆ B ↔ "\u2200 x, x ∈ A → x ∈ B."

    • A = B ↔ "\u2200 x, x ∈ A → x ∈ B ∧ x ∈ B → x ∈ A."

Examples of Set Proofs

  • Example 2.3.5: Proof examples of set relationships:

    1. Prove if A ⊆ B and B ⊆ C, then A ⊆ C.

    2. Prove A ⊆ B if and only if A ∪ B = B.

Proofs Involving Multiples

  • Example 2.3.7: Prove a | b if and only if bZ ⊆ aZ.

    • (1) If a | b, show bZ is a subset of aZ.

    • (2) If bZ ⊆ aZ, show a | b.

Proof by Contradiction

  • Method 2.3.9: To prove a universal statement by contradiction:

    1. Assume that the statement is false.

    2. Find an element t in S such that ¬P(t).

    3. Show this leads to a contradiction.

  • Example 2.3.10: Prove for all x in (0, π/2), sin x + cos x > 1 using contradiction.

Expressing Universal Statements

  • It is possible to express universal statements without using "for all" explicitly.

  • Example 2.3.11: Prove the sum of a rational number and an irrational number is irrational.

Existential Quantifiers

  • Existence Statements: Of the form "There exists x such that P(x)" is true if the truth set of P(x) is non-empty.

  • Method 2.3.13: To prove “\u2203 x \in S such that P(x)":

    • Display an element a in S that makes P(a) true (constructive proof) or prove it by contradiction.

  • Example 2.3.14: Prove:

    1. Exist integers m and n such that 2m + 7n = 1.

    2. There exists a positive integer n such that n² > 2n.

Unique Existence

  • Unique Existential Quantifier Method 2.3.19: To prove “\u2203! x \in S such that P(x)":

    1. Proves existence of x such that P(x).

    2. Show P(y) ∧ P(z) → (y = z).

  • Example 2.3.20: Prove every nonzero real number has a unique multiplicative inverse.

Exercises for Unique Existence

  • Exercise 2.3.21: Prove the equation x⁵ + 2x - 5 = 0 has a unique real solution between x = 1 and x = 2.

robot