×

# 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}$$.

Note by Raj Magesh
2 years, 3 months ago

Sort by:

Subbed for any good solutions other than simple inequality. =3= · 2 years, 3 months ago

$${ m }^{ n }\quad ?{ \quad 2 }^{ mn }\\ { m }^{ n }\quad ?\quad { ({ 2 }^{ m }) }^{ n }\\ m\quad <\quad { 2 }^{ m }\\ { m }^{ n }\quad <{ \quad 2 }^{ mn }$$

*I use the ? to show that the relation is not yet known · 2 years, 3 months ago