1
$\begingroup$

I am currently trying to practice the technique of transfinite induction with the following problem:

Suppose that $X$ is a non-empty subset of an ordinal $\alpha$, so that $X$ is well-ordered by $\in$. Show that $\text{type}(X; \in) \leq \alpha$.

My approach thus far:

Let $\beta = \text{type}(X; \in)$ and $f: X \rightarrow \beta$ be an order-preserving isomorphism. Now we show that $f(\xi) \leq \xi$ for all $\xi \in X$ by transfinite induction.

Base Case: Let $\xi_{0} \in X$ be minimal with respect to $\in$ in $X$. As $f$ preserves order, it must be the case that $f(\xi_{0}) = \emptyset$ and so $f(\xi_{0}) \leq \xi_{0}$.

Inductive Step: Suppose that $f(\xi) \leq \xi$ for all $\xi < \gamma$ for some $\gamma$. Now we deduce that $f(\gamma) \leq \gamma$.

My question is how to prove this crucial step $f(\gamma) \leq \gamma$.

After proving this, then by transfinite induction we have that $f(\xi) \leq \xi$ for all $\xi \in X$ and so $\beta = f(X) \subseteq \alpha$ and so $\text{type}(X; \in) = \beta \leq \alpha$ as desired.

$\endgroup$
6
  • $\begingroup$ Do you already know that $\alpha$ itself is well-ordered by $\in$? $\endgroup$
    – hmakholm left over Monica
    Apr 2, 2016 at 20:03
  • $\begingroup$ @HenningMakholm Isn't it part of the definition of an ordinal that it is well-ordered by $\in$? $\endgroup$
    – Exit path
    Apr 2, 2016 at 20:04
  • $\begingroup$ Yes, this is included in the definition of an ordinal; we say that $z$ is an ordinal iff $z$ is a transitive set (i.e. $\forall y \in z$ implies $y \subseteq z$) and $z$ is well-ordered by $\in$. $\endgroup$
    – Oiler
    Apr 2, 2016 at 20:07
  • $\begingroup$ @leibnewtz: It's part of the most common definition, but there are others. (I asked because when one does know that, it is trivial that $X$ is well-ordered, and I hadn't yet read the question closely enough to conclude that the OP probably already has figured that out). $\endgroup$
    – hmakholm left over Monica
    Apr 2, 2016 at 20:11
  • $\begingroup$ @Oiler Just as a remark, transfinite induction (and therefore also strong induction on the natural numbers) doesn't require a base case. You get that for free since $\forall \alpha< \emptyset (P(\alpha))$ is vacuously true. $\endgroup$
    – Exit path
    Apr 2, 2016 at 20:20

2 Answers 2

Reset to default
3
$\begingroup$

Things will go a bit smoother if you strengthen the induction hypothesis to include "... and $f(X\cap\gamma)$ is an initial segment of $\beta$".

If $\gamma\notin X$ then there's nothing new to prove. So assume that $\gamma\in X$.

Now, for $f$ to be an order isomorphism, $f(\gamma)$ has to be the smallest ordinal that is not an $f(\xi)$ with $\xi<\gamma$. Due to the induction hypothesis we cannot have $f(\xi)=\gamma$ for any such $\xi$, so $f(\gamma)$ is the minimum of a class of ordinals that includes $\gamma$ itself. Therefore $f(\gamma)\le \gamma$.

By the way, you don't need any explicit base case when you're doing ordinal induction. The induction scheme itself supplies the necessary base case -- the induction hypothesis "such-and-such holds for all $\xi<\alpha$" is vacuously true (and therefore not helpful) when $\alpha=0$.

$\endgroup$
0
2
$\begingroup$

It’s easier if you replace $f$ by its inverse and work with an order-isomorphism $f:\beta\to X$. Then $f$ is an order-isomorphism of $\beta$ into $\alpha$, and you want to show that $\xi\le f(\xi)$ for each $\xi\in\beta$. If not, let $\gamma\in\beta$ be minimal such that $f(\gamma)<\gamma$. Then by the minimality of $\gamma$ and the fact that $f$ is order-preserving you have

$$f(\gamma)\le f\big(f(\gamma)\big)<f(\gamma)\;,$$

which is absurd. Hence $\xi\le f(\xi)$ for all $\xi\in\beta$.

$\endgroup$
4
  • $\begingroup$ Having trouble understanding what you mean by $f(f(\gamma))$. How can we apply $f$ to $f(\gamma)$ as $f(\gamma)$ is in $X$ and the domain of $f$ is $\beta$? $\endgroup$
    – Oiler
    Apr 2, 2016 at 20:52
  • $\begingroup$ @Oiler: $f(\gamma)$ is an ordinal, and if it’s less than $\gamma$, then it’s in $\beta$ and hence in the domain of $f$. $\endgroup$
    – Brian M. Scott
    Apr 2, 2016 at 20:54
  • $\begingroup$ Perfect. Thank you. This is much more clear to me now. +1 $\endgroup$
    – Oiler
    Apr 2, 2016 at 20:56
  • $\begingroup$ @Oiler: You’re welcome. $\endgroup$
    – Brian M. Scott
    Apr 2, 2016 at 20:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .