2.4. Bijection and Isomorphism 29
ˆ c


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
We can ramp this up even further to multi-
variable functions, functions from
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
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