# Thread: On proving a set is countable

1. ## On proving a set is countable

By my text's definition, a set $S$ is countable if there is a function $f$ which establishes a one-to-one correspondence (bijection) between $S$ and $\mathbb{N}$.

Could we say that, consequently, a set $A$ is countable if there is a function which establishes a one-to-one correspondence between $A$ and another countable set?

For example, say we want to show that $S_n = \left\{ \frac{m}{n} : m\in \mathbb{Z} \right\}$ is countable for each $n \in \mathbb{N}$. I know that the function $f : S_n \rightarrow \mathbb{N}$ defined by
$$f\left(\frac{m}{n}\right) = \begin{cases} 2m-1& m > 0 \\ -2m&m\leq 0 \end{cases}$$
is a bijection from $S_n$ to $\mathbb{N}$.

There's also a bijection between $S_n$ and $\mathbb{Z}$, the identity map (kinda). Could this be enough to deduce countability?

2. ## Re: On proving a set is countable

Originally Posted by MadSoulz
By my text's definition, a set $S$ is countable if there is a function $f$ which establishes a one-to-one correspondence (bijection) between $S$ and $\mathbb{N}$.

Could we say that, consequently, a set $A$ is countable if there is a function which establishes a one-to-one correspondence between $A$ and another countable set?

For example, say we want to show that $S_n = \left\{ \frac{m}{n} : m\in \mathbb{Z} \right\}$ is countable for each $n \in \mathbb{N}$. I know that the function $f : S_n \rightarrow \mathbb{N}$ defined by
$$f\left(\frac{m}{n}\right) = \begin{cases} 2m-1& m > 0 \\ -2m&m\leq 0 \end{cases}$$
is a bijection from $S_n$ to $\mathbb{N}$.

There's also a bijection between $S_n$ and $\mathbb{Z}$, the identity map (kinda). Could this be enough to deduce countability?
For some reason, I cannot read this posting. I done thousands of these proofs. But I have no idea what this is about.

I will say from what I see the function $f$ is not into $\mathbb{N}$ because it can be negative.

3. ## Re: On proving a set is countable

The answer to the question you ask is "yes". If there exist a bijection from set A to set B and you know that B is countable then so is A.

I will say from what I see the function $f$ is not into $\mathbb{N}$ because it can be negative.
Yes, Plato, that was the point, f(m/n) is a bijection from $S_n$ to Z and there is a bijection from Z to N. Z is countable so $S_n$ is countable.

4. ## Re: On proving a set is countable

Originally Posted by Plato
For some reason, I cannot read this posting. I done thousands of these proofs. But I have no idea what this is about.

I will say from what I see the function $f$ is not into $\mathbb{N}$ because it can be negative.
Sorry for the confusion. Hopefully this clears it up.

Consider two sets, $A$ and $B$. Suppose that there exists a bijection between $A$ and $B$ and that $B$ is countable. Is this enough to deduce that $A$ is countable.

5. ## Re: On proving a set is countable

Originally Posted by HallsofIvy
Yes, Plato, that was the point, f(m/n) is a bijection from $S_n$ to Z and there is a bijection from Z to N. Z is countable so $S_n$ is countable.
But he did post $\large S_n\to\mathbb{N}$

6. ## Re: On proving a set is countable

Originally Posted by Plato
I will say from what I see the function $f$ is not into $\mathbb{N}$ because it can be negative.
Are you sure $f$ can be negative?

$m \mapsto 2m - 1$ for $m > 0$ which is positive.

For $m < 0$ we have $m \mapsto -2m$ which, too, is positive.

7. ## Re: On proving a set is countable

Originally Posted by MadSoulz
Are you sure $f$ can be negative?
$m \mapsto 2m - 1$ for $m > 0$ which is positive.
For $m < 0$ we have $m \mapsto -2m$ which, too, is positive.
No I am not sure of anything, because I still cannot read the positng.

Why not simply state the question?

8. ## Re: On proving a set is countable

Originally Posted by Plato
No I am not sure of anything, because I still cannot read the positng.

Why not simply state the question?
The second line of my posts states my question clearly...

If that line is not clear, then my initial reply to you states my question...

9. ## Re: On proving a set is countable

The "question", I thought, was quite clearly stated:
"Could we say that, consequently, a set A is countable if there is a function which establishes a one-to-one correspondence between A
and another countable set?" and the answer to that is "yes". The rest was an example: having shown a bijection between $S_n$ and $Z$, it follows that, since Z is countable, that $S_n$ is countable.

(Perhaps it is the fact that m/n depends upon both m and n that bothers you? That bothered me at first until I realized that the question was about $S_n$ in which n is fixed, and its members depend only on m.)