Welcome to our community

Be a part of something great, join today!

Countable sets

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,036
Hey!! :eek:

  1. Show that the set of all positive rational numbers is a countable set.
    (Hint: Consider all points in the first quadrant of the plane of which the coordinates x and y are integers.)
  2. Show that the union of a countable number of countable sets is a countable set.


I have done the following:
  1. Let $x,y>0$. We write a positive rational $\frac{x}{y}$ at the point (x, y) in the plane in the first quadrant. Now we have to count these points, or not?
  2. Do we have to use induction here?

(Wondering)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,739
Hey mathmari!!

We should make a so called swan walk. That applies to both your problems.
The swan walk for the positive rationals is 1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, ... (Thinking)
 

Greg

Perseverance
Staff member
Feb 5, 2013
1,382
As an aside, see Chapter 1, exercise 4 (Examples I) of that PDF. I believe the general result implies countability.

You'll have to scroll down to see exercise 4; the link above is not direct.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,036
We should make a so called swan walk. That applies to both your problems.
The swan walk for the positive rationals is 1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, ... (Thinking)
Does this mean that we correspond to these rationals the respective point and then we count them as follows?

rationals.JPG

(Wondering)

- - - Updated - - -

As an aside, see Chapter 1, exercise 4 (Examples I) of that PDF. I believe the general result implies countability.

You'll have to scroll down to see exercise 4; the link above is not direct.
So, do we have to write the positive rationals as a sequence? (Wondering)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,739
Does this mean that we correspond to these rationals the respective point and then we count them as follows?

So, do we have to write the positive rationals as a sequence? (Wondering)
Yes.
greg1313 's reference shows a slightly different swan-walk, which boils down to the same thing.
We can write the positive rationals as a sequence, which means that we can 'count' them.
That is, we can define a mapping $\mathbb N \to \mathbb Q_{>0}$ that is surjective, which shows that the positive rationals are countable. (Thinking)
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,036
Yes.
greg1313 's reference shows a slightly different swan-walk, which boils down to the same thing.
We can write the positive rationals as sequence, which means that we can 'count' them.
That is, we can define a mapping $\mathbb N \to \mathbb Q_{>0}$ that is surjective, which shows that the positive rationals are countable. (Thinking)
Ah ok!

But using the given hint, do we 'count' the positive rationals as in the picture of #4 ? If yes, how could we prove that formally without just with the picture?

(Wondering)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,739
Ah ok!

But using the given hint, do we 'count' the positive rationals as in the picture of #4 ? If yes, how could we prove that formally without just with the picture?
Any positive rational can be written as $\frac p q$ where $p$ and $q$ are positive integers.
So each positive rational will show up in the sequence.
We might formalize the actual sequence a bit more, defining the actual mapping.
Did you try? Otherwise you can check out greg1313 's reference. (Thinking)
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,036
Any positive rational can be written as $\frac p q$ where $p$ and $q$ are positive integers.
So each positive rational will show up in the sequence.
We might formalize the actual sequence a bit more, defining the actual mapping.
Did you try?
1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, ...

First we have all the fractions where the sum of numerator and denominator is equal to 2, then all the fractions where the sum of numerator and denominator is equal to 3, then all the fractions where the sum of numerator and denominator is equal to 4, etc.

The fraction p/q will appear if we write down all the fractions with sum of numerator and denominator equal to $p+q$.

Do we have to justify that we get this fraction after finite number of terms?


Is everything correct? Or did you mean something else? (Wondering)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,739
1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, ...

First we have all the fractions where the sum of numerator and denominator is equal to 2, then all the fractions where the sum of numerator and denominator is equal to 3, then all the fractions where the sum of numerator and denominator is equal to 4, etc.

The fraction p/q will appear if we write down all the fractions with sum of numerator and denominator equal to $p+q$.

Do we have to justify that we get this fraction after finite number of terms?


Is everything correct? Or did you mean something else?
Yes. That is what I meant. And I believe it is sufficient for a proof. (Nod)
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,036
Yes. That is what I meant. And I believe it is sufficient for a proof. (Nod)
Ah ok! Great!! (Nerd)


What about the second question to show that the union of a countable number of countable sets is a countable set?
Do we have to show first that it holds for two sets and then we show the desired by induction?

Let $A=(a_1, a_2, \ldots )$, $B=(b_1, b_2, \ldots )$ be two countable sets. We define $f:\mathbb{N}\times\mathbb{N}\rightarrow A\times B$ with $f(n,m)=(a_n, b_m)$. This map is surjective, isn't it?
We have that $\mathbb{N}\times\mathbb{N}$ is counatble, right? Then it follows that $A\times B$ is also countable.

