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.)