1. Reminder: transformations form a group

Last time, we studied transformations of finite incidence geometries. We used several ideas repeatedly. For example, if a line has two points, then its image under a transformation is again a line with two points. Also, if two lines meet at a point, then their images are two lines meeting at the image of that point.

Today, we study an infinite example.

First, recall that a group is a set \(G\) together with an operation which takes two elements of \(G\) and gives back another element of \(G\). The operation must satisfy the following properties:

(a)

Closure: if \(g,h\in G\), then \(g\ast h\in G\).

(b)

Neutral element: there is an element \(e\in G\) such that \(g\ast e=e\ast g=g\) for every \(g\in G\).

(c)

Inverse: for every \(g\in G\), there is an element \(h\in G\) such that \(g\ast h=h\ast g=e\).

(d)

Associativity: parentheses do not matter.

In our case, if \(\mathcal M\) is a model satisfying axioms I1 and I2, then \(\operatorname {Aut}(\mathcal M)\), with composition, is a group.

In practice, this means:

• if \(f\) and \(g\) are transformations, then \(f\circ g\) is a transformation;
• the identity map is a transformation;
• if \(f\) is a transformation, then \(f^{-1}\) is also a transformation;
• when composing transformations, parentheses do not matter.

2. Other examples of groups

3. The integer line

We now define a model \(\mathcal M_{\mathbb Z}\). The points are

The lines are the subsets of the form

Thus \(\{0,1\}\), \(\{1,2\}\), \(\{2,3\}\), \(\{-1,0\}\), and \(\{-2,-1\}\) are lines.

The goal of this activity is to determine

A transformation of \(\mathcal M_{\mathbb Z}\) is a bijection \(f:\mathbb Z\to \mathbb Z\) such that, for every \(k\in \mathbb Z\), the image

is again a line. In other words, \(f(k)\) and \(f(k+1)\) must be consecutive integers.

4. First examples and non-examples

No. Let \(f\) be this map. Then

But \(\{0,2\}\) is not a line, because \(0\) and \(2\) are not consecutive. Hence \(f\) is not a transformation.

No. Let \(f\) be this map. Then

Again, \(\{0,2\}\) is not a line. Hence \(f\) is not a transformation.

5. Translations

For every \(\ell \in \mathbb Z\), define

We claim that \(T_\ell \) is a transformation.

First, \(T_\ell \) is a bijection. Its inverse is \(T_{-\ell }\), since \(T_{-\ell }(T_\ell (k))=k\).

Second, \(T_\ell \) sends lines to lines. Indeed,

This is the line

Therefore \(T_\ell \) is a transformation.

6. Reflections

Define

We claim that \(s\) is a transformation.

First, \(s\) is a bijection, and \(s^{-1}=s\). Second,

This is a line, because \(-k-1\) and \(-k\) are consecutive. Thus \(s\) is a transformation.

More generally, for any \(a\in \mathbb Z\), the map

is a transformation. It is the composition \(T_a\circ s\).

7. Normalizing an arbitrary transformation

Let \(f\in \operatorname {Aut}(\mathcal M_{\mathbb Z})\). Suppose

We want to reduce to the case where \(0\) is fixed.

Since \(T_{-m}\) is a transformation, the composition

is also a transformation. Moreover,

Now we ask: where can \(g(1)\) go?

Since \(\{0,1\}\) is a line, its image under \(g\) must be a line:

The only lines containing \(0\) are \(\{-1,0\}\) and \(\{0,1\}\). Therefore

Thus every transformation can be normalized so that \(0\) is fixed, and then there are two cases:

or

8. Case 1: \(g(0)=0\) and \(g(1)=1\)

We now prove that if \(g\in \operatorname {Aut}(\mathcal M_{\mathbb Z})\), \(g(0)=0\), and \(g(1)=1\), then

Step 1: showing that \(g(2)=2\)

Since \(\{1,2\}\) is a line, its image is a line:

Thus \(g(2)\) must be adjacent to \(1\). Therefore

But \(g(0)=0\), and \(g\) is injective. Since \(2\neq 0\), we cannot have \(g(2)=0\). Therefore

Step 2: showing that \(g(3)=3\)

Since \(\{2,3\}\) is a line, its image is a line:

Thus \(g(3)\) must be adjacent to \(2\). Therefore

But \(g(1)=1\), and \(g\) is injective. Since \(3\neq 1\), we cannot have \(g(3)=1\). Therefore

9. Reminder: what is induction?

We now want to show that \(g(k)=k\) for all nonnegative integers \(k\).

When a pattern repeats, a common proof strategy is induction. The idea is the following. Suppose we want to prove a statement \(P(n)\) for every integer \(n\geq 0\). It is enough to prove:

(a)

Base case: \(P(0)\) is true.

(b)

Induction step: assuming \(P(k)\) is true, prove \(P(k+1)\).

We will use a slightly stronger version, called strong induction. To prove \(P(n)\) for all \(n\geq 0\), we prove:

(a)

Base case: \(P(0)\) is true.

(b)

Strong induction step: assuming \(P(0),P(1),\dots ,P(k)\) are true, prove \(P(k+1)\).

10. Step 3: showing that \(g(k)=k\) for all \(k\geq 0\)

We prove by strong induction that

for all \(k\geq 0\).

The base case is \(k=0\), and it is true because \(g(0)=0\).

Now assume that \(g(0)=0,g(1)=1,\dots ,g(k)=k\), where \(k\geq 1\). We want to prove that \(g(k+1)=k+1\).

Since \(\{k,k+1\}\) is a line, its image is a line:

Therefore \(g(k+1)\) must be adjacent to \(k\). Hence

But \(g(k-1)=k-1\) by the induction hypothesis, and \(g\) is injective. Since \(k+1\neq k-1\), we cannot have \(g(k+1)=k-1\). Therefore

By strong induction,

for every \(k\geq 0\).