a1267ab wrote: Let $f:\mathbb{R}\to\mathbb{R}$ be a bijective function. Does there always exist an infinite number of functions $g:\mathbb{R}\to\mathbb{R}$ such that $f(g(x))=g(f(x))$ for all $x\in\mathbb{R}$? Here is a rather complex proof. I hope that somebody will find a simpler one. 1) If $\not\exists n$ such that $f^{[n]}(x)=x$ Then consider for $g(x)$ : $f(x),f^{[2]}(x), f^{[3]}(x), ...,f^{[k]}(x), ...$ Q.E.D. 2) If $\exists n\in\mathbb Z_{>0}$ such that $f^{[n]}(x)=x$ $\forall x$ For any $x\in\mathbb R$, let $d(x)\in\mathbb Z_{>0}$ the smallest positive integer such that $f^{[d(x)]}(x)=x$ $d(x)|n$ and so $|d(\mathbb R)|$ is finite. So $\exists k\in\mathbb Z_{>0}$ such that $|A=d^{-1}(\{k\})|$ is infinite Let us then consider relation $\sim$ over $A$ defined as $x\sim y$ $\iff$ $\exists i\in\{1,2,...,k\}$ such that $f^{[i]}(x)=y$ This is an equivalence relation over $A$ with infinitely many equivalence classes Let then $r(x)$ from $A\to A$ any choice function which associates to a real $x\in A$ a representant (unique per class) of its equivalence class Let then $i(x)$ from $A\to\{1,2,3,...,k\}$ the function such that $x=f^{[i(x)]}(r(x))$ Since we have infinitely many equivalence classes, we can split $B=r(A)$ in two infinite equinumerous subsets $B_1$ and $B_2$ and choose a bijection $h(x)$ from $B_1\to B_2$ Let then define $g(x)$ as : $\forall x\notin A$ : $g(x)=x$ $\forall x\in A$ : - If $r(x)\in B_1$ : $g(x)=f^{[i(x)]}(h(r(x)))$ - If $r(x)\in B_2$ : $g(x)=f^{[i(x)]}(h^{-1}(r(x)))$ This allows us to build infinitely many such $g(x)$ And it is easy to see that $g(g(x))=f(x)$ and so that $f(g(x))=g(f(x))=g(g(g(x)))$ Q.E.D.

So there must exists positive integer $n$ that $f^n(x)=x$ for all $x$. It's clear that there must exists positive integer $d$ that for infinite $x$, the length of cycle of $f$ containing $x$ is equal to $d$. Pick (assuming axiom of choices) countably infinite amount of those cycles and form a sequence, called $\mathcal{C}_1,\mathcal{C}_2,\dotsc$ In each cycle $\mathcal{C}_i$ assume it goes $c_{1,i}\to c_{2,i}\to \cdots \to c_{d,i}\to c_{1,i}$. Then choose $$g(x)=\begin{cases}c_{j,i+1} & , \text{ if }x=c_{j,i}\in \mathcal{C}_i\\ f(x) & ,\text{ otherwise.}\end{cases}$$It's clear that there exist infinitely many ways to choose the sequence $\mathcal{C}_1,\mathcal{C}_2,\dotsc $

So the new question is: is the truth of the problem statement equivalent to choice?

It's worth noting that the statement can be strengthened to Quote: Let $f:S\to S$ be a bijection where $S$ is some infinite set. Then $|\{g\in S^S:f\circ g\equiv g\circ f\}|\geqslant |S|$ and this bound is sharp. Without much additional effort.

What does the dark lord mean by cycles?

I think \nexists $\nexists$ looks better than \not\exists $\not\exists$

A slightly different approach. The idea is to define $g$ appropriately at some point and then expand it . Technically it is implemented using Zorn's lemma via two steps. 1) We define $g$ over some set $A$, such that it commutes with $f$ over $A$. It can be done in infinitely many ways. 2) We extend $g$ over $\mathbb{R}$ using Zorn's lemma. The details follow. 1) If there exists $x_0\in \mathbb{R}$ with $f^n(x_0)\neq x_0$ for every $n\in\mathbb{N}$ we may define $g(x_0):= y_0, g(f^n(x_0)):= f^n(y_0),n=1,2,\dots$, where $y_0\in\mathbb{R}$ is any point that satisfies $f^n(y_0)\neq y_0,\forall n\in\mathbb{N}$. There are infinitely many such $y_0$, for example every $f^j(x_0)$ does the job. In case that for any $x\in\mathbb{R}$ there exists $m\in\mathbb{N}$ with $f^m(x_0)=x_0$ , we can take some $x_0,x_1,\dots $ and any $y_0,y_1,\dots$ with $g^{m_j}(y_j)=y_j, j\in\mathbb{N}$ , where $m_j$ is the least natural such that $f^{m_j}(x_j)=x_j,j=0,1,\dots$ and proceed as above. Such $y_j,j=0,1,\dots$ do exist, for example $y_j:=f^i(x_j),i=1,2,\dots,m_j-1$. There are infinitely many such choices (the case $f\equiv \text{ id}$ is easily considered). Till now, we have constructed a non-empty set $A\subset \mathbb{R}$ with the following properties: \begin{align*} i)\,\, &f(A)\subset A\\ ii)\,\, &\forall x\in A, f(g(x))=g(f(x)) \end{align*}2) Using Zorn's lemma, there exists a maximal set under inclusion, satisfying $i)$ and $ii)$. Assuming $A\neq \mathbb{R}$ we may take $x_0\in \mathbb{R}\setminus A$ and define appropriately (as done above) $g$ at $x_0$ and at every point $f^j(x_0),j=1,2,\dots$. It means $A$ is not maximal, a contradiction. Hence $A=\mathbb{R}$ and we are done.

Solution with a lot of hints from p_square The answer is $\boxed {\text {YES}}$ First note that if there exists some $x$ such that the sequence $\{x,f(x),f(f(x)) \dots \}$ then we could just take the sequence of functions $\{f,f^2,f^3, \dots \}$ . As $f$ doesn't have a finite order , hence the sequence is infinite and hence it works. Next we consider the case when there exists some $n \in \mathbb N$ such that $\forall x$ we have $f^n(x)=x$ . Note that this means that $f$ is composed of cycles and some cycle of length $p \mid n$ must occur infinitely many times . Now we consider two cycles of the form $(a_1\mapsto a_2 \mapsto \dots a_p\mapsto a_1)$ and $(b_1\mapsto b_2 \mapsto \dots b_p\mapsto b_1)$ . Define a function $g$ as follows $:=$ $g(x)=f(x) \forall x \neq a_i$ $g(a_1)=b_1$ Note that it can be inductively proved that if $g(a_i)=b_i$ then $g(a_{i+1})=b_{i+1}$ . Hence we basically keep $g$ almost the same as $f$ everywhere except we take two cycles , fix one of them and map the other one onto the fixed one . Since infinitely many pairs of cycles of length $p$ can be found , we are done $\blacksquare$

a1267ab wrote: Let $f:\mathbb{R}\to\mathbb{R}$ be a bijective function. Does there always exist an infinite number of functions $g:\mathbb{R}\to\mathbb{R}$ such that $f(g(x))=g(f(x))$ for all $x\in\mathbb{R}$? Proposed by Daniel Liu . . here is mine. if there don't exist an $n$ such that $f^n(x)=x$ then we are done as $g(x)=f^i(x)$ works and done now let $f^n(x)=x$ for any $x$ let there be an $S_i$ such that $|S_i|=|R|$ where $S_i=\{x | Ord_f x=i \}$ now take $i$ cycle of lenght $i$ with $p_{1,1},p_{1,2},...,p_{1,i}$ . . . $p_{i,1},p_{i,2},...,p_{i,i}$ with $f(p_{j,k})=p_{j,k+1}$ and all of $p_{u,v}$ are different . the indices are mode $i$ now let $g(p_{j,k})=p_{j+1,k}$ for $ j<i$ and $g(p_{i,k})=p_{1,k+1}$ for any other $x$ put $g(x)=f(x)$ then we have $g^i(x)=f(x)$ for any real $x$ which this works in the statement . . and since $|S_i|=|R|$ the ways we can choose $i$ cycle of lenght $i$ is not finite

I hope this works Put the function onto a graph, and draw an arrow between $x$ and $f(x)$. Consider the cycle decomposition of this permutation; if some $x$ doesn't lie on a cycle or an infinite cycle, then we can take $g(x) = f^{k}(x)$ for all $k$. Thus, assume all $x$ lie on a finite cycle. Furthermore, I claim there has to be a cycle with maximal length; if not, then we could always take $g(x) = f^{k}(x)$, and there will be a cycle with length larger than $k$, so this function is different from other $g(x) = f^{k}(x)$. Let $M$ be the maximal length over all cycles. Then, since $M$ is finite, there exists some $n$ such that there are infinite cycles that have length $n$. Now, consider two such cycles, $c$ and $d$. For every element not in $c$ or $d$, let $g$ be equal to $f$. Next, pair the elements in $c$ and $d$ such that for each ${x, y}$ where $x\in c, y\in d$, then $f(x), f(y)$ is also a pair. Let $g(x) = f(y), g(y) = f(x)$ for all the pairs. It's not hard to see that this works, and since there are infinite many cycles, we can choose infinite many such pairs of cycles.

The answer is yes. First suppose there does not exist $n \geq 1$ with $f^n(x)=x$. Then we can let $g(x)$ equal $f(x),f^2(x),\ldots$. These are all distinct, because if $f^a(x)=f^b(x)$ and $a \neq b$, then we can apply $f^{-\min(a,b)}(x)$ to both sides (which exists because $f$ is a bijection) to obtain a contradiction, so such functions all work. Now suppose there exists $n \geq 1$ with $f^n(x)=x$. This means that $f$ is made of an (infinite) number of disjoint cycles, all of length $\leq n$. By infinite pigeonhole, it follows that there exists some $k \geq 0$ where $f$ has infinitely many cycles of length $k$. Now pick any two cycles $c_1,c_2$, and suppose in cycle $c_1$ can be described as $a_1 \to a_2 \to \cdots \to a_k$ and $c_2$ can be described as $b_1 \to b_2 \to \cdots \to b_k$. Then consider the function $$g(x)=\begin{cases}a_i & x=b_i\\b_i & x=a_i\\ f(x)&\text{otherwise},\end{cases}$$which can be easily verified to work. Since there are an infinite number of choices for $\{c_1,c_2\}$, we have constructed an infinite family of functions, so we're done. $\blacksquare$

For any set \(S\), there's a natural correspondence between functions \(f\colon S\to S\) and \(\mathbb{N}\)-actions on \(S\), and this correspondence sends bijective \(f\) to precisely those \(\mathbb{N}\)-actions on \(S\) that are the restrictions of \(\mathbb{Z}\)-actions on \(S\). Given an \(\mathbb{N}\)-action \(\mathfrak{F}\) on \(S\) obtained by the above correspondence from \(f\colon S\to S\), the collection of functions \(f'\colon S\to S\) commuting with \(f\) is itself naturally in bijection to \(\text{Hom}_{\mathbb{N}\textbf{-Set}}\left(\mathfrak{F},\mathfrak{F}\right)\). Every \(\mathbb{N}\)-set decomposes canonically as a (perhaps quite large) coproduct of indecomposable \(\mathbb{N}\)-sets, each of which is connected, and in such a way that the \(\mathbb{N}\)-action \(\mathfrak{F}\) on \(S\) is the restriction of a \(\mathbb{Z}\)-action on \(S\) iff the same can be said for each of its canonical indecomposable summands. But there are only countably many indecomposable \(\mathbb{Z}\)-actions on \(S\), each of which acts on a countable set, from which the particular result desired follows upon canonically decomposing the restricted \(\mathbb{Z}\)-action \(\mathfrak{F}\) on \(\mathbb{R}\) corresponding to \(f\colon\mathbb{R}\to\mathbb{R}\) as \(\mathfrak{F}\simeq\sum_{i\colon \mathcal{I}}\mathfrak{F}_{i}\) and remarking that \[\text{Hom}_{\mathbb{N}\textbf{-Set}}\left(\mathfrak{F},\mathfrak{F}\right)\ \simeq\ \text{Hom}_{\mathbb{N}\textbf{-Set}}\left(\sum_{i_{0}\colon \mathcal{I}}\mathfrak{F}_{i_{0}},\sum_{i_{1}\colon\mathcal{I}}\mathfrak{F}_{i_{1}}\right)\ \simeq\ \prod_{i_{0}\colon \mathcal{I}}\sum_{i_{1}\colon\mathcal{I}}\text{Hom}_{\mathbb{N}\textbf{-Set}}\left(\mathfrak{F}_{i_{0}},\mathfrak{F}_{i_{1}}\right).\]

The answer is YES. First, suppose that there did not exist $n$ such that $f^n(x) = x$ for all $x.$ Then, an infinite set of functions $g$ that works is \[ \{x, f(x), f^2(x), \dots , \} \]which works because we never have $f^{a} (x) = f^{b} (x).$ Hence, suppose there did exist such an $n.$ Since $f$ is a bijection, it can be partitioned into infinitely many chains of sequences of length $n$, i.e \[ x \to f(x) \to f^2(x) \to \dots f^{n-1} (x). \]Consider two of these chains, say $A = \{a_0, a_1, \dots , a_{n-1} \}$ and $B = \{b_0, b_1, \dots , b_{n-1} \}.$ Now define \[g(x) = \begin{cases} f(x) \quad x \not \in A, B \\ f(a_i) \quad x = b_i \\ f(b_i) \quad x = a_i \end{cases}. \]Now, if $x \not \in A, B,$ $f(g(x)) = f^2(x) = g(f(x)).$ Otherwise, if $x \in A,$ $f(g(a_i)) = f(b_i) = b_{i+1}$ and $g(f(a_i)) = g(a_{i+1}) = b_{i+1}.$ Similarly $x \in B$ gives $f(g(x)) = g(f(x)).$ Thus, $g(x)$ satisfies the given condition. Since there are an infinite number of pairs $(A, B)$ there must be an infinite number of functions $g$ as desired. $\blacksquare$

Consider the set $S=\{f^k: k\in \mathbb{Z} \}$. All functions in $S$ clearly work. So if $|S|$ is infinite, we are just done. So assume $S$ is finite. Then there exists some infinite chain $k_1<k_2<\cdots$ of integers for which $f^{k_1}=f^{k_2}=\cdots$. Since $f$ is a bijection, inverses exist. So we can write $f^{k_2-k_1}=\text{id}$. If $k_2-k_1=1$, then $f=\text{id}$, and the problem is trivial. Else, we hence have some $r\ge 2$ for which $f^r=\text{id}$. Combined with $f$ being a bijection, this implies there exist infinitely many cycles in the arrow diagram of $f$. In particular, the arrows diagram must now be a union of disjoint cycles, each of which has length at most $r$. (Before, there was a possibility of ``infinite cycles'' that never close.) So there exists some $s \le r$ for which there are infinitely many cycles with length exactly $s$. Number the cycles $C_1,C_2,\ldots$. Say $C_1$ is $(a_0\to a_1\to \cdots \to a_{s-1}\to a_0)$ and for some arbitrary $k\ge 2$, $C_k$ is $(b_0\to b_1\to \cdots \to b_{s-1}\to b_0)$. Then let $g(a_i)=b_i$ for all $i\in [0,s)$ and let $g(x)=\text{id}$ for all $x\not \in \{a_0,\ldots,a_{s-1}\}$. So now $f(g(a_i))=f(b_i)=b_{i+1}=g(a_{i+1})=g(f(a_i))$ for all $i \in [0,r)$ (indices mod $s$) and $f(g(x))=f(x)=g(f(x))$ for all other $x$. Since there are different such $g$ for each different $k\ge 2$, we have an infinite number of functions $g$ that work in any case.

Firstly, note that $g=f^i$ work if there isn't some $n$, such that $f^n=id$ (when such $n$ doesn't exist, these functions will be infinitely many), so now consider this case. Note that there are infinitely many cycles of some fixed length $d \mid n$ by infinite pigeonhole (the graph is union of cycles as $f$ is a bijection). For each pair of cycles, let $g$ interchange them and $g(x)=f(x)$ for the other values $x$; these obviously work and are infinitely many.

\[\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\]Yes. Suppose there were only a finite number of possibilities for $g$. Claim: There exists a fixed positive integer $n$ such that $f^n(x) = x\forall x$. Proof: If not, then set $g = f,f^2, f^3, \ldots, $. All such functions work. $\square$ Now let $d$ be a divisor of $n$ such that there are infinitely many cycles of $f$ with length $d$. Choose any two of these cycles, and call them $A = a_1 \rightarrow a_2 \rightarrow \cdots \rightarrow a_d$ and $B = b_1 \rightarrow b_2 \rightarrow \cdots \rightarrow b_d$. Consider $g$ mapping $a_i$ to $b_i$, $b_i$ to $a_i$, and fixing everything else. Such a function works for any choice of $A,B$. Since there are infinitely many choices of $A,B$, we have infinitely many functions $g$ satisfying the condition.

Silly funny arrows! Define an orbit to be any set in the form $\{ \ldots, f^{-1}(x), x, f(x), \ldots \}$ and let $\mathcal{S}$ denote the set of all orbits. For any orbit $A \in \mathcal{S}$ obeying $|A| \geq 2$ note that $g(\alpha) = f(\alpha)$ and $g(\alpha) = \alpha$ for all $\alpha \in A$ both obey the identity $f(g(\alpha))=g(f(\alpha))$. Note that the number of orbits is uncountable but there are countably many orbits, but each orbit has countable size, thus there are infinitely many orbits. So, assume that there are infinitely many orbits $A_1,A_2, \ldots$ obeying $|A_i| \geq 2$. Note that for every orbit $A_i$ we can independently define $g(\alpha)$ as either $f(\alpha)$ or $f^{-1}(\alpha)$ for all $\alpha \in A_i$. There are infinitely many $A_i$ and each $A_i$ has at least two choices for $g$ that are independent, so there are (uncountably) infinite number of $g$ as desired. If there are infinitely many orbits of size $1$, this means that there is an infinite $Y$ set of fixed points of $f$. Thus, any choice of $g$ which is bijective on $Y$ and is the identity everywhere else will satisfy the FE. There are (uncountably) infinite such choices of $g$ so we are done. $\blacksquare$

The answer is yes. Consider the directed graph representing $f$ and any cycle $C$ in the graph. Pick any $x \in C$. I claim that we can provide a valid construction for any choice of $g(x)$, which will imply the problem. Suppose that $g(x) \in C_1$ for some other cycle $C_1$. Then, for any $f^k(x)$ in $C$, we can pick $g(f^k(x)) = f^k(g(x))$. This yields an image of $g$ for every element in $C \sqcup C_1$. If $g(x) \in C$ too, then $g(x) = f^{k_0+1}(x)$ for any $x \in C$ and some $k_0$, thus we can define $g$ on $C$. So we can perform this step, and then set $g(x)$ to be the identity for any $x$ for which we haven't defined it yet, which yields an infinite number of $g$.

The answer is yes. Draw a graph with real numbers as vertices and directed edges corresponding to $f$. Note that since $f$ is bijective, all connected components are (finite) cycles or infinite trees. However, due to bijectivity, the only type of tree that is possible is a infinite chain with one vertex leading to the next. Case 1: At least one such chain exists. Then, for any positive integer $n$, we could let $g$ correspond to advancing $n$ levels in this chain in this connected component (while in all other connected components $g$ behaves the same as $f$), so this gives infinitely many solutions. Case 2: No such chain exists. Then, all connected components are cycles. However, since cycles have finite length, there must be infinitely many cycles. In each cycle, having $g$ be the identity or have $g$ be the same as $f$ in that cycle works, so we have at least two choices for each cycle that are independent of each other. Since there are infinitely many cycles, we are done.

If there isn't any positive integer $n$ such that $f^n(x) = x$, then $g = f^k$ works for all $k$. Therefore we can assume that there exists $n$ such that $f^n(x) = x$. Then $f$ is made of an infinite number of disjoint cycles. By pigeonhole principle, there exists some $k \ge 0$ such that $f$ has infinitely many cycles of length $k$. Now pick any two cycles $a, b$ of length $k$. Assume cycles $a, b$ are described as $a_1 \to a_2 \to \dots \to a_k$ and $b_1 \to b_2 \to \dots \to b_k$, respectively. Then define $g$ as follows: $g(a_i) = b_i, g(a_i) = b_i$ and $g(x) = f(x)$, otherwise. Since there are infinitely many choices of $a, b$, so we're done. $\blacksquare$

I will prove that in a bijection from $\mathbb{R}\to\mathbb{R}$, there are infinitely many distinct cycles or infinite length paths of the form $f^n(m)$, note that the set ${n, f(n), f(f(n)), \dots}$ is countably infinite and thus an infinite number of these sets such that they are not subsets of each other must be needed to cover all the reals. Thus we can define an infinite number of functions $g$ such that for one of the subsets ${n, f(n), \dots}$, $g(n)=f^{-1}(n)$ and for all other values $g(n)=n$.

Yes! Note that $f$ can only have infinite chains and cycles. If $f$ has any infinite chain, we can let $g$ be the identity for anything besides one infinite chain, and otherwise advance in the chain by $n$ for some positive integer $n$. Otherwise, $f$ has infinitely many cycles of length $\ge 2$ or $f$ has infinitely many cycles of length $1$ (or both). For the former case, let $g$ be the identity for all but one such cycle, and advance by one on that cycle. For the latter case, let $g$ be the identity for everything that isn't a fixed point, and any function on the fixed points works. $\blacksquare$

Interesting problem: If there doesn't exists some $n$ such that $f^n(x) \equiv x$ for all $x \in \mathbb R$, then $g$ can take any of the functions: $f, f^2, f^3, \cdots$. If $f^n(x) \equiv x$ for all $x \in \mathbb R$, for some $n \in \mathbb N$. Consider some cycle of length $p$ which occurs infinitely many times (because $p|n$, thus finite possibilities for $p$). Let $(x_1, \cdots, x_p), (y_1, \cdots, y_p)$ denote those cycles. Then, letting $f(x) = g(x)$ for all $x \neq x_i$, and let $f(x_1)=g(y_1)$, which implies $f(x_k)=g(x_k)$ for all $k$. There exists infinitely many such functions and we are done.