Set Theory Proof of $m^n < 2^{mn}$ for $m,n \in Z^{+}$

$n^m<2^{mn}$ for $m,n \in Z^{+}$

I chanced upon a rather interesting proof of this while studying sets, relations and functions in math class. Try to see if you can find it!

To get you started, consider two non-empty sets $A$ and $B$ containing $m$ and $n$ elements respectively. I'll post the solution in a few days...

SOLUTION

1. Consider two non-empty sets $A$ and $B$ containing $m$ and $n$ elements respectively.

2. The CARTESIAN PRODUCT of $A$ and $B$, given by $A \times B = \{(a,b):a \in A, b \in B\}$, is the set that contains all possible ordered pairs of the form $(a,b)$. Obviously, this set contains $mn$ elements.

3. A RELATION between two sets $A$ and $B$ is defined as a subset of their Cartesian product. Then, how many relations are possible between $A$ and $B$? This is the number of possible subsets of the Cartesian product, or, in other words, the number of elements in the POWER SET of $A \times B$. How do we find the number of possible subsets of $A \times B$? To choose a subset from a set, what do we do? We either choose an element to be part of the subset or not, i.e. we make a choice between 2 alternatives. Since there are $mn$ elements in the set, and we need to make a choice for each element, the number of subsets possible is given by $\boxed{2^{mn}}$.

4. A FUNCTION between two sets $A$ and $B$ is a subset of their Cartesian product too (just like a relation) but with an additional constraint: all elements of $A$ should have exactly one image in $B$. Then, how many functions are possible between $A$ and $B$? Since each element in $A$ has $n$ possible choices of an image in $B$ and there are $m$ elements in $A$, there are a total of $\boxed{n^{m}}$ possible functions from $A$ to $B$.

5. The final step is just logic: if a function is a relation with a constraint, there have to be fewer possible functions than relations.

Hence, $n^m < 2^{mn}$.