Re: zorn's lemma and ascending chain condition

In article <1145724449.666815.75570@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Mike <mit12354@xxxxxxxxx> wrote:
I am trying to figure out if the proof of the following well known fact
uses Zorn's lemma:

Let V be a partially ordered set. Suppose V satisifies the ascending
chain condition (every strictly increasing sequence x1<x2<x3< is
finite). Show that every non-empty subset of V has a maximal element.

The usual proof goes as follows: assume there is a nonempty subset T
that has no maximal element, then there exists element x1 in T since T
is non empty, and then there exists bigger element x2 in T since x1 is
not maximal, and then an x3 in T such that x1<x2<x3, and continue in
this manner. We get an infinite strictly increasing sequence, a
contradiction.

Am I using Zorn's lemma / axiom of choice here? It seems that in
constructing the sequence I'm making infinitely many arbitrary choices,
but I'm not sure.

You are using the principle of dependent choices. The
proof by contradiction assumes that there is a non-empty
subset of U with no maximal element. Consider the relation
R which is the "<" relation restricted to UxU. The the
contradiction assumption assumes that for any x in U, there
is a y in U with x < y. The principle of dependent choices
gives an increasing sequence.


Thanks,
Mike



--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@xxxxxxxxxxxxxxx Phone: (765)494-6054 FAX: (765)494-0558
.