A finite set of positive integers is called cardinal if contains the integer , where denotes the number of distinct elements in . Let be a function from the set of positive integers to itself, such that for any cardinal set , the set is also cardinal. Here denotes the set of all integers that can be expressed as for some in . Find all possible values of .
Note: As an example, is a cardinal set because it has exactly 3 distinct elements, and the set contains 3.
Solutions — 2
Solution 1
Solution 1. The possible values are 1, 2, and 2024.
Construction. The function for all works. Also, for all and , works. Finally, for all works as well.
It remains to show these are the only possible values for .
Proof. Denote . The cardinal set gives . Consider the following two cases:
* is unbounded. Fix any , with . Pick distinct integers such that and are all pairwise distinct, for . Then is a cardinal set. Then is a cardinal set with distinct elements, so lies in this set, hence . This gives the identity function.
* is bounded. Suppose for all and some integer .
Claim. For any integer satisfying , if there are infinitely many integers such that , then .
Proof. Let be one of the integers with . Consider other integers , such that for , and are all pairwise distinct. Then is a cardinal set, so the image set, which consists of the singleton is cardinal, hence .
So for every , there are only finitely many integers such that . Thus, there exists an integer such that for all , . Now for every , consider the cardinal set . Then the image set consists of , which can be cardinal only when or .
By the above reasoning, can only be 1, 2, or 2024, each of which occurs as an example.
Solution 2
Solution 2. We present a second proof of the fact that the proposed values are the only possibilities. Considering the singleton cardinal set , we see that . The cardinal set gets mapped to , so must be 2 or 1.
Case 1. Suppose . Now is a cardinal set, and therefore so is . This means is 1 or 2.
Case 2. Suppose . The cardinal set shows that , but the cardinal set proves cannot be 2. Thus there are two sub-cases:
2.1. . Then the set is cardinal, hence so is , implying, as before, .
2.2. . In this case, we show via induction that for all .
The base cases are already known. Now consider , and assume for all . Consider the cardinal which implies .
However, consider the -element cardinal set . For its image to be cardinal cannot equal any number in ; else its cardinality would be , which isn't in the set. So .
Finally, consider the -element set . If , its image would only have elements, and thus would not be cardinal. So we conclude that and the induction is complete. In particular, .