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...