# There exists a finite set of natural numbers which isn't a proper subset of any other finite set of natural numbers?

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...

• Clearly, $B = \mathbb{N}$. What exactly do you want proved? – Karolis Juodelė Aug 11 '12 at 10:54
• @KarolisJuodelė $B$ is not finite, but I cannot see why $B=\mathbb{N}$. – user20266 Aug 11 '12 at 10:59
• 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\}$. – Karolis Juodelė Aug 11 '12 at 11:07

## 1 Answer

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$.