Results 1 to 9 of 9
Like Tree1Thanks
  • 1 Post By HallsofIvy

Thread: On proving a set is countable

  1. #1
    Member
    Joined
    Sep 2013
    From
    United States
    Posts
    85
    Thanks
    3

    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?
    Last edited by MadSoulz; Jul 15th 2017 at 04:07 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,153
    Thanks
    2604
    Awards
    1

    Re: On proving a set is countable

    Quote Originally Posted by MadSoulz View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,109
    Thanks
    2802

    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.
    Last edited by HallsofIvy; Jul 15th 2017 at 05:05 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2013
    From
    United States
    Posts
    85
    Thanks
    3

    Re: On proving a set is countable

    Quote Originally Posted by Plato View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,153
    Thanks
    2604
    Awards
    1

    Re: On proving a set is countable

    Quote Originally Posted by HallsofIvy View Post
    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}$
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Sep 2013
    From
    United States
    Posts
    85
    Thanks
    3

    Re: On proving a set is countable

    Quote Originally Posted by Plato View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,153
    Thanks
    2604
    Awards
    1

    Re: On proving a set is countable

    Quote Originally Posted by MadSoulz View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Sep 2013
    From
    United States
    Posts
    85
    Thanks
    3

    Re: On proving a set is countable

    Quote Originally Posted by Plato View Post
    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...
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,109
    Thanks
    2802

    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.)
    Thanks from MadSoulz
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proving a set is countable
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Nov 5th 2013, 07:52 AM
  2. Replies: 1
    Last Post: Jun 3rd 2013, 04:48 PM
  3. proving the set of finite decimals is countable
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Sep 29th 2010, 01:07 PM
  4. Proving countable set
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Apr 14th 2010, 01:29 PM
  5. Replies: 11
    Last Post: Oct 11th 2008, 06:49 PM

/mathhelpforum @mathhelpforum