In the first post, I mentioned the three thoughts that occurred to me the first time I ever saw an induction proof; to wit:

- WTF did I just see?
- How did that even work?
- How did they ever come up with this?

The first post was meant to address the first question more fully by making the process of proving something by induction more clear. The second post and this one are meant to address the second and third questions.

Last time we went over the Peano axioms, which include the induction axiom:

- For any set of natural numbers , if and , then the set contains all natural numbers.

Isomorphism will show us how we can create a set of natural numbers that represent some other object, like sums or binary trees, prove things about that set, and translate those proofs into proofs about our original objects. We assume that this set includes just the natural numbers corresponding to objects with some quality we like, such as having nodes in level . Then we can prove that the set has the properties asked for in the inductive axiom, which shows that it includes all natural numbers. This means the set of all natural numbers corresponding to objects with the quality we like is, in fact, the set of all natural numbers. The isomorphism allows us to conclude that every one of the objects has the quality we like.

If you were to use Unlimited Rulebook: Secession Version and jump a thousand feet into the sky, that’s the view you’d see of how an induction proof really works. Let’s get a little bit closer and examine how isomorphisms really let us do all this amazing stuff.

## The Missing Link: Isomorphism

Isomorphism is a very deep mathematical idea, one that I won’t go into too much, because it’s very profound and I would just embarrass myself. The best explanation I’ve found of the idea for non-mathematicians is in Douglas Hofstadter’s *Gödel, Escher, Bach*. But here’s the “For Dummies” version of the idea.

An isomorphism is a transformation between two sets. It’s basically a function, but a special kind: it preserves all the properties of the set.

Say we have a list of items and we’ve chosen to number the items, like this:

- Hitagi Crab
- Mayoi Snail
- Suruga Monkey
- Nadeko Snake
- Tsubasa Cat
- Karen Bee
- Tsukihi Phoenix

We could have just as easily given each item a letter, like this:

- Hitagi Crab
- Mayoi Snail
- Suruga Monkey
- Nadeko Snake
- Tsubasa Cat
- Karen Bee
- Tsukihi Phoenix

It’s pretty obvious that that’s the same list. It has the same items in the same order; nothing has actually changed except for the labels we use to refer to items. In other words, there is an isomorphism between the first list and the second list, a function that maps numbers 1–7 to letters a–g. If we know Nadeko Snake is number 4 in the first list and want to know where Nadeko Snake falls in the second list, we can calculate and see that it’s d, so we know Nadeko Snake is at position d in the second list.

When you do an induction proof and choose what to “induct on”, you’re actually constructing an isomorphism between the object the proof is about and the natural numbers. In our first binary tree example, we wanted to prove that level of a binary tree has nodes. We inducted on the exponent of 2. We can also say that we mapped a level of a binary tree to a natural number label, and then showed that there’s a formula for the number of nodes in a level that depends on the label that level gets in our labeling scheme, and that the formula works for any label, as long as the label is a natural number.

In the second example, we wanted to show that a binary tree with levels has nodes. Here we chose to induct on the number of levels; we mapped the tree to a natural number which represented the number of levels it had. We then showed there was a formula that would let you calculate how many nodes the tree had based on the number of levels it had in our labeling scheme. The labeling of trees according to how many levels they have was the isomorphism.

In the classic example, proving that , we induct on . It helps here if you can think of the sum as a single object with no internal structure that changes according to what is set to. Think of it like a Borg drone, say. A drone is just a drone; they’re basically all the same, except for whatever label we gave them when we lined them up. Think of these sums like that; they’re basically all the same, except for the label we give them.

Next time we’ll use isomorphisms and the Peano axioms to finish answering the second point from the above list: how does induction even work? How does it actually prove that some pattern remains valid off into the infinity of the natural numbers? We’ll see.

Summary

- Isomorphisms are basically functions that “relabel” a set of objects. Although the objects are reanamed, they still have the same properties they did before.
- When you write an induction proof and choose what to induct on, you are constructing an isomorphism from the objects you care about (binary trees, sums, regions of a circle, horses, whatever) to the natural numbers.