30 2. Background no two domain elements map to the same range element. It is sur- jective, or onto, if the codomain equals the range. Since no function can take a single domain element to multiple range elements, and by definition it must give an image (output) to every domain ele- ment (well... see §3.1.2), a function that is both one-to-one and onto uniquely pairs off the elements of the domain and codomain. Such functions are called bijections. Some authors will refer to a bijection as a “one-to-one correspondence they are also called permutations. For sets, bijections are everything. It does not matter whether we use the letters A through Z or the numbers 1 through 26 a set of the same size is essentially the same set. Two sets (without structure) are isomorphic if there is a bijection between them. Two sets with additional structure may be bijective without being isomorphic. When there are relations (including functions) on the elements, to say two structures are isomorphic we need a special kind of bijec- tion: one that preserves the relations. For example, an isomorphism between two partial orders P and Q is a bijection f : P Q such that for all x, y P , x ≤P y f(x) ≤Q f(y). As a consequence, any logical statement about the relation will hold in one structure if and only if it holds in the other, such as ∀x∃y(x y). Isomorphism must be defined separately for each kind of object, but it follows the same template each time: a bijection that preserves the structure. Example 2.4.1. Let A = {{1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}} and B = {∅, {a}, {b}, {a, b}}. A and B are in bijection, or isomorphic as sets. However, they are not isomorphic as partial orders, under the relation of subset inclusion. A is a linear order and B a diamond A satisfies the statement ∀x ∀y (x y y x) and B satisfies its negation, ∃x ∃y (¬(x y)&¬(y x)). An isomorphism between a structure and itself is called an auto- morphism. 2.5. Recursion and Induction Recursive definitions and proofs by induction are opposite sides of the same coin. Both have some specific starting point, and then a way to extend from there via a small set of operations. For induction, you
Previous Page Next Page