Is this part correct? (Wondering)


Now we have to use the induction to show that $\displaystyle{\bigcup_{n\in \mathbb{N}}M_n}$ is countable:

Base case: For $n=1$ it holds since then we have just one set, which is countable.

Inductive Hypothesis: We suppose that the statement holds for $n=k$.

Inductive step: We want to show that it holds for $n=k+1$. We have that $\bigcup_{n=1}^{k+1}M_n=\bigcup_{n=1}^{k}M_n\cup M_{k+1}$. The first one $\bigcup_{n=1}^{k}M_n$ is countable from the inctuctive hypothesis and $M_{k+1}$ is also ccountable.
So we have a union of two countable sets, which is countable because of the above argument.

Is everything correct? (Wondering)
 
Last edited:

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,739
Ah ok! Great!! (Nerd)


What about the second question to show that the union of a countable number of countable sets is a countable set?
Do we have to show first that it holds for two sets and then we show the desired by induction?

Let $A=(a_1, a_2, \ldots )$, $B=(b_1, b_2, \ldots )$ be two countable sets. We define $f:\mathbb{N}\times\mathbb{N}\rightarrow A\times B$ with $f(n,m)=(a_n, b_m)$. This map is surjective, isn't it?
We have that $\mathbb{N}\times\mathbb{N}$ is counatble, right? Then it follows that $A\times B$ is also countable.

Is this part correct?
It is correct, although you may want to explain why $\mathbb{N}\times\mathbb{N}$ is countable.
It is countable for the same reason as $\mathbb Q_{>0}$, which is because we can define a swan walk.
That is, we can define a surjective map $\mathbb N \to \mathbb N \times \mathbb N$, showing that it is countable.

Now we have to use the induction to show that $\displaystyle{\bigcup_{n\in \mathbb{N}}M_n}$ is countable:

Base case: For $n=1$ it holds since then we have just one set, which is countable.

Inductive Hypothesis: We suppose that the statement holds for $n=k$.

Inductive step: We want to show that it holds for $n=k+1$. We have that $\bigcup_{n=1}^{k+1}M_n=\bigcup_{n=1}^{k}M_n\cup M_{k+1}$. The first one $\bigcup_{n=1}^{k}M_n$ is countable from the inctuctive hypothesis and $M_{k+1}$ is also ccountable.
So we have a union of two countable sets, which is countable because of the above argument.

Is everything correct?
I believe so yes.
EDIT: As Country Boy mentions below, induction is not good enough. We really need a surjective mapping of $\mathbb N$ to all elements.
Btw, we're mixing cartesian products and unions, which is strictly speaking not correct.


Instead we can also define a swan walk through all the sets.
Let $a_{ij}$ be the $j$th element of the $i$th set.
Then $a_{11}, a_{12}, a_{21}, a_{13}, a_{22}, ...$ is a countable sequence that contains all elements in all sets. (Nerd)
 

Country Boy

Well-known member
MHB Math Helper
Jan 30, 2018
432
Ah ok! Great!! (Nerd)


What about the second question to show that the union of a countable number of countable sets is a countable set?
Do we have to show first that it holds for two sets and then we show the desired by induction?
NO! "Induction" would show only that the union of any finite number of countable sets is countable.

Let $A=(a_1, a_2, \ldots )$, $B=(b_1, b_2, \ldots )$ be two countable sets. We define $f:\mathbb{N}\times\mathbb{N}\rightarrow A\times B$ with $f(n,m)=(a_n, b_m)$. This map is surjective, isn't it?
We have that $\mathbb{N}\times\mathbb{N}$ is counatble, right? Then it follows that $A\times B$ is also countable.

Is this part correct? (Wondering)


Now we have to use the induction to show that $\displaystyle{\bigcup_{n\in \mathbb{N}}M_n}$ is countable:

Base case: For $n=1$ it holds since then we have just one set, which is countable.

Inductive Hypothesis: We suppose that the statement holds for $n=k$.

Inductive step: We want to show that it holds for $n=k+1$. We have that $\bigcup_{n=1}^{k+1}M_n=\bigcup_{n=1}^{k}M_n\cup M_{k+1}$. The first one $\bigcup_{n=1}^{k}M_n$ is countable from the inctuctive hypothesis and $M_{k+1}$ is also ccountable.
So we have a union of two countable sets, which is countable because of the above argument.

Is everything correct? (Wondering)