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.

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

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – user18096 Nov 30 '11 at 12:15
  • $\begingroup$ 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. $\endgroup$ – hmakholm left over Monica Nov 30 '11 at 14:18
  • $\begingroup$ 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. $\endgroup$ – user18096 Nov 30 '11 at 14:30
  • $\begingroup$ Yes, ordinals are well-ordered sets. In fact, they are the canonical well-ordered sets; any WO set is order-isomorphic to some ordinal. $\endgroup$ – hmakholm left over Monica Nov 30 '11 at 14:33
  • $\begingroup$ gr8..thank you for your help. $\endgroup$ – user18096 Nov 30 '11 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.