Is it a theorem of ZF that every partial order can be extended to another that makes the set directed?

Solution 1:

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