Math Is Fun Forum

cxc001

Member

Registered: 2010-04-09

Posts: 17

Prove set S is countable iff there exists a surjective/injective funct

Question
(a) A nonempty set S is countable if and only if there exists surjective function f:N->S
(b) A nonempty set S is countable if and only if there exists a injective function g:S->N

In either case (a) or (b) |S|<|N| in order for surjective function f: N->S and injective function g:S->N to exist.  Do I need to prove |S|<|N|, cardinality of an countable set is less then the cardinality of natural number???  If so, how to prove it?  Well, I know that I need to construct a injective function f:S->N and show that the function is NOT bijective (mainly surjective since it needs to be injective)

There are two way proves for both (a) and (b)
(a-1) prove if a nonempty set S is countable, then there exists surjective function g:S->N;  (a-2) also prove if there exists surjective function g:S->N, then a nonempty set S is countable

(b-1) prove if a nonempty set S is countable, then there exists a injective function g:S->N;  (b-2) also prove if there exists a injective function g:S->N, then a nonempty set S is countable

How to proceed in detail if it's not such a hassle for those of you to show me?  It would be greatly appreciated!

cxc001

Member

Registered: 2010-04-09

Posts: 17

Re: Prove set S is countable iff there exists a surjective/injective funct

Okay, here is what I got so far.

There should be two steps that I need to prove to show |S|<|N|
step 1) to construct a injective function f:S->N
step 2) to prove the function f:S->N is NOT bijection (mainly NOT surjective function)

Step 1) I started with trying to contrust a injection f:S->N
Since S is finite nonempty set, then the elments of set S can be listed as S={s1, s2, s3,...,sn), and |S|=n
Since N is denumerable set by theorem (countable infinite set), then N={1, 2, 3,...,n,...}
Let f(s1)=1, f(s2)=2,...,f(sn)=n
In order to show the function is injecitive, I have to show two different elements have two different images which is if f(x)=f(y), then x=y (use proof by contrapositive method)
So Let f(x)=f(y), I need to show that x=y
[This is where I stucked, how should I go from there?]

For step 2) to prove the function f:S->N is NOT bijection (mainly NOT surjective function) seems quite complicated!
[I attemped to use the proof by contradiction first]
Assume by contradiction that there exists a bijective function f:S->N
[Then how I go from there? This is where I stucked again!]

Last edited by cxc001 (2010-04-11 16:05:31)

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Prove set S is countable iff there exists a surjective/injective funct

In order to show the function is injecitive, I have to show two different elements have two different images which is if f(x)=f(y), then x=y (use proof by contrapositive method)

This is true by the very definition of f.  You send the nth entry in your listing of A to the nth natural number.  The only way two things can get sent to the same natural number is if they are both in the nth entry, but this is clearly absurd.

So Let f(a1)=f(a2), I need to show that a1=a2

No!  You just picked two elements from your set (which you know are not equal I might add), but to prove injectivity they must be left as general elements.  You are not allowed to pick them.

Also, what is this set A?

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

cxc001

Member

Registered: 2010-04-09

Posts: 17

Re: Prove set S is countable iff there exists a surjective/injective funct

Oh my bet, I should have used the set S instead of A.  So how do I construct the bijective function f:N->S correctly then?

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Prove set S is countable iff there exists a surjective/injective funct

The standard definition of countable is that it can be put in a 1-1 correspondence with the integers.  As such, not all countable sets are of the same cardinality of the integers.  So your attempt to put them in a bijective correspondence is futile (since it's not true).

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Prove set S is countable iff there exists a surjective/injective funct

As such, not all countable sets are of the same cardinality of the integers.

Don’t all countable sets have the same cardinality? Do you mean not all infinite sets have cardinality

?

So how do I construct the bijective function f:N->S correctly then?

f does not have to be bijective! For S to be countable,

only needs to be surjective. For example, S might be the set of all even natural numbers and f could be the function

.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Prove set S is countable iff there exists a surjective/injective funct

Don’t all countable sets have the same cardinality? Do you mean not all infinite sets have cardinality

?

Jane, we've had this discussion before.  The usual definition is that a set is countable if it has the same cardinality as some subset of the integers.  Some authors (enough to be notable) take countable as meaning the same cardinality as the integers.  Based on the two problems cxc001 is trying to solve, it should be apparent that he is using the first definition.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

cxc001

Member

Registered: 2010-04-09

Posts: 17

Re: Prove set S is countable iff there exists a surjective/injective funct

Thanks both!

Yes, NOT all countable sets are of the same cardinality.

A set is countable if it is either finite or denumerable
1)  Two finite countable sets are not necessarily of the same cardinality
2)  Every two denumerable sets are of the same cardinality.

Set S is denumerable if there is a bijection f:N->S

So S could be either nonempty finite set or denumerable set
1)  If S is nonempty finite set, then we need to construct a surjection f:N->S where |N|>|S|, and construct an injection g:S->N such that |S|<|N|

I had an earlier post of asking how to prove the |S|<|N|, set S is a nonempty finite set, which means |S|=n, and the elements of S can be listed as S={s1, s2, ... ,Sn}, construct a function f:S->N to be injection where |S|<|N| but NOT surjection where |S|>|N|

2)  If S is denumerable set, since the cardinality of natural number is denumerable by Theorem, then |S|=|N|, so f:N->S would be bijection and the inverse of f donated by g:S->N would be bijection as well

Should I be doing both cases???  It make more sense to assume that set S is nonempty finite set right?

Last edited by cxc001 (2010-04-12 04:18:02)

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Prove set S is countable iff there exists a surjective/injective funct

Oops. I was thinking only of “countably infinite” there. Why I was doing that I have no idea.

But yes, cxc001’s problem clearly takes the term countable to mean “finite or countably infinite”.