I'm aware this result (and the standard/obvious proof) is considered basic and while I've accepted and used it numerous times in the past, I'm starting to question its validity, or rather that said proof doesn't subtly require a form of the AC. (Disclaimer: it's been some time since I've looked at set theory.)

I found the same question answered here using the same method I'd used in the past. (Why are infinite cardinals limit ordinals?) My posting here is more concerned with the apparent assumptions required to use this argument.

The (apparent) issue here is that it presupposes that $\omega$ is the least infinite ordinal, i.e. a subset of any infinite ordinal $\alpha$. Now a countable choice argument could easily prove this, but this shouldn't be necessary, one would think.

I've considered this: a simple (natural) induction argument showing that every natural number is an element of any infinite ordinal. This would show $\omega\subseteq \alpha$, or that $\omega$ is the least infinite ordinal. Does this seem right?

Thank you

To clarify: I'm trying to show that $\omega$ is the least infinite ordinal. Evidently some define it this way, (there is clearly some least infinite ordinal) but the definition of $\omega$ I'm working with involves defining inductive classes and taking their intersection, which is then axiomatized as a set. (These two definitions should be equivalent)

  • $\begingroup$ Aware of what results? $\endgroup$ – William Elliot Jun 22 '18 at 2:15
  • 2
    $\begingroup$ Would you make a clear simple statement of what you are trying to prove? $\endgroup$ – William Elliot Jun 22 '18 at 2:18
  • $\begingroup$ Maybe you should be explicit about which proof you have in mind. Here's how I would do it. You have $0,1,2,3,\ldots$ followed by infinite ordinals, until you get up to the ordinal $\alpha$ that you want to consider. Now establish a bijection by placing that successor ordinal before $0.$ Is that the argument you had in mind? $\endgroup$ – Michael Hardy Jun 22 '18 at 4:34
  • 2
    $\begingroup$ How do you define $\omega$ if not "the least infinite ordinal"? $\endgroup$ – Asaf Karagila Jun 22 '18 at 7:31
  • $\begingroup$ Well it's been some time but the standard construction of the naturals (define "inductive classes," etc then of course we can assume $\omega$ is a set) then taking their union is what I had in mind. $\endgroup$ – STK 299 Jun 23 '18 at 22:43

Hopefully you already know that $\omega$ (defined as the intersection of all inductive sets) is an ordinal in the first place.

Hopefully you also know that the ordinals are totally ordered by $\in$ -- that is, for ordinals $\alpha,\beta$ we always have either $\alpha\in\beta$ or $\alpha=\beta$ or $\beta\in\alpha$.

What is an infinite ordinal? Usually "finite" is defined to mean, "equinumerous with an element of $\omega$". So if $\alpha$ is an ordinal that is not finite, then in particular it is not itself an element of $\omega$. Therefore we have either $\omega=\alpha$ or $\omega\in\alpha$. In either case we have $\omega\subseteq\alpha$.

  • $\begingroup$ Yes, thank you. This resolved my question. I was definitely overthinking this-it's been a while since I've looked at set theory (and I'm aware that On, the class of ordinals, has these properties) and this "problem" came to my mind the other day. $\endgroup$ – STK 299 Jun 23 '18 at 23:44

The definition of $\omega$ is "the least infinite ordinal". So there are no hidden assumptions.

But even ignoring that, the proof I gave in the answer you linked doesn't use any "presupposed assumption". It only uses the fact that if $\alpha$ is an infinite ordinal, then for any finite ordinal $n$, $n<\alpha$.

In any case, an ordinal is by definition a well-ordered set. So we can exploit that to define a choice function on its subsets. So usually when choice is needed to prove things in general, it can be eliminated in the case of ordinals (since we already have a choice function).

You are correct, however, that induction is needed to prove that no infinite ordinal is a predecessor of a finite ordinal. For example by proving first that a subset of a finite set is finite (which is where you'd use induction), and the noting that if $\alpha\in\beta$, then $\alpha\subseteq\beta$, and so if $\beta$ is finite, $\alpha$ must be too.

  • $\begingroup$ Thanks Asaf-I commented above about how else to define the naturals. Clearly there is a least infinite ordinal but from the standard definition of "finite" and the naturals, I don't see how to show that the naturals comprise this least ordinal. Is there a way to explain this, showing equivalence to the "definition" of $\omega$ I wrote above? $\endgroup$ – STK 299 Jun 23 '18 at 22:59
  • $\begingroup$ I understand the second part may be relevant to the question I asked; it seems one way to approach this would be to prove that no infinite ordinal precedes a finite ordinal/natural number. (Which seems trivial now that I think I about it; I was looking for confirmation re: the last part of my post, that this method is correct.) (MINOR EDIT: I meant to say "intersection," not "union," above, regarding another way to construct/define the naturals.) $\endgroup$ – STK 299 Jun 23 '18 at 23:05
  • $\begingroup$ I've written a few comments already but I just wanted to state (probably "preaching to the choir") that the assumption (and I don't mean "hidden" assumption) in your second paragraph is equivalent to what I was trying to prove: that $\omega\subseteq \alpha$ for infinite $\alpha$. Wish I could give "resolution karma" to you as well-thank you for your help. $\endgroup$ – STK 299 Jun 23 '18 at 23:54

(1). In the absence of Infinity, Choice, and Foundation (Regularity):

Let $On$ be the class of ordinals. Define the class $FOn$ of finite ordinals as $\{x\in On: \forall y\in x\cup \{x\}\;(y=0\lor y\ne \cup y)\}.$

Prove that $\forall x\in FOn \;\forall y\in x\;(y\in FOn).$

(1-i). That is, $FOn$ is a transitive class.

(1-ii). Any set or definable class of ordinals is well-ordered by $\in.$

(2). Introducing Infinity. Suppose $\exists z\in On\backslash FOn.$ For any $x\in FOn$ we have $(z=x\lor z\in x\lor x\in z).$ But $z=x\in FOn$ cannot hold, and $z\in x\implies z\in FOn$ by def'n of $FOn.$ So every $x\in FOn$ belongs to $ z .$

So by Comprehension $\exists O \;\forall x\;( x\in O \iff (x\in z\land x\in FOn)).$ That is, the set $O$ is equal to $FOn.$

So by (I-i) and (1-ii), and by the def'n of $On,$ we have $O\in On.$ Now for any $z'\in On\backslash FOn$ we have $z'\geq O$ because $z'<O\implies z'\in O\implies z'\in FOn,$ a contradiction. So $O=FOn$ is the least infinite ordinal. Usually denoted by $\omega.$

And now prove that $0\in FOn$ (i.e. $FOn$ is not empty) and that $\forall x \in FOn\;(x+1\in FOn).$

  • $\begingroup$ You're working with different machinery/definitions of the finite ordinals than I've been using but I see how this construction works-thanks for the response. $\endgroup$ – STK 299 Jun 26 '18 at 1:43

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.