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.

I need to show specifically using transfinite induction that given two well-ordered sets $\left(A,<_{1}\right)$ and $\left(B,<_{2}\right)$ there is only one isomorphism between them. To do this I want to show by induction that there is only one way to define the mapping and that is: $$\forall\, x\in A: \varphi\left(x\right)=\min\left(B\backslash\varphi\left(\left\{ a\in A\,:\, a<_{1}x\right\} \right)\right)$$ Showing the base of the induction is no problem and the induction hypothesis would be that $$\forall\, y<_{1}x\,:\,\varphi\left(y\right)=\min\left(B\backslash\varphi\left(\left\{ a\in A\,:\, a<_{1}y\right\} \right)\right)$$ My problem is that I can't seem to manage to use the hypothesis in order to prove the step. I've found a couple of ways to show this definition of the mapping is indeed necessary but none of those used the induction hypothesis. My plan was to mark $$c_{0}=\min\left(B\backslash\varphi\left(\left\{ a\in A\,:\, a<_{1}x\right\} \right)\right)$$ Using the fact $\varphi$ is surjective take $y\in A$ such that $\varphi\left(y\right)=c_{0}$ and show that it can't be that $y<_{1}x$ or $x<_{1}y$ and thus necessarily $y=x$. If someone could give me a way to show either one of these are false using the induction hypothesis it would solve my problem.

Thanks a lot!

share|improve this question
add comment

2 Answers

up vote 7 down vote accepted

What you want to show is that if $f\colon A\to B$ is an isomorphism of the given well-orders then $f=\varphi$.

Suppose that for $x\in A$ we have that $f\upharpoonright\{a\in A\mid a<_1 x\}=\varphi\upharpoonright\{a\in A\mid a<_1 x\}$. If $f(x)=\varphi(x)$ then we may continue the induction; otherwise $\varphi(x)<f(x)$ (by the definition of $\varphi$). Since $f$ is a bijection between the sets there is some $x'$ such that $\varphi(x)=f(x')$. It is not possible that $x'<x$ because for $a<x$ we have $\varphi(a)=f(a)$; so $x<x'$ but then we have $f(x')<f(x)$ which is a contradiction to the fact that $f$ is an order isomorphism.


From the assumption that the orders are isomorphic we deduce that there is some isomorphism and by the proof above it has to be $\varphi$.

share|improve this answer
add comment

You might find it easier simply to show that if $f,g:A\to B$ are order-isomorphisms, then $f=g$, using induction to show that $f(a)=g(a)$ for all $a\in A$. Clearly $f(\min A)=g(\min A)$. Suppose that $a\in A$ is $<_1$-minimal such that $f(a)\ne g(a)$. Without loss of generality assume that $f(a)<_2 g(a)$. Show that $f(a)\notin\operatorname{ran}g$ to get a contradiction.

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