1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Bijection Cardinality

  1. Dec 5, 2013 #1
    1. The problem statement, all variables and given/known data

    Let K be any set and let F* be the set of all functions with domain K. Prove that card K < card F*.

    3. The attempt at a solution

    I am first able to show that card K <= card F*, by creating an invertible function from K into F*.
    let f: K -> F*
    be defined so that if k is an element of K, then f(k) = {(i,k): i is an element of K}.
    Basically we create a function with function value of k in all points.

    But this only shows <= , I am not sure of to prove <. Then I think I must assume that there is a bijection, but that this leads to a contradiction. How do I do that?
  2. jcsd
  3. Dec 5, 2013 #2


    User Avatar
    Homework Helper

    You don't need to use a proof by contradiction.

    Show that there exists a bijection from the power set of [itex]K[/itex] to the set of functions from [itex]K[/itex] to [itex]\{0,1\}[/itex]. This set is a proper subset of [itex]F^{*}[/itex], since the codomain of a function in [itex]F^{*}[/itex] can be any non-empty set.

    Why does this imply that there is no bijection from [itex]K[/itex] to [itex]F^{*}[/itex]?
  4. Dec 5, 2013 #3

    Ok, I'll try, I was not able to find an bijection from P(K) to the functions, but an injection, but I think it still works.

    Lemma: card (P(K)) <= card L
    L is the set of functions with codomain {0,1}, and domain K.
    Define F2: P(K)-> L
    F2(K') = {(i,j) : i is an element of K: j = 1 if i is an element of K', else j = 0}
    K' is a subset of K.
    F2 gives a function which has domain K, and this new function is 1 only if it is evaluated in K'.
    it is must be invertible because if F2(K')=F2(K''), then K'=K''.

    Now we have that:

    Card K < Card(P(K)) <= card(L) <= card(F*), since L is a subset of F*.
    We can't have a bijection from K to F*, because then we could create an injection from P(K) to K, which is impossible.

    Out of curiosity, how would you make the F2 function also surjective?

    Haha, I see that the function I defined is actually surjective. Thanks for the help, it was a very smart trick!
    Last edited: Dec 5, 2013
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted