next up previous
Next: Tuesday, May 2, 2000 Up: Lecture Notes Previous: Some Examples Done in

Monday, May 1, 2000

Topics covered in lecture:

a.  all subsets of finite sets are finite

b.  subtraction counting principle

c.  pigeonhole principle

Theorem:  All subsets of finite sets are finite.

Proof:  Let A be a finite set.  This means that for some natural number
n, |A| = n:  there is a bijection f from A to n.

We prove the theorem in the form ``For all n, if A is a set such that |A| = n
and B is a set such that B c= A, then B is finite'', by induction on n
(the size of the finite set A).

Basis step:  If A is a set of size 0, then it is the empty set, and moreover
any subset B of A is the empty set also, and the empty set is finite (it is
of cardinality 0).

Induction step: Suppose for a fixed natural number n that every subset
B of any set A of cardinality n is finite (this is the inductive
hypothesis).  Our goal is to show that every subset B of any set A
of cardinality n+1 is finite.

Let A be an arbitrarily chosen set of cardinality n+1.  Let B be any subset
of A.

If B = A, then we know (by hypothesis introducing A) that B is finite (it has
cardinality n+1).

If B =/= A, then select some x such that x E A-B.  Clearly B is a
subset of A-{x}.  It will be sufficient to show that A-{x} has
cardinality n, for it will then follow by inductive hypothesis that
any subset (e.g. B) of a set of cardinality n (which A-{x} will then
be seen to be) is finite.

Lemma:  If A is a set of cardinality n+1 and x E A, then |A -{x}| = n.

Proof of Lemma:  |A| = n+1 means that we can select a bijection f
from A to n+1 = nU{n}.  For some y, f(y) = n.  There are two cases in
our argument:  either x = y or x =/= y.

If x=y, then the restriction of f to A-{y} = A-{x} is a bijection with
domain A-{x} and range (n+1) - {f(y)} = (n+1) - {n} = n.  In this case
we have |A - {x}| = n as desired.

If x =/= y, we consider the restriction of f to A-{x,y}, with its
codomain restricted to its range.  This is a bijection from A - {x,y}
to (n+1) - {f(x),n} = n - {f(x)}.  Observe that y is not in the domain
A - {x,y} and f(x) is not in the codomain n - {f(x)}.  Observe that
({y},{(y,f(x))},{f(x)}) is a bijection with domain and codomain
disjoint from that of the restricted version of f.  So ((A-{x,y}) U {y},
(f|\(A-{x,y}) U {(y,f(x))}, (n - {f(x)}) U {f(x)}) =
(A - {x}, (f|\(A-{x,y}) U {(y,f(x))}, n) is a bijection.  Thus
|A - {x}| = n as desired.

Of course, this is easier to see with diagrams.  The x=y case is really
obvious with a diagram, and the x =/= y case reduces to moving one arrow!

Since |A - {x}| = n holds in both cases, we have completed the proof of
the Lemma and of the Theorem that all subsets of finite sets are finite.

The Basic Counting Principle of Subtraction

Theorem:  If A is a finite set and B is a subset of A, then
|A-B| = |A| - |B|.

Proof:  A-B is a subset of A, and so is B.  Both sets are finite by
the preceding theorem.  They are disjoint and their union is A, so
by the basic counting principle of addition we have |A-B| + |B| = |A|,
and by the definition of subtraction we have |A-B| - |A| - |B|.

The Pigeonhole Principle

Lemma:  If (A,f,B) is an injection and A, B are finite sets, it follows
that |A| <= |B|.

Proof:  The finite set B is the union of the two disjoint sets
range(f) (= {y E B.(Ex E A.f(x)=y)}) and B-range(f), which are finite
by the recently proved theorem.  In addition, |range(f)| = |A|; if
(A,f,B) is an injection, then (A,f,range(f)} is a bijection.

Thus |B| = |range(f)| + |B - range(f)| = |A| + |B - range(f)|,
so |A| <= |B| by definition of <= (recall that we define m <= n
as meaning (Ek.m+k=n)).

Theorem (the Pigeonhole Principle):  If |A| > |B|, and (A,f,B) is
a function, it is not an injection.

Proof:  This is simply the contrapositive of the Lemma!

Relevance:  The informal form of the Pigeonhole Principle is that if
we put m objects in n boxes, with m > n, some box will contain more
than one object.  Formalize this by fixing a numbering of objects and
a numbering of boxes and defining f(i) = j for i E m and j E n just
in case the ith object goes in the jth box.  By the theorem just proved,
f cannot be an injection.  This implies that f(i) = f(k) for some i =/= k,
which says that object i and object k both go in box f(i) = f(k),
which is what we want to show (two distinct objects go in the same box.)

Randall Holmes