2

I am studying infinite sets,and I can't understand the following proof of the fact that the set of positive rational numbers and the set of positive integers are of the same size.

Proof from book

(...)Even the set of all positive rational numbers .which seems immensely larger than the set of positive integers,is actually the same size.We make the correspondence by writing the rationals in a grid:

$\begin{pmatrix} \cfrac{1}{1} & \cfrac{1}{2} & \cfrac{1}{3} & \cfrac{1}{4} & \cdots \\ \cfrac{2}{1}& \cfrac{2}{2} & \cfrac{2}{3} &\cfrac{2}{4}&\cdots\\ \cfrac{3}{1}&\cfrac{3}{2}&\cfrac{3}{3}& \cfrac{3}{4}& \cdots\\\ \cfrac{4}{1}&\cfrac{4}{2}&\cfrac{4}{3}&\cfrac{4}{4}&\cdots\\ \vdots&\vdots&\vdots&\vdots&\ddots\ \end{pmatrix}$

We can create a similar grid for the positive integers by filling up along the diagonals as follows:

$\begin{pmatrix} 1&2&4&7&\cdots\\3 & 5 & 8 & 12&\cdots \\ 6&9&13&18& \cdots\\ 10&14&19&25& \cdots\\\vdots&\vdots&\vdots&\vdots&\ddots \end{pmatrix}$

We then correspond each rational to the integer in the correspond place in the grid.

Question: What is the one-to-one correspondence the author is talking about?

Is the fact that for every diagonal in the rational numbers grid we have that the sum of the numberators (or denominators) is equal to the number on the $1^{st}$ column of the positive integers grid ?

Nameless
  • 1,480
  • 1
    $1$ corresponds to $1/1$, $2$ to $1/2$, $3$ to $2/1$, $4$ to $1/3$, $5$ to $2/2$, $6$ to $3/1$, $7$ to $1/4, etc. – Simon S Nov 18 '15 at 13:49
  • yes,but why should that be a 1:1 correspondence?I could make another grid,and say that $1$ corresponds to $1/2$,$2$ to $1/3$ etc...I am not understanding why the above grid solve me the problem. – Nameless Nov 18 '15 at 13:51
  • It's a one-to-one correspondence of grid entries. In other words, we have found a surjective (onto) map $\mathbb Z \to \mathbb Q$. There is also an obvious injective (one-to-one) map $\mathbb Z \to \mathbb Q$ defined by $n \mapsto n$. Hence the cardinalities of the two sets must be the same. – Simon S Nov 18 '15 at 13:53
  • I don't follow you.Since the two sets are infinite ,I can always have an entrie for every term,no ?(I am a beginner in set theory,please don't make the argument too hard to grasp for me :S ) The problem is to show that both infinities grow at equal rate,no ? – Nameless Nov 18 '15 at 13:55
  • What do you mean by "grow at equal rate"? The goal here is to show that there are as many elements in $\Bbb{Z}$ as there are in $\Bbb{Q}$. If, as you say, for any two infinite sets you "can always have an entry for every term" try looking for a $1:1$ correspondence from $\Bbb{R}$ to $\Bbb{Z}$... – A.P. Nov 18 '15 at 14:07
  • It is not a bijection from $N$ to $Q^+$ since the $2 \to 1/2$ and $12\to 2/4$. See my edit to my question at http://math.stackexchange.com/questions/1487568/meaning-of-floor-symbols-in-fx-dfrac12-lfloor-x-rfloor-x-1 – Dan Christensen Nov 19 '15 at 17:27

2 Answers2

6

Two sets $A, B$ have the same cardinality (the same 'size') if there is a bijection $A \to B$. That is, a one-to-one correspondence between the elements of $A$ and the elements of $B$.

The famous 'diagonalization' argument you are giving in the question provides a map from the integers $\mathbb Z$ to the rationals $\mathbb Q$. The trouble is it is not a bijection. For instance, the rational number $1$ is represented infinitely many times in the form $1/1, 2/2, 3/3, \cdots$.

Thus this diagonalization provides a map $\mathbb Z \to \mathbb Q$ which is onto the rationals but not one-to-one. Hence whatever the cardinalities of the two sets are, all we can conclude for now is that the cardinality of the integers is more than or equal to the cardinality of the rationals. Write

$$|\mathbb Q| \leq |\mathbb Z|$$

To complete the argument, note that $|\mathbb Z| \leq |\mathbb Q|$, as we can easily see by constructing a map $\mathbb Z \to \mathbb Q$ defined by mapping each integer $n$ to the rational number $n/1 = n$. This map is clearly one-to-one, but it is not onto.

Therefore

$$|\mathbb Z| \leq |\mathbb Q| \leq |\mathbb Z|$$

and we can conclude that

$$|\mathbb Z| = |\mathbb Q| $$

