22
$\begingroup$

The Order Extension Principle (OEP) is the proposition that every partial order on a set can be extended to a linear order on the same set. The OEP is a theorem of ZFC but not of ZF, and it is among the many choice principles that appear in a book such as Axiom of Choice by Herrlich.

Among notions between those of posets and linearly ordered sets is that of directed sets. One can think of an analogue of the OEP but for directed sets: every partial order on a set can be extended to an order that makes the set directed. Is this a theorem of ZF? (The statement was not on the said book.)

$\endgroup$
5
  • $\begingroup$ I see Zermelo-Fraenkel axioms has something to do with axiom of choice, but how it is different from axiom of choice? $\endgroup$ – Charlie Chang Aug 1 '20 at 4:26
  • 2
    $\begingroup$ Just a remark for someone who is trying to solve this: any counterexample must have no maximal elements. So "the obvious" attempts with amorphous sets are doomed to fail. $\endgroup$ – Asaf Karagila Aug 1 '20 at 23:58
  • $\begingroup$ @CharlieChang See the first paragraph here. $\endgroup$ – Alex Kruckman Aug 2 '20 at 1:02
  • $\begingroup$ I think I have a proof that this is not provable in ZF but the details are kind of messy and it will take me a little while to write up. $\endgroup$ – Patrick Lutz Aug 7 '20 at 16:36
  • $\begingroup$ Actually, the proof I had in mind doesn't seem to work (as I discovered when I tried to actually write it down). $\endgroup$ – Patrick Lutz Aug 15 '20 at 23:26
3
$\begingroup$

No, there is a model of ZF with a partial order that cannot be extended to a directed order.

Since we're just trying to find a weird object, we can use a Fraenkel-Mostowski permutation model and apply an embedding theorem, such as the First Embedding Theorem in Jech, The Axiom of Choice, Chapter 6. (I haven't checked Herrlich's book to see if there is a relevant theorem there.)

Take the set of atoms $A$ to be the free Boolean algebra on a countable set of generators. For each finite subalgebra $B$ define $G_B$ to be the automorphisms of $A$ fixing $B.$ The permutation group consists of all automorphisms of $A,$ and the normal filter is generated by $\{G_B:\text{finite subalgebras }B\subset A\}.$

This gives us a permutation model $\mathcal N$ which contains the Boolean algebra $A.$ The Boolean algebra gives $A$ the partial order where $a\leq b$ means $a\Rightarrow b.$ Consider a partial order $\preceq$ on $A\setminus\{0_A\}$ extending $\leq.$ I will show that $\preceq$ is not downwards directed i.e. the opposite order is not directed. (I'm dualizing here because it will be notationally neater to use small elements rather than big elements.)

There is a finite subalgebra $B\subset A$ such that $\preceq$ is fixed by the extension of $G_B$ to an automorphism of $\mathcal N.$ Let $a_1,\dots,a_k$ be the atoms of $B$ (the $\leq$-minimal elements of $B\setminus \{0_A\}$).

$A$ is homogeneous, in fact a Fraïssé limit, which means we can pick new elements with any desired consistent relation to a finite set of existing elements, and to extend automorphisms of any finite subalgebra to the whole of $A.$

Lemma: For all $i$ and all $0\leq b,c\leq a_i$ we have $b\preceq c \implies b\leq c$.

Proof: We only need to consider the case that $b$ and $c$ are $\leq$-incomparable but $b\prec c.$ Let $d=b\wedge c.$ If $d=0$ then we can use an automorphism swapping $b$ and $c$ to deduce $c\prec b.$ If $d>0,$ write $b'=b-d$ and $c'=c-d.$ We can use an automorphism cycling $b'\to d\to c'\to b'$ two times to get from $b'\vee d\prec c'\vee d$ to $d\vee c'\prec b'\vee c'$ and then to $c'\vee b'\prec d\vee b'.$ This gives $c\preceq b.$ In either case we have contradicted antisymmetry of $\preceq.$ $\Box$

Pick $b_1,\dots,b_k$ with $0<b_i<a_i$ and pick $i$ such that $b_i$ is a $\preceq$-minimal element of $b_1,\dots,b_k.$ Suppose for contradiction that there exists $c$ with $c\preceq b_i$ and $c\preceq a_i-b_i.$ We can assume $c<a_j$ for some $j.$ (There is a $j$ such that $c\wedge a_j>0$; pick $c'$ to be any $0<c'<c\wedge a_j$ just to rule out the extra case $c'=a_j.$) If $j\neq i$ then by an automorphism swapping $c'$ and $b_j$ but fixing $B\cup \{b_i\},$ we have $b_j\preceq b_i,$ contradicting minimality of $b_i.$ The remaining case is $c'<a_i.$ By the Lemma, $c'\leq b_i$ and $c'\leq a_i-b_i,$ which cannot happen for $c'>0.$

$\endgroup$
2
  • $\begingroup$ How is $\hat A$ related to $A$? $\endgroup$ – Pteromys Jul 17 at 14:24
  • $\begingroup$ @Pteromys: no difference, that was my misunderstanding. I have corrected this now. $\endgroup$ – Harry West Jul 21 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.