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