Simon S
  • 26,524
  • I just can't understand how we can talk about "size" with infinity ?Aren't we making infinity finite by talking of "size" ?I am trying to understand this concept but my brain just can't tackle this paradox... – Nameless Nov 18 '15 at 14:20
  • Whatever the cardinality/size of the integers $\mathbb Z$ is, it isn't finite. So it makes sense to extend the notion of cardinality to non finite numbers. – Simon S Nov 18 '15 at 14:21
  • What this example of $|\mathbb Z| = |\mathbb Q|$ shows is that once we pass to infinite cardinalities, so curious results can arise. In some naive sense, the rationals are much bigger than the integers. However what this result shows is that actually they are the same size! – Simon S Nov 18 '15 at 14:23
  • Can't I have a one-to-one correspondence with sets of different size,but still infinite ? – Nameless Nov 18 '15 at 14:28
  • @Nameless No. In fact, two sets by definition have the same cardinality if there's a one-to-one correspondence (aka a bijection) between them, and this is true for both finite and infinite sets. – kviiri Nov 18 '15 at 14:30
  • There must be then some kind of definition on the type of 1-1 correspondece we can have,no ?If two sets are infinite,you can match every term of a set with another element of the other set and call it 1:1 correspondence . – Nameless Nov 18 '15 at 14:35
  • @Nameless, there's a definition, it's called bijection, and it's exactly what your describe: you match every term of a set with its own term of another set. But it's not possible between all infinite sets, for example between the set of natural numbers and the set of real numbers have no bijection between them. – kviiri Nov 18 '15 at 14:37
  • Where can I find some examples where a bijection is not possible ?Thanks for your time btw. – Nameless Nov 18 '15 at 14:41
  • @Nameless, the best-known example is indeed Naturals vs Reals, and probably the best-known proof is Cantor's diagonal argument: https://en.wikipedia.org/wiki/Cantor's_diagonal_argument . I think the proof behind it should be fairly simple too. I hope you find this interesting! :) – kviiri Nov 18 '15 at 14:46
  • @SimonS. Your answers are amazing, I wish if you could be one of the tutors who answers my questions. – Avv Apr 01 '21 at 11:32
1

The idea is that the correspondence is between the numbers that appear in the same place in the two grids. So $1$ corresponds to $\frac{1}{1}$, $2$ corresponds to $\frac{1}{2}$, $3$ corresponds to $\frac{2}{1}$, $4$ corresponds to $\frac{1}{3}$ and so on.

Now in the comment you wondered why not fill the grids in another way? Well the grids in the example are filled in a very systematic way. For the integers the diagonals from the upper right to the lower left are filled with consequetive integers. And for the rationals the rational $\frac{x}{y}$ occurs at row $x$ and column $y$.

The reason for these systematic fillings is that it now becomes easy to see that the grids do in fact contain all the rational numbers and natural numbers respectively. Therefore we can be sure that the correspondance we have doesn't miss any numbers. Afterall since every rational number is in the top grid there must be a natural number that corresponds to it.

However this correspondance is best viewed as a surjection from the naturals onto the rationals. It is not quite one-to-one as $\frac{1}{1}=\frac{2}{2}=\frac{3}{3}$ so $1,5$ and $13$ all correspond to the same rational.

Jorik
  • 1,411
  • I am trying to understand,bear with me.If both sets are infinite,how can I say that they are of the same size ?What size is infinity ?How can infinity have the same size of "another" infinity ?Isn't this just a paradoxal argument ? – Nameless Nov 18 '15 at 14:17
  • Well infite sets are somewhat unintuitive. We simply define two sets to be of the same size if there is some one-to-one correspondance between them. This has some consequences which seem weird at first. For example the sizes of $\mathb{N}$ and $\mathbb{Q}$ are the same. But it turns out there are different sizes of initite set. For example $\mathbb{R}$ is really biger than $\mathbb{N} despite both being infinite – Jorik Nov 18 '15 at 14:21
  • That's the point I am finding hard to understand.If two sets are infinite,I can always have a one-to-one correspondence for ever .For every rational I can have an integer.But I don't understand how that means that they're both of the same size.For example if we take some set $R$ which is bigger than $S$ ,but both they are infinite,I can always have a one-to-one correspondence even though $R$ is greater than $S$. – Nameless Nov 18 '15 at 14:27
  • For infite sets the notion of bigger is also not obvious. We say that $R$ is of at least the same size as $S$ if we can find an injection from $S$ to $R$. But it is not true that there is always a one-to-one correspondence. The set of all real numbers cannot be put into a one-to-one correspondence with the naturals. There are truly more real numbers. Here is a like to wikipedia that explains this phenomenon. – Jorik Nov 18 '15 at 14:43
  • Yes if two sets $A$ and $B$ are infinite, then there is a 1-1 function from one into the other, let's say $A\to B$, and it will "go on forever". For example, $A=\Bbb N$ the integers, and $B=\Bbb R$ the reals. But no function $\Bbb N\to \Bbb R$ can exhaust $\Bbb R$, there will always be some reals that is "misses", doesn't assign any integer to. The enumeration will go on forever, but if the end of time can be reached by a simple counting operation like "day after day", then forever simply isn't long enough to enumerate $\Bbb R$. – BrianO Nov 18 '15 at 22:15