The tree for the problem of bijections from n to n: To show that the number of bijections from n to n is n!, consider the tree (T <=(T),T), where T is the set of injections (m,f,n) where m is a natural number <= n and <=(T) is the subset relation restricted to this set. This is a tree because each such injection (m,f,n) is ``preceded'' in the tree only by the injections (k,f|\k,n) formed by restricting the function f with domain m = {0,1,...m-1} to the domain k = {0,1,...,k-1} with k<=m; it is not hard to see that these functions are linearly ordered by inclusion (they are completely determined by choosing how long an initial segment of the domain of f to use). Moreover, the relation ({},{},{}) is a root for this tree. Take any injection (m,f,n) with m<n. This will be an element of level m of the tree, and all elements of level m are of this form. A child of (m,f,n) is an injection (m+1,f',n) which extends (m,f,n); the only choice to make in extending f from domain m = {0,...,m-1} to domain m+1 = {0,...,m} is the decision of what value to assign to f'(m); there are n-m possibilities, since we cannot reuse any of the m values in the range of f. Thus we have a uniformly branching tree with b(m) = n-m for each m <= n. Level n of this tree will contain the bijections from n to n, and there are Pi{i<n}(n-i) = n! of these. It may not be immediately obvious that Pi{i<n}(n-i) = n!: look at the example of 4: Pi{i<4}(4-i) = (4-0)*(4-1)*(4-2)*(4-3) = 4*3*2*1 = 4! Theorem: Every nonempty finite linear order has a largest element. We need to formalize this statement somewhat. We say that a linear order (A,R,A) is finite just in case A is a finite set. (In this case R will also be a finite set, but a larger one). We say that x E A is a largest element of the linear order (A,R,A) just in case (Ay E A.y R x). (We could also say (Ay E A. x R y -> x = y); this is equivalent for linear orders, but expresses a different concept for partial orders). We prove the theorem by induction on the cardinality of the set A. Basis: n = 0 This is trivial, since a nonempty finite linear order cannot have n=0. Induction Step: Suppose that all nonempty linear orders of cardinality n have largest elements. Show that all nonempty linear orders of cardinality n+1 have largest elements. There are two cases: either n = 0 or n > 0. If n = 0, we observe that A has only one element, which will obviously be the desired largest element. If n =/= 0, we select an element x from A, and consider the linear order (A-{x}, R|\(A-{x}, A-{x}) obtained by restricting the linear order to A-{x}. This linear order on the set A-{x} of size n has a largest element y by hypothesis. By connectedness of linear orders, we have x R y | y R x. Case 1: (x R y) For any element z of A, either z = x R y or z E A-{x} and so z R y because y is the largest element of the restricted order. In either case, z R y so in this case (A,R,A) has a largest element. Case 2: (y R x) For any element z of A, either z = x R x or z E A-{x}, in which case z R y R x (z R y because y is largest in the restricted order). In either case z R x, so in this case (A,R,A) has a largest element. Theorems about Bijections: The converse of a bijection is a bijection: Suppose (A,f,B) is a bijection. Its converse is defined as (B,f{-1},A), where f{-1} is defined as {(y,x) : (x,y) E f}. The essence of the proof is that (A,f,B) is source covering/connected just in case (B,f{-1},A) is target covering/connected, and also (A,f,B) is target covering/connected just in case (B,f{-1},A) is source covering/connected. We show this for the two ``source'' properties. (A,f,B) is source covering = (Ax E A.(Ey E B.(x f y))) = (Ax E A.(Ey E B.(y f{-1} x))) (by definition of f{-1} and this is exactly the assertion that (B,f{-1},A) is target covering! (A,f,B) is source constricted = (Ax E A.Ayz E B.((x f y & x f z) -> y = z)) = (Ax E A.Ayz E B.((y f{-1} x & z f{-1} x) -> y = z)) which is the assertion that (B,f{-1},A) is target constricted! The other two cases go the same way. As a meatier example of a proof that a function is a bijection, I proved a theorem given above in the notes without proof: Theorem: Suppose that A ^ C = {} (A and C are disjoint) and B ^ D = {} (B and D are disjoint) and (A,f,B) and (C,g,D) are bijections. Then (A U B,f U g,B U D) is a bijection. I will actually only prove that it is source covering and source constricted; the proofs of the other two parts look much the same. Source covering: We need to show that for every x in A U C, there is y in B U D such that x (f U g) y (that is, (x,y) E f U g). Either x is in A or x is in C. If x is in A, there is y in B such that x f y, because f is a bijection and so source covering. This y is also in B U D, and clearly we also have x (f U g) y. If x is in C, there is y in D such that x g y, because g is a bijection and so source covering. This y is also in B U D, and clearly x (f U g) y. In both cases, we have established that there is y such that x (f U g) y, so we have established that (A U B,f U g,B U D) is source covering. The proof that (A U B,f U g,B U D) is target covering is essentially the same (except that the roles of A and B are interchanged and the roles of B and D are interchanged). Source Constricted (this is harder): We need to show that if x E A U C, x (f U g) y and x (f U g) z, then y = z. Suppose x E A U C, x (f U g) y and x (f U g) z. Either x E A or x E C. Suppose x E A. Then we have x f y and x f z, because we cannot have x g y or x g z, since x is not in the domain C of g (since we assumed that A and C are disjoint). By source constrictedness of f (following from bijectionhood of f) we have y = z as desired. Suppose x E C. Then we have x g y and x g z, because we cannot have x f y or x f z, since x is not in the domain A of f (since we assumed that A and C are disjoint). By source constrictedness of g (following from bijectionhood of g) we have y = z as desired. Since y = z follows in both cases, we have established that (A U B,f U g,B U D) is source constricted. The proof that (A U B,f U g,B U D) is target constricted is essentially the same (except that the roles of A and B are interchanged and the roles of B and D are interchanged). This completes the proof of the theorem. A student observed that it is interesting that the assumption that the domains and codomains are disjoint only comes into play in the proofs of the ``constricted'' properties. Symmetry is an important feature of proofs; it can reduce the amount of labor required, but one also has to be careful that one does not claim symmetry where it does not exist! Theorem: There is no injection from {0,1,2} into {0,1}. Proof: Suppose otherwise. Choose such an injection f. We have f(0) E {0,1}, so we have f(0) = 0 or f(0) = 1. Suppose f(0) = 0. Now observe that we also have f(1) = 0 or f(1) = 1 (for the same reason). But we cannot have f(1) = 0 because f is an injection. So f(1) = 1. Now consider f(2). f(2) =/= f(0) = 0 and f(2) =/= f(1) = 1, but f(2) = 0 or f(2) = 1 must hold as well. This is a contradiction. Suppose f(0) = 1. Now observe that we also have f(1) = 0 or f(1) = 1 (for the same reason). But we cannot have f(1) = 1 because f is an injection. So f(1) = 0. Now consider f(2). f(2) =/= f(1) = 0 and f(2) =/= f(0) = 1, but f(2) = 0 or f(2) = 1 must hold as well. This is a contradiction. In both cases we have derived a contradiction from the assumption that there is an injection from {0,1,2} into {0,1}, so this statement must be false. Notice that once again we have a symmetry between the two cases of our proof!