Categories: archive |books

Book: How To Prove It: A Structured Approach

  • Read: January 2012
  • Rating: 9/10

How To Prove It: A Structured Approach by Daniel Kelleman is a fantastic book on how to write mathematical proofs. It’s also a fantastic resource on set theory and general logic. I read this book in preparation for some of my forthcoming grad school computer science classes, but I wish I read it years ago. The level of detail is perfect. The book starts off very simply, and teaches individual things about simple problems. It slowly shows harder and harder proofs and introduces different techniques for writing proofs. Each section has very clear details about how to use that technique as well as several great examples of the technique in action. The book shows a great amount of scratch work, as well as final proofs. This is a must read for any Mathematics or Computer Science or other engineering major, and a must read for those interested in logic.

My Notes

Introduction

  • Deductive Reasoning: Reduce and Solve a problem
  • Conjecture: Guess
    • Once proven, it is a theorem
  • Primes of 2^n - 1 = Mersenne Primes

Chapter 1 - Sequential Logic

Valid argument: premises cannot all be true withot the conclusion being true as well

Truth Table:

  • Demorgan’s Laws
    • ¬(P∧Q) = ¬P∨¬Q
    • ¬(P∨Q) = ¬P∧¬Q
  • Commutative Laws
    • P∧Q = Q∧P
    • P∨Q = Q∨P
  • Associate Laws
    • P∧(Q∧R) = (P∧Q)∧R
    • P∨(Q∨R) = (P∨Q)∨R
  • Idempotent Laws
    • P∧P = P
    • P∧P = P
  • Distributive Laws
    • P∧(Q∨R) = (P∧Q) ∨ (P∧R)
    • ∀P∨(Q∧R) = (P∨Q) ∧ (P∨R)
  • Double Negation Law
    • ¬¬P = P
  • Tautology Laws (always true)
    • P∧(a tautology) = P
    • P∨(a tautology) = tautology
    • ¬(a tautology) = contradiction
  • Contradiction Laws (always false)
    • P∧(a contradiction) = contradiction
    • P∨(a contradiction) = P
    • ¬(a contradiction) = tautology

1.3 - Variables and Sets

  • Set = collection of objects {}

  • Object are called elements of the set

  • ∈ = “is an element of”

  • y ∈ { x | x^2 < 9 } => elementhood test

  • y = free variable

  • x = dummy or bound variable

  • Truth set of P(x) = {x | P(x)}

  • Common universes of discourse:

    • R = {x | x is a real number}
    • Q = {x | x is a rational number}
    • Ζ = {x | x is an integer}
    • Ν = {x | x is a natural number}

  • ∅ = empty or null set = {}

1.4 - Set Operations

  • A ∩ B = {x | x ∈ A and x ∈ B} = intersection of sets A and B
  • A ∪ B = {x | x ∈ A or x ∈ B} = union of sets A and B
  • A \ B = {x | x ∈ A and x ∉ B} = difference of sets A and B

Often we use Venn Diagrams to represent

  • A ⊆ B = A is a subset of B = all elements in A are in B
  • A ∩ B = ∅ = disjoint = no same elements

1.5 - Conditional and Biconditional Connectives

  • P → Q = If P then Q = conditional

  • P = Antecedent

  • Q = Consequent

  • ¬P∨Q = P→Q = ¬P∨¬Q = ¬(P∧¬Q)

  • Q→P = Converse of P→Q

  • ¬Q→¬P = contrapositive of P→Q = P→:

  • Q↔P = biconditional = if and only if (iff) = P→Q and Q→P are true = (P→Q)∧(Q→P)

Chapter 2 - Quantificational Logic

  • ∀ xP(x) = “for all x, P(x)” = universal quantifier

  • ∃ xP(x) = “there exists an x such that P(x)” = existential quantifier

  • Order of quantifiers makes a difference:

    • ¬∃ xP(x) = ∀ x ¬ P(x)
    • ¬∀ xP(x) = ∃ x ¬ P(x)

  • Can reorder same types ∃ ∀

    • ∃ y ∃ x or ∃ x ∃ y = “there are objects x and y such that …”
    • ∀ x ∀ y or ∀ y ∀ x = “for all objects x and y …”

  • ∃! xP(x) = “there is exactly one value of x such that P is true”

  • The universal quantifier distributes over conjunction (the existential quantifier doesn’t!)

    • ∀ x (E(x) ∧ T(x)) = ∀ xE(x) ∧ ∀ xT(x)

  • Indexed set

    • Power set of A = ℘(A) = {x | x ≤ A}

  • Intersection of family = ∩F = {x | ∀ A (A ∈ F → x ∈ A)}

  • Union of family = ∪F = {x | ∃ A (A ∈ F ∧ x ∈ A)}

Chapter 3 - Proofs

A proof is simply a deductive argument whose premises are the hypothesis of the theorem and whose conclusion is the conclusion of the theorem

  • Never assert anything until you can justify it completely

  • To prove a conclusion of the form P→Q

    • assume P is true and then prove Q

  • Givens = statements known or assumed true

  • Goal = statement that remains to be proven

3.2 - Proofs Involving Negations and Conditionals

  • Goal = ¬P

    • instead of a goal that says what shouldn’t be true, see if you can rephrase as a goal that says what should be true

  • By contradiction, suppose P is true, proof of contradiction, thus P is false

    • assume conclusion is false

3.3 - Proofs Involving Quantifiers

  • If you can prove arbitrary P(x), then ∀ P(x)
    • x must be arbitrary (not assumed equal to any other object)
    • don’t say “all”, “every”, etc

When solving ∃x, then pick an x that solves the equation - it doesn’t matter how you find it (the ‘how’ is not part of the proof)

3.4 - Proofs Involving Conjunctions and Biconditionals

  • iff ↔ proofs
    • solve → then solve ← (must do both)

3.5 - Proofs Involving Disjunctions

  • P ∨ Q = P or Q is true, you’re not sure which
    • called “cases” = must solve 2 proofs
    • if proof broken down to cover full proof with 2+ cases, then it called exhaustive
    • they can both be true

3.6 - Existence and Uniqueness Proofs

  • ∃! x P(x)
  • Existence = [proof of ∃ x P(x)]
  • Uniqueness = [proof of ∀ y ∀ z (P(y) ∧ P(z)) → y = z]

Chapter 4 - Relations

4.1 - Ordered Pairs and Cartesian Products

P(x,y) = two free variables = pair(a,b)

  • Cartesian product
    • AxB = {(a,b) | a ∈A and b ∈B}
    • order matters

Truth set of p(x,y) = {(a,b) ∈ AxB | p(a,b)}

4.2 - Relations

  • R ⊆ AxB is called a relation from A to B

  • Domain of R = Dom(R) = {a ∈ A | ∃ b ∈ B ((a,b) ∈ R)}

  • Range of R = Ran(R) = {b ∈ B | ∃ a ∈ A ((a,b) ∈ R)}

  • Inverse of R = R^-1 = {(b,a) ∈ BxA | (a,b) ∈ R}

  • Composition

    • TºE = {(s,p) ∈ SxP | ∃ c ∈ C ((s,c) ∈ E and (c,p) ∈ T)}
    • Example. If Joe is in Bio 12 and Bio 12 is taught by Prof X, then:
      • (Joe, Bio 12) ∈ E and (Bio 12, Prof X) ∈ T
      • So (Joe, Prof X) ∈ TºE

4.3 - More about Relations

  • R is a relation on A:
    • R is reflexive if ∀ x ∈ A (xRx) = ∀ x ∈ A ((x,x) ∈ R)
      • if f iA ⊆ R (note: iA = identity relation on A)
    • R is symmetric if ∀ x ∈ A ∀ y ∈ A (xRy → yRx)
      • if f R = R^-1
    • R is transitive if ∀ x ∈ A ∀ y ∈ A ∀ z ∈ A ((xRy∧yRz) → xRz)
      • if f RºR ⊆ R

4.4 - Ordering Relations

  • R is partial order on A if it is reflexive, transitive, and antisymmetrical.

  • R is total order if partial order and:

  • ∀ x ∈ A ∀ y ∈ A (xRy ∨ yRx)

  • R minimal element

  • R largest and maximal element

  • Upp and lower bound

4.5 - Closures

  • L is an element of F and it’s a subset of every element of F

  • Then it (L) is the reflexive closure of M

  • L = {(x,y) ∈ RxR | x ≤ y }

  • Reflexive closure of strict partial order is always partial order

  • Reflexive closure of strict total order is always total order

4.6 - Equivalence Relations

  • Equivalence relations on A if it is reflexive, symmetric, and transitive.

  • Pairwise disjoint = all elements of f are disjoint = ∀ x ∈ f ∀ y ∈ f (x ≠ y → x ∧ y = 0)

  • f is a partition of A if:

    • ∪ƒ = A

  • f is pairwise disjoint if:

    • ∀ x ∈ ƒ(x ≠ 0)

Facts proven primarily of using them to prove a theorem = lemma

  • ∃ k ∈ Ζ (x - y = km) = x is congruent to y modulo m
    • x ≡ y mod m

Chapter 5 - Functions

Suppose P is the set of all people. Let H = {(p,n) ∈ P X Ν | person p has n children}. The H is relation from P to Ν. For every p ∈ P, there is exactly one n ∈ Ν s.t. (p,n) ∈ H. H is a fuction from P to Ν.

  • F is a function from A to B:

    • ∀ a ∈ A ∃! b ∈ B((a,b) ∈ F)
    • represented as ƒ:A→B

  • Suppose ƒ:A→B

    • Unique b = "value of ƒ at a" = "image of a under ƒ"
    • f(a) = b

Theorem 5.1.4. Suppose f and g are functions from A to B. If ∀ a ∈ A(f(a) = g(a)), then f=g.

5.1.5

Suppose ƒ:A→B and g:B→C. The gºf:A→C for any a ∈ A, the value of gºf at a is given by the formula (gºf)(a) = g(f(a))

5.2 - One-to-One and Onto

