# Cardinal Exponentation

• Dec 30th 2012, 10:22 AM
MachinePL1993
Cardinal Exponentation
Hello,

How come the cardinality of set $\displaystyle A^{B}$ can be presented as $\displaystyle |A|^{|B|}$,wre $\displaystyle |X|$ denotes the cardinality of set$\displaystyle X$? How can it be justified?
• Dec 30th 2012, 11:16 AM
Plato
Re: Cardinal Exponentation
Quote:

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

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

If both $\displaystyle A~\&~B$ are finite sets, where $\displaystyle \|A\|=m~\&~\|B\|=n$ then any function $\displaystyle f:A\to B$
is just $\displaystyle f\subseteq A\times B$ having the properties:
$\displaystyle \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 $\displaystyle f$ has exactly $\displaystyle m$ distinct pairs.
Each of those pairs has $\displaystyle n$ possible second terms.
Thus there are $\displaystyle n^m$ or $\displaystyle \|B\|^{\|A\|}$ possible functions from $\displaystyle A\to B.$
• Dec 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 $\displaystyle f:\mathbb{N} \to \mathbb{N}$?

Can we also do it like this?

$\displaystyle |\mathbb{N}^{\mathbb{N}}|=|\mathbb{N}|^{|\mathbb{N }|}=\aleph_{0}^{\aleph_{0}}$
• Dec 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 $\displaystyle f:\mathbb{N} \to \mathbb{N}$.
Can we also do it like this?
$\displaystyle |\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: $\displaystyle A \sim B\;\& \,M \sim N \Rightarrow A^M \sim B^N$.

Here: $\displaystyle A\sim B$ means set with the same cardinality.
• Dec 30th 2012, 02:29 PM
MachinePL1993
Re: Cardinal Exponentation
How does $\displaystyle A \sim B\;\& \,M \sim N \Rightarrow A^M \sim B^N$ relate to the fact that $\displaystyle |X^{Y}|=|X|^{|Y|}$? I know how to prove this property, but I have no idea how it relates to exponentation.
• Dec 30th 2012, 02:40 PM
Plato
Re: Cardinal Exponentation
Quote:

Originally Posted by MachinePL1993
How does $\displaystyle A \sim B\;\& \,M \sim N \Rightarrow A^M \sim B^N$ relate to the fact that $\displaystyle |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.

• Dec 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 $\displaystyle 2^n$ subsets.
For example, if |A|= 0, then A is the empty set: {}. Its only subset is {} itself so it has $\displaystyle 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 $\displaystyle 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 $\displaystyle 2^3= 8$ subsets.

One can prove that if |A|= n then A has $\displaystyle 2^n$ subsets by induction on n.
That is where the notation comes from.
• Dec 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 $\displaystyle A\sim |A|$ and $\displaystyle B\sim |B|$, then $\displaystyle B^A\sim|B|^{|A|}$, which means that $\displaystyle \left| B^A\right| =|B|^{|A|}$ (because$\displaystyle \left| B^A\right| \sim B^{A}$).
Can somebody please explain to me how come $\displaystyle A\sim |A|$ ? From what I understand for set $\displaystyle 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.