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

  • Thread starter cxc001
  • Start date
  • #1
16
0
(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


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 f:N->S; (a-2) also prove if there exists surjective function f:N->S, 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

---------------------------------------------------
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 A is denumerable if there is a bijection f:N->A
---------------------------------------------------

How to construct a surjection f:N->S?
Also the inverse of function f which is g:S->N is also injection?

Please help!
 

Answers and Replies

  • #2
1,631
4
I am assuming 'denumerable'='countably infinite'.
Suppose S is countable.
If S is countably infinite then there is a bijection, by definition, f:N-->S, so we are done.

If S is finite, then we know that there is a bijection h:{1,2,...,n}-->S. We can extend this to a surjection f:N-->S, as follows, f(i)=h(i) if 1<=i<=n, and f(i)=h(1) if i>n.

Now, assume that f:N-->S is a surjection. We need to show that S is either finite or countably infinite. If S is finite then it is clearly countable. Assume S is infinite.

Define E_i={j|f(i)=f(j)}. That is it consists of all elements in N that are mapped to the same element in S. Then consider the following mapping

h:S--> defined by h: i-->j, where j is some element of E_i... we can show that such a mapping is a bijection. Hence S is countably infinite.

You can do other cases similarly, and also fill in the gaps that i have left for you in this proof.
 
Last edited:
  • #3
16
0
Thanks!
 

Related Threads on Prove set S is countable iff there exists a surjective/injective function

Replies
10
Views
2K
Replies
14
Views
3K
  • Last Post
Replies
3
Views
990
Replies
13
Views
2K
Replies
3
Views
1K
  • Last Post
Replies
4
Views
4K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
4K
Top