Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm having trouble understanding the definition of cardinal exponentiation.

Let's start with the definitions / claims I've been given:

For any finite sets $A,B$, such that if $|A|=a$ and $|B|=b\neq 0$ then the number of functions from $A$ to $B$ is $b^a$. ( I'm guessing this is only used when both sets are finite ).

For any sets $A,B$, $B^A$ is the set of functions from $A$ to $B$.

For every set $A$, $|P(A)|=|\left \{ 0,1 \right \}^A|$

Now for the definition and why I don't understand it:

Let $a,b$ be cardinal numbers. Let $A,B$ be sets such that $|A|=a, |B|=b$. Then $|B^A|=b^a$.

How analagous to normal exponentiation is this and where does in differ when we introduce cardinals like $\aleph_0$ or $C$?

Is $2^2=4$ and is $\frak c^2=c\cdot c=c\times c$?

share|improve this question
    
It is not only when $A$ and $B$ are finite that $|B^A| = |B|^{|A|}$. That's the definition of exponentiation of cardinal numbers. –  Michael Hardy Dec 7 '11 at 23:53
add comment

2 Answers 2

up vote 4 down vote accepted

When you say "normal exponentiation", you can think about natural numbers, real numbers, complex numbers, and so on.

Assuming that you mean natural numbers, we want a coherent behavior from infinite sets to the laws we have figured out on finite sets. In particular, we want $|A^B| = |A|^{|B|}$.

First let us review the basic laws of cardinal arithmetics:

  1. $|A|+|B| = |\{0\}\times A\cup\{1\}\times B|$, that is addition of cardinals is the disjoint union of representatives.

  2. $|A|\cdot|B| = |A\times B|$, that is multiplication is cardinality of the product.

  3. $|A|^{|B|} = |A^B|$. This is the nugget of gold in this question, and we'll discuss this through the rest of this answer.

Of course we want these actions to behave in coherence with finitary actions. Multiplication is distributive over addition, exponentiation over multiplication, and so on and so forth. I will not get into that here.

Why do we want that? Because if we denote $n=\{0,\ldots,n-1\}$ for every $n\in\mathbb N$, then $k^n$ is just the amount of functions from any set of $n$ elements to any set of $k$ elements. This means that if $|A|=|C|$ and $|B|=|D|$ then we would like that $|A^B|=|C^D|$.

In other words, the cardinality is an equivalence relation and we want all the cardinal arithmetic to be independent of the choice of representatives (at least when finitely many sets are involved).

However, infinite sets - and in particular $\aleph$ numbers - behave much differently than finite sets. For example $|\{0,\ldots,n-1\}\cup\{n\}|>n$ while $|\mathbb N\cup\{-1\}|=|\mathbb N|$. Even more so, $|\mathbb N\times\mathbb N|=|\mathbb N|$. This means that some things, while working "the same" are going to work differently.

For your last question, we can notice that $\{f\colon\{1,2\}\to X\}$ would simply correspond to functions choosing two elements each time. This is just specifying ordered pairs in a very canonical way - $f(1)$ is the left coordinate and $f(2)$ is the right one.

This means that $A^{\{0,\ldots,n-1\}}$ can be thought of as the set of $n$-tuples from $A$, or $\underbrace{A\times\ldots\times A}_{n\text{ times}}$.

The laws of cardinal arithmetic tells us that $|A|\cdot|B| = |A\times B|$, so we have that $|A^{\{0,\ldots,n-1\}}|=|\underbrace{A\times\ldots\times A}_{n\text{ times}}|=\underbrace{|A|\cdot\ldots\cdot|A|}_{n\text{ times}}=|A|^n$. Of course, since we deal with infinite sets we are no longer guaranteed an actual increase of cardinality, but the laws work the same.

What if $|A|$ and $|B|$ are infinite? Well, we already have the laws for how we wanted exponentiation to behave, now we just need to apply them. We can think of $A^B$ as $B$-tuples of $A$, that is every element of $B$ is an index of a sequence from $A$. These sequences need not be finite, nor countable - not even well ordered.

And indeed, we see that if $A=\{0,1\}$ then the rule $|P(B)| = |\{0,1\}^B|=|\{0,1\}|^{|B|}=2^{|B|}$ holds as we wanted it to hold.

share|improve this answer
    
As always, nice answer. You should come teach at OpenU :-). I would just edit for clarity that: $|P(B)| = |\{0,1\}^B|=|\{0,1\}|^{|B|}$ –  Robert S. Barnes Dec 8 '11 at 8:44
    
@Robert: How about you come to study at BGU instead? :-) –  Asaf Karagila Dec 8 '11 at 8:48
add comment

You can demonstrate quite easily that given natural numbers $m,n$ that the cardinal exponent $n^m$ agrees with the usual arithmetic one (with the slight quibble that the definition of cardinal exponentiation gives $0^0 = 1$, which is, at times, left undefined in ordinary arithmetic). The basic idea is that if $M = \{ a_1, \ldots , a_m \}$ and $|N|=n$, then in constructing a function $f: M \to N$ we have $|N|=n$ choices for $f(a_1)$, and $|N|=n$ choices for $f(a_2)$, etc. So for each of the $m$ elements of $M$ we have $n$ choices for the corresponding value of $f$ at that element, and each distinct sequence of choices will yield a distinct function $M \to N$. Finally, in ordinary arithmetic $n \cdots n$ ($m$ times) is $n^m$.

In convincing yourself that the cardinal exponent $n^0$ is $1$ for a natural number $n$, note that according to the formal set-theoretic definition, $\emptyset$ is a function with domain $\emptyset$, and it is the only such function. In convincing yourself that the cardinal exponent $0^m$ is $0$ for a natural number $m \geq 1$, note that no function with a non-empty domain can have range $\emptyset$.

Not only that, but some of the familiar rules for ordinary exponentiation go through for cardinal exponentiation. For instance:

  1. $\kappa ^0 = 1$.
  2. $0^\mu = 0$ for $\mu > 0$.
  3. $\kappa ^{\mu + \nu} = \kappa ^\mu \kappa ^\nu$;
  4. $(\kappa ^\mu )^\nu = \kappa ^{\mu \nu}$; and
  5. $(\kappa \lambda)^\mu = \kappa^\mu \lambda^\mu$.

(Note that we cannot apply to Binomial Theorem to calculate $( \kappa + \lambda )^\mu$.)

share|improve this answer
    
+1 for another nice answer! : ) –  Matt N. Dec 7 '11 at 15:12
1  
+1 nice. So basically it's how many different ways can I choose m non-unique elements from a set of n elements. So $B^A=BxBx...B$ which is the $|A|=a$ times Cartesian product of $B$. Or more clearly maybe it's $|B^{A}|=|\left \{(b_1,b_2,...,b_{|A|})|b_1,...,b_{|A|} \in B^{A}\right \}|=|B|^{|A|}$ –  Robert S. Barnes Dec 8 '11 at 8:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.