next up previous
Next: Tuesday, April 18, 2000 Up: Lecture Notes Previous: Wednesday, April 12

Monday, April 17, 2000

At this point, with the properties of our formal number theory
verified for the arithmetic implemented in our set theory (mod a
homework assignment to verify the properties of multiplication) we
will relax and assume that our arithmetic and algebraic knowledge is
on a firm footing.  We will still be careful in our reasoning about
sets.

Counting Principles for Addition and Multiplication

Basic Counting Principle for Addition

Theorem: If |A| = m and |B| = n and A and B are disjoint (A ^ B = {})
then |A U B| = m+n

Proof:  Suppose we have a bijection (A,f,m) and a bijection (B,g,n)
and that A and B are disjoint sets.  Our goal is to construct a bijection
from A U B to m+n.

Define f' as the map which takes each a in A to (f(a),0).  f' is a bijection
from A to mx{0} (it is the composition of f with the obvious bijection
from m to mx{0}).

Similarly, define g' as the map which takes each b in B to (g(b),1).
g' is a bijection from B to n x {1} (it is the composition of g with
the obvious bijection from n to n x {1}).

Observe that the bijections (A,f',mx{0}) and (B,g',nx{1}) have
disjoint domains and disjoint codomains.  Thus ((A U
B),(f'Ug'),((mx{0})U(nx{1}))) is a bijection.  Thus A U B ~=~
((mx{0})U(nx{1})) ~=~ m+n, and we know that the relation of being the
same size is transitive (we can compose a bijection from A U B to
((mx{0})U(nx{1})) and a bijection from ((mx{0})U(nx{1})) to m+n to get
the bijection we want).

A More General Counting Principle for Addition

Theorem: For any finite sets A and B, |A U B| = |A| + |B| - |A ^ B|

Proof:  I'll give a shorter proof here than I did in class, though
the idea is the same.

A and B-A are disjoint sets, and A U (B-A) = A U B.  So, by the Basic
Counting Principle for addition, |A| + |B-A| = |A U B|.

A ^ B and B-A are disjoint sets, and (A^B) U (B-A) = B.  Thus
|A^B| + |B-A| = |B|, so |B-A| = |B| - |A^B|.

Thus |A U B| = |A| + |B-A| = |A| + |B| - |A^B|, completing the proof.

Basic Counting Principle for Multiplication

Theorem:  Let |A| = m, and, for all B E A, let |B| = n, and for any B E A
and C E A, either B=C or B^C = {}; in other words, A is a set of m 
disjoint n-element sets.  Then |U[A]| = m*n.

Proof: Let (A,f,m) be a bijection from A to m.  For each element B
of A, let (B,g_B,n) be a bijection from B to n.  

For each element b of U[A], there is a uniquely determined element
of A to which b belongs, because distinct elements of A are disjoint.
We call this set P(b). (P for ``partition'').

We define a map h as follows: for each b in U[A], define h(b) as
(f(P(b)),g_(P_b)(b)).  Recall that f is a bijection from A to n, so
f(P(b)) is an element of m, while g_(P(b)) is a bijection from P(b) to
n, so g_(P(B)(b) is an element of n, and the ordered pair is an
element of m x n.  It is not hard to see that this is a bijection from
U[A] to m x n.  Thus we have U[A] ~=~ m x n ~=~ m*n, so |U[A]| = m*n
as desired.

One tricky aspect of making this completely rigorous would be
demonstrating that the process of choosing a bijection g_B for each B
in A can be made precise.  This isn't a problem here, because A is a
finite set; for infinite sets a special axiom of set theory is needed
to ensure that choices can be made in this kind of situation.



Randall Holmes
2000-05-05