Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'd like to show that posets that satisfy the ascending chain condition (ACC) have maximal elements. I noticed this statement looks much like Zorn's lemma which holds for inductively ordered sets. Posets satisfying the ACC themselves look like inductively ordered sets: in the former every chain should terminate, while in the latter every chain has an upper bound.

The question is:

  1. How different are inductively ordered set from posets that satisfy the ACC?
  2. How different is the proof of posets that satisfy the ACC having maximal elements from that of Zorn's lemma? Does it require the Axiom of Choice?
share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

The principle of Dependent Choice, a strictly weaker version of the axiom of choice, is sufficient to prove that every poset with the ACC has maximal elements. To see this, pick any element $p_0$ of your poset. If it is not maximal, pick $p_1$ above it. Continuing in this way, pick $p_{n+1}$ above $p_n$, unless it was maximal. By the ACC, we must eventually reach a maximal element. The choice principle used in this argument is exactly what DC allows: one can successively make countably many choices.

Meanwhile, it is consistent with ZF that there are posets having the ACC, but having no maximal elements. For example, suppose that $A$ is an infinite Dedekind finite set of reals, which is known to be relatively consistent with ZF. Thus, $A$ is infinite and has no countable subset. Let $P$ be the partial order consisting of all finite subsets of $A$, ordered by inclusion. This partial order clearly has no maximal elements, but it does have the ACC, since any infinite increasing chain of finite subsets of $A$ would give rise to a countable subset of $A$, a contradiction.

A more striking way to put it is that consistently with ZF there can be a tree $T$, in which every node has finite height and at least two immediate successors, but there is no infinite branch. This tree, as a partial order, has the ACC since any infinite chain would determine an infinite branch. But it has no maximal elements, by the successor condition. The situation with this tree is that one can always continue any finite branch a little more, but the model of set theory is too impoverished to provide a way to climb all the way up, and there is no set of choices that coherently makes infinitely many of the choices.

One can build such a tree using the infinite Dedekind finite set $A$, by considering the finite subsets of $A$, enumerated in the order of the real line. Thus, $a\leq b$ if both are finite subsets of $A$, and $a$ is an initial segment of $b$ in the $\mathbb{R}$-order.

Theorem. DC is equivalent to the assertion that every ACC poset has a maximal element.

Proof. Above we showed that DC suffices for that conclusion. Conversely, consider a relation $R$ for which we would like to establish an instance of DC. So every $a$ has at least one $b$ with $a\mathrel{R}b$. Let $P$ be the partial order consisting of all finite chains through $R$, that is, finite sequences $\langle a_0,\ldots,a_n\rangle$ with $a_i\mathrel{R} a_{i+1}$, and we order them by extension. If there is no infinite chain, then this set has the ACC. But it has no maximal elements.QED

Meanwhile, in the context of set theory with the axiom of choice, the ACC condition is much more severe than the inductive hypothesis of Zorn's lemma, and there are numerous inductive posets without the ACC.

share|improve this answer
    
Is the axiom of dependent choice equivalent to posets with the ACC having maximal elements under ZF? –  Pteromys Dec 11 '11 at 13:45
    
Yes, I edited to add a proof of this. –  JDH Dec 11 '11 at 13:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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