Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cardinality Problem: Prove |A| < |N|

  1. Apr 10, 2010 #1
    Prove cardinality of every finite nonempty set A is less then cardinality of natural number 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!!!
  2. jcsd
  3. Apr 11, 2010 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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!
  4. Apr 11, 2010 #3
    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: Apr 11, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook