1

Following my last question, Does $\Bbb R-\Bbb Q$ have a well ordered subset of type $\omega\cdot\omega$, I would like to have better tools to look at a set and know what order types can it have.

I already understood that for a set to have a subset of type $\omega+n$, it should have a bounded and infinite subset. One can prove $\Bbb Z$ doesn't have one, so $\Bbb Z$ doesn't have a subset of type $\omega+n$.

What about other types? For example, how can I know whether the negative rational numbers have a subset of type $\omega\cdot\omega$, or whether $\Bbb R$ has a subset of type $\omega^\omega$, without having to construct it?

Community
  • 1
Whyka
  • 1,953

2 Answers2

1

From this question (ultimately, you're using transfinite recursion for countable ordinals; Asaf's answer is quite clear) we know that every countable ordinal order-embeds into $(\mathbb{Q},\leq)$, and so because $\mathbb{R}\setminus \mathbb{Q}$ contains a subset order-isomorphic to $\mathbb{Q}$ (say, $q\mapsto \pi+q$ is the embedding), we see that $\mathbb{R}\setminus \mathbb{Q}$ contains a copy of every countable ordinal.

Since $\omega^2$ and $\omega^\omega$ are countable ordinals, we know that $\mathbb{R}$ contains copies of each, along with $\mathbb{Q}$ and $\mathbb{R}\setminus \mathbb{Q}$.

Community
  • 1
Hayden
  • 16,737
  • Thanks! And what about $\Bbb R_-$, the negative reals? Does it have a type $\omega^2$? I tend to think it doesn't, but what is a proof to that? – Whyka Jun 29 '15 at 10:00
  • 1
    It contains a subset order isomorphic to $\mathbb{Q}$, so using the above, yes. Given any of the sets you're interested in, just turn to "Is there a copy of $\mathbb{Q}$ in it?" By "copy" I mean a subset order isomorphic to $\mathbb{Q}$. – Hayden Jun 29 '15 at 13:14
  • That's simple and helpful. Thanks a lot! – Whyka Jun 29 '15 at 13:38
1

As I pointed in the previous question, every dense set embeds every countable linear ordering, in particular every countable ordinal.

You don't even have to use transfinite recursion for this.

Suppose that $(A,<)$ is a dense linear order without endpoints, and $(D,\prec)$ is a countable linear ordering, enumerate $D$ as $\{d_n\mid n<\omega\}$, by induction define an embedding $f(d_n)=x$ such that $\{f(d_k)\mid d < n\}\cup\{x\}$ is isomorphic (with $f$, extended using $d_n\mapsto x$) to $\{d_k\mid k\leq n\}$.

For example, you pick some $a_0$ so that $f(d_0)=a_0$, suppose that you mapped $d_0,\ldots,d_5$ already, look where $d_6$ lies in the order of $\prec$ with relation to $d_0,\ldots,d_5$. Because $A$ is dense, there is some $x$ which satisfies the same relation with $a_0,\ldots,a_5$. Choose one and continue.

If $A$ happened to be countable (or otherwise well-orderable), we can enumerate it, and choose the least possible index for such $x$, otherwise the axiom of choice is implicitly assumed.

Asaf Karagila
  • 393,674
  • I'm sorry, I don't know what is embedding orders nor what is a countable ordinal. Is it like countable cardinals? An ordinal of a countable set? – Whyka Jun 28 '15 at 18:33
  • Nor the axiom of choice, nor transfinite induction :-( – Whyka Jun 28 '15 at 18:36
  • 1
    We say that $(A,<_A)$ can be embedded into $(B,<_B)$ if there is an injective function $f\colon A\to B$ such that $a<_Aa'\iff f(a)<_Bf(a')$. If $f$ is onto, we say that it is an isomorphism. It means, in other words, that there is a copy of $A$ inside $B$. Ordinals are simply canonical well-orders, like $\omega$ or $\omega^\omega+\omega^3\cdot5+\omega+42$. Countable ordinals are just those ordinals which are countable, or in other words, countable well-orders. – Asaf Karagila Jun 28 '15 at 18:42
  • Thanks! Now I think I know what embedding is- שיכון? – Whyka Jun 28 '15 at 18:44
  • 1
    The axiom of choice is a natural axiom, it means essentially that you make arbitrary choices when you provably have at least one choice (so in the case of my answer, for example, you can choose many points to be $a_0$ or $a_1$ and so on, and the axiom of choice is the formal tool that allows you to be sure that you can neglect specifying which element exactly, and just focus on knowing that there are elements which satisfy your requirements). Transfinite induction is not used here, and perhaps is best saved for a different occasion. If you study at HUJI maybe take a set theory course next year – Asaf Karagila Jun 28 '15 at 18:45
  • 1
    Yes, that is the correct translation. – Asaf Karagila Jun 28 '15 at 18:45
  • I don't study at HUJI, I study physics and mathematics at the Technion. – Whyka Jun 28 '15 at 18:47
  • Now that I know you are there, it could have been nice to study there! :-) – Whyka Jun 28 '15 at 18:47
  • From the answers to this post, it seems like all ordinals involving $\omega$ are countable. Can I have an example of a non-countable order type? – Whyka Jun 28 '15 at 18:51
  • 1
    Well, $\omega_1$ is the least uncountable well-order, and that's pretty much the best example I can give you. Or more specifically, consider all the countable ordinals, they have their natural order of "end extensions", then this set is also well-ordered and by an easy argument it has to be uncountable. That is $\omega_1$. Other than that, take any uncountable set, using the axiom of choice it can be well-ordered, that ordinal you have is by definition uncountable. But there is no "nice" way to describe an uncountable ordinal. – Asaf Karagila Jun 28 '15 at 18:59
  • So the regular well ordering on R is uncountable? – Whyka Jun 28 '15 at 19:03
  • The usual ordering of $\Bbb R$ is not well, it's not even good. It's dense! It's as far away from being a well order as possible! Moreover, it is provable that without assuming the axiom of choice (or a fragment thereof) you cannot prove the existence of a well-ordering of $\Bbb R$, so those are inherently non-descriptive. We can prove they exist in $\sf ZFC$, but generally we cannot write a formula describing them. – Asaf Karagila Jun 28 '15 at 19:05
  • Can you give an example then of an uncountable set which is well ordered? – Whyka Jun 28 '15 at 19:08
  • 1
    Look at all the ways you can well-order a countable set. Many of those are isomorphic; so just pick one from each isomorphism class (or just consider the isomorphism classes). This set is well-ordered by the following way, $R\prec S$ if both are well-orders of a countable set, and $R$ is isomorphic to a proper initial segment of $S$. If this set is countable it would be an element of itself, and it would be a contradiction to being well-ordered. So this is an uncountable set which is well-ordered. – Asaf Karagila Jun 28 '15 at 19:20