$$

Structure Preserving Maps

The aim of this lecture is to convince you of the crucial concept of a structure preserving map. It pervades all of computer science, mathematics and physics ^[1] and appears in many different incarnations, the simplest one coming from universal algebra.

We will use ideas from our lecture on universal algebra

• to illustrate the importance of structure preserving maps from the point of view of data types and

• to axiomatise induction in a completely syntax independent way using nothing more than the notion of a structure preserving map.

We start with the following question that will lead us right to the heart of the issue.

Are there more rational numbers than integers?

What do you think: Are there more rational numbers than integers?

(This is one of those great questions where both yes and no is a correct answer depending on how you justify it.)

Convention: Only for this lecture, when I talk about rationals and integers I mean the positive rationals and positive integers and I denote them by

$\mathbb{Q}$ and

$\mathbb{N}$, respectively.

Conclusion 1: There are strictly more rationals than integers.

There are more rationals than integers

At first, it seems obvious that there are more rationals than integers.

We can visualise this by looking at the numberline where there are gaps between integers, but the rationals are dense.

In symbolic notation, we look at the inclusion

$$\mathbb{N}\hookrightarrow \mathbb{Q}$$

which is injective but not surjective, hence not bijective: Every integer is a rational, but there are rationals that are not integers.

There are more integers than rationals

But maybe we can encode rationals by integers?

After all, we know that rationals are stored in a computer as sequences of bits and that every sequence of bit is an integer in binary notation.

This suggests that there is an injective function

$$\mathbb{Q}\to \mathbb{N}$$

showing that there are at least as many rationals as integers. Equivalently, and easier to explain, we can also look for a surjective function

$$\mathbb{N}\to \mathbb{Q}$$

We know from the fact that rationals can be represented on a digital computer that such a map must exist.

But what is an easy way to describe such a map explicitely?

It was found by Cantor and is most easily given by a picture. You can derive from the picture an algorithm that computes the functions

$\mathbb{Q}\to \mathbb{N}$ and

$\mathbb{N}\to \mathbb{Q}$ via going through a while loop. You can also challenge your math-muscles and derive an explicit formula that does not need going through a loop.

Remark: The map

$\mathbb{N}\to \mathbb{Q}$ given by the picture assigns more than one code to each rational as eg

$1/2=2/4$. Thus the picture gives a surjective but not bijective

$\mathbb{N}\to \mathbb{Q}$. But we define a bijective map from it by eliminating duplicate codes.

Conclusion 2: There is a bijection between integers and rationals. In other words, there are exactly as many integers as there are rationals.

It seems that we reached a contradiction between the two Conclusions.

Thinking about it, it looks like Concusion 2 is winning. Because, by reaching Conclusion 1, we made a mistake. We argued that an map

$A\to B$ that is injective but not surjective proves that there are strictly more

$B$ than

$A$. This is true for finite sets, but wrong for infinite sets.

Nevertheless, Conclusion 1 looks intuitively correct. So can we restore intuition and justify it by an explanation that stands up to scientific standards of scrutiny?

The answer is yes and what we need for the justification is the notion of structure preserving map.

Structure preserving maps

Extending Conclusion 2, we can say that all countably infinite sets are of the same size.

This is familar for us from programming. All infinite data types can be encoded by sequences of bits, so any infinite data type can be encoded by any other infinite data type.

But, surely, that does not mean that all data types are the same.

How do we solve this conundrum?

We get our cue from the previous discussion of abstract data types: Data types are more than data, they are also operations on data.

So in what sense is the inclusion

$$\mathbb{N}\hookrightarrow \mathbb{Q}$$

a "good" map but the encoding

$$\mathbb{N}\to \mathbb{Q}$$

a "bad" map?

$\mathbb{N}\hookrightarrow \mathbb{Q}$ preserves all the structure relevant to us in our example: addition and multiplication, but also division and substraction where defined. ^[2]

$\mathbb{N}\to \mathbb{Q}$ does not preserve addition and multiplication. Can we make this precise?

Let us denote by

$h$ the map

$\mathbb{N}\to \mathbb{Q}$.

Exercise: Find examples that show that addition and multiplication are not preserved by

$h:\mathbb{N}\to \mathbb{Q}$. In other words, find integers

$n,m$ such that

$$h(n+m)\ne h(n)+h(m)$$ and similarly for multiplication. (Hint: Actually, any numbers

$n,m$ should do.)

Claim: There is no structure preserving bijection ^[3]

$$\mathbb{N}\to \mathbb{Q}.$$

Conclusion 3: To summarize:

• If we define, as is usual, that two sets have the same size if there is a bijection between them, then
  $\mathbb{N}$ and
  $\mathbb{Q}$ have the same size. This justifies Conclusion 2.
• There is no structure preserving bijection between
  $\mathbb{N}$ and
  $\mathbb{Q}$ (where I mean structure, in this example, to refer to addition (or just "
  $+1$") and/or multiplication). Thus, if we understand
  $\mathbb{N}$ and
  $\mathbb{Q}$ as algebra (ie data types) equipped with addition and/or multiplication instead of as mere sets, Conclusion 1 is justified.

Remark: Addition and multiplication are examples of algebraic structure, given by operations, ie, functions. There are other example of structure, such as relational structure. For example we may ask: Is there an order-preserving bijection

$\mathbb{N}\to \mathbb{Q}$? ^[4]

Do all infinite sets have the same size?

This is an excursion that leads a bit off the main thread, so feel free to skip. But it is too important to not stop for a few comments.

We have seen that Cantor showed that there are as many rationals as integers. Sets that have the same size, or cardinality as one says in mathematics, as the integers are called countable. Obviously, by definition, all countably infinite sets have the same size. Cantor's discovery was that there are more countably infinite sets than one might first think. Even the rationals, that are dense on the numberline, are countable.

But even more importantly, Cantor also showed that we cannot simply say: "Integers and Rationals have the same size because they are both infinite". In fact, Cantor showed that the infinite sets form an infinite hierarchy of ever strictly bigger infinite sets. The mathematical area called set theory studies this infinite hierarchy of infinite sets.

Exercise: If you know Cantor's proof that there is no bijection from integers to reals, think about why this proof fails to show that there is no bijection between integers and rationals.

---

1. … and much more … linguistics is another area and I am sure we can think about more. ↩︎

2. In programming terms: If we first type-cast the integers 1 and 2 to floats 1.0 and 2.0 and then add them as floats we get the same result as if we first add 1 and 2 and then type-cast the result to a float. In other words, type casting, which is a map int->float, preserves addition (and multiplication and a lot of other operations). ↩︎

3. Let

   $h:\mathbb{N}\to \mathbb{Q}$ preserve addition. Then
   $h$ is order-preserving, that is,
   $n\le m\Rightarrow h(n)\le h(m)$. Also,
   $h$ is injective (recall that, in this chapter, we write
   $\mathbb{N}$ and
   $\mathbb{Q}$ for the sets of positive integers/fractions). So while there are infinitley many fractions between
   $h(1)$ and
   $h(2)$, none of them can be in the image of
   $h$. We have shown that
   $h$ is not bijective. ↩︎

4. Preservation of addition implies preservation of order. But the converse is not true. So there are more order-preserving maps than addition preserving one. Nevertheless, the answer to the question is "No". ↩︎