Results 1 to 8 of 8
Like Tree4Thanks
  • 1 Post By Plato
  • 1 Post By Plato
  • 1 Post By Plato
  • 1 Post By HallsofIvy

Math Help - Cardinal Exponentation

  1. #1
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Cardinal Exponentation

    Hello,

    How come the cardinality of set A^{B} can be presented as |A|^{|B|},wre |X| denotes the cardinality of set X? How can it be justified?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,793
    Thanks
    1688
    Awards
    1

    Re: Cardinal Exponentation

    Quote Originally Posted by MachinePL1993 View Post
    How come the cardinality of set A^{B} can be presented as |A|^{|B|},wre |X| denotes the cardinality of set X? How can it be justified?

    The justification for using that notation, B^A, for the set of all functions A\to B is a generalization from the finite case.

    If both A~\&~B are finite sets, where \|A\|=m~\&~\|B\|=n then any function f:A\to B
    is just f\subseteq A\times B having the properties:
    \begin{gathered}  1)\quad \left( {\forall a \in A} \right)\left( {\exists b \in B}\right)\left[{(a,b)\in f} \right] \hfill \\    2)\quad (c,d) \in f \wedge (c,e) \in f \Rightarrow d = e \hfill \\\end{gathered} .

    So the function f has exactly m distinct pairs.
    Each of those pairs has n possible second terms.
    Thus there are n^m or \|B\|^{\|A\|} possible functions from A\to B.
    Last edited by Plato; December 30th 2012 at 01:17 PM.
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Re: Cardinal Exponentation

    What if we are dealing with infinite sets?For example how would we denote the cardinality of a set of all functions f:\mathbb{N} \to \mathbb{N}?

    Can we also do it like this?

    |\mathbb{N}^{\mathbb{N}}|=|\mathbb{N}|^{|\mathbb{N  }|}=\aleph_{0}^{\aleph_{0}}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,793
    Thanks
    1688
    Awards
    1

    Re: Cardinal Exponentation

    Quote Originally Posted by MachinePL1993 View Post
    What if we are dealing with infinite sets? How would we denote the cardinality of a set of all functions f:\mathbb{N} \to \mathbb{N}.
    Can we also do it like this?
    |\mathbb{N}^{\mathbb{N}}|=|\mathbb{N}|^{|\mathbb{N  }|}=\aleph^{\aleph}
    That is exactly the point. In fact, that is the whole point.

    This is a standard theorem: A \sim B\;\& \,M \sim N \Rightarrow A^M  \sim B^N .


    Here: A\sim B means set with the same cardinality.
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Re: Cardinal Exponentation

    How does A \sim B\;\& \,M \sim N \Rightarrow A^M  \sim B^N relate to the fact that |X^{Y}|=|X|^{|Y|}? I know how to prove this property, but I have no idea how it relates to exponentation.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,793
    Thanks
    1688
    Awards
    1

    Re: Cardinal Exponentation

    Quote Originally Posted by MachinePL1993 View Post
    How does A \sim B\;\& \,M \sim N \Rightarrow A^M  \sim B^N relate to the fact that |X^{Y}|=|X|^{|Y|}? I know how to prove this property, but I have no idea how it relates to exponentiation.

    Please do not ask for instruction.
    You need to get a good set theory textbook.
    You will find multiple sections on cardinal arithmetic which includes cardinal exponentiation.

    There is no simple (short) answer to your question.
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,978
    Thanks
    1643

    Re: Cardinal Exponentation

    If you know how to prove it, you should at least know what it looks like for finite sets! If |A| has n elements, then the A has a total of 2^n subsets.
    For example, if |A|= 0, then A is the empty set: {}. Its only subset is {} itself so it has 2^0= 1 subset. If |A|= 1, then it has 1 member. Call that member "x". Then A= {x} so the two subsets are {} and {x} itself. If |A|= 2, then, say, A= {1, 2} so that its subsets are {}, {1}, {2}, {1,2} a total of 2^2= 4 subsets. If |A|= 3, we can represent A as {1, 2, 3}. Its subsets are {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, a total of 2^3= 8 subsets.

    One can prove that if |A|= n then A has 2^n subsets by induction on n.
    That is where the notation comes from.
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Re: Cardinal Exponentation

    So I've written to my tutor asking for help and here's what he had to say:
    Since you know that A\sim |A| and B\sim |B|, then B^A\sim|B|^{|A|}, which means that \left| B^A\right| =|B|^{|A|} (because \left| B^A\right| \sim B^{A}).
    Can somebody please explain to me how come A\sim |A| ? From what I understand for set A,|A| is a number/cardinal number that defines the cardinality of the set, but I didn't know that the cardinal number has the same cardinality as the set it corresponds to, which what the tutor wrote to me suggests.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. efficient modular exponentation
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: February 24th 2011, 04:30 PM
  2. regular cardinal. ZFC
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 24th 2010, 04:47 PM
  3. Cardinal Exponentiation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 2nd 2010, 01:09 PM
  4. Set theory/ Cardinal Help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: February 16th 2010, 08:02 PM
  5. Cardinal Exponentials
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 13th 2009, 12:25 PM

Search Tags


/mathhelpforum @mathhelpforum