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.

This is a concept that seems very intuitive to me, but I feel my proof is messy. Could someone more experienced than I perhaps offer some criticism/tell me if I'm even correct?

Let $A\subset\omega$. I want to show that $A$ is infinite if and only if $$ \forall_m(m\in\omega\implies\exists_n(n\in A\land (m\lt n))). $$

Here $a<b\iff a\in b$ for $a,b\in\omega$. Also, $A\sim B$ means two sets are in bijection.

I think my proof is too roundabout. I prove $\implies$ by the contrapositive. Suppose the above property is not true. So there exists an $m$ such that there is no $n\in A$ such that $m<n$. This means for all $n\in A$, $n\leq m$, which implies $n\lt m^{+}$. So $A\subseteq m^+$. If $A=m^+$, then obviously $A\sim m^+$, so by definition $A$ is finite. If $A\subsetneq m^+$, then we know $A\sim p$ for some $p<m^+$, so $A$ is finite by definition.

For $\impliedby$, I feel things get even worse. I try to prove the contrapositive by contradiction. I suppose $A$ is finite, but the property holds. Now if $A$ is empty, the property is false, a contradiction, so the contrapositive holds as needed. So assume $A$ is nonempty. Since $A$ is finite, $A$ must have a greatest element. (I try to justify this by applying the well-ordering principle on the reverse ordering. This is probably my biggest concern, is it acceptable?) Denote this element $k$. Consider $k^+$. Then $k^+\in\omega$, and by the property, we have that there is a $p\in A$ such that $k^+<p$, but $k<p$, a contradiction.

Apologies for this messy proof. How can I clean it up/correct it? Many thanks.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

It seems the crux of what you want to prove is that every finite ordered set has a largest element. To show this is true, I would use induction. I suppose you could also argue that all finite ordered sets are well-ordered as you suggest but that seems to be equally complicated. So to use induction, you suppose that every size $n$ ordered set has a maximal element. Then consider a size $n+1$ ordered set $S$, and remove an element $a$. Then $S\setminus\{a\}$ has a largest element $b$. Now the larger of $a$ and $b$ is a largest element for $S$.

share|improve this answer
    
I guess the deeper question is what definition of "finite" is being used for subsets of $\omega$. –  Carl Mummert Mar 13 '11 at 2:38
    
I'm taking finite to mean "bijective with a section of the positive integers." –  Grumpy Parsnip Mar 13 '11 at 2:41
    
@Jim, thanks for pointing this out. @Carl, my definition of a finite set is that the set is in bijection to some natural number. I've seen the proof Jim Conant offers above, so I hope it still works with my definition? If anything, foundational math makes me doubt everything I thought I knew before. –  Dani Hobbes Mar 13 '11 at 2:43
1  
The point is not so much to doubt what you know, but to verify that a certain collection of axioms is sufficient to prove the things that you already know. Your proof seems fine to me overall; Jim Conant's comment addresses the part that was in bold. –  Carl Mummert Mar 13 '11 at 2:49
    
@Hobbie: I agree with Carl that your overall proof looks fine, and I was just addressing the comment in bold that you were unsure about. –  Grumpy Parsnip Mar 13 '11 at 2:58

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.