2
$\begingroup$

Two statements are made in Grayson's paper. First, a lemma:

Lemma 2.1. Suppose $X$ is a partially ordered set, and $F$ is a collection of subsets which are well ordered by the ordering of $X$. Suppose also that for any $C, D ∈ F$, either $C ≤ D$ or $D ≤ C$. Let $E = \bigcup_{C∈F} C$. Then $E$ is well ordered, and for each $C ∈ F$ we have $C ≤ E$.

and then, the main result:

Theorem 2.2 (Zorn's Lemma). A partially ordered set $X$ with upper bounds for its well ordered subsets has a maximal element.

He never explicitly uses Lemma 2.1 in the proof of the Theorem 2.2, and I'm left wondering where in the proof of the latter is the former used. Here is the proof of Theorem 2.2:

Proof: Suppose not. For each well ordered subset $C ⊆ X$ pick an upper bound $g(C) \notin C$. A well ordered subset $C ⊆ X$ such that $c = g(\{c' ∈ C | c' < c\})$ for every $c ∈ C$ will be called a $g$-set. We claim that if $C$ and $D$ are $g$-sets, then either $C ≤ D$ or $D ≤ C$. To see this, let $W$ be the union of the subsets $B ⊆ X$ satisfying $B ≤ C$ and $B ≤ D$. Since a union of closed subsets is closed, we see that $W ≤ C$ and $W ≤ D$, and $W$ is the largest subset of $X$ with this property. If $W = C$ or $W = D$ we are done, so assume $W < C$ and $W < D$, and pick elements $c ∈ C$ and $d ∈ D$ so that $W = \{c' ∈ C | c' < c\} = \{d' ∈ D | d' < d\}$. Since $C$ and $D$ are $g$-sets, we see that $c = g(W) = d$. Let $W' = W ∪ \{g(W)\}$; it’s a $g$-set larger than $W$ with $W' ≤ C$ and $W' ≤ D$, contradicting the maximality of $W$. Now let $W$ be the union of all the $g$-sets. It’s a $g$-set, too, and it’s the largest $g$-set, but $W' = W ∪ {g(W)}$ is a larger $g$-set, yielding a contradiction.

Where is Lemma 2.1 used?

$\endgroup$
3
  • $\begingroup$ What is a g-set? $\endgroup$
    – Paul Frost
    Commented Jan 22 at 8:04
  • $\begingroup$ How do you know that he uses the lemma in the proof of the theorem? $\endgroup$
    – Filippo
    Commented Jan 22 at 8:32
  • $\begingroup$ @Filippo I don't, but why would he include it if not? $\endgroup$
    – Sam
    Commented Jan 22 at 10:39

1 Answer 1

1
$\begingroup$

The lemma is used when the author writes "It's a $g$-set, too, and it's the largest $g$-set". The "it" here is $W$, the union of the family of all $g$-sets.

To verify the claim, we must check (1) $W$ is well-ordered, (2) $W\subseteq X$, (3) for all $w\in W$, $w = g(\{w'\in W\mid w'<w\})$, and (4) for every $g$-set $C\leq X$, $C\leq W$.

(1) and (4) follow directly from the Lemma, (2) is obvious, and (3) is an easy check.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .