3
$\begingroup$

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)$?

  • 1
    "Isometry" is the wrong word. "Isomorphism" would be fine.2010-12-08
  • 0
    @Qiaochu Yuan: Right, I corrected it.2010-12-08
  • 0
    @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$.2010-12-08
  • 0
    @Arturo Magidin: I have modified the question to give this.2010-12-08
  • 0
    @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)?2010-12-08
  • 0
    @Arturo Magidin: It is the range, but the range of a relation $f$ here is defined as $\text{ran} f = \{ x : (\exists x)((x,y) \in f) \}$.2010-12-08
  • 0
    @Jonas: Ehr... do you mean $\mathrm{ran}f = \{x:\exists y((x,y)\in f)\}$, or do you mean $\mathrm{ran}f = \{y : \exists x ((x,y)\in f)\}$? If the latter, I still don't see how your $f$ is even well defined, since you *must* get that $f(x_0) = \{\emptyset\}$, but that is not an initial segment of $X$ unless $x_0$ *is* the emptyset.2010-12-08
  • 0
    @Arturo: Uh, the later. I must think about it, thank you for bringing it to my attention.2010-12-08
  • 0
    @Jonas T: *I* could be misinterpreting something (if so, sorry!). I always have to start almost from scratch to think about the Transfinite Recursion Theorem...2010-12-08
  • 0
    @Arturo: Don't we just have $0 = \emptyset$, $1 = \{\emptyset\}$, $2 = \{\emptyset, \{\emptyset\}\}$ and so on?2010-12-08
  • 0
    @Jonas T: But you started with an arbitary well ordered set. The least element doesn't have to be $0$, it doesn't even have to contain $0$. Did you mean to start with an *ordinal*? Or for your map to go to the set of initial segments of the unique ordinal that $X$ is isomorphic to?2010-12-08
  • 0
    @Arturo: Sorry, it probably must be isomorphic to its canonical representant, that is the well-ordered set $X$ that is equal to the true initial segments of $X$ (ordered by inclusion) such that $x < y$ is equivalent to $\hat{x} \subset \hat{y}$.2010-12-08
  • 0
    @Jonas T: Then you want your map to be $f(x) = \hat{x}$, don't you?2010-12-08
  • 0
    @Arturo: Does that follow from my $F$ then? For the canonical representant we have the $1,2,3$ and so on as I defined above, and isn't this what the given $f$ gives?2010-12-08
  • 0
    @Jonas T: If by "canonical representation" you mean the (unique) ordinal that is isomorphic to the well order $X$, then I still don't know what the range of an element of an ordinal is supposed to be, so I don't know what your $F$ is, but I grant that you can define a function $f$ that satisfies your equation, $f(x) = f|_{\hat{x}}$.2010-12-08
  • 0
    @Arturo: Right, I agree, like it is written it is not so... well-defined (but that is how it is given to me). I'll think about it. And I don't see how I can apply Qiaochu's hint.2010-12-08
  • 0
    @Jonas T: Well, I've tried answering the question assuming $X$ is an ordinal.2010-12-08

2 Answers 2

2

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

2

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