Book: How To Prove It: A Structured Approach
published on 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)
 iff iA ⊆ R (note: iA = identity relation on A)
 R is symmetric if ∀ x ∈ A ∀ y ∈ A (xRy → yRx)
 iff R = R^1
 R is transitive if ∀ x ∈ A ∀ y ∈ A ∀ z ∈ A ((xRy∧yRz) → xRz)
 iff RºR ⊆ R
 R is reflexive if ∀ x ∈ A (xRx) = ∀ x ∈ A ((x,x) ∈ 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  OnetoOne and Onto
Onetoone (11) “injection”: ¬∃ a1 ∈ A ∃ a2 A(f(a1) = f(a2) ∧ a1 ≠ a2)
Onto “surjection”: ∀ b ∈ B ∃ a ∈ A(f(a) = b)
If both 11 and onto, then called “Bijection” or “11 correspondence”
5.3  Inverses of Functions
 Suppose ƒ: A→B. If ƒ is 11 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 11
 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 11 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.46.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 11 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:
 P → Q:
 Assume P is true and prove Q
 Prove the contrapositive; that is, assume Q is false and prove that P is false
 ¬Q:
 Reexpress as a positive statement
 Use proof by contradiction; that is, assume that P is true and try to reach a contradiction
 P ∧ Q:
 Prove P and Q separately. In other words, treat this as two separate goals: P and Q.
 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.
 P ↔ Q:
 Prove P → Q and Q → P, using methods listed under 1.
 ∀x P(x):
 Let x stand for an arbitrary object and prove P(x).
 ∃x P(x):
 Find a value of x that makes P(x) true. Prove P(x) for this value of x.
 ∃!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))
 ∀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:
 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
 ¬P:
 Reexpress as a positive statement
 In a proof by contradiction, you can reach a contradiction by proving P
 P ∧ Q:
 Treat this as two givens, P, and Q
 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.
 P ↔ Q:
 Treat this as two givens: P → Q and Q → P
 ∀x P(x):
 You may plug in any value, say a, for x, and conclude that P(a) is true
 ∃x P(x):
 Introduce a new variable, say x0, into the proof, to stand for a particular object for which P(x0) is true
 ∃!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:
 Proof by contradiction: assume the goal is false and derive a contradiction.
 Proof by cases: consider several cases that are exhaustive, that is, that include all possibilities. Prove the goal in each case.
Questions? Email me: this domain AT gmail DOT com