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.
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.)
In my humble opinion, the general principle should have a very similar proof to the original principle to be considered a proper generalization. After reconstructing a proof of your original principle, I obtained the following generalization.
Theorem. Let $X$ be a poset in which every nonempty set has an inf. (Note that $X$ has a minimal element $0$ and that every set which is bounded above has a sup.) If $S \subseteq X$ is such that:
- If $x \in S$ and $y < x$ then $y \in S$.
- If $x \in S$ and $x < y$ then there is some $z \in S$ such that $x < z \leq y$.
- Every subset of $S$ which is bounded above (in $X$) has its sup in $S$.
Then $S = X$. (Note that 3 formally implies that $0 \in S$ since $0$ is the sup of the empty set.)
This is slightly different than the original principle, but one recovers the original principle by applying the above theorem to the subset $S' = \{x \in X : [0,x] \subseteq S\}$ instead of $S$.
After writing down the proof I had in mind, I realized that condition 1 is not necessary.
Proof of Theorem. Suppose $y \notin S$. Let $x = \sup\{z \in S : z \leq y\}$. By 3, $x \in S$ and so $x < y$. By 2, there is a $z \in S$ such that $x < z \leq y$, which contradicts the definition of $x$. QED
This is a reply to Cam's question.
No, I did not base my talk directly on Kalantari's article, although I think it would be possible to do so. Instead I wrote up some lecture notes before the talk (and polished them a bit afterwards, once I realized I was on to something). See
http://alpha.math.uga.edu/~pete/realinduction.pdf
This document is not intended for publication. Please feel free to use it as you see fit.