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
http://alpha.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 X$, 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 (POI2) and (POI3) 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.
[Edit: as Francois Dorais points out, adding a minimum is not enough; still a partially ordered set satisfying DCC need not have infima. So what I am asking about really is different from Noetherian induction.]
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 (POI2) modified slightly to
(POI2'): 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 (POI1), (POI2') and (POI3) but is proper.
Neither can I think of some small modification of (POI2') 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 casesas a special case the principle of ordered inductionand the principle of Noetherian induction?
Best Answer
Something very close to François' conditions achieves the desired if-and-only-if version of the theorem for partial orders, providing an induction-like characterization of the complete partial orders, just as Pete's theorem characterizes the complete total orders.
Suppose that $(P,\lt)$ is a partial order. We say that it is complete if every subset $A$ has a least upper bound $sup(A)$ and a greatest lower bound $inf(A)$. This implies that $(P,\lt)$ has a least and greatest element, and in this case, it is easy to see that completeness is equivalent to the assertion that every set has a greatest lower bound (the least upper bound of a set with upper bounds is the greatest lower bound of its upper bounds). The complete partial orders are exactly the complete lattices.
For the purpose of this question, let us define that $S\subset P$ is inductive if the following occur:
In (2), by a largest element, I mean an element that is larger than all other elements (in distinction with maximal element, a weaker concept). Conditions (2) and (3) are both slightly weaker than François' conditions. The difference in (2) is that we no longer assume that a condition $x\in S$ can be extended in any particular direction, and the difference in (3) is that we are not assuming here that $P$ is complete, but only that $S$ contains the suprema of its subsets, when these suprema exist.
Lastly, define that a partial order $(P,\lt)$ has partial-order induction if the only inductive set is all of $P$.
Theorem. For any partial order $(P,\lt)$, the following are equivalent:
Proof. For the forward implication, suppose $(P,\lt)$ is complete. It follows that $(P,\lt)$ has least and greatest elements, since these are the sup and inf of the emptyset. Suppose that $S\subset P$ is inductive. By (3) we know $sup(S)\in S$, which would make it the largest element of $S$, contrary to (2), unless $sup(S)$ is largest in $P$, in which case $S=P$ by (1). So $(P,\lt)$ has partial-order induction.
Conversely, suppose that $(P,\lt)$ has least and greatest elements and satisfies partial-order induction. We want to prove completeness. Suppose $B\subset P$ is nonempty and has no greatest lower bound. Let $S$ be the set of lower bounds of $B$. This is closed downwards, and so (1) holds. Since $B$ has no greatest lower bound, it follows that $S$ has no largest element, and so (2) holds. Finally, if $A\subset S$ and $sup(A)$ exists in $P$, then it remains a lower bound of $B$, since every element of $B$ is an upper bound of $A$ and $sup(A)$ is the least upper bound of $A$. Thus, (3) holds and so $S$ is inductive, contrary to the fact that it contains no elements of $B$. Thus, $B$ must have a greatest lower bound after all, and so $(P,\lt)$ is complete. QED
Note that when $(P,\lt)$ is a total order, then these concepts reduce to the conditions Pete mentions in the question (adding a least and greatest element if necessary). Thus, this theorem seems to be the desired generalization.
(I have deleted my other answer to the question, as it was based on a misunderstanding of the question.)