1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Condition for Countability

  1. Mar 7, 2013 #1

    CAF123

    User Avatar
    Gold Member

    I seem to have a couple of contradictory statements of what a countable set is defined to be:
    In my textbook I have:
    'Let E be a set. E is said to be countable if and only if there exists a 1-1 function which takes ##\mathbb{N}## onto E.'

    This implies to me that that there has to exist a beijection from ##\mathbb{N}## to E since they use 1-1 and onto in the defintion.

    In my notes I have: E is said to be countable if there is a bijection ##f: \mathbb{N} \mapsto E##'

    However, when I looked on Wikipedia, I read:
    A set S is called countable if there exists an injective function f from S to the natural numbers N.

    Is there a contradiction here and if so, what is the true defintion?
     
  2. jcsd
  3. Mar 7, 2013 #2

    WannabeNewton

    User Avatar
    Science Advisor

    The true definition is: a set [itex]S[/itex] is countable if there exists an injection [itex]f:S\rightarrow \mathbb{N}[/itex]. Note it does NOT have to be a surjection as well, in general. IF [itex]f[/itex] also happens to be surjective then we say [itex]S[/itex] is countably infinite.
     
  4. Mar 7, 2013 #3

    CAF123

    User Avatar
    Gold Member

    That was a quick reply. What exactly does countably infinite mean?
    If I understand correctly, then if a set is finite it is automatically countable. So an infinite set is countable provided there exists a bijection from N to E?
     
  5. Mar 7, 2013 #4

    WannabeNewton

    User Avatar
    Science Advisor

    A set [itex]S[/itex] is countably infinite if there exists a bijection [itex]f:S\rightarrow \mathbb{N}[/itex]. If [itex]S[/itex] is not countable (i.e. neither countably infinite nor countably finite) then we say [itex]S[/itex] is uncountable. So, for example, [itex]\mathbb{Z},\mathbb{Q}[/itex] are countably infinite but [itex]\mathbb{R}[/itex] is uncountable (the proof of this is one of the most beautiful proofs in mathematics and was shown by Cantor using the extremely elegant diagonal argument).
     
  6. Mar 7, 2013 #5

    CAF123

    User Avatar
    Gold Member

    I have in my notes that '....bijection from N to S'. But you have bijection from S to N. I suppose it won't matter here. But for an injection N to S, is an injection S to N the same thing. (it seems so, but I just want to clarify).
     
  7. Mar 7, 2013 #6

    WannabeNewton

    User Avatar
    Science Advisor

    No it doesn't mean the same thing. There exists an injection [itex]f:\left \{ 1,2 \right \}\rightarrow \mathbb{N}[/itex] (it is just the inclusion map). Does that imply there exists an injection [itex]f:\mathbb{N}\rightarrow \left \{ 1,2 \right \}[/itex]? It doesn't of course!
     
  8. Mar 7, 2013 #7

    Bacle2

    User Avatar
    Science Advisor

    Just to add that the Cantor-Schroder-Bernstein says that if there are injections between N and S and between S and N , then there is a bijection between N and S .
     
  9. Mar 7, 2013 #8

    WannabeNewton

    User Avatar
    Science Advisor

    A fun and short exercise is to show, using the well ordering theorem, that there exists an uncountable well - ordered set [itex]Y[/itex] such that [itex]\forall x\in Y[/itex], there exist only countably many [itex]y\in Y[/itex] such that [itex]y < x[/itex]. It's a pretty awesome result considering we are talking about an uncountable, totally ordered set!
     
  10. Mar 7, 2013 #9

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Different authors tend to use different terminology. Some authors use countable to denote that there is a bijection to the natural numbers. In their terminology, finite sets are not countable. Other authors (the majority, I guess), allow finite sets to be countable.
     
  11. Mar 8, 2013 #10

    CAF123

    User Avatar
    Gold Member

    For sets that are finite and said to be countable does that mean there always exists an injection from S to N?

    In your example, an injection could be ##1 \mapsto 1## and ##2\mapsto 2##?

    Or if we take a set {1} then the injection could be ##1 \mapsto a##, ##a \in \mathbb{N}##.
     
  12. Mar 8, 2013 #11

    WannabeNewton

    User Avatar
    Science Advisor

    Yes to all your questions.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Condition for Countability
  1. Countable list (Replies: 4)

  2. Countable bits (Replies: 12)

  3. Countable sets (Replies: 20)

Loading...