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!

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

    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

    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


    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

Similar Threads for Proof denumerable equinumerous Date
Logic behind a proof Yesterday at 6:17 PM
Proof about equality. Sunday at 1:06 PM
Proof of minimum polynomial Apr 12, 2018
Help with Newton root approximation proof Mar 27, 2018
Prove that roots of trig polynomials are denumerable Sep 4, 2017