Skip to main content
2 of 6
added 69 characters in body
Pete L. Clark
  • 65.4k
  • 12
  • 241
  • 381

A principle of mathematical induction for partially ordered sets?

Recently I learned that there is a useful analogue of mathematical induction over $\mathbb{R}$ (more precisely, over intervals of the form $[a,\infty)$ or $[a,b]$). It turns out that this is an old idea: it goes back to Khinchin and Perron, but has for some reason never quite caught on and thus keeps getting rediscovered. A nice recent paper is

www.math.uga.edu/~pete/Kalantari07.pdf

[As a side note, I gave a talk two days ago in the VIGRE Graduate Seminar at UGA -- essentially, a colloquium for graduate students, with talks which are supposed to be accessible to first and second year students -- about induction over the real numbers with applications to snappy proofs of essentially all the basic "hard theorems" of honors calculus / elementary real analysis. It was a smashing success: the students both enjoyed stretching their minds around this new form of induction and appreciated the application to consolidated proofs of theorems which were, in their recent memeory, not so quick or easy to prove.]

The way I like to state the principle is a little different from Kalantari's approach. [I actually got confused by Kalantari's "axioms for induction" when I first saw them and was under the impression that they were wrong. In fact I was wrong, and he quickly responded to my email on the subject, setting me straight and, kindly, mentioning that others had made the same mistake.] Here's my preferred version:

Let $(X,\leq)$ be a totally ordered set with a least element, which we may as well call $0$.

Say that $X$ has infima if...every nonempty subset $S$ of $X$ has an infimum.

Say that $S \subset X$ is an inductive subset if all of the following hold:
(POI1) $0 \in S$.
(POI2) For all $x \in S$, if there exists $z \in X$ such that $x < z$ -- in other words, if $x$ is not a maximum element of $X$ -- then there exists $y > x$ such that the interval $[x,y]$ is contained in $S$.
(POI3) For all $x \in S$, if $[0,x) \subset S$, then $x \in S$.

Finally, we say that $X$ satisfies the principle of ordered induction if the only inductive subset of $X$ is $X$ itself.

Theorem: For a totally ordered set $X$ with a minimum element, TFAE:
(i) $X$ has infima.
(ii) $X$ satisfies the principle of ordered induction.

The proof is straightforward. Applying this to half-closed intervals as above gives real induction. Also, applying it to a well-ordered set recovers transfinite induction exactly as it is usually stated -- i.e., with an extra axiom for "limit elements", even though one could formally combine (ii) and (iii) into a single case.

This issue came up on Tuesday on our sister site math.SE -- someone asked whether there was such a thing as real induction -- and I answered it, yes, as above. Then someone commented on my answer: what about generalizations to partially ordered sets?

There is a well-known principle of induction on partially ordered sets satisfying the descending chain condition, or equivalently, in which every nonempty subset has a minimum. This is called, by mathematicians of various stripes, well-founded induction or Noetherian induction. (As far as I can see it should be called Artinian induction. Anyone want to address that? Edit: I am satisfied by Dave Anderson's comment below.)

Note that a partially ordered set with DCC need not have a minimum element, which is certainly necessary for the above setup in totally ordered sets. But this isn't a big deal: if $(X,\leq)$ is a poset satisfying DCC, the poset $X_0$ obtained by adjoining a minimum element $0$ still satisfies DCC, and nothing is lost here.

After a little thought I was optimistic that there should be a version of induction partially ordered sets with a minimum element. I even thought that the right definition of inductive subset should be essentially the one given above, with (ii) modified slightly to

(ii'): for every $x \in S$ and $z \in X$ with $x < z$, there exists $y \in (x,z]$ such that the entire interval $[x,y]$ is contained in $S$.

And then I tried to prove that any poset with a minimum and having infima satisfies the principle of ordered induction. And I couldn't. Eventually I found the following counterexample: let $A$ be an infinite set and $X = 2^A$ be its power set, partially ordered by inclusion. Of course $X$ has infima: take the intersection. Let $S$ be the collection of all finite subsets of $A$. Then $S$ satisfies (i), (ii') and (iii) but is proper.

Neither can I think of some small modification of (ii') which evades this example. I still think there should be some kind of principle of induction in partially ordered sets with infima, but I don't know what to do. Can anyone state such a principle which recovers as special cases the principle of ordered induction and the principle of Noetherian induction?

Pete L. Clark
  • 65.4k
  • 12
  • 241
  • 381