Here's a proof: Let $A$ be a family of all finite sets of natural numbers partially ordered by set inclusion. Let $A' = \{A_k\}$ ($k \in K$) be any totally/simply ordered subset of $A$. Consider the set $B = \bigcup A_k$ (union of all sets in $A'$). Note that for every $k \in K$, $A_k \subset B$; hence $B$ is a upper bound of $A'$.

Since every totally/simply ordered subset of $A$ has an upper bound, by Zorn's Lemma, $A$ has a maximal element, i.e. a finite set which isn't a proper subset of any other finite set.

Since the statement 'proved' is obviously false, which step in the proof is incorrect?

I'm guessing $B$ isn't finite so couldn't be an upper bound for $A'$ because the upper bound needs to be finite so Zorn's lemma can't really be applied but I can't see how I could go about proving this. Maybe I'm wrong...

  • $\begingroup$ Clearly, $B = \mathbb{N}$. What exactly do you want proved? $\endgroup$ – Karolis Juodelė Aug 11 '12 at 10:54
  • 1
    $\begingroup$ @KarolisJuodelė $B$ is not finite, but I cannot see why $B=\mathbb{N}$. $\endgroup$ – user20266 Aug 11 '12 at 10:59
  • $\begingroup$ In fact, $B$ is anything at all. What I should have said is that for some $A'$, $B = \mathbb{N}$, namely $A' = \{A_n | n \in \mathbb{N}\}, A_n = \{1 \dots n\}$. $\endgroup$ – Karolis Juodelė Aug 11 '12 at 11:07

Assuming $K$ is a finite index set, $\bigcup A'\in A$ will be a lowest upper bound for $A'$. If $A'$ is an infinite set however, $B=\bigcup A'$ will be infinite and thus $B\not\in A$ and so Zorn's fails. You have not exhibited any sort of upper bound for all of $A$ that is actually an element of $A$, and indeed there isn't one.

Note that $|B|=|\bigcup A'|\le |A'|$ is why $A'$ infinite implies $B$ infinite. Also $\bigcup A':=\displaystyle\bigcup\limits_{S\in A'}S$.


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.