2.4. Bijection and Isomorphism 29

A

✁✁✁✁✁✁✁✁

❃❃❃❃❃❃❃❃

ˆ c

❂

❂❂❂❂

ˆ

b

✁✁✁✁❂✁❂❂

✁

✁✁

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

1You

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.