Return to Answer

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

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

Let me tweak François' conditions slightly and achieve the desired if-and-only-if version of the theorem for partial orders having least and greatest elements.

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, completeness is equivalent to the assertion that every set has a greatest lower bound. The complete partial orders are exactly the complete lattices.

• (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) Every subset $A\subset S$ for which $sup(A)$ exists in $P$ has $sup(A)\in S$.

Another way to express (3) is: 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 they exist.

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)=1$, in which case $S=P$ by (1). So $(P,\lt)$ has partial-order induction.

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.

• (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.

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.

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 they exist.

Another way to express (3) is: 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 they exist.