Is the equivalence of the ascending chain condition and the maximum condition equivalent to the axiom of dependent choice?

Question

Assuming the axiom of dependent choice, for a partially ordered set $(X,\le)$, the following statements are equivalent:

1. $X$ fulfils the ascending chain condition, i. e. every chain $x_1\le x_2\le\ldots\in X$ stabilises.

2. $X$ fulfils the maximum condition, i. e. any nonempty subset of $X$ contains a maximal element.

In order to prove the implications 2.$\Rightarrow$1., the axiom of dependent choice is unnecessary.

Assuming the negation of the axiom of dependent choice, does a poset which fulfils the ascending chain condition but not the maximum condition necessarily exist?

Answer 1

Yes. Assume $\neg DC$. Then there exists $S$ and a binary relation $R$ on $S$ (that is, $R\subset S\times S$ ) and some $x_0\in S$, such that : $$(1)...\; \forall x\in S\;\exists y\;(\;(x,y)\in R).$$ $$(2)...\; \neg \exists H:\omega \to S\; \;(H(0)=x_0\land \forall n\in \omega \; (\;(H(n),H(n+1)\;)\in R).$$ For $n\in \omega$ let $F_n$ be the set of functions $f:n\to S$ such that $$(3)...\; n\ne 0\implies f(0)=x_0.$$ $$(4)...\; \forall j<n \;(\;(f(j),f(j+1))\in R).$$

Let $F=\cup_{n\in \omega}F_n.$ For $f,g \in F,$ let $f\leq g$ iff $$(5)...\; f=g \quad \text {or}$$ $$ (6)...\; (f\subsetneqq g) \land \forall n\in dom (f)\; (g(n)=f(n)).$$

Suppose there exists $C:N\to F$ such that $\forall n\in N\; (C(n)\leq C(n+1)$ but such that the chain $(C(n))_{n\in N}$ does not stabilize, that is, $C$ is not eventually-constant. For $n\in N$ let $t(n)$ be the least $m>n$ such that $C(m)\ne C(n).$ Then $$H=\cup_{n\in N} C(t(n))$$ is a function from $\omega$ to $S$ that violates (2).

And $F$ has no maximal elements because for $f= \phi$ (the empty function) we have $\phi\leq \{(0,x_0\}\not \leq \phi,$ and for $\phi \ne f\in F$ with $dom (f)= n \ne 0,$ there exists $y\in S$ with $(f(n-1),y)\in R,$ so $f\leq f\cup \{(n,y)\}\not \leq f.$

Answer 2

Assume that the ascending chain condition implies the maximum condition. Then we can almost prove Dependent Choice:

Let $X$ be a non-empty set and $R$ a binary relation such that for all $x\in X$ there exists $y\in X$ with $xRy$. We want to show that there exists a map $\omega\to X$, $n\mapsto x_n$ such that $x_nRx_{n+1}$ for all $n\in\omega$.

Let ${\prec}=\bigcup_{n=1}^\infty R^n$ be the transitive hull of $R$.

Case (i): There exists $x_0\in X$ with $x_0 \prec x_0$. Then for some $m$, $x_0R^mx_0$, i.e., there exist $x_1,x_2,\ldots , x_{m-1}$ with $x_0Rx_1,x_1Rx_2,\ldots, x_{m-1}R x_0$. This allows us to use $n\mapsto x_{n\bmod m}$.

Case (ii): There is no $x\in X$ with $x \prec x$. Then $\prec$ is a partial order. As for every $x\in X$ there is $y\in X$ with $xRy$ (and so also $x\prec y$), we see that $X$ has no maximal element. We conclude that the ascending chain condition does not hold for $(X,\prec)$, i.e., there exists a non-stationary chain $x_0 \prec x_1 \prec x_2 \prec\ldots$ Now each $\prec$-step can be replaced with finitely many $R$-steps and we are done. Unfortunately, it seems that it requires some choice to pick these. :(

Answer 3

Yes, and it is easy to see this with the following equivalent of $\sf DC$.

$\sf DC$ is equivalent over $\sf ZF$ to the statement "Every tree of height $\omega$ without leaves has a maximal branch".

Now, if $\sf DC$ fails, there is a tree of height $\omega$ without leaves, but without a maximal branch. This means that every chain in this tree is finite, but there is no maximal elements.

To see that $\sf DC$ is equivalent to this principle, first note that the principle implies $\sf DC$ by the fact that if $S$ is a non-empty set and $R$ is a relation on $S$ satisfying the hypothesis of $\sf DC$, then the tree of all finite sequences where each element is $R$-related to its successors is a tree of height $\omega$ without maximal nodes, so a branch corresponds to the function from $\Bbb N$ to $S$ guaranteed by $\sf DC$. In the other direction, if $\sf DC$ holds and we have a tree of height $\omega$ without maximal nodes, then the partial order itself satisfy the requirements of $\sf DC$ and therefore there is a function from $\Bbb N$ into the tree which is order preserving, and it is not hard to verify that this is indeed a branch.