# Showing a subset $A$ of $\omega$ is infinite

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