Interpretation of induction in terms of symmetry transformations

1. Sep 22, 2014

Boorglar

It just occurred to me that induction can be seen as a statement quite analogous to that of "a function whose derivative is 0 on an interval is constant on that interval".

Suppose there is a property P about the natural numbers that we want to prove. Then let P: N -> {0, 1} be a function for which P(n) = 1 if P holds for n, and 0 otherwise.

Induction states that if one can show that P holds for 1, and that P holds for n+1 if P holds for n, then P holds for all natural numbers. But we can reinterpret this as saying that if P(1) = 1, and P(n+1)-P(n) = 0 (i.e. P is symmetric with respect to the successor operator), then P(n) = 1 for all n (i.e. it is constant on the set of natural numbers).

Here the "derivative" is the difference operator P(n+1) - P(n). The symmetry is the successor operator n -> n+1.
This is similar to how the derivative is related to infinitesimal translations, but in a discrete instead of continuous way.

So the inductive step means that P(n) is symmetric wrt translations (or the "Lie derivative" is 0), and so it is reasonable to believe that P should be constant. Then P(1) = 1 simply gives the value of this constant.

Is there any use of looking at induction this way? Could there be a generalization of induction on any set with a symmetry mapping in which differentiation (or difference) makes sense? It seems like induction could follow from some topological properties... After all, the statement about derivatives can be proven from the properties of real numbers

2. Sep 22, 2014

Boorglar

Actually yes induction is equivalent to the well-ordering property of natural numbers (every set of natural numbers has a smallest element). This is analogous to the greatest lower bound property for reals (which is used to prove the mean value theorem).

3. Sep 23, 2014

Citan Uzuki

Actually, this statement is a little bit weaker than induction. Induction states that $(P(1) \wedge \forall n (P(n) \Rightarrow P(n+1))) \Rightarrow \forall n P(n)$. Your statement is equivalent to $(P(1) \wedge \forall n (P(n) \Leftrightarrow P(n+1))) \Rightarrow \forall n P(n)$. Note the iff.

That being said, your weaker statement does have a couple of easy generalizations outside of the well-ordering property. For instance, consider the following statement:

Clearly, your weak induction property is just this statement applied to the graph formed from the natural numbers by inserting an edge between n and n+1 for every n. We can also consider this other statement:

We can consider this statement to be a generalization of the previous one by declaring a subset U of the nodes of G to be open if every neighbor of a node in U is itself in U (this basically amounts to declaring the open sets in G to be disjoint unions of the connected components of G). So it seems that the generalization that you were looking for at the beginning is the idea that a locally constant function on a connected set is constant.

4. Sep 23, 2014

Boorglar

Oh, I see you're right about the iff (instead of just one-way implication) in my reformulation (P(n+1)-P(n) = 0 means P(n+1) iff P(n)).

That is interesting. Yes, this is the sort of generalization I was looking for. Out of curiosity, is this statement true? It certainly seems pretty general. Are there some proofs that make use of a similar idea? I know about double-inductive proofs (which induct on two integers at the same time); this is what led me to look for generalizations.

5. Sep 24, 2014

Citan Uzuki

Yeah, it's true. The proof is pretty easy, simply note that $\{x \in X: P(x)\}$ is nonempty, open, and closed, so since X is connected, it must be all of X. This fact is the most commonly used way of proving that something is true on a connected domain.