4
$\begingroup$

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 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. 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, 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^+, but $k, a contradiction.

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

1 Answers 1

2

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

  • 0
    @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.2011-03-13