Problem:
Let , and let be the set consisting of all nonempty subsets of . The function is "garish" if there do not exist sets such that is a proper subset of and . Determine, with proof, how many garish functions exist.
Problem:
Let , and let be the set consisting of all nonempty subsets of . The function is "garish" if there do not exist sets such that is a proper subset of and . Determine, with proof, how many garish functions exist.
Solution:
There are such functions. If is any bijective map from to itself (i.e. a permutation of ), then the function defined by (here is the cardinality of set ) is garish. To see this, just note that if is a proper subset of , then , so . There are possible choices of the map , and all of them give different maps (this follows from the fact that every element of is the cardinality of some set in ), so we get garish functions this way. We now wish to show that every garish function is of this form.
Let be garish; our crucial observation is the following: If are the elements of in some order, we shall say that this ordering "produces" a sequence of values . These values are all different, since, of any two of these sets, one is properly contained in the other. But there are exactly possible values for , namely , so any produced sequence consists of exactly these in some order.
Now choose any integer , . We will show that has the same value on all -element sets. We can assume (otherwise there is only one -element set). First consider any two sets that differ by at most one element; let them be and . Assume . Let the remaining elements of (if there are any) be in any order. Consider the sequences produced from the two orderings and . From the above, each produced sequence contains every element of exactly once. But these two sequences are identical except that the first has where the second has , so we conclude that these two values of are identical. Also, if , then the two values are equal (trivially).
This shows that has the same value on two -element sets differing by element. Now if and are any two sets in , we have (applying this repeatedly) that
So is constant over all -element sets. Thus we can define the function by letting be the value of on any -element set, and uniquely determines since for all . Moreover, if for some , then letting , we have , a contradiction since is a proper subset of . Thus, is one-one; but since it maps the finite set to itself, it is actually bijective. Thus all garish functions are indeed in the form claimed above.
Alternate Solution:
We observe that garish functions can be constructed, precisely as described in the first solution, and we wish to show that all garish functions are of this form. We use induction on . In the base case , there is only one possible function, given by , and it is garish. Now consider any , and suppose the statement is true for . If is a garish function, let for each . Then all are different: if for some , then would not be garish, since is a proper subset of . Thus, the elements equal in some order. Partition into three subsets: let consist of the nonempty subsets of , let , and let be the rest of (the proper subsets of containing ). We claim that, if , then . This follows from the induction hypothesis. Formally, we first observe that for since . Then, if we define by (and this is well-defined since are distinct), then the composite is a garish function from to , so, by the induction hypothesis, it takes the same value on all -element sets; since is injective, takes the same value on all -element sets, as claimed. Also, if (so ) then , by assumption.
Now consider any set ; we have . We claim that ; this will be shown by strong downward induction on the cardinality . If , then and . On the other hand, the set has elements and is contained in ; it certainly has subsets of respective cardinalities , all of which lie in ; thus, from the previous paragraph. From this, garishness gives and , so .
The induction step is similar: suppose we have proven that, for all with , , and we wish to move to the case . By successively adding elements to , we can construct sets of respective cardinalities , which all lie in , except for . Also, if , then has elements and lies in ; repeatedly removing elements, we get sets of respective sizes . So we have for by the induction hypothesis, and for because these sets lie in . But each of the either contains or is contained in , so cannot equal any of these ; hence, it must equal , completing the induction step.
At this point, we have shown that for each , and one sees as in the previous solution that for some bijective function , as needed.