Cardinality Problem: Prove |A| < |N|

  • Thread starter cxc001
  • Start date
  • #1
16
0
Prove cardinality of every finite nonempty set A is less then cardinality of natural number N
|A|<|N|

set A is nonempty finite set
natural number N is denumerable (infinite countable set)

|A|<|N| if there exist a injective (one-to-one) function f: A->N, but NO bijective function, which means NO surjective (onto) function

How to prove it in detail???

Help please!!!
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
Before trying to worry about how to prove it in detail, first worry about how to sketch a proof... or even just getting ideas to understand the situation better.

When you tell us where you're at on the problem, then we will be able to help you figure out how to get unstuck!
 
  • #3
16
0
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:

Related Threads on Cardinality Problem: Prove |A| < |N|

  • Last Post
Replies
4
Views
10K
Replies
19
Views
520
  • Last Post
Replies
6
Views
795
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
14
Views
7K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
13
Views
3K
Top