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
    I don't have any proposition to apply on it. How about this argument that if $g$ is injection then there is a subset of $\alpha$ ,say $\gamma$ , such that we have $\beta\sim\gamma$. We get an isomorphism. And then we can apply the proposition that no two distinct ordinals can be isomorphic hence we must have $\beta=\gamma$. Clearly if, $\gamma=\alpha$ then we get $\alpha=\beta$ but if $\gamma$ is a strict subset of $\alpha$ we get $\beta<\alpha$ by transitivity of $\in$ ,as required. Is that correct argument? By the way thank you for correcting me.2011-11-30
  • 0
    First on, your Proposition 3 is actually applicable -- we know there is an order-preserving injective function $\beta\to\alpha$; thus $\alpha$ is not an initial segment of $\beta$. In your argument you don't know that $\gamma$ is an ordinal -- only that it's a subset of $\alpha$. But not all subsets of ordinals are themselves ordinals.2011-11-30
  • 0
    Ohh!! I see. Thank you for clearing it. I misunderstood Proposition 1(i), in which $\beta$ is already an ordinal. Also there are few propositions given in my Set theory notes regarding well-ordered sets. Can I apply the results of well-ordered sets to ordinals;as my understanding is that ordinals are well-ordered sets satisfying totality condition.2011-11-30
  • 0
    Yes, ordinals are well-ordered sets. In fact, they are the _canonical_ well-ordered sets; any WO set is order-isomorphic to some ordinal.2011-11-30
  • 0
    gr8..thank you for your help.2011-11-30