Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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... :-) –  Asaf Karagila Feb 17 '13 at 1:19
add comment

1 Answer

up vote 2 down vote accepted

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

share|improve this answer
    
I see, I didn't notice that. Thank you very much! –  Fred Feb 17 '13 at 1:29
    
As for $z$, I also thought it should be a typo. But you never know... –  Fred Feb 17 '13 at 1:35
    
@Fred: You’re welcome! (Yes, that kind of typo is a bit nerve-wracking.) –  Brian M. Scott Feb 17 '13 at 2:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.