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?

  • $\begingroup$ By "stabilizes" do you mean that the chain has an upper bound? $\endgroup$ – DanielWainfleet Apr 17 '16 at 19:44
  • $\begingroup$ @user254665 Rather that there exists some $n$ such that $x_n=x_{n+1}=\ldots$ $\endgroup$ – Hagen von Eitzen Apr 17 '16 at 19:45
  • $\begingroup$ The answer is yes and my answer will be up at about 5:30 EDT $\endgroup$ – DanielWainfleet Apr 17 '16 at 19:56
  • $\begingroup$ Basketball half-time was productive for me.Answer posted 5:00 EDT $\endgroup$ – DanielWainfleet Apr 17 '16 at 21:00

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

  • $\begingroup$ A set-theoretic tree is a set $T$ with a binary relation $<_T$ which is transitive,irreflexive, and anti-symmetric,such that for each $x\in T,$ the set pred$_T(x)=\{y:y<_Tx\}$ is well-ordered by $<_T.$ (Pred=predecessors). In my A, the relation $<$ on $F,$ where $f<g \iff (f\leq g\land f\ne g)$ makes $F$ a tree, A tree is well-pruned iff it has no maximal members. In $ZF,$ the axiom $DC$ is equivalent to : Any well-pruned non-empty tree has a chain $(x_n)_{n\in N}.$ $\endgroup$ – DanielWainfleet Apr 18 '16 at 17:38

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.


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


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.