Take the 2-minute tour ×

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

2 Answers 2

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|improve this answer

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

share|improve this answer

Your Answer


