Results 1 to 11 of 11

Math Help - set of functions

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    170

    set of functions

    Given two sets  A and  B , let  A^{B} be the set of all functions  f: B \to A . Prove that for any set  A ,  \text{card}(\bar{2}^{A}) = \text{card}(\mathcal{P}(A)) .

    Here,  \bar{2} = \{1,2\} . In other words, we want to prove that  \text{card}(\bar{2}^{A}) = 2^{n} ?

    So  \bar{2}^{A} is the set of all functions  f: A \to \bar{2} . It does not say anything about the sets being countable/uncountable, or finite/infinite. Since any element  x \in A maps to either of two values, then using the characteristic function, the total number of functions is  2^{n} if  A is countably infinite or finite. But if  A is uncountable/infinite, then  \text{card}(\bar{2}^{A}) = 2^{\aleph_{1}} ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,383
    Thanks
    1474
    Awards
    1
    Allow me to point out that it is usual to define \overline 2  = \left\{ {0,1} \right\}.
    This proof also uses the idea of characteristic function: B \in P(A),\;\chi _B (x) = \left\{ {\begin{array}{lr}   {0,} & {x \notin B}  \\   {1,} & {x \in B}  \\<br />
\end{array}} \right.
    Note that \chi _B \in \overline 2 ^A .
    Now define \Psi :P(A) \mapsto \overline 2 ^A ,\;\left[ {\forall B \in P(A)\,,\,\Psi (B) = \chi _B } \right].

    Now it up to you to show that \Psi is a bijection.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie Catherine Morland's Avatar
    Joined
    Jul 2008
    Posts
    17
    Quote Originally Posted by particlejohn View Post
    Here,  \bar{2} = \{1,2\} . In other words, we want to prove that  \text{card}(\bar{2}^{A}) = 2^{n} ?

    So  \bar{2}^{A} is the set of all functions  f: A \to \bar{2} . It does not say anything about the sets being countable/uncountable, or finite/infinite.
    Well, if you're going to prove 2^n, then shouldn't A be a finite set with n elements?

    It's a matter of combinatorics. Any element in A can be mapped to 0 or 1, so there are exactly two choices for it. Since there are n elements in A, there are 2^n ways of mapping A to {0,1}; hence there are 2^n functions from A to {0,1}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2008
    Posts
    170
    That was the ambiguity that I pointed out.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,383
    Thanks
    1474
    Awards
    1
    Quote Originally Posted by Catherine Morland View Post
    Well, if you're going to prove 2^n, then shouldn't A be a finite set with n elements?
    Quote Originally Posted by particlejohn View Post
    That was the ambiguity that I pointed out.
    There is no ambiguity.
    The outline of a proof that I gave you shows that for any set A we have a bijection P(A) \leftrightarrow \overline 2 ^A .
    This works for any set, the cardinality does not matter.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2008
    Posts
    170
    Quote Originally Posted by Plato View Post
    Allow me to point out that it is usual to define \overline 2  = \left\{ {0,1} \right\}.
    This proof also uses the idea of characteristic function: B \in P(A),\;\chi _B (x) = \left\{ {\begin{array}{lr}   {0,} & {x \notin B}  \\   {1,} & {x \in B}  \\<br />
\end{array}} \right.
    Note that \chi _B \in \overline 2 ^A .
    Now define \Psi :P(A) \mapsto \overline 2 ^A ,\;\left[ {\forall B \in P(A)\,,\,\Psi (B) = \chi _B } \right].

    Now it up to you to show that \Psi is a bijection.
    We want to show that  \Psi(B) = \chi_B is a bijection. Suppose that  C \in \mathcal{P}(A) . Then  \Psi(B) = \Psi(C) = \chi_{B} implies that  B = C for injectivity. For all  y \in \bar{2}^{A} ,  \Psi(B) = y for surjectivity.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,383
    Thanks
    1474
    Awards
    1
    Quote Originally Posted by particlejohn View Post
    We want to show that  \Psi(B) = \chi_B is a bijection. Suppose that  C \in \mathcal{P}(A) . Then  \Psi(B) = \Psi(C) = \chi_{B} implies that  B = C for injectivity. For all  y \in \bar{2}^{A} ,  \Psi(B) = y for surjectivity.
    If  y \in \bar{2}^{A} , let D = \left\{ {a \in A:y(a) = 1} \right\} then {\Psi (D) = \chi _D  = y}.
    Do you see why?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jun 2008
    Posts
    170
    Quote Originally Posted by Plato View Post
    If  y \in \bar{2}^{A} , let D = \left\{ {a \in A:y(a) = 1} \right\} then {\Psi (D) = \chi _D  = y}.
    Do you see why?
     D is the set of all elements that belong to  A (e.g. value is  1 ). Hence  \Psi(D) = \chi_{D} = y .
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by particlejohn View Post
    Here,  \bar{2} = \{1,2\} .
    This is a little bit off topic but you might it interesting we define 2 to be \{ 0,1\} where 0=\emptyset and 1=\{0\}. This is what Plato said. Thus, there is no need to write \bar 2 = \{ 0,1\} because in fact 2=\{0,1\}.

    This might look strange but this is how we define natural numbers. We define 0 = \emptyset. We define 1=\{ 0\} = \{ \emptyset \}. We define 2=\{0,1\} = \{ \emptyset, \{ \emptyset\} \}. We define 3=\{0,1,2\}=\{ \emptyset, \{ \emptyset\}, \{\emptyset, \{\emptyset\} \} \}. We would like to say natural numbers are repetitions of this form. However, this is not a formal enough statement. So this is what we do. Let x be a set and define x+1 = x\cup \{ x\}. Thus is follows 0 = \emptyset, 1 = 0+1,2=1+1,3=2+1. We cannot say "and so on" because that is not a formal term. To do this we define an inductive set to be a set I such that 0\in I and if x\in I then x+1\in I. One of the axioms we place into Set Theory is called Axiom of Infinity which says "an inductive set exists", the reason we do this is because using the simpler axioms we cannot construct inductive sets and we would like to make set theory more interesting by allowing infinite sets. Finally, since there is an inductive set I define \mathbb{N} = \{ x\in I | x \mbox{ is in every inductive set } \}. This set \mathbb{N} are called the natural numbers and this is a purely formal construction of the naturals.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Jun 2008
    Posts
    170
    Quote Originally Posted by ThePerfectHacker View Post
    This is a little bit off topic but you might it interesting we define 2 to be \{ 0,1\} where 0=\emptyset and 1=\{0\}. This is what Plato said. Thus, there is no need to write \bar 2 = \{ 0,1\} because in fact 2=\{0,1\}.

    This might look strange but this is how we define natural numbers. We define 0 = \emptyset. We define 1=\{ 0\} = \{ \emptyset \}. We define 2=\{0,1\} = \{ \emptyset, \{ \emptyset\} \}. We define 3=\{0,1,2\}=\{ \emptyset, \{ \emptyset\}, \{\emptyset, \{\emptyset\} \} \}. We would like to say natural numbers are repetitions of this form. However, this is not a formal enough statement. So this is what we do. Let x be a set and define x+1 = x\cup \{ x\}. Thus is follows 0 = \emptyset, 1 = 0+1,2=1+1,3=2+1. We cannot say "and so on" because that is not a formal term. To do this we define an inductive set to be a set I such that 0\in I and if x\in I then x+1\in I. One of the axioms we place into Set Theory is called Axiom of Infinity which says "an inductive set exists", the reason we do this is because using the simpler axioms we cannot construct inductive sets and we would like to make set theory more interesting by allowing infinite sets. Finally, since there is an inductive set I define \mathbb{N} = \{ x\in I | x \mbox{ is in every inductive set } \}. This set \mathbb{N} are called the natural numbers and this is a purely formal construction of the naturals.



    And that is precisely why we can't have half integers contained in  \bold{N} , because of the principle of induction?

    Moreover, the natural numbers  \bold{N} never repeat (e.g. we cannot have  1,2,3,3,4, \ldots )? What is the difference between formal difference and actual difference (e.g. we have  a // b and  a--b )?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by particlejohn View Post
    And that is precisely why we can't have half integers contained in  \bold{N} , because of the principle of induction?
    I do not know what you mean by this.

    Moreover, the natural numbers  \bold{N} never repeat (e.g. we cannot have  1,2,3,3,4, \ldots )? What is the difference between formal difference and actual difference (e.g. we have  a // b and  a--b )?
    I do not know what you mean by this. Do define a-b we find need to define what it means a+b for arbitrary integers.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: April 15th 2010, 05:50 PM
  2. Replies: 3
    Last Post: February 23rd 2010, 04:54 PM
  3. Replies: 11
    Last Post: November 15th 2009, 11:22 AM
  4. Replies: 7
    Last Post: August 12th 2009, 04:41 PM
  5. Replies: 1
    Last Post: April 15th 2008, 09:00 AM

Search Tags


/mathhelpforum @mathhelpforum