One-to-one (1-1) “injection”: ¬∃ a1 ∈ A ∃ a2 A(f(a1) = f(a2) ∧ a1 ≠ a2)

Onto “surjection”: ∀ b ∈ B ∃ a ∈ A(f(a) = b)

If both 1-1 and onto, then called “Bijection” or “1-1 correspondence”

5.3 - Inverses of Functions

  • Suppose ƒ: A→B. If ƒ is 1-1 and onto, then ƒ^-1:B→A

  • ƒ^-1ºƒ = iA and ƒºƒ^-1 = iB. (for ƒ:A→B and ƒ^-1:B→A)

  • Suppose ƒ:A→B

    • If function g:B→A s.t. gºƒ = iA then ƒ is 1-1
    • If function g:B→A s.t. ƒ*ordm;g = iB then ƒ is onto
5.3.4

  • Suppose ƒ:A→B. Then the following are equal:

    • ƒ is 1-1 and onto
    • ƒ^-1:B→A
    • There is a function g:B→A s.t. gºƒ = iA and ƒºg = iB

  • Example. 10^log x = x = log 10^x (base 10)

    • f(x) = 10^x
    • g(x) = log x
    • g(f(x)) = log 10^x = x ... f(g(x)) = 10^log x = x

So log is the inverse of “raise 10 to the power” function

Chapter 6 - Mathematical Induction

  • Form of proof:
    • Base Case: [Proof of P(0) goes here]
    • Induction step: [Proof of ∀ n ∈ Ν(P(n) → P(n+1) goes here]

6.3 Recursion

  • Prove ƒ(0), then ƒ(n), therfore ƒ(n+1)
  • If we use ”…”, then we may be able to use recursion

6.4-6.5 Strong Induction and Closures Again

Some interesting proofs in the book here.

Chapter 7 - Infinite Sets

  • A and B are sets. A is equinumerous w/B if ƒ: A→B is 1-1 and onto (shown as A~B)

  • Suppose A~B and C~D, then:

    • AxC ~ BxD
    • if A and C are disjoint and B and D are disjoint, then A∪C~B∪D

  • Sets A, B, and C:

    • A~A
    • if A~B, then B~A
    • if A~B and B~C, then A~C

Summary of Proof Techniques

To prove a goal of the form:

  1. P → Q:
  • Assume P is true and prove Q
  • Prove the contrapositive; that is, assume Q is false and prove that P is false
  1. ¬Q:
  • Reexpress as a positive statement
  • Use proof by contradiction; that is, assume that P is true and try to reach a contradiction
  1. P ∧ Q:
  • Prove P and Q separately. In other words, treat this as two separate goals: P and Q.
  1. P ∨ Q:
  • Use proof by cases. In each case, either prove P or prove Q.
  • Assume P is false and prove Q, or assume Q is false and prove P.
  1. P ↔ Q:
  • Prove P → Q and Q → P, using methods listed under 1.
  1. ∀x P(x):
  • Let x stand for an arbitrary object and prove P(x).
  1. ∃x P(x):
  • Find a value of x that makes P(x) true. Prove P(x) for this value of x.
  1. ∃!x P(x):
  • Prove ∃x P(x) (existence) and ∀y ∀z ((P(y) ∧ P(z)) → y=z) (uniqueness)
  • Prove the equivalent statement ∃x (P(x) ∧ ∀y (P(y) → y = x))
  1. ∀n ∈ ΝP(n);
  • Mathematical Induction: Prove P(0) (base case) and ∀n ∈ Ν (P(n) → P(n+1)) (induction step)
  • Strong induction: Prove ∀n ∈ Ν[(∀k < nP(k)) → P(n)]

To use a given of the form:

  1. P → Q:
  • If you are also given P, or you can prove that P is true, then you can conclude that Q is true
  • Use the contrapositive: if you are given or can prove that Q is false, you can conclude that P is false
  1. ¬P:
  • Reexpress as a positive statement
  • In a proof by contradiction, you can reach a contradiction by proving P
  1. P ∧ Q:
  • Treat this as two givens, P, and Q
  1. P ∨ Q:
  • Use proof by cases. In case 1 assume P is true, and in case 2 assume Q is true
  • If you are also given that P is false, or you can prove that P is false, you can conclude that Q is true. Similarly, if you know that Q is false you can conclude that P is true.
  1. P ↔ Q:
  • Treat this as two givens: P → Q and Q → P
  1. ∀x P(x):
  • You may plug in any value, say a, for x, and conclude that P(a) is true
  1. ∃x P(x):
  • Introduce a new variable, say x0, into the proof, to stand for a particular object for which P(x0) is true
  1. ∃!x P(x):
  • Introduce a new variable, say x0, into the proof, to stand for a particular object for which P(x0) is true. You may also assume that ∀y ∀z ((P(y) ∧ P(z)) → y=z)

Techniques that can be used in any proof:

  1. Proof by contradiction: assume the goal is false and derive a contradiction.
  2. Proof by cases: consider several cases that are exhaustive, that is, that include all possibilities. Prove the goal in each case.