Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If $(X, \lt)$ is a well-ordering I can show by transfinite recursion over the ordinals that the function $f(x) = \text{ran} f |_{\hat{x}}$ exists (where $\hat{x} = \{ y : y \lt x\}$).

I have obtained $f$ this way, Let $V$ be the class of all sets and $F:V \to V$ be a class-function, then there is a unique $G:ON \to V$ where $ON$ is the class of all ordinals such that $F(\alpha) = F(G|_\alpha)$. So I can apply this to get a function $f$ such that $f(x) = F(f|_\hat{x})$. Now I let $F = \{(x, \text{ran} x) : x \in V\}$ and then I get the function as above.

Now, this should be an isomorphism (order preserving bijection) between $X$ and the set of true initial segments of $X$, $I_X$ ordered by inclusion.

However, when I have $x < y$, then I see that $\text{ran} f|_\hat{x} \subset \text{ran} f|_\hat{y}$. So $f(x) \leq f(y)$. Why do I have $f(x) \neq f(y)$?

share|cite|improve this question
"Isometry" is the wrong word. "Isomorphism" would be fine. – Qiaochu Yuan Dec 8 '10 at 20:09
@Qiaochu Yuan: Right, I corrected it. – Jonas Teuwen Dec 8 '10 at 20:11
@Jonas T: I don't really see your function; could you give you set up your recursion? Because I get that if $x_0$ is the least element of $X$, then $f(x_0)=\emptyset$ (no problem there); but then if $x_1$ is the successor of $x_0$, then $f(x_1) = \mathrm{ran}f|_{\{x_0\}} = \{f(x_0)\} = \{\emptyset\}$, and I don't see why that is an initial segment of $X$. – Arturo Magidin Dec 8 '10 at 20:58
@Arturo Magidin: I have modified the question to give this. – Jonas Teuwen Dec 8 '10 at 21:03
@Jonas: Okay, I think I see my problem: I've interpreted $\mathrm{ran}$ as "range", But that's apparently not what you mean. Do you mean "rank" (smallest ordinal $\alpha$ such that $x\in V_{\alpha+1}$, the $\alpha+1$st term of the cumulative hierarchy)? – Arturo Magidin Dec 8 '10 at 21:10
up vote 2 down vote accepted

Okay, it looks like you are thinking of your $(X,\lt)$ as an ordinal, rather than an arbitrary set.

I claim that for all $y\in X$, if $x\lt y$, then $f(x)\neq f(y)$ and $f(x)\subseteq f(y)$. You have already shown $f(x)\subseteq f(y)$, so we just need to show the inequality.

If $y=\emptyset$, the least element of $X$, then there is nothing to do and the claim holds.

Assume the claim holds for all $z\lt y$. Let $x\lt y$. If $x^+$, the successor of $x$, is also less than $y$, then $f(x)\subseteq f(x^+)\subseteq f(y)$, and $f(x)\neq f(x^+)$ by the induction hypothesis, so $f(x)\neq f(y)$.

If $y=x^+$, then $\hat{y} = \hat{x}\cup\{x\}$. So $f(y) = f(x)\cup\{f(x)\}$. If $f(x)\cup\{f(x)\} = f(x)$, then $f(x)\in f(x)$, which is impossible since ordinals are well-founded relative to $\in$. Therefore, $f(y)=f(x)\cup\{f(x)\}\neq f(x)$.

By transfinite induction, the claim holds for all $y\in X$.

share|cite|improve this answer

You need to use the fact that a well-ordering can't be isomorphic to any of its initial segments.

share|cite|improve this answer

Your Answer


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.