0
$\begingroup$

In Naive Set Theory we have a proof that two well ordered sets are either similar to one another or one of them is similar to an initial segment of the other.

It goes like this:

We assume that $X$ and $Y$ are non-empty well ordered sets such that neither is similar to an initial segment of the other; we proceed to prove that under these circumstances $X$ must be similar to $Y$. Suppose that $a \in X$ and that $t$ is a sequence of type $a$ in $Y$; in other words $t$ is a function from $s(a)$ into $Y$. Let $f(t)$ be the least of the proper upper bounds of the range of $t$ in $Y$, if there are any; in the contrary case, let $f(t)$ be the least element of $Y$. In the terminology of the transfinite recursion theorem, the function $f$ thereby determined is a sequence function of type $X$ in $Y$. Let $U$ be the function that the transfinite recursion theorem associates with this situation. An easy argument (by transfinite induction) shows that, for each $z$ in $X$, the function $U$ maps the initial segment determined by $a$ in $X$ one-to-one onto the initial segment determined by $U(a)$ in $Y$. This implies that $U$ is a similarity, and the proof is complete.

My questions are:

  1. Is the hypothesis of neither set being similar to an initial segment of the other used implicitly in some way inside the proof or, simply, it just doesn't get in the way of the conclusion?
  2. What is it about $z$?

In case the terminology is not clear:

A sequence of type $a$ in $Y$ is a function from the initial segment of $a$ in $X$ into $Y$; A sequence function of type $X$ in $Y$ is a function whose domain consists of all sequences of type $a$ in $Y$, for all elements $a$ in $X$.

$\endgroup$
  • $\begingroup$ Wow. It's impossible for me to understand without opening the book, which I don't have. Indeed it's hard to be thorough and naive... :-) $\endgroup$ – Asaf Karagila Feb 17 '13 at 1:19
1
$\begingroup$

To answer the second question first, $z$ appears to be a typo for $a$.

The hypothesis of neither set being similar to an initial segment of the other is essential. If $X$ were similar to an initial segment of $Y$, you could still construct the function $U$, and it would still be one-to-one, but it would not map $X$ onto $Y$. If $Y$ were similar to an initial segment of $X$, you’d have an $a\in X$ such that $Y$ has no sequence of type $a$.

$\endgroup$
  • $\begingroup$ I see, I didn't notice that. Thank you very much! $\endgroup$ – user36546 Feb 17 '13 at 1:29
  • $\begingroup$ As for $z$, I also thought it should be a typo. But you never know... $\endgroup$ – user36546 Feb 17 '13 at 1:35
  • $\begingroup$ @Fred: You’re welcome! (Yes, that kind of typo is a bit nerve-wracking.) $\endgroup$ – Brian M. Scott Feb 17 '13 at 2:09
  • $\begingroup$ Late correction to this answer: the hypothesis that $Y$ is not similar to an initial segment of $X$ is not needed for the existence of sequences of type $a$ - there are always these as long as $Y$ is non-empty, as constant sequences are allowed. The hypothesis is actually used to show that $U$ is injective / one-to-one, so that at no point does $Y$ "run out" and cause $U$ to start generating the least element of $Y$ again. $\endgroup$ – reavowed Jun 13 '18 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy