2.4. Bijection and Isomorphism 29 A ✁✁✁ ✁✁✁ ❃❃❃ ❃❃❃ ˆ ❂❂ ❂✁ ❂❂❂ ˆ ✁✁ ✁✁ ✁✁ ❂❂ ❂❂ ˆ ✁✁✁ ✁❂✁❂❂ ✁✁ a ❃❃ ❃❃❃ ❃❃❃ b c Figure 2.1. Subsets of {a, b, c}. Our final note is to point out relations generalize functions. The function f : A A may be written as a binary relation on A consist- ing of the pairs (x, f(x)). A binary relation R, conversely, represents a function whenever [(x, y) R & (x, z) R] y = z (the vertical line rule for functions).1 We can ramp this up even further to multi- variable functions, functions from An to A, by considering (n+1)-ary relations. The first n places represent the input and the last one the output. The advantage to this is consolidation we can prove many things about functions by proving them for relations in general. 2.4. Bijection and Isomorphism As mentioned, a function f : A B may be thought of as a relation Gf A×B, the Cartesian product of its domain (also denoted dom f) and codomain, though the property that every element of A appear in exactly one pair of Gf is not particularly natural to state in terms of relations. Gf is called the graph of f. Before we proceed recall also that the range of f, rng f, is {f(x) : x A} B. When are two sets “the same?” How about two partial orders? The notion of isomorphism is, loosely, the idea that two mathematical structures may be essentially the same, even if cosmetically different. Recall that a function between two sets is injective, or one-to-one, if 1 You might object that this does not require every element of A be in the domain of the function. We will not be concerned by that see §3.1.2.
Previous Page Next Page