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: Help with proof

  1. Sep 5, 2008 #1
    1. The problem statement, all variables and given/known data

    You have a set A. Let [tex]B^{A}[/tex] be the set of all functions mapping A into the set B={0,1}. Prove the cardinality of[tex]B^{A}[/tex] = the cardinality of the power set of A.

    2. Relevant equations[/b

    3. The attempt at a solution
    I feel about 50% sure about the proof. What do you think? Since A is a set, A has n elements where n is a natural number. Let g be the function mapping A into B s.t {n[tex]\in[/tex]A : n = 0 or n = 1}. So for each n in A there are 2 distinct possibilities (i. e mapping to 0 or 1). Since [tex]B^{A}[/tex] is the set containing all functions of type g, the cardinality of [tex]B^{A}[/tex] = [tex]2^{n}[/tex], which is also known as the cardinality of the power set of A.

    Thanks for helping!
     
  2. jcsd
  3. Sep 5, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    If you want to show the cardinalities are equal the easiest way is to exhibit a 1-1 mapping between subsets of A and members {0,1}^A. Your 'proof' doesn't actually ever say what it is. Can you be more explicit? If you have subset S of A define the mapping. If you have a mapping define the subset.
     
  4. Sep 6, 2008 #3
    I'm not sure how to create a mapping from the power set of A into the interval? Since the problem talks about the functions of A, I'm not sure what the power set of A would look like?
     
  5. Sep 6, 2008 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    It's not an interval. B={0,1} is just the set consisting of the elements 0 and 1. B^A is just the set of all mappings from A->B, i.e. all functions f, such that f(a)=0 or 1 for each a in A. If you have a subset C of A what's the obvious way to define the corresponding function f? If you have a function f what's the corresponding subset C?
     
  6. Sep 7, 2008 #5
    You said there is an obvious function, but it is not obvious to me. Would the function C (the subset of A) going to B be the function of P(A)? I know we have to show there is a 1-1 function from P(A) to B (to the A). I have no idea how.
     
  7. Sep 7, 2008 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Given a subset C, to me the obvious function f is f(a)=0 if a is not in C and f(a)=1 if a is in C. Given a function f define C={a such that f(a)=1}. It's called the characteristic function of the subset.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook