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.)
Best Answer
Goodstein's Theorem
http://en.wikipedia.org/wiki/Goodstein%27s_theorem
is proved using an induction of length $\epsilon_0$.