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

[playboy]

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 textbook 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 textbook 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?"

 

[matt grime]

If a set is in bijection with N is it infinite? Of course.

 

[playboy]

If a set is in bijection with N is it infinite? Of course.

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 textbook 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?

 

[matt grime]

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.

 

[honestrosewater]

Maybe it would help to look at the terms for the three kinds of sets this way.

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 let's 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

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 countable ≠ uncountable 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.

 

[playboy]

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}

 

[matt grime]

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.