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.