1
$\begingroup$

Can someone please comment on my solution? I wish to know if my solution is right and every step is well-justified. I will state all propositions that I use in my solution and refer to them later in my solution.

Proposition 1: Let $\alpha,\beta$ be ordinals. Then following hold:

(i) $\beta\in\alpha\iff\beta\subset\alpha$.

(ii) Exactly one of $\alpha\in\beta, \alpha=\beta, \beta\in\alpha$ holds.

Proposition 2: Suppose that $b$ is well-ordered by $\triangleleft$ and let $f:a\preceq b$. Define $<\cdot$ on $a$ by

$x<\cdot y\iff f(x)\triangleleft f(y)$. Then $<\cdot$ is a well-ordering of $a$, and if $f$ is also surjective then $f$ is an isomorphism between $\langle a,<\cdot\rangle$ and $\langle b,\triangleleft\rangle$.

Proposition 3 There can be no order-preserving injective function from a well-ordered set to an initial segment of it.

QUESTION: Let $\alpha,\beta$ be ordinals and let $f:\alpha\rightarrow\beta$ be an order preserving surjective function. Show that $\beta\leq\alpha$.

SOLUTION: Suppose $\beta\nleq\alpha$, i.e , $\beta\notin\alpha$ and $\beta\neq\alpha$. Hence by Proposition 1(ii) we must have $\alpha\in\beta$ (i.e $\alpha<\beta$). Then by Proposition 1(i) we have $\alpha\subset\beta$. Now $f$ is order-preserving so for all $x,y\in\alpha$ we have

$x\in_\alpha y\implies f(x)\in_\beta f(y)\tag{I}$

where $\in_\alpha=\{\langle x,y\rangle | x,y\in\alpha\land x\in y\}$ and $\in_\beta$ is defined similarly.

$f$ must be an injective function as if we have $f(x)=f(y)$ and $x\neq y$ then by totality of $\in_\alpha$ either $x\in_\alpha y$ or $y\in_\alpha x$. Then by (I) we have $f(x)\in_\beta f(y)$ or $f(y)\in_\beta f(x)$ respectively. But $f(x)=f(y)$ so we get $f(x)\in_\beta f(x)$ or $f(y)\in_\beta f(y)$ which cannot be by Axiom of Foundation.

As $f$ is also surjective hence by Proposition 2, $f$ is an isomorphism between $\langle\alpha,\in_\alpha\rangle$ and $\langle\beta,\in_\beta\rangle$ , and there can be no isomorphism between two distinct ordinals, (given two distinct ordinals, one must be an initial segment of the other and by Proposition 3 , no well-ordered set is isomorphic to an initial segment of itself) hence $\alpha=\beta$. Contradiction!!!

Hence our supposition was wrong and we cannot have $\alpha\in\beta$ so we must have either $\alpha=\beta$ or $\beta\in\alpha$ ...i.e... $\beta\leq\alpha$ as required.

1 Answers 1

3
  • You shouldn't need to define $\in_\alpha$ and $\in_\beta$ explicitly -- it's well known that the ordinary $\in$ provides the relevant order for every ordinal, and being pedantic here just confuses rather than clarifies.

  • Are you sure you're using the right definition of "order-preserving surjective"? I'd expect something along the lines of "if $a\leq b$ then $f(a)\leq f(b)$", which would ruin your argument that $f$ is injective.

  • It seems you're never using your initial assumption that $\beta\nleq\alpha$ for anything except reaching a contradiction when you finally conclude $\alpha=\beta$. Essentially your argument (if it is valid) is a direct one and shouldn't be disguised as a proof by contradiction.

It seems to me to be more promising to start by defining $g:\beta\to\alpha$ as $g(x)=\min f^{-1}(\{x\})$. Then $g$ is an order-preserving injection $\beta\to\alpha$. (Show that!) Do you have any propositions that apply to that situation?

  • 0
    gr8..thank you for your help.2011-11-30