3

Does $\Bbb R- \Bbb Q$ have a well ordered subset of type $\omega\cdot\omega$?

I thought of taking the subset to be A={$n\cdot \sqrt{m}:n\in\Bbb N,m\in P$} where P is the set of all prime numbers, with the well ordering - $\sqrt{2}<\sqrt{3}<\sqrt{5}<\sqrt{7}<...<2\cdot\sqrt{2}<2\cdot\sqrt{3}<2\cdot\sqrt{5}<...<3\cdot\sqrt{2}<3\cdot\sqrt{3}<...<m\cdot\sqrt{2}<m\cdot\sqrt{3}<m\cdot\sqrt{5}<...$

A is indeed a subset of $\Bbb R- \Bbb Q$ and the well ordering is of type $\omega\cdot\omega$.

Am I correct?

And if I have to use the regular order of numbers, does there still exist a subset with such an ordering type?

Whyka
  • 1,953
  • You have to use the regular ordering of numbers... – David C. Ullrich Jun 27 '15 at 18:18
  • @DavidC.Ullrich why is that? – Whyka Jun 27 '15 at 18:24
  • 2
    That's implicit in the problem. The author must have intended that you use the standard order. Why? Because if you're allowed to make up your own order then asking the question about $\mathbb R\setminus\mathbb Q$ makes no sense; if you're allowed to make up your own order than that set is the same as any other set with the same cardinality. – David C. Ullrich Jun 27 '15 at 18:38
  • @DavidC.Ullrich I see. Thanks. If so, does there exist a subset of $\Bbb Z$ (with the regular well ordering) of type $\omega+1$? I thought there is, because I can take $\Bbb N$ with the order $1<2<3<...<0$, But now I tend to think I'm wrong. – Whyka Jun 27 '15 at 18:42
  • 1
    No, there's no $\omega+1$ in $\mathbb Z$. – David C. Ullrich Jun 27 '15 at 18:55
  • @DavidC.Ullrich what about the subset {$n/(n-1)$}$\cup1$? It is a subset of $\Bbb Z$ and of type $\omega+1$, isn't it? – Whyka Jun 27 '15 at 19:50
  • 1
    @Whyka $\mathbb Z\ne\mathbb Q$ – David C. Ullrich Jun 27 '15 at 19:51
  • @DavidC.Ullrich Oh of course. I mixed them up. Thank you! – Whyka Jun 27 '15 at 19:52
  • @DavidC.Ullrich I hope I'm not bothering you. One last question. How do I prove there isn't a type $\omega+1$ in $\Bbb Z$? – Whyka Jun 27 '15 at 21:24
  • 1
    @Whyka: Show that in $\Bbb Z$ every bounded set with a minimal element is finite. – Asaf Karagila Jun 27 '15 at 21:36
  • 1
    @Whyka What Asaf said. Or show that if $n_j$ is an increasing sequence then $n_j\to\infty$ (which says exactly there is no $n$ with $n>n_j$ for all $j$). – David C. Ullrich Jun 27 '15 at 21:50
  • @DavidC.Ullrich - Nice, thanks. Is there a way to prove $n_j\rightarrow\infty$ or is it an intrinsic property of $\Bbb Z$? – Whyka Jun 27 '15 at 22:01
  • hmm. The $\mathbb Z$ part is $n_{j+1}>n_j$ implies $n_{j+1}\ge n_j+1$. So by induction $n_j\ge n_0+j$. Now the Archimedean property shows that, erm, $j\to\infty$ as $j\to\infty$... – David C. Ullrich Jun 27 '15 at 22:14
  • 1
    @David: That sounds like an overkill. Much easier is to show that for any $k\in\Bbb Z$, the tail segment ${n\in\Bbb Z\mid k<n}$ has order type $\omega$. – Asaf Karagila Jun 28 '15 at 03:48
  • @AsafKaragila I proved that every bounded subset of Z is finite by constricting an isomorphism to a finite ordinal. But, just to make sure I understand- how does this prove there is no subset of Z of type w+1? Is it because type w+1 is supposed to be bounded because it has a last element, therefore there exists a bounded subset which is infinite and this is what we showed to be wrong? – Whyka Jun 28 '15 at 12:36
  • 1
    Yes, that is the idea. $\omega+1$ has minimal and maximal elements, but it's infinite. – Asaf Karagila Jun 28 '15 at 12:45
  • @AsafKaragila Yeah, but then we have to show that $\omega$ does not contain a subset isomorphic to $\omega+1$. Which is obvious, but which it seems to me is also exactly what we want to prove. And of course it's true on some high-falutin set-theoretic grounds, but... – David C. Ullrich Jun 28 '15 at 18:26
  • When I found myself saying we need to show $j\to\infty$ as $j\to\infty$ I decided I must be confused. But on reflection I don't think I was. We have a strictly increasing sequence $(n_j)$ of integers. We need to show that given an integer $A$ there exists $j$ such that $n_j>A$. But $n_j\ge n_0+j$, so $n_j>A$ for any $j>A-n_0$. – David C. Ullrich Jun 28 '15 at 18:29
  • 1
    @David: But that's one of the key points about well-orders. No well-ordered set can be embedded into a proper initial segment of itself; and $\omega$ is the least non-empty well-ordered set [read: order type] which is infinite, so any proper initial segment is finite by definition. – Asaf Karagila Jun 28 '15 at 18:47
  • @AsafKaragila Well of course. I was trying to say something that might be more accessible in what one might call the present context... never mind. – David C. Ullrich Jun 28 '15 at 19:00
  • 1
    @David: You didn't say anything wrong. I just think that well-orders are not very difficult to understand (once you get past that "oh, but a well-order is only what the natural numbers have!" phase). And the basic theorems about well-orders are enlightening, useful and worth pursuing on their own! – Asaf Karagila Jun 28 '15 at 19:03
  • @AsafKaragila Yes of course. Unless it's a context where any sort of abstraction is totally incomprehensible... Go buy a cup of coffee, and try to explain to the guy behind the counter that no well ordered set can be embedded into a proper initial segment of itself. I'm thinking of like the linear algebra student who asked here how to "find $\ker(x,y,z)=(z,y,0)$"; I can guarantee you the problem actually asked for the kernel of $T$, where $T(x,y,z)=(x,y,0)$, and the student doesn't see the difference between that and what he wrote. – David C. Ullrich Jun 28 '15 at 19:21
  • @David: My department bought a very nice automatic espresso machine, to make sure that I won't even have to go to the other building to make my coffee. I haven't bought coffee in a while now (with rare exceptions when I'm on the go and have no time to engage with what otherwise would be considered flirting with the barista). – Asaf Karagila Jun 28 '15 at 19:25
  • @AsafKaragila Fine then. I withdraw all my objections and comments. Hadn't thought it through, sorry. – David C. Ullrich Jun 28 '15 at 19:39
  • @David: :-D :-D – Asaf Karagila Jun 28 '15 at 19:43

1 Answers1

5

There's an incredibly easy answer to this.

Theorem. If $(A,<)$ is a dense linearly ordered set, then countable linear order can be embedded into $A$.

This is really a theorem about $\Bbb Q$ itself, and then a consequence from the fact that every dense linear order has a subset isomorphic to $\Bbb Q$.

But to see this more concretely with $\omega\cdot\omega$, just pick an $\omega$ sequence of irrational numbers, e.g. $x_n=\pi+n$, then for each $x_n$, pick a sequence of order type $\omega$ in $(x_{n-1},x_n)$. For example, in this case, $y_{n+1,k}=\pi+n+\frac k{k+1}$.

Now show that $\{x_n\mid n<\omega\}\cup\{y_{n,k}\mid n,k<\omega\}$ is the wanted sequence.

Asaf Karagila
  • 393,674
  • Why did you add $\frac 1\pi^i$? Will $\frac n{n-1}$ work as well? – Whyka Jun 27 '15 at 21:33
  • 1
    Yes, you're absolutely. I wanted to make sure this remains irrational. And while it's probably not hard to show that my suggest works, it's much easier with your suggestion. – Asaf Karagila Jun 27 '15 at 21:35
  • Thanks! And is there a more rigorous way to say "this subgroup is type $\omega\cdot\omega$ because each of the $\omega$ elements of form $\pi+n$ is followed by a series of $\omega$ elements"? – Whyka Jun 27 '15 at 21:38
  • 1
    Yes, you can actually construct the isomorphism with the lexicographic order on $\omega^2$. $(n,k)\mapsto \pi+n+\frac k{k+1}$. – Asaf Karagila Jun 27 '15 at 21:41
  • 1
    Also, subset. :-) – Asaf Karagila Jun 27 '15 at 21:52
  • 1
    Too late to change... Tough life... :-) – Whyka Jun 27 '15 at 21:55
  • 1
    זה לא ממש עובד באנגלית. – Asaf Karagila Jun 27 '15 at 21:55
  • Actually, this is almost also a proof of the quoted theorem: Assume the ordinal $\alpha$ is countable and all $\beta<\alpha$ can be embedded into $\mathbb Q$. Then for each $\beta<\alpha$ pick a distinct one of the countably many intervals $(n.n+1)\cap\mathbb Q$, into which we can also embed $\beta$. The order type of the union is countable and contains each $\beta$, hence is $\ge\alpha$ and contains $\alpha$ as subset. - Finally if we find a copy $\alpha$ within $\mathbb Q$, we can translate it by $\sqrt 2$ and then find it within $\mathbb R-\mathbb Q$ – Hagen von Eitzen Jun 28 '15 at 13:04
  • 2
    @HagenvonEitzen: The quoted theorem is for every countable linear order, not just for well-orders. – hmakholm left over Monica Jun 28 '15 at 13:08