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

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$A$ is finite. If $A\subsetneq m^+$, then we know $A\sim p$ for some $p$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
    I guess the deeper question is what definition of "finite" is being used for subsets of $\omega$.2011-03-13
  • 0
    I'm taking finite to mean "bijective with a section of the positive integers."2011-03-13
  • 0
    @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.2011-03-13
  • 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.2011-03-13
  • 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