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.


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

  • $\begingroup$ I guess the deeper question is what definition of "finite" is being used for subsets of $\omega$. $\endgroup$ – Carl Mummert Mar 13 '11 at 2:38
  • $\begingroup$ I'm taking finite to mean "bijective with a section of the positive integers." $\endgroup$ – Cheerful Parsnip Mar 13 '11 at 2:41
  • $\begingroup$ @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. $\endgroup$ – Dani Hobbes Mar 13 '11 at 2:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Carl Mummert Mar 13 '11 at 2:49
  • $\begingroup$ @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. $\endgroup$ – Cheerful Parsnip Mar 13 '11 at 2:58

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.