Let , and be the set of all subsets of . Determine the number of functions satisfying the condition for all .
Solution
The answer is .
We first observe that the minimum element of is the minimum of the minimum elements of and for all finite sets and of integers.
Let the value of be . Then by the given property of we have for all . Note that there are different ways to determine the values of for all sets in of size . We will prove that the values of for the remaining sets are uniquely determined.
We apply induction on to prove that
for all .
For , it is trivial and the case for results from the condition on .
Using the induction hypothesis and the observation above we can conclude that the claim is true for as well.
On the other hand, by (*) and the observation above it can be easily verified that the condition on is satisfied for all . Therefore, as we obtain that there are such functions.