Cardinality Problem: Prove |A| < |N|

[cxc001]

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!

 

[Hurkyl]

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!

 

[cxc001]

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!]