\(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}\).
Note by
Raj Magesh
3 years, 9 months ago
Easy Math Editor
*italics*or_italics_**bold**or__bold__paragraph 1
paragraph 2
[example link](https://brilliant.org)> This is a quote# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"2 \times 32^{34}a_{i-1}\frac{2}{3}\sqrt{2}\sum_{i=1}^3\sin \theta\boxed{123}Comments
Sort by:
Top NewestSubbed 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