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 cases~~ as a special case the principle of ordered induction ~~and the principle of Noetherian induction~~?
> 
> 
> 



A principle of mathematical induction for partially ordered sets with infima?
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](http://en.wikipedia.org/wiki/Complete_lattice).


For the purpose of this question, let us define that
$S\subset P$ is *inductive* if the following occur:


* (1) $S$ is downward closed: $y\lt x\in S\to y\in S$;
* (2) $S$ has no largest element, except possibly the largest element of $P$;
* (3) If $d=sup(A)$ for some $A\subset S$, then $d\in S$.


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:


* $(P,\lt)$ is complete.
* $(P,\lt)$ has least and greatest elements and satisfies partial-order induction.


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


