Interpretation of induction in terms of symmetry transformations

[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

 

[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).

 

[Citan Uzuki]

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).

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:

Let G be a connected graph, and P a predicate on the nodes of G. Suppose that there is a node x₀ for which P(x₀), and that for all pairs of adjacent nodes x and y, P(x) iff P(y). Then for all nodes x, P(x) holds.

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:

Let X be a connected topological space, and P a predicate on X. Suppose that P is locally constant, meaning that for each x in X, there is an open neighborhood U of x such that for all y in U, P(y) iff P(x). Then if there is some x₀ in X for which P(x₀) holds, then P(x) holds for every x in x.

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.

 

[Boorglar]

Actually, this statement is a little bit weaker than induction

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)).

Let X be a connected topological space, and P a predicate on X. Suppose that P is locally constant, meaning that for each x in X, there is an open neighborhood U of x such that for all y in U, P(y) iff P(x). Then if there is some x0 in X for which P(x0) holds, then P(x) holds for every x in x.

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.

 

[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.