(Types of) induction on infinite chains

Question

This question may be trivial, or overly optimistic. I do not know (but I guess the latter...). I am a group theorist by trade, and the set-up I describe cropped up in something I want to prove. So this question is out of my comfort zone, but I am happy to clarify anything if needed.

I have a countable set $S$ equipped with a partial order $<$ and a minimum element $0$ (so $0<x$ for all $x\in S\setminus\{0\}$). I want to perform induction on chains which contain $0$, so $0<x<\dotsb<y<z$, in this order. As in: if property $P$ holds for $0, x, \dotsc, y$ then $P$ holds for $z$. Obviously I can perform induction on a finite chain. My question is:

What are my options if I want to to perform induction on infinite chains?

I believe one option would be transfinite induction, and in order to apply this I would need to prove that every chain not containing $0$ has a minimum element. But this condition on chains is unlikely to hold in my setting. So I am wondering: do I have any other options?

[An example to keep in mind is the chain with elements from $\{2^n\mid n\leq m\}\cup\{0\}$ for some fixed integer $m$, with the natural ordering inherited from $\mathbb{Q}$. So the chain $0<\dotsb<2^{m-1}< 2^m$. This example makes me think the question is not trivial - standard induction will not work.]

Answer 1

You seem to be asking about well-founded induction. It generalizes many forms of induction, including the usual induction on numbers and transfinite induction on ordinals.

Consider a relation $<$ on a set $A$. Say that $S \subseteq A$ is $<$-progressive when, for all $x \in A$, $$(\forall y < x \,.\, y \in S) \Rightarrow x \in S.$$ In words, an element is in $S$ as soon as all of its predecessors are. There is a logical counter-part: say that $\phi$ is a property of elements of $A$, then $\phi$ is $<$-progressive when, for all $x \in A$, $$(\forall y < x \,.\, \phi(y)) \Rightarrow \phi(x).$$

A well-founded relation is a relation $<$ on a set $A$ such that, if $S \subseteq A$ is $<$-progressive then $S = A$. A well-founded relation enjoys the following induction principle: If $\phi$ is a $<$-progressive property then $\phi(x)$ holds for all $x \in A$. In fact, the induction principle is just a reformulation of the definition of well-foundedness.

We have the following characterization:

Theorem. Let $<$ be relation on $A$. The following are equivalent:

1. $<$ is well-founded,
2. every nonempty subset $S \subseteq A$ has a $<$-minimal element,
3. there are no infinite descending chains $\cdots < x_3 < x_2 < x_1$ in $A$.

To summarize, a relation $<$ without infinite descending chains gives us the following induction principle: Suppose that for every $x \in A$ we have $(\forall y < x . \phi(y)) \Rightarrow \phi(x)$. Then $\forall z \in A. \phi(z)$.

The descending chain condition is useful for figuring out whether induction is valid. For example, we cannot use induction on $A = \{0\} \cup \{2^{-m} \mid m \in \mathbb{N}\}$ when we order $A$ using $<$, but we can if we order it with $>$.

A final remark: a linearly ordered well-founded relation is just a well-ordered relation. Induction on well-ordered relations is a bit more familiar, as it is just ordinal induction.

Answer 2

You can't just do induction on chains without adding extra info. If you could, I could give you the chain $0 < z$ and thus see without much inductive work that the property holds. To have a chance at classical induction, you need a concept of successor, i.e. a function $f : S \to S$, such that for every two elements $a,b \in S$ with $a < b$, you can construct a chain $a = a_0$, $a_{i+1} = f(a_i)$ and $a_m = b$ for a finite $m$.
As you come from group theory, try to think about composition series. You might be able to prove a result along such a series, but if you consider any sequence of subgroups, things will be a lot harder up to impossible.

For completeness sake, note that multiple functions $f$ are allowed. This plays a role for example in context free languages or regular expressions. You show that the desired property holds for the starting element(s) and you show that every rule in the language keeps the property intact, hence it holds for the whole language.

Regarding transfinite induction, we normally assume that a property holds for all $y < z$. That is much stronger than just assuming that it holds along a single chain (even if it is a fine one) up to $z$.

Unfortunately I don't fully understand your example. The set you have given contains all $2^n$ without any restrictions imposed by $m$ (the restriction $n \leq m$ is void as both $n$ and $m$ run trough all of $\mathbb{Z}$), so the set is just $\{2^n \mid n \in \mathbb{Z}\}$. Of course standard induction from small to big will not work here, as you don't have a smallest element in $\mathbb{Z}$, but two inductions, starting at $n = 0$ and going up and down should do the trick, depending on the property you want to show.