B Is this a finite argument of the countable infiniteness of the rationals?

[mcastillo356]

TL;DR Summary

I am not sure to see the expected bijection between the rationals and the natural numbers

Hi, PF

Theorem
The set $\mathbb{Q}$ of the rational numbers is countably infinite.

Proof
The rational numbers are arranged thus

$$\cfrac{0}{1},\,\cfrac{1}{1},\,\cfrac{-1}{1},\,\cfrac{1}{2},\,\cfrac{-1}{2},\,\cfrac{2}{1},\,\cfrac{-2}{1},\,\cfrac{1}{3},\,\cfrac{2}{3},\,\cfrac{-1}{3},\,\cfrac{-2}{3},\,\cfrac{3}{1},\,\cfrac{3}{2},\,\cfrac{-3}{1},\,\cfrac{-3}{2},\,\cfrac{1}{4},\,\cfrac{3}{4},\,\cfrac{-1}{4},\,\cfrac{-3}{4},\,\cfrac{4}{1},\,\cfrac{4}{3},\,\cfrac{-4}{1},\,\cfrac{-4}{3}\cdots{}$$

It is clear that every rational number will appear somewhere in this list.

Thus it is possible to set up a bijection between each rational number and its position in the list, which is an element of $\mathbb{N}$

$\blacksquare$

Attempt

Impossible to arrange any bijection, except if it implicitly recalls Cantor's comparison between rational and natural numbers, this is:



Greetings, Marcos

 

[anuttarasammyak]

Easily you can include minus rational numbers in your attempt.

 

[mcastillo356]

Easily you can include minus rational numbers in your attempt.

In the list provided first appears every rational with numerator and denominator less than or equal to one, in absolute value; then those with numerator and denominator less than or equal to two in absolute value; then those with numerator and denominator less than or equal to three in absolute value, and so on. In each of these groups we don't repeat those already written.

Each of these groups, this is, the rationals with the numerator and denominator less than, or equal to $n$ in absolute value, are a finite number?.

Attempt Each of them, ie, $\Big |\cfrac{0}{1},\,\cfrac{1}{1},\,\cfrac{-1}{1}\cdots{}\Big |$ are... I don't see the finiteness in these groups, except if we pick them one by one.

$\therefore$ In this enumeration we reach any rational

 

[pbuk]

I don't understand exactly what you are asking, it is not coming over very well in English.

You might find it easier to rearrange your list like this:

$$\cfrac{0}{1},\,\cfrac{1}{1},\,\cfrac{-1}{1},\,\cfrac{1}{2},\,\cfrac{-1}{2},\,\cfrac{2}{1},\,\cfrac{-2}{1},\,\cfrac{1}{3},\,\cfrac{-1}{3},\,\cfrac{2}{3},\,\cfrac{-2}{3},\,\cfrac{3}{1},\,\cfrac{-3}{1},\,\cfrac{3}{2},\,\cfrac{-3}{2},\,\cfrac{1}{4},\,\cfrac{-1}{4},\,\cfrac{3}{4},\,\cfrac{-3}{4},\,\cfrac{4}{1},\,\cfrac{-4}{1},\,\cfrac{4}{3},\,\cfrac{-4}{3}\dots{}$$

Can you see how the diagonal arrangement you pictured enumerates every number in even positions in this list? Then by negating the numerator we can traverse Cantor's table again enumerating every number in odd positions greater than one in this list.

We have now constructed the bijection you are looking for.

Alternatively forget that list and note the bijection between $\mathbb{Q}^- \text{ and } \mathbb{Q}^+$. We can then use the normal argument to create the bijection between $\mathbb{Q}^+ \text{ and } \mathbb{N}$.

 

[Mark44]

Your thread title is confusing or misleading.

Is this a finite argument of the countably infiniteness of the rationals?​

Both sets, the integers and the rationals, are countably infinite.

 

[mcastillo356]

Your thread title is confusing or misleading.
Both sets, the integers and the rationals, are countably infinite.

Certainly, there is no finite way to approach to infiniteness.

I don't understand exactly what you are asking, it is not coming over very well in English.

No language gets along well with the thread title.

You might find it easier to rearrange your list like this:

$$\cfrac{0}{1},\,\cfrac{1}{1},\,\cfrac{-1}{1},\,\cfrac{1}{2},\,\cfrac{-1}{2},\,\cfrac{2}{1},\,\cfrac{-2}{1},\,\cfrac{1}{3},\,\cfrac{-1}{3},\,\cfrac{2}{3},\,\cfrac{-2}{3},\,\cfrac{3}{1},\,\cfrac{-3}{1},\,\cfrac{3}{2},\,\cfrac{-3}{2},\,\cfrac{1}{4},\,\cfrac{-1}{4},\,\cfrac{3}{4},\,\cfrac{-3}{4},\,\cfrac{4}{1},\,\cfrac{-4}{1},\,\cfrac{4}{3},\,\cfrac{-4}{3}\dots{}$$

Can you see how the diagonal arrangement you pictured enumerates every number in even positions in this list? Then by negating the numerator we can traverse Cantor's table again enumerating every number in odd positions greater than one in this list.

We have now constructed the bijection you are looking for.

Alternatively forget that list and note the bijection between $\mathbb{Q}^- \text{ and } \mathbb{Q}^+$. We can then use the normal argument to create the bijection between $\mathbb{Q}^+ \text{ and } \mathbb{N}$.

I must work on this so as to start making sense. The bijection $\mathbb{Q}^-\leftrightarrow{\mathbb{Q}^+}$ will be, if possible, my next step. The bijection between $\mathbb{Q}^+ \text{ and } \mathbb{N}$ is familiar to me. I will turn back to this last quote's first bijection suggested: now I don't understand it

Greetings, Marcos

 

[Mark44]

The bijection $\mathbb{Q}^-\leftrightarrow{\mathbb{Q}^+}$ will be, if possible, my next step.

This is trivial. Each positive rational number $\frac m n$ pairs uniquely with $\frac{-m}n$ and vice versa.

Greetings, Marcos

Just as a tip, it's customary to say this at the start of your post rather than at the end. Or you can simply omit it.

 

[anuttarasammyak]

The bijection between Q+ and N is familiar to me.

How about the bijection between Q+ and odd N together with the bijection between Q- and even N ?

 

[pbuk]

How about the bijection between Q+ and odd N together with the bijection between Q- and even N ?

As already shown in post #4?

 

[mcastillo356]

How about the bijection between Q+ and odd N together with the bijection between Q- and even N ?

Atempt to understand the quote

Alternatively forget that list and note the bijection between $\mathbb{Q}^- \text{ and } \mathbb{Q}^+$. We can then use the normal argument to create the bijection between $\mathbb{Q}^+ \text{ and } \mathbb{N}$.

@Mark44 described the bijection $\mathbb{Q}^-\rightarrow{\mathbb{Q}^+}$

Bijection between $\mathbb{Q}^+$ and $\mathbb{N}$ is at the first post.

You might find it easier to rearrange your list like this:

$$\cfrac{0}{1},\,\cfrac{1}{1},\,\cfrac{-1}{1},\,\cfrac{1}{2},\,\cfrac{-1}{2},\,\cfrac{2}{1},\,\cfrac{-2}{1},\,\cfrac{1}{3},\,\cfrac{-1}{3},\,\cfrac{2}{3},\,\cfrac{-2}{3},\,\cfrac{3}{1},\,\cfrac{-3}{1},\,\cfrac{3}{2},\,\cfrac{-3}{2},\,\cfrac{1}{4},\,\cfrac{-1}{4},\,\cfrac{3}{4},\,\cfrac{-3}{4},\,\cfrac{4}{1},\,\cfrac{-4}{1},\,\cfrac{4}{3},\,\cfrac{-4}{3}\dots{}$$

Can you see how the diagonal arrangement you pictured enumerates every number in even positions in this list? Then by negating the numerator we can traverse Cantor's table again enumerating every number in odd positions greater than one in this list.

We have now constructed the bijection you are looking for.

I don't understand; attempt: negating the numerator causes it to have no effect in odd positions.

 

[anuttarasammyak]

Usually you count starting from 1/1 ,
1,2,3,4,5,…
But change it now to:
3,5,7,9,11,…

Make another table by putting minus to all the elements
And count the way ,
2,4,6,8,10,…

In the end count 1 for 0.

[EDIT] In the table some numbers are counted, some are not.
If the fraction is reducible e.g. $\frac{2}{4}=\frac{1}{2}$ do not count it and go to next. If irreducible, count.

 

[mcastillo356]

I understand the following bijections:
$$\mathbb{N}\rightarrow{\mathbb{Q}^-}$$
$$\mathbb{N}\rightarrow{\mathbb{Q}^+}$$
$$\mathbb{N}\rightarrow{2\mathbb{N}}$$
$$\mathbb{N}\rightarrow{3\mathbb{N}}$$

Usually you count starting from 1/1 ,
1,2,3,4,5,…
But change it now to:
3,5,7,9,11,…

Make another table by putting minus to all the elements
And count the way ,
2,4,6,8,10,…

I've tried to figure it out in the Geogebra file I've made: $h(g\circ{f})$

In the end count 1 for 0.

For this case there is also the Geogebra file: $g\circ{f}$

 

[kickaxe]

New here, but Cantor does not include non negative integers. So the whole argument seems moot.

But again, new, so I may be wrong, or out of line, idk.

 

[mcastillo356]

Welcome @kickaxe, very interesting your post. Now I'm on the bus. I will post soon.
As you, I don't know, or better said, you can call this thread exploratory, if not misleading, as @Mark44 suggested

 

[Mark44]

New here, but Cantor does not include non negative integers.

Adding the negative integers doesn't pose any great difficulities. If you can agree that the cardinality of $\mathbb N$ is equal to the cardinality of $\mathbb {2N}$, we can find one-to-one maps for all of the integers. Here's one possibility:
For the positive integers, $n \to 2n$.
$1 \to 2, 2 \to 4, 3 \to 6$, and so on, which frees up all of the positive odd integers 1, 3, 5, etc.
For zero and the negative integers, $n \to -2n + 1$.
$0 \to 1, -1 \to 3, -2 \to 5$, and so on.
The two functions I showed demonstrate a bijection (one-to-one map) between the set of all integers $\mathbb Z$ to the set of positive integers $\mathbb N$.
If you tell me any integer, I'll tell you which positive integer it maps to. Conversely, if you tell me a positive integer, I'll tell you which integer generated it.

 

[mcastillo356]

Adding the negative integers doesn't pose any great difficulities. If you can agree that the cardinality of $\mathbb N$ is equal to the cardinality of $\mathbb {2N}$, we can find one-to-one maps for all of the integers. Here's one possibility:
For the positive integers, $n \to 2n$.
$1 \to 2, 2 \to 4, 3 \to 6$, and so on, which frees up all of the positive odd integers 1, 3, 5, etc.
For zero and the negative integers, $n \to -2n + 1$.
$0 \to 1, -1 \to 3, -2 \to 5$, and so on.
The two functions I showed demonstrate a bijection (one-to-one map) between the set of all integers $\mathbb Z$ to the set of positive integers $\mathbb N$.
If you tell me any integer, I'll tell you which positive integer it maps to. Conversely, if you tell me a positive integer, I'll tell you which integer generated it.

Fine. I've got to read it twice. My target, anyhow, is $\mathbb{Q}\rightarrow{\mathbb{N}}$

 

[Mark44]

Fine. I've got to read it twice. My target, anyhow, is $\mathbb{Q}\rightarrow{\mathbb{N}}$

The simplest way is to look at the table in post #11. For a given rational number in the table, count how many steps it takes to get to it along the diagonal paths shown in the figure. If there's a formula for the mapping, I don't know what it is.

 

[mcastillo356]

The simplest way is to look at the table in post #11. For a given rational number in the table, count how many steps it takes to get to it along the diagonal paths shown in the figure. If there's a formula for the mapping, I don't know what it is.

@pbuk suggested on #4. Don't know if it's allowed to paste a link into a well-known video sharing company. But it is the solution: Correspondence of Naturals and Rationals, by Amanda Hager.

 

[anuttarasammyak]

Let us count the lattice points from Origin (0,0) as shown below.

They are countable. Any lattice point has its count number. We can regard that the lattice points (m,n) where m, n are positive, negative or zero,.corresponds to fraction $\frac{n}{m}$. They include not only Q but also duplications, e.g.,
\frac{2}{4}=\frac{1}{2}=\frac{-3}{-6}
, integers e,g,
\frac{-3}{1}=-3
and not defined ones, e.g.,
\frac{5}{0}
They are countable and include Q. Why is Q not countable ?

 

[mcastillo356]

In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. $\mathbb{Q}$ is countable.
Assuming the axiom of choice, a set is countable if its cardinality is not greater than that of the natural numbers.
A countable set that is not finite is said to be countably infinite.
Why is Q not countable ? It is. Doesn't suffice the link I've suggested in my previous post? It might not, I honestly don't know.
I need feedback on the video proposed.

Let us count the lattice points from Origin (0,0) as shown below.

View attachment 357901
They are countable. Any lattice point has its count number. We can regard that the lattice points (m,n) where m, n are positive, negative or zero,.corresponds to fraction $\frac{n}{m}$. They include not only Q but also duplications, e.g.,
\frac{2}{4}=\frac{1}{2}=\frac{-3}{-6}
, integers e,g,
\frac{-3}{1}=-3
and not defined ones, e.g.,
\frac{5}{0}
They are countable and include Q. Why is Q not countable ?

Brilliant, but I think it is already argued in the link pointed.
@anuttarasammyak, I don't understand your approach to $\mathbb{Q}$. Imo, it is easier to consider them as a whole, as for they're countable no matter if we think about subsets of it

 

[Mark44]

Why is Q not countable ?

The set $\mathbb Q$ is countable (again, countably infinite).

It's possible that your confusion arises from a misunderstanding about what is meant by "countable."

 

[anuttarasammyak]

Why is Q not countable ? It is.

Q is a countable infinite set. What do you want more in this thread ?