Proof Recipes
by Chef Ken Monks
The following "proof recipes" are intended to act as a guide to help you keep your sense of direction when you are writing your proofs. The notation and definitions used correspond to the conventions and notation used in our current course and textbook. In some cases I have omitted details for the sake of clarity. Thus, these recipes should be used as a guide, not a reference. The list is not meant to be comprehensive or all inclusive. Rather the recipes that appear are the ones which are used most frequently in the homework problems. Rather than use standard mathematical notation here, I am using notation that can be used in plain text email so we can correspond during the course about the topics below.
I. Notation used in all of the recipes
=> implies
<=> iff
<= less than or equal to
>= greater than or equal to
@ for all
# there exists
#! there exists a unique
& and
or or
~ not
~= not equal to
| divides
~| does not divide
-><- contradiction (Q&~Q)
f:A->B f is a function from A to B
Z,Q,Re,C the integers, rationals, reals, and complex numbers
a=b (mod c) a is congruent to b mod c
a in B a is an element of B
<- this is a symbol which means
"stop assuming what was assumed in the last Assume statement." or
"end Assume"
II. Proof Recipes - Foundations
A. Logic (Based on Gentzen's Natural Deduction)
a. Propositional Logic
; and +
To show W and V
1. Show W
2. Show V
; &- (first version)
To show W
1. Show W and V
; &- (second version)
To show V
1. Show W and V
; =>- (Modus Ponens)
To show V
1. Show W
2. Show W=>V
; =>+
To show W=>V
1. Assume W
2. Show V
3. <-
; or- (proof by cases)
To show R
1. Show W or V
2. Show W=>R
3. Show V=>R
; or- (alternate "expanded" version)
To show R
1. Show W or V
2. Assume W
3. Show R
4. <-
5. Assume V
6. Show R
7. <-
; or+ (first version)
To show W or V
1. Show W
; or+ (second version)
To show W or V
1. Show V
; <=>- (first version)
To show W=>V
1. Show W<=>V
; <=>- (second version)
To show V=>W
1. Show W<=>V
; <=>+
To show W<=>V
1. Show W=>V
2. Show V=>W
; ~+ (proof by contradiction)
To show ~W
1. Assume W
2. Show -><-
3. <-
; ~- (also proof by contradiction)
To show W
1. Assume ~W
2. Show -><-
3. <-
; -><- + (definition of -><-)
To show -><-
1. Show W and ~W
; -><- + (second version)
To show -><-
1. Show W
2. Show ~W
b. Quantifiers
Note: W(b) denotes the expression obtained when all of free occurrences of a
in statement W(a) are replaced by b.
; @-
To show W(t)
1. Show @x,W(x)
**Restrictions on @- rule:
* No free variable in t may become bound when t is substituted for x in W(x)
; #-
To show W(t) for some t.
1. Show #x,W(x)
**Restrictions on #- Rule:
* t must be a new constant in the proof
; @+
To show @x,W(x)
1. Let s be arbitrary.
2. Show W(s)
**Restrictions on the @+ Rule:
* s cannot appear as a free variable in any assumption or premise
* W(s) cannot contain any constants which were produced by the #- Rule
; #+
To show #x,W(x)
1. Show W(t)
Note: In this rule t can be an expression, and W(x) can be the expression
obtained by replacing one or more of the occurances of t with x.
**Restrictions on the #+ Rule
* No free variable in t may become bound when t is substituted for x in W(x)
; definition of #! (first version)
To show #!x,W(x)
1. Show #x,W(x) and @y, W(y) => x=y
; definition of #! (second version)
To show #x,W(x) and @y, W(y) => x=y
1. Show #!x,W(x)
**Restrictions on the #! rules
* No free variable in y can become bound when y is substituted for x in W(x).
c. Logic with Equality
; Reflexivity
To show x=x
(you don't have to do anything!)
; Extensionality (substitution)
To show W with the nth free occurrence of x replaced by y
1. Show x=y
2. Show W
**Restrictions on the substitution rule:
* No free variable in y may become bound when y is substituted for x in W
d. Copy a line (formerly known as the Stupidity rule)
; Copy (aka Stupidity)
To show W
1. Show W
Note: this rule is useful when you want to "copy" a line that has
already been proven in your proof down to another line to make the
proof more readable. It isn't really necessary.
B. Set Theory
To show A is a subset of B
1. Let x in A
2. Show x in B
To show A=B (when A and B are sets)
1. Let x in A
2. Show x in B
3. Let y in B
4. Show y in A
To show f = g (when f and g are functions)
1. Show Domain(f) = Domain(g)
2. Show Codomain(f) = Codomain(g) *
3. Let x be in Domain(f)
4. Show f(x) = g(x)
* Often in mathematics we refer to functions by the same name if they have
the same domains and agree on all values but have a slightly different
codomain. It should be clear from context if this is being done or not
in a particular situation.
To show x is in f(S)
1. Show f : B -> C
2. Show S is a subset of B
3. Show #y, y in S and f(y) = x
To show #y, y in S and f(y) = x
1. Show f : B -> C
2. Show S is a subset of B
3. Show x is in f(S)
To show x is in f^(-1)(T)
1. Show f : B -> C
2. Show T is a subset of C
3. Show f(x) in T
To show f(x) is in T
1. Show f : B -> C
2. Show T is a subset of C
3. Show x is in f^(-1)(T)
To show x in AxB
1. Show #a in A,#b in B, x=(a,b)
To show (a,b)=(c,d)
1. Show a=c and b=d
To show (x1,...,xn)=(y1,...,yn)
1. Let i in {1,2,..,n}
2. Show xi=yi
To show f:B->C is injective
1. Let x, y in B
2. Assume f(x) = f(y)
3. Show x=y
4. <-
To show f:B->C is surjective
1. Let y in C
2. Show #x in B, f(x)=y
To show f:B->C is bijective
1. Show f is injective
2. Show f is surjective
To show a relation R on X is an equivalence relation
1. Let x,y,z be in X
2. Show x R x
3. Assume xRy
4. Show yRx
5. <-
6. Assume xRy and yRz
7. Show xRz
8. <-
To show xRa (where R is an equiv reln on X and x,a in X)
1. Show x in [a]
To show x in [a] (where R is an equiv reln on X and x,a in X)
1. Show xRa
To show f=F|A (where A is subset of the domain of F)
1. Let a in A
2. Show f(a)=F(a)
To show F is an extension of f
1. Show f=F|Domain(f)
To show a relation R from X to Y is a function
1. Let x be in X
2. Show #y in Y, (x,y) in R
3. Let a,b in Y
4. Assume (x,a) in R and (x,b) in R
5. Show a=b
6. <-
To show m = max S where S is a finite set of real numbers
1. Show m in S
2. Let n in S
3. Show n <= m
III. Proof Recipies - Metric Spaces
To show (X,d) is a metric space
1. Show d : X x X -> R (usually given)
2. Let x,y,z in X.
3. Show d(x,y)>=0
4. Show d(x,y)=d(y,x)
5. Show d(x,z)<=d(x,y)+d(y,z)
6. Show d(x,x)=0
7. Assume d(x,y)=0
8. Show x=y.
To show f:(X,d)->(Y,d') is continuous at a in X
1. Let epsilon in R+
2. Define delta
3. Show delta in R+
4. Let x in X
5. Assume d(x,a)<delta
6. Show d'(f(x),f(a))<epsilon
7. <-
To show y in B(x;delta) in metric space (X,d)
1. Show d(y,x)<delta
To show d(y,x)<delta in metric space (X,d)
1. Show y in B(x;delta)
To show N is a neighborhood of a in metric space (X,d)
1. Show #delta, B(a;delta) subset N
To show #delta, B(a;delta) subset N
1. N is a neighborhood of a in metric space (X,d)
To show d(y,x)<delta in metric space (X,d)
1. Show y in B(x;delta)
To show U is an open subset of metric space (X,d)
1. Let x in U.
2. Show U is a neighborhood of x in (X,d).
To show U is a closed subset of metric space (X,d)
2. Show X-U is open.
To show f:(X,d)->(Y,D) is continuous (*after section 2.6 only*)
1. Let U be an open subset of Y.
2. Show f^(-1)(U) is open.
To show lim(xn,n->infinity)=x in (X,d)
1. Let epsilon>0
2. Show #N,@n>N,d(xn,x)<epsilon
To show x0,x1,x2,... is a Cauchy sequence in a metric space (X,d)
1. Let e in R+
2. Choose N in N+
3. Let i,j>N
4. Show d(xi,xj)<e
To show lim(xn,n->infinity)=x in (X,d) (second version)
1. Let epsilon>0
2. Choose N>0
3. Let n>N
4. Show d(xn,x)<epsilon
IV. Proof Recipies - Topology
To show (X,t) is a topological space (where X is a set and t a set of subsets of X)
1. Show {} in t
2. Show X in t
3. Let S subset t
4. Show UNION A is an element of t
A in S
5. Let n be a positive integer and U1,U2,...,Un be elements of t
6. Show U1 intersect U2 intersect U3 ... intersect Un is an element of t
To show U is open in topological space (X,t)
1. Show U in t
V. Proof Recipies - Modern Algebra
Notation and definitions in this section are based on:
Course: Modern Algebra I, University of Scranton
Text: Abstract Algebra by Hungerford
Notation:
Zn Z sub n, the ring Z mod n.
R a generic ring
0R zero sub R, the zero element in the ring R
1R 1 sub R, the identity of multiplication in ring R
AxB the cartesian product of sets A and B
(+) the plus sign inside the circle symbol
(x) the dot inside the circle symbol
* usually means multiplication but is often omitted eg a*b=ab
f(x) an element of R[x]
.f(x) the function .f:R->R induced by the f(x) in R[x]
C. Number Theory (arithmetic in Z)
To show a|b
1. Show a~=0
2. Show as=b for some integer s
To show d is the gcd(a,b)
1. Show d|a
2. Show d|b
3. Let c be an integer
4. Assume c|a and c|b
5. Show c <= d
6. <-
To show d is the gcd(a,b) in Z
1. Show d > 0
2. Show d|a
3. Show d|b
4. Let c be an integer
5. Assume c|a and c|b
6. Show c|d
7. <-
To show an integer p (other than 0,1,-1) is prime
1. Let d be an integer
2. Assume d|p
3. Show d=p or d=-p or d=1 or d=-1
4. <-
To show an integer p is prime
1. Let b,c be integers
2. Assume p|bc
3. Show p|b or p|c
4. <-
To show a=b (mod n) where n~=0
1. Show n|(a-b)
--Math Induction
To show @n,P(n) (where P(n) is a statement about the natural numbers)
1. Show P(0)
2. Let k in N
3. Assume P(k)
4. Show P(k+1)
5. <-
--Strong Math Induction
To show @n,P(n) (where P(n) is a statement about the natural numbers)
1. Show P(0)
2. Let k in N
3. Assume @j,0<=j<=k => P(k)
4. Show P(k+1)
5. <-
--Math Induction starting from r
To show @n>=r,P(n) (where P(n) is a statement about the natural numbers)
1. Show P(r)
2. Let k in N and k>=r
3. Assume P(k)
4. Show P(k+1)
5. <-
D. Ring Theory
To show (R,+,*) is a ring
1. Let a,b,c in R
2. Show +:RxR->R (closure of +)
3. Show *:RxR->R (closure of *)
4. Show (a+b)+c=a+(b+c)
5. Show a+b=b+a
6. Show #z in R, @a in R, z+a=a
7. Show #x in R, a+x=0R 8. Show a*(b*c)=(a*b)*c 9. Show a*(b+c)=(a*b)+(a*c) 10. Show (b+c)*a=(b*a)+(c*a)
[Notes: * in steps #2 and #3 it usually suffices to show that a+b in R and a*b in R.
* in line 7, 0R is the element referred to by z in line 6]
[Note: We will abbreviate a*b by ab as usual as long as it doesn't cause
confusion. We will also assume the usual algebraic heirarchy so that we
can write a(b+c)=ab+ac without confusion.]
To show (R,+,*) is a commutative ring
1. Show (R,+,*) is a ring
2. Let a,b in R
3. Show ab=ba
To show (R,+,*) is a ring with identity
1. Show (R,+,*) is a ring
2. Show #1 in R, @a in R, 1*a=a*1=a
To show (R,+,*) is a division ring
1. Show (R,+,*) is a ring with identity 1~=0
2. Let a in R
3. Assume a~=0
4. Show #x in R, ax=1
To show (R,+,*) is an integral domain
1. Show (R,+,*) is a commutative ring with identity 1~=0
2. Let a,b in R
3. Assume ab=0
4. Show a=0 or b=0
To show (R,+,*) is a field
1. Show (R,+,*) is a commutative ring with identity 1~=0
2. Let a in R
3. Assume a~=0
4. Show #x in R, ax=1
(Thm 3.2)
To show (S,+,*) is a subring of a ring (R,+,*)
1. Show S is a subset of R
2. Show 0R in S
3. Let a,b in S
4. Show a+b in S
5. Show ab in S
6. Show -a in S
[Note: When we write (S,+,*) in this rule the symbols + and * denote the
restriction of the operations +,* in R to SxS.]
(Thm 3.6)
To show (S,+,*) is a subring of a ring (R,+,*)
1. Show S is a nonempty subset of R
2. Let a,b in S
3. Show a-b in S
4. Show ab in S
To show a is a unit in a ring with identity R
1. Show #b, ab=1R=ba
To show a and b are associates in a commutative ring with identity R
1. Show a=bu for some unit u in R
To show a is a zero divisor in ring R
1. Show a~=0R 2. Show #b in R, ab=0R or ba=0R
To show f:R->S is a ring homomorphism
1. Let a,b in R
2. Show f(a+b)=f(a)+f(b)
3. Show f(ab)=f(a)f(b)
To show f:R->S is an isomorphism
1. Show f is a homomorphism
2. Show f is bijective
E. Polynomials and R[x]
[In the recipies that follow, F will always denote a field.]
To show f=g in R[x]
1. Let n in N
2. Show the coef. of xn in f(x) equals the coef. of xn in g(x)
To show f | g in F[x]
1. Show f~=0F 2. Show fh=g for some h in F[x]
To show d=gcd(f,g) in F[x]
1. Show d is monic
2. Show d | f
3. Show d | g
4. Let c in F[x]
5. Assume c | f and c | g
6. Show deg(c)<=deg(d)
To show d=gcd(f,g) in F[x]
1. Show d is monic
2. Show d | f
3. Show d | g
4. Let c in F[x]
5. Assume c | f and c | g
6. Show c | d
To show p is irreducible in F[x]
1. Show p is nonconstant
2. Let d in F[x]
3. Assume d|p
4. Show d is a unit or d is an associate of p
To show p is irreducible in F[x]
1. Show p is nonconstant
2. Let b,c in F[x]
3. Assume p|bc
4. Show p|b or p|c
To show a in R is a root of f in R[x] where R is a commutative ring
1. Show .f(a)=0R
To show a f is irreducible in F[x] where deg(f)=2 or deg(f)=3
1. Let a in F
2. Show .f(a)~=0F
To show (x-a) is a factor of f in F[x]
1. Show a is a root of f
To show f=g (mod p) where p~=0
1. Show p | f-g
F. Ideals and Quotient Rings
To show I is an ideal in ring R
1. Show I is a subring of R
2. Let r in R
3. Let a in I
4. Show ra in I and ar in I
To show a is in Ker(f) where f:R->S is a ring homomorphism
1. Show f(a)=0R
To show a=b mod I where I is an ideal of ring R
1. Show a-b in I
To show ring S is isomorphic to quotient ring R/I
1. Show there is a surjective homomorphism f:R->S
2. Show I=Ker(f)
G. Integral Domains
To show p is irreducible in an integral domain R
1. Let r,s in R
2. Assume p=rs
3. Show r is a unit or s is a unit
H. Groups
To show (G,*) is a group
1. Show *:GxG->G (closure)
2. Let a,b,c in G
3. Show a*(b*c)=(a*b)*c (associative)
4. Show #e in G, @a in G, a*e=a=e*a (identity)
5. Show #d in G, a*d=e=d*a (inverses)
To show a group G has finite order
1. Let a in G
2. Show #k in N, ak=e
To show element a in group G has order k
1. Show ak=eG 2. Let m be a positive integer 3. Assume am=eG
4. Show m>=k.
To show H is a subgroup of G
1. Show H is a subset of G
2. Let a,b in H
3. Show a*b in H
4. Show a-1 in H
To show H is a subgroup of G
1. Show H is a finite subset of G
2. Let a,b in H
3. Show a*b in H
To show a group G is cyclic
1. Show #a in G, @b in G, #k in Z, b=ak
To show a subset S generates a group G
1. Let g in G
2. Show g=b1*b2*...*bn for some b1,...,bn in S U S-1 where S-1={x in G : #s in S, x=s-1 }
To show a group G is finitely generated
1. Let g in G
2. Show #s1,s2,...,sk in G, g=b1*b2*...*bn for some b1,...,bn in {s1,s2,...,sk,s1-1,...,sk-1}
To show a group G is Abelian
1. Let a,b in G
2. Show ab=ba
To show f:G->H is a group homomorphism
1. Let a,b in G
2. Show f(a*b)=f(a)*f(b)
To show f:G->H is a group isomorphism
1. Show f is a group homomorphism
2. Show f is bijective
To show a=b mod K where K is a subgroup of G
1. Show a*b-1 in K
To show H is a normal subgroup of G
1. Show H is a subgroup of G
2. Let a in G
3. Let b in H
4. Show a*b*a-1 in H
To show H is a normal subgroup of G
1. Show H is a subgroup of G
2. Let a in G
3. Let b in H
4. Show a-1*b*a in H
To show G is isomorphic to MxN
1. Show M, N are normal subgroups of G
2. Show (M intersect N)={e}
3. Let a in G
4. Show #m in M,#n in N, a=mn.
To show G=N1xN2x...xNk
1. Let i in {1,...,k}
2. Show Ni is a normal subgroup of G
3. Let a in G
4. Show a=a1*a2*...*ak for some a1 in N1, a2 in N2,..., ak in Nk 5. Assume a1*a2*...*ak=b1*b2*...*bk for some a1,b1 in N1,...,ak,bk in Nk.
6. Let i in {1,...,k}
7. Show ai=bi.
I. Extension Fields
To show S=F(u)
1. Show F is a subfield of S
2. Show u in S
3. Let J be a subfield of S
4. Assume F subset J and u in J
5. Let x in S
6. Show x in J
7. <-
To show S=F(u1,...,un)
1. Show F is a subfield of S
2. Show u1,...,un in S
3. Let J be a subfield of S
4. Assume F subset J and u1,...,un in J
5. Let x in S
6. Show x in J
7. <-
To show K is a splitting field of f(x) over F
1. Show f(x)=c(x-u1)(x-u2)...(x-un) for some c in F and u1,...,un in K
2. Show K=F(u1,...,un)
To show K is a normal extension of F
1. Let p(x) in F[x] and v in K
2. Assume p(x) is irreducible and v is a root of p(x)
3. Show p(x) splits over K
4. <-
VI. Proof Recipies - Chaos and Fractals
A. Contraction maps
To show f:X->X is a contraction map on (X,d)
1. Choose s in (0..1)
2. Let x,y in X
3. Show d(f(x),f(y))<=s*d(x,y)
To show f:I->R is a contraction map on an open interval I of R
1. Show f(I) is a subset of I
2. Choose s in (0..1)
3. Let x in I
3. Show |f'(x)|<=s
B. Chaos
To show f:(X,d)->(X,d) has sensitive dependence on initial conditions
1. Choose t>0
2. Let x in X
3. Let e>0
4. Choose y in B(x;e)-{x}
5. Show #k>0, d(f^k(x),f^k(y))>t
To show f:(X,d)->(X,d) is transitive
1. Let x,y in X
2. Let e>0
3. Choose z in B(x;e)
4. Show #k>0, d(f^k(z),y)<e
To show A is dense in (X,d)
1. Show A is a subset of X
2. Let e>0
3. Let x in X
4. Show #y in A, d(x,y)<e
