BACKGROUND 9 We shall be particularly interested in invertible functions. The following definitions are relevant in this context. Definition. We say that / is an onto or surjective function if R = T. For each r e /?,we set f-\r) = {deD:f(d)=r}. We say that / is a one-to-one or injective function if / _ 1 ( r ) contains only one element for each r e R. If / is both one-to-one and onto, then we say that / is bijective or a one-to-one correspondence or an isomorphism between D and T .If D = T and / : D -* D is bijective, then often / is called a permutation of the set D, especially if D is a finite set. Whenever / : D -+ T is bijective, the set {(t,f-\t)):teT}TxD is the graph of a function f~l : T - D. We call f~l the inverse of the function / . Definition. We say that the sets D and T have the same cardinality if there is a one-to-one correspondence / : D —• T. We write |D| to denote the cardinality of the set D. If D has the same cardinality as the set of natural numbers {l,2,...,w}, then we write \D\ = n. Pigeon-Hole Principle. If A is a subset of the finite set B and if A and B have the same cardinality, then A = B. Note that the Pigeon-Hole Principle is true only for finite sets. For example the set N of natural numbers and the set 2N of even natural numbers have the same cardinality but are obviously not equal. If D = T, then we can form the composition / o g of two functions / : D - D and g : D - D: fog(d) = f(g(d)). Of course we can also form g o / , and usually these two functions are not equal. Again it is useful to think of / o g dynamically as "first do g to D, then do / . " This operation of composition of functions will be of absolutely crucial significance to us. For any set D, there is a distinguished bijective function / : D — • D, called the identity function, defined by the rule I(x) = x for all x e D. Thus, speaking dynamically, / is the function that "does nothing" to D. Every point of D is a fixed point of / . If / : D - D is a bijective function, then the inverse function / ~ 1 is characterized by the functional equation / o Z " 1 = / = Z " 1 o / . Note that in all cases, equality of functions f = 8 means f{x) = g(x) for all x e D, where D is the domain of both / and g.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2003 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.