A well ordered set haven't the same order that any section

32 Views Asked by At

Suppose that $(A,\leq)$ is a set with a well order, and $S\subset A$ any section ($S\neq A$).

Def: a section is a subset that: if $a\in S\to b\in S$ for all $b\leq a$.

Prove that $A$ and $S$ haven't the same order, ie don't exist a bijection $\phi$ between both such that if $a\leq b \to \phi(a)\leq\phi(b)$.

My proof: suppose that exist $\phi:S\to A$. Because $A$ have a well order, exist $s_1\in S$ minimal. Is clear that $\phi(s_1)=s_1$.

Now, $S-\{s_1\}$ is a subset and exist $s_2\in S-\{s_1\}$ minimal and $\phi(s_2)=s_2$.

Let $T=\{s\in S: \phi(s)\neq s\}\subset S\subset A$, and exist a $ t\in T$ minimal.

Look $\phi^{-1}(t)$:

If $\phi^{-1}(t)=s\leq t \to t\leq \phi(s)=s$ abs!

If $ t\leq\phi^{-1}(t) \to \phi(t)\leq t$ put $s=\phi(t)\leq t$ if $s\neq t$, $s\in T$ and contradice the minimallity of $t$.

Then, $\phi$ is not surjective,abs.

It's ok? Thanks!

1

There are 1 best solutions below

3
On BEST ANSWER

Basically this looks good! A couple minor comments:

First of all, your lines about $s_1$ and $s_2$ don't actually contribute anything to the final proof; so you don't need them.

Second, you technically need to say why $T$ is nonempty (this isn't hard, but you need to say it).

Third, if $t<\phi^{-1}(t)$, how do you know that $\phi(t)$ is in $T$? (It is, but you need to say why.)


Here's another proof which is of a similar spirit but might be a bit easier to visualize:

  • Since $S\subsetneq A$, there is some minimal $x\in A\setminus S$.

  • Since $S$ is a section (BTW I've never seen this word before - the more common term is initial segment), we have $x>s$ for all $s\in S$.

  • Now think about $\phi^{-1}(x)$ - call this "$x_1$." We have $x_1\in S$, so $x_1<x$.

  • Now think about $\phi^{-1}(x_1)$ - call this "$x_2$." We must have $x_2<x_1$ (why? apply $\phi^{-1}$ to both sides of $x_1<x$.).

  • Continuing this way, we may define a sequence $x_i$ recursively as $x_0=x$, $x_{n+1}=\varphi^{-1}(x_n)$. By induction $x_n>x_{n+1}$ . . .

  • . . . which contradicts the assumption that $A$ was well-founded.