Order embeddings and Ordinals

106 Views Asked by At

How do I show that there are two countable linear orders that can't be order-embedded into each other? I have been trying to use $\omega$ and -$\omega$, but I am getting a lost.

Also, while working through this problem I considered ordinals like $\omega + 1$, but I am having a hard time visualizing what this set looks like. I know $\omega$ is just the set of all finite ordinals, so is something like $\omega + 1$ the set of all finite ordinals with another copy of $1$ in the set? I just need some guidance with how to visualize these types of ordinals if possible.

2

There are 2 best solutions below

0
On BEST ANSWER

As to the last question $\omega+1$ is just the natural numbers, with an extra element $M$ that is the max of the set: for all $n$, $n \le M$. In set theory, $\omega+1 = \omega \cup \{\omega\}$, where the first part of this union is the naturals, om $0$ onwards, and the last is a singleton set of $\omega$, which is the maximum. As the linear ordinal in ordinals, we use $n < m$ iff $n \in m$ iff $n \subseteq m$. So it's clear that the element of $\omega+1$ is bigger than all members of $\omega$. As a subset of the reaas you can think of $\{-\frac{1}{n+1} : n \ge 0\} \cup \{0\}$ in the linear ordering from the reals as a copy of $\omega+1$.

You are right that $\omega$ and $-\omega$ have no mutual embeddings.

Suppose there is an embedding $f: \omega \rightarrow -\omega$. Suppose $f(0) = -n$, for some $n \in \omega$. Then for all $n> 0$, we must have $f(n) \ge f(0)$, so $f(0)$ is a minimum of $-\omega$. This clearly does not exist (for any $-n$, $-n+1$ is strictly smaller), so we have a contradiction.

The other direction also has no embedding, as $f(0)$ should be a maximum of its image, and no infinite subset of $\omega$ has a maximum.

0
On

Consider $\mathbb{N}$ and $\mathbb{S} = \{a \in \mathbb{Z}: a$ is negative or $0\}$ with their canonical orderings. Assume that $f: \mathbb{N} \to \mathbb{S}$ is an embedding. Then $f(0) = -a$ for some $a \in \mathbb{N}$. Now consider $f(a +1)$. Where can this go?

Likewise, assume that $g: \mathbb{S} \to \mathbb{N}$. Then $g(0) = b$ for some $b \in \mathbb{N}$. Now consider $g(b+1)$. Where can this go?