Confusion in Proof of "Zorn's Lemma $\implies$ Tukey's Lemma"

282 Views Asked by At

Definitions: A Subset $C$ of a partially order set $(P,<)$ is said to be a chain if $C$ is linearly ordered by $<$. $u$ is an upper bound of $C$ if $c\le u$ for each $c\in C$. We say that $a\in P$ is a maximal element if $a<x$ for no $x\in P$. A family of sets $\mathfrak{F}$ has finite character if for any set $X$, $X\in\mathfrak{F}\iff Y\in\mathfrak{F}$ for any finite subset $Y$ of $X$.

  1. Zorn's Lemma: Let $(P,<)$ be a non-empty partially ordered set with the property that every chain in $P$ has an upper bound. Then $P$ has a maximal element.
  2. Tukey's Lemma: If a non-empty family of sets $\mathfrak{F}$ has finite character then $\mathfrak{F}$ has a maximal element with respect to the partial order of inclusion ($\subseteq$)

Proof of $1\implies 2$: Assume $\mathfrak{F}$ is a non-empty family of sets with fintite character, with partial ordering of inclusion, $\subseteq$. If $\mathcal{C}$ is a chain in $\mathfrak{F}$ and if $A=\bigcup\{X\mid X\in \mathcal{C}\}$, then every finite subset of $A$ belongs to $\mathfrak{F}$ and therefore $A\in\mathfrak{F}$. Obviously $A$ is an upper bound of $\mathcal{C}$. Hence we can apply Zorn's Lemma and get a maximal element of $\mathfrak{F}$.

What I do not understand is that why should every finite subset of $A$ belong to $\mathfrak{F}$? I mean suppose $X,X'\in\mathcal{C}$ and let $X_1,X_1'$ be finite where $X_1\subseteq X$ and $X_1'\subseteq X'$. Then obviously $X_1$ and $X_1'$ should be in $\mathfrak{F}$ since $\mathfrak{F}$ has finite character. However $X_1\cup X_1'$ is a finite subset of $A$, and how can we guarantee that it is also in $\mathfrak{F}$?

1

There are 1 best solutions below

3
On BEST ANSWER

Since $\cal C$ was a chain, every finite subset of $A$ is a subset of some $X\in\cal C$, but since $X\in\frak F$ by assumption, so must be all of its finite subsets.

Therefore every finite subset of $A$ is a finite subset of some $X\in\frak F$, and therefore an element of $\frak F$.


The point here is to take the usual argument using Zorn's lemma in almost any conceivable case: you have a compact property, i.e. a property that holds if and only if it holds for finite subsets (linear independence, being a chain or an antichain, etc.) and to test that the "limit object of a given chain" has this property you merely verify that every finite part of this limit object already had it. And how? Just like the above argument goes.