Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proof: If S is denumerable, then S is equinumerous w/ a proper subset

  1. Feb 5, 2006 #1
    The question is:

    " Prove that if S is denumerable, then S is equinumerous with a proper subset of itself"

    To begin, I am confused with the term denumerable because the text book gives some diagram which is throwing me off. So can somebody clarify this for me:

    A set S is denumerable if S and N (natural numbers) are equinumerous. That is, their is a BIJECTIVE function f: N---->S

    The text book says N is INFINITE. So if N is infite, that means that S HAS TO BE INFINTE if S is denumerable?

    Now I'm reading the books diagram like this:

    Countable sets are FINITE OR DENUMERABLE
    Infinite sets are UNCOUNTABLE OR DENUMERABLE

    So is this true: "if a set S is denumerable, then it HAS TO BE INFINITE?"
     
  2. jcsd
  3. Feb 5, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    If a set is in bijection with N is it infinite? Of course.
     
  4. Feb 5, 2006 #3
    If a set is Denumerable, then it is in bijection with N. That means it has to be infite also. That is what i thought. So every denumerable set is infinite.

    But the text book says this:

    Countable sets are FINITE OR DENUMERABLE
    Infinite sets are UNCOUNTABLE OR DENUMERABLE

    Is the above true? If an infine set is Denumerable, then how can a countable set be Denumerable?
     
  5. Feb 6, 2006 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    The *definition* of countable is that it is either finite or denumerable. It is just a definition.

    Definition: a set is countable if it can be placed in bijection with some subset (including N itself) of the natural numbers, otherwise it is uncountable.
     
  6. Feb 6, 2006 #5

    honestrosewater

    User Avatar
    Gold Member

    Maybe it would help to look at the terms for the three kinds of sets this way.
    Code (Text):

    1)   [b]finite[/b]        not denumerable        countable

    2) not finite       [b]denumerable[/b]           countable

    3) not finite      not denumerable     [b]not countable[/b]
    Your book lets not finite = infinite and not countable = uncountable.

    But just as a warning, not everyone uses these terms the same way -- and it's somewhat confusing. If you learn yours, you can figure out what other people are talking about. One other use is
    Code (Text):
    1)  [b]finite[/b]       not countable    not uncountable

    2) not finite      [b]countable[/b]      not uncountable

    3) not finite    not countable     [b]uncountable[/b]
    This way, not countableuncountable and not uncountable = at most countable. I prefer the way your book does it because it fits better with the ways negation normally works in English (with not, un-, in-) and doesn't unnecessarily complicate things, e.g., by making something both not countable and at most countable.
     
    Last edited: Feb 7, 2006
  7. Feb 7, 2006 #6
    Thank you honestrosewater for that post, it helps.

    My TA gave examples of countable numbers
    Q = {m/n, m,n in Z}

    I was trying to tell him that "m,n in Z" can't make it countable?

    I say this because a set is countable if f:N--->s is surjective or if f:S---->N is injective.

    so shouldn't it be Q = {m/n, m,n in N and n cannot be 0}
     
  8. Feb 7, 2006 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Well, modulo the issue that you can't have zero as a denominator, I don't get you at all.

    Firstly Q means the rational numbers, and you have to have negative rationals.

    Secondly, why does having Z bother you? Z obviously has a bijection with the naturals, or an injection into the naturals, so there is no problem at all. Q is simply (a subset of) the product of two countable sets, and is hence countable.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook