Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Clearly, $B = \mathbb{N}$. What exactly do you want proved? –  Karolis Juodelė Aug 11 '12 at 10:54
1  
@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 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.