4
$\begingroup$

I want to prove the following statement:

In well-ordered set $\langle\mathbb{N},<\rangle$, moving $0,1,2,3,...,n-1$ to the end, retaining that order, results in a well-ordered set $\langle \Bbb N,<^{(n)}\rangle$.

My work:

Saying that the relation obtained is $<^{(n)}$. I proved that the relation is a total order, but how one can prove that to every non-empty subset of $\langle\mathbb{N},<^{(n)}\rangle$ has least element (first element).

Thank you.

  • 1
    I think [tag:elementary-set-theory] tag is more suitable. I've also added [tag:ordinals], since the question deals with well-ordered sets.2012-05-04

2 Answers 2

2

It is easy to divide to cases here. Suppose $A\subseteq\mathbb N$ is non-empty.

  • If $0,\ldots,n-1\notin A$, show that $\min_< A$ (the minimal element of the usual order) is still minimal in the new order.

  • If $A\subseteq\{0,\ldots,n-1\}$ then the same as above, $\min_ is the same.

  • Lastly, if $A$ contains both elements from $\{0,\ldots,n-1\}$ and elements from $\{n,n+1,\ldots\}$, show that $\min_< \Big(A\cap\{n,n+1,\ldots\}\Big)$ is the new minimum.

2

HINT: Let $A$ be a non-empty subset of $\Bbb N$. It's convenient to let $M=\Bbb N\setminus\{0,1,\dots,n\}$.

There are two cases.

  1. $A\cap M\ne\varnothing$. In this case the $<^{(n)}$-least element of $A$ must belong to $M$ (why?), and $<$ and $<^{(n)}$ give the same ordering of $M$, so ... ?

  2. $A\subseteq\{0,1,\dots,n\}$. This case is easy: why?

  • 0
    @Martin: Aargh. You're right: it was a *different* typo that I fixed before. (Both were holdovers from an earlier version that was harder to read.)2012-05-04