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