# Cardinal Exponentation

• December 30th 2012, 10:22 AM
MachinePL1993
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?
• December 30th 2012, 11:16 AM
Plato
Re: Cardinal Exponentation
Quote:

Originally Posted by MachinePL1993
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.$
• December 30th 2012, 02:11 PM
MachinePL1993
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}}$
• December 30th 2012, 02:21 PM
Plato
Re: Cardinal Exponentation
Quote:

Originally Posted by MachinePL1993
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.
• December 30th 2012, 02:29 PM
MachinePL1993
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.
• December 30th 2012, 02:40 PM
Plato
Re: Cardinal Exponentation
Quote:

Originally Posted by MachinePL1993
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.

You need to get a good set theory textbook.
You will find multiple sections on cardinal arithmetic which includes cardinal exponentiation.

• December 30th 2012, 03:24 PM
HallsofIvy
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.
• December 30th 2012, 04:19 PM
MachinePL1993
Re: Cardinal Exponentation
So I've written to my tutor asking for help and here's what he had to say:
Quote:

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.