\(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:
Top NewestSubbed for any good solutions other than simple inequality. =3= – Samuraiwarm Tsunayoshi · 3 years ago
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 – Niven Achenjang · 3 years ago
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... :) – Raj Magesh · 3 years ago
Log in to reply