2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Examples like this are talked about in MathOverflow question 38238. Gerhard "Not Doing Blue Lines Presently" Paseman, 2019.03.21. $\endgroup$ – Gerhard Paseman Mar 21 at 15:56
  • 1
    $\begingroup$ Your definition of "minimal" is in fact "minimum". $\endgroup$ – Asaf Karagila Mar 21 at 18:48
  • $\begingroup$ @GerhardPaseman Thanks for the link - that looks something like what I am after! $\endgroup$ – NotDominicRaab Mar 22 at 8:48
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Well-founded relations do not have to be transitive, transitivity does not enter well-founded induction in any way. Also, considering the original question, it might be worth stressing that this is a complete characterization: induction holds for a binary relation if and only if it is well founded. $\endgroup$ – Emil Jeřábek Mar 22 at 13:03
  • $\begingroup$ @EmilJeřábek: I did not require that a well-founded relation be transitive, so what are you talking about? Transitivity is needed for the theorem only, as stated. I will stress that the induction is the same thing as well-foundedness. $\endgroup$ – Andrej Bauer Mar 22 at 15:36
  • $\begingroup$ You don’t need transitivity or irreflexivity for the theorem. You do not need the reflexivization $\le$ either, if you simply state condition 2 so that $S$ has a $<$-minimal element. $\endgroup$ – Emil Jeřábek Mar 22 at 15:41
  • $\begingroup$ I am not aware of a proof that doesn't require transitivity. The one I have does. Do you have a reference? $\endgroup$ – Andrej Bauer Mar 22 at 17:26
  • $\begingroup$ This is an absolutely elementary proof. 1 and 2 are really just contrapositive of each other. For 2->3, if $\dots<x_2<x_1<x_0$ is an $<$-chain, then $\{x_i:i\in\omega\}$ has no $<$-minimal element. For 3->2, assume that $X$ has no $<$-minimal element, and fix $x_0\in X$. Using dependent choices, find a sequence $\langle x_i:i<\omega\rangle$ of elements of $X$ such that $x_{i+1}<x_i$ for each $i$; that there is always a next element to choose from is precisely the statement that $X$ has no $<$-least element. You obtain a $<$-descending chain. $\endgroup$ – Emil Jeřábek Mar 22 at 17:56
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry, in my example $m$ was meant to be fixed. I've edited this in. $\endgroup$ – NotDominicRaab Mar 21 at 14:34
  • $\begingroup$ It'll probably take me a while to process everything you wrote, but regarding your first sentence: I know this, and my question is trying to work out what extra info. I might need. $\endgroup$ – NotDominicRaab Mar 21 at 14:35
  • $\begingroup$ This makes it even easier. In that case, you have a starting point for your chain, $2^m$, and go down from there, completely classical induction. You just need to treat the 0 by hand. $\endgroup$ – Dirk Mar 21 at 14:35
  • $\begingroup$ I think you are taking my chain to be upside-down (but I'm not sure, and I hope you are correct!). I know that the result holds for $0$, and that if it holds for $2^k$ then it holds for $2^{k+1}$. I want to understand $2^m$. The issue, as I see it, is that I need to somehow "connect" the infinite descending chain of $2^k$s with the minimal element $0$. $\endgroup$ – NotDominicRaab Mar 21 at 14:39
  • 1
    $\begingroup$ Yes, ok, in this case induction doesn't work, as you have no way to get from $0$ to $2^{-\infty}$, so to speak, there is no proper successor of $0$. That's why I suggested to take a different starting point in this case, because we have a rather easy rule to go from $2^k$ to $2^{k-1}$, and also a highest starting point. As you want to show that the property holds for all elements of the set, it shouldn't make a difference if you start at $0$ or at $2^m$. $\endgroup$ – Dirk Mar 21 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.