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?

Printable View

- Dec 30th 2012, 10:22 AMMachinePL1993Cardinal 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 AMPlatoRe: Cardinal Exponentation

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 PMMachinePL1993Re: 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 PMPlatoRe: Cardinal Exponentation
- Dec 30th 2012, 02:29 PMMachinePL1993Re: 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 PMPlatoRe: Cardinal Exponentation
- Dec 30th 2012, 03:24 PMHallsofIvyRe: 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 PMMachinePL1993Re: 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}$).