168 Chapter 14

Mathematicians give a lot of respect to their isomorphism concepts. We consider iso-

morphisms not just between orders but between graphs, between vector spaces, between

groups, rings, and fields, and so on. Every mathematical structure gives rise to a corre-

sponding isomorphism concept: two mathematical structures are isomorphic just in case

there is an isomorphism between them, a bijective function copying the objects and re-

lations of the first structure exactly to form the second structure. Thus, structures are

isomorphic exactly when they are copies of each other, and the isomorphism function de-

tails exactly how the copying is carried out, linking each object in one structure with its

counterpart in the other. The mathematical attitude toward mathematical structure is that

we only ever care about our mathematical structures up to isomorphism—having an iso-

morphic copy of the structure is just as good, for any mathematical purpose, as having any

other copy of it.

Let us illustrate the isomorphism concept by showing that P

fin

(N) is isomorphic to an-

other familiar order. In chapter 3, we defined that a positive integer is square-free if it is not

a multiple of any perfect square larger than 1. Equivalently, n is square-free if the prime

factorization of n consists of distinct primes, each appearing with exponent one. Let us

denote by SF the set of square-free positive integers.

Theorem 127. The partial order of finite sets of natural numbers P

fin

(N), ⊆!is isomorphic

to the partial order of square-free positive integers under divisibility

SF, |

!

.

Proof. Let us associate every square-free number with the set of primes that divide it. This

is a finite set of primes, and because every square-free number is determined by the set

of primes that divide it, it follows that different square-free numbers have different prime

divisors. Furthermore, division of numbers corresponds to inclusion of these sets of primes,

in the sense that n | m just in case every prime factor of n is also a prime factor of m. And

every finite set of prime numbers arises as the prime factors of the corresponding product,

obtained simply by multiplying those primes together. Thus, the association of a square-

free number with its set of prime divisors is an isomorphism of

SF, |

!

with the collection

of finite sets of prime numbers

P

fin

(P), ⊆

!

, where P is the set of prime numbers, ordered

by inclusion. Since there are infinitely many primes, we may also see that

P

fin

(P), ⊆

!

is

isomorphic to

P

fin

(N), ⊆

!

, since any bijection between the set of primes P and N extends

to the finite subsets of these sets under inclusion.

That was a soft approach, providing a somewhat abstract proof that the two orders are

isomorphic. The reader is asked in the exercises to provide an explicit isomorphism be-

tween P

fin

(N) and SF.

14.5 The rational line is universal

Let us turn now to Cantor’s remarkable theorem about the rational number order.