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.