1. Not finding help here? Sign up for a free 30min 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!

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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Help with proof
  1. Help with a proof. (Replies: 10)

  2. Proofs help (Replies: 7)

  3. Help with a proof! (Replies: 8)

  4. Help with a Proof (Replies: 1)

  5. Proof help! (Replies: 3)

Loading...