So this problem was proposed by a professor in a class yesterday. Here’s my solution up for people to read, ponder, speculate, comment, critique, improve, and digress on.
Problem
Given any set , and a bijection , there are functions such that and , the identity function. ## Solution
Definitions, assumptions, and set-outs
We accept the Axiom of Choice and use it freely. We define a function
as follows:
Here for each
, the corresponding
is usually denoted by
. A restriction of a function to a certain
subset
of the domain
is defined as
. In the context of this problem, all the domains
and codomains we consider will be assumed to be non-empty.
Definition (Cycle). A bijection with is called a cycle if there is a bijection such that for all and .
Definition (Iterated composition). For bijection , we define , the identity function on and for each , we define . Moreover for any , we define .
Definition (Orbit). Given a function , and some , the orbit of under is defined by .
Lemma 1. If a function is bijective, then for any , the restriction is also bijective. Proof. First we see that has to be injective, because , hence too . We can also see that surjective right by its definition, since for every , there is such that .
Lemma 2. For any collection of bijections with all pairwise disjoint and all pairwise disjoint, the union function is also bijective.
Proof. First we show that it is injective. Suppose . Clearly if and with then . If , then since is injective, we have . Therefore we have being injective. Now we show that is surjective. Consider any . Then for some . Now since is surjective, there is such that , and hence is surjective too, and therefore bijective.
Lemma 3. (Group theoretic) Given any permutation can be written as a composition of disjoint cyclic permutations. Proof. This proposition is well-known and we accept it without explicit proof here.
Solutions, step by step
Finite set case
First we show that the proposition holds for any finite set . So without loss of generality, we take with some . So what we do is that we show this for all with any bijection . For , there is nothing much to be done, and . So for the decomposition, is the only choice. Suppose we have such a decomposition for any bijection of size upto . Now consider . Then if there is any cycle , with of course , then being a bijection, we can write as the union of two distinct bijections of size smaller than (by Lemma 1), which therefore can be decomposed (by induction hypothesis) into and , with all four functions satisfying the requirements, i.e. all being identities on respective sets. So now by Lemma 2 we can have the two required functions being and . The only case left is when there is no such smaller cycle in the function. By Lemma 3 we can see that this is only possible if is itself a cycle. This can be broken down into two very similar but slightly different cases, namely for being even, and odd, respectively. Case 1. If is even, say , then we construct as follows: It should be clear enough that these two indeed follow the conditions as required. Case 2. If is odd, say , then the construction is as follows: Again it should be clear enough that these satisfy both requirements. And with this we have finished the induction, and therefore the proof of the proposition for the case of a finite set.
Countably infinite case
Now we show that the proposition holds for a very special countably infinite case. The more general cases will be dealt with in the final solution. So the case here is when is of the form , indexed by , with all distinct, where for any , . This is indeed an orbit of the function where we not only consider the sequence of composing on , but also the sequence “backtracking” from . The instances where anywhere in the composition sequence or the “backtracking” sequence there is a loop or cycle, will not be considered in this case and will instead be dealt with only in the final general case. So with the outset aside, the construction of the functions is as follows: This too is left to the consideration of the reader to see why this construction satisfies the requirements of the proposition.
The final solution
Given the set and a bijection on it, we consider the following equivalence relation first. We define by (or alternatively ) if and only if there is such that . Now we consider the set of all equivalence classes (the set of all distinct orbits of ) such that, for all with , we have , and that (since the set is just a partition of ), and that for any , we have .
So now we have a closer look at each . Notice that , and that it is of one of two forms. The first is when is a finite orbit, and for some , where , , and so on, with . Notice that this also includes the case of the fixed points of , where we do not go beyond . The second is when is countably infinite, in particular, we index it with the integers, as . Here for any , . It is easy to see that since is bijective, if we start from any “first” element, we will always have more equivalent elements (of ) by taking repeated inverses. We claim that these two are the only possibilities, namely that any such infinite can always be indexed by the integers, and moreover that cannot be uncountable. Both of these claims are easy to show, since, by choosing any , if , then there is such that , so we can uniquely assign the index to that , since is injective. This also removes the possibility of being uncountable because we have demonstrated a surjection . So therefore we have shown, rather argued, that any equivalence class is countable.
Now consider the following set of restrictions of the function Each is bijective, as can be easily checked by the definition of each class . And since each distinct is disjoint, we can see (by the way we have defined a function as a set of pairs) that Now, to finish off the problem, notice that we have already solved it for bijections over any finite set and any countably infinite acyclic chain in the previous two cases. So using those results, we see that for each , there are such that and . So now we define the final two required functions over as Notice that these functions do really follow these properties, as can be easily checked.
Therefore, given any , and bijection , we can decompose into two self-inverse bijections , i.e. with such that .