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.