\(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**

Consider two non-empty sets \(A\) and \(B\) containing \(m\) and \(n\) elements respectively.

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.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}}\).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\).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}\).

## Comments

Sort by:

TopNewestSubbed for any good solutions other than simple inequality. =3=

Log in to reply

\( { 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

Log in to reply

Well, of course you're right algebraically, but that's not the curious proof I saw. I'll post the solution soon, maybe in two more days... :)

Log in to reply