1

I'm studying Cantor's diagonalization, but something seems unclear to me.

There is this table for diagonalization:

╔═══════════════════════╗
║ X  1   2   3   4   5  ║
║ 1 1/1 1/2 1/3 1/4 1/5 ║
║ 2 2/1 2/2 2/3 2/4 2/5 ║
║ 3 3/1 3/2 3/3 3/4 3/5 ║
║ 4 4/1 4/2 4/3 4/4 4/5 ║
║ 5 5/1 5/2 5/3 5/4 5/5 ║
╚═══════════════════════╝

And there can be a bijection between the diagonal

From 2/1 -> 1/2

From 3/1 -> 1/3 (diagonals)

From 4/1 -> 1/4

I don't understand where the bijection really is? I guess 2/1=2 ($\mathbb{N}$) is mapped to 1/2 ($\mathbb{Q}$)

But what about 2/5? I can only see that 2/5 will make |$\mathbb{N}$| < |$\mathbb{Q}$|

However, I can only think that |$\mathbb{N}$x$\mathbb{N}$| = |$\mathbb{Q}$|

What am I missing or misunderstanding and where's the bijection? Can you give me 2 elements that are mapping to each other?

Kevin Van Ryckegem
  • 115
  • 1
    follow the arrows: https://qph.is.quoracdn.net/main-qimg-7f948c04fbc3859f685fe3c57aa5347a?convert_to_webp=true – ThePortakal Jan 14 '16 at 17:44
  • It can't be $\left\vert \mathbb N \times \mathbb N \right\vert = \left\vert \mathbb Q \right\vert$, as, for example, $\frac{1}{2}=\frac{2}{4}=\frac{3}{6}=\cdots$ is repeated. This happens with every element and its equivalence class. – Miguel Mars Jan 14 '16 at 17:45
  • just thought of that, but still I can't see how it would be equal in size, if you think about 2/5, 3/5, those can't be reduced and there is no smaller way in order to represent this, so the $\mathbb{N}$ value 5 should map to more than 1 number? @ThePortakal I still don't understand, which value of $\mathbb{N}$ maps to which value of $\mathbb{Q}$ – Kevin Van Ryckegem Jan 14 '16 at 17:48
  • 1
    Look at the picture in the link: $1 \mapsto \frac 11$, $2 \mapsto \frac 21$, $3 \mapsto \frac 12$, $4 \mapsto \frac 13$, $5 \mapsto \frac 31$ ($5 \mapsto \frac 22$ is not true because we alrealy counted $\frac 11$), $6 \mapsto \frac 41$, $7 \mapsto \frac 32$ etc. – ThePortakal Jan 14 '16 at 17:51

2 Answers2

2

This answer may not be what you're looking for, but the fact is that in this proof, one rarely actually gives a bijection itself. Instead, the countability of the rationals is proved much more easily using some simpler theorems.

Namely, a countable union of countable sets is countable.

Now define $A_n$ as the set of rationals in reduced form with denominator $n$. For example, $A_1$ is the set of integers, $A_2$ is the set of odd numbers with denominator $2$, and so forth.

Since each of these sets is countable, we have $\Bbb{Q}=A_1\cup A_2\cup A_2\cup\cdots$ is rational.

Now to relate that back to diagonalization, it turns out that Cantor is basically doing the same thing. To be rigorous, once we count a number, we have to remove it from the list. So once we could $1/1$, we need to remove $2/2$, $3/3$, etc.

One possible bijection could start as follows: $1/1$ maps to $1$, $2/1$ maps to $2$, $1/2$ maps to $3$, and so on. The point that I am trying to make is that the bijection itself doesn't really matter; the point is that we know we can make one.

pancini
  • 19,216
1

Consider this sequence and see if it helps:

1 maps to 1/1

2 maps to 2/1

3 maps to 1/2

4 maps to 1/3

5 maps to 3/1 (As the 2/2 is already included in the list we are building)

6 maps to 4/1

7 maps to 3/2

8 maps to 2/3

9 maps to 1/4

10 maps to 1/5

11 maps to 5/1 (As the others are already done on this diagonal.)

12 maps to 6/1

13 maps to 5/2

14 maps to 4/3

15 maps to 3/4

16 maps to 2/5

Thus there is keeping track of what is already handled if there are common factors.

JB King
  • 3,644
  • 2
    If 1 and 5 both get mapped to the same number, I don't see how this is a bijection. – Asaf Karagila Jan 14 '16 at 17:50
  • That helps! Didn't know that's how I was supposed to read the arrows :). I think I got the concept of "same size" of infinity is wrong. As I see it, even if you remove doubles: 1 would map to 1/1. 2 would map to { 1/2, 2/1 }. 3 would map to { 1/3, 2/3 }. And as I see here, the set of $\mathbb{N}$ would be smaller than $\mathbb{Q}$. I guess my reasoning is wrong? – Kevin Van Ryckegem Jan 14 '16 at 17:52
  • Fine, I'll tweak it so there isn't the over counting being done. – JB King Jan 14 '16 at 17:56
  • The idea is to show how this mapping can take any rational and map it to a natural and vice versa. Thus, the cardinality of the sets are the same whether it be naturals, integers or rationals even. – JB King Jan 14 '16 at 17:58
  • Alright, I guess I'm thinking too much on this one! It's pretty clear, just get any kind of bijection between the two sets and they have the same cardinality. Thanks! – Kevin Van Ryckegem Jan 14 '16 at 18:00