Cardinal arithmetic exponentiation

Question

I am reading a book on set theory and the following theorem has been left as an exercise to the reader.

Let $a,b,c$ be cardinals with $a,b>0$. If $b\leq c$ then $a^b \leq a^c$.

How would we go about proving this with just the definitions and mappings. I have the following work:

Let $A,B,C$ be sets and $a=|A|,b=|B|,c=|C|$. Then $f$ is an injective function from $B$ to $C$. I think we have to then define another function between the two specified sets and prove that it is injective. Any tips on how to proceed?

Answer 1

This is, in fact, not true. Consider $a = b = 0$ and $c = 1$. Then $b \leq c$, but $1 = a^b > 0 = a^c$ (using the definitions of cardinal exponentiation to calculate $0^0$).

To solve this, let $a = |A|$, $b = |B|$, $c = |C|$ and suppose we have some element $k \in A$. WLOG, take $B \subseteq C$. We see that $a^b = |\{f : B \to A\}|$ and $a^c = |\{g | C \to A\}|$. Then given $f : B \to A$, define $h_f : C \to A$ by $h_f(x) = f(x)$ if $x \in B$ and $k$ otherwise. Then we see that $h$ is a 1-1 function from $\{f : B \to A\}$ to $\{g : C \to A\}$, since $h_f |_B = f$ and thus if $h_f = h_{f'}$, we have $f = h_f|_B = h_g|_B = g$.

Answer 2

Given sets $X$, $Y$, and $Z$, with $Z\neq\varnothing$, and a function $g\colon Y\to X$, we naturally obtain a function $Z^X\to Z^Y$ by “precomposition”: define $g_*\colon Z^X\to Z^Y$ by $g_*(f) = f\circ g$.]

(You also get a function $g^*\colon X^Z\to Y^Z$, by $g^*(f) = g\circ f$ which has dual properties, but that function isn’t going to be useful here…)

Note that this makes sense: $f$ is a function $f\colon X\to Z$, and $g$ is a function $Y\to X$, so $g_*(f)$ is a function $Y\to Z$, that is, an element of $Z^Y$.

To prove the result you want with the assumption that $a,b\gt 0$, show that:

• If $g$ is surjective, then prove that $g_*$ is injective; this is a property of surjective functions.

• If there is an injection $X\to Y$, and $X\neq\varnothing$, then there is a surjection $Y\to X$ (and you do not even need to invoke the Axiom of Choice for that).