Skip to main content
added 1930 characters in body
Source Link
Stefan Mesken
  • 1.1k
  • 6
  • 17

If $\operatorname{card}(X) > \omega$ is regular, the answer is yes:

Lemma 1. Let $\kappa$ be a regular, uncountable cardinal and let $f \colon \kappa \to \kappa$ be such that $S := \{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is unbounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \kappa. $$

Proof. For each $\alpha \in \kappa$ let $C_{\alpha} := \{ f^{n}(\alpha) \mid n < \omega \}$ and $$ g_{\alpha} \colon \kappa \to \kappa, \xi \mapsto \begin{cases} f(\xi) & \text{, if } \xi \in C_{\alpha} \\ \xi & \text{, otherwise}. \end{cases} $$

Then $$\begin{align*} f \circ g_{\alpha} &= f^2 \restriction C_{\alpha} \cup f \restriction (\kappa \setminus C_{\alpha}) \\ &= g_{\alpha} \circ f. \end{align*}$$

It now suffices to show that $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Let $\alpha < \kappa$. By our assumption there is some $\xi < \kappa$ such that $\sup \bigcup_{\beta \le \alpha} C_\beta < \xi$ and $f(\xi) \neq \xi$. Thus, for all $\beta \le \alpha$, $g_{\beta}(\xi) = \xi \neq f(\xi) = g_{\xi}(\xi)$. The regularity of $\kappa$ now implies $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Q.E.D.

Lemma 2. Let $\kappa$ be a (possibly singular) cardinal and let $f \colon \kappa \to \kappa$ be such that $\{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is bounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) = 2^\kappa > \kappa. $$

Proof. Fix $\alpha < \kappa$ such that $f(\xi) = \xi$ for all $\xi \ge \alpha$. Then for each $g \colon \kappa \to \kappa$ with $g \restriction \alpha = \operatorname{id}$ we have $f \circ g = g \circ f$ and there are $2^\kappa > \kappa$ many such functions $g$. Q.E.D.

So the remaining cases are

Q 1. Let $f \colon \omega \to \omega$ be such that $\{f^n \mid n < \omega\}$ is finite. Are there infinitely many $g \colon \omega \to \omega$ such that $f \circ g = g \circ f$?

This case has now been handled by Martin Goldstern and Will Sawin in separate answers. So the only remaining question is:

Q 2. Let $\kappa$ be a singular cardinal. Is there some function $f \colon \kappa \to \kappa$ such that $$ \operatorname{card} (\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) < \kappa? $$


Let me provide, as a first approach to Q 2., the details of my previous claim in the comment section:

Lemma 3. Let $\kappa$ be a cardinal such that $\operatorname{cf}(\kappa) > \omega$ and let $f \colon \kappa \to \kappa$ be such that $S := \{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is unbounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \operatorname{cf}(\kappa). $$

Proof. The argument is a slight refinement of the previous proof of Lemma 1:

For each $\alpha \in \kappa$ let $C_{\alpha} := \{ f^{n}(\alpha) \mid n < \omega \}$ and $$ g_{\alpha} \colon \kappa \to \kappa, \xi \mapsto \begin{cases} f(\xi) & \text{, if } \xi \in C_{\alpha} \\ \xi & \text{, otherwise}. \end{cases} $$

Then $$\begin{align*} f \circ g_{\alpha} &= f^2 \restriction C_{\alpha} \cup f \restriction (\kappa \setminus C_{\alpha}) \\ &= g_{\alpha} \circ f. \end{align*}$$

We now recursively construct a strictly increasing sequence $(\alpha_\beta \mid \beta < \operatorname{cf}(\kappa))$ such that, for all $\beta < \operatorname{cf}(\kappa)$, $f \circ g_{\alpha_\beta} = g_{\alpha_\beta} \circ f$:

Given $(\alpha_\beta \mid \beta < \gamma)$ for some $\gamma < \operatorname{cf}(\kappa)$ note that $\bigcup_{\beta < \gamma} C_{\alpha_\beta}$ is not cofinal in $\kappa$. Hence there is some $\xi > \sup \bigcup_{\beta < \gamma} C_{\alpha_\beta}$ such that $f(\xi) \neq \xi$. Let $\xi$ be minimal with this property and let $\alpha_\gamma := \xi$. As before we see that $f \circ g_{\alpha_\gamma} = g_{\alpha_\gamma} \circ f$ and $g_{\alpha_\gamma} \not \in \{ g_{\alpha_\beta} \mid \beta < \gamma \}$. Hence the resulting sequence $(g_{\alpha_\beta} \mid \beta < \operatorname{cf}(\kappa))$ is as desired. Q.E.D.

If $\operatorname{card}(X) > \omega$ is regular, the answer is yes:

Lemma 1. Let $\kappa$ be a regular, uncountable cardinal and let $f \colon \kappa \to \kappa$ be such that $S := \{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is unbounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \kappa. $$

Proof. For each $\alpha \in \kappa$ let $C_{\alpha} := \{ f^{n}(\alpha) \mid n < \omega \}$ and $$ g_{\alpha} \colon \kappa \to \kappa, \xi \mapsto \begin{cases} f(\xi) & \text{, if } \xi \in C_{\alpha} \\ \xi & \text{, otherwise}. \end{cases} $$

Then $$\begin{align*} f \circ g_{\alpha} &= f^2 \restriction C_{\alpha} \cup f \restriction (\kappa \setminus C_{\alpha}) \\ &= g_{\alpha} \circ f. \end{align*}$$

It now suffices to show that $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Let $\alpha < \kappa$. By our assumption there is some $\xi < \kappa$ such that $\sup \bigcup_{\beta \le \alpha} C_\beta < \xi$ and $f(\xi) \neq \xi$. Thus, for all $\beta \le \alpha$, $g_{\beta}(\xi) = \xi \neq f(\xi) = g_{\xi}(\xi)$. The regularity of $\kappa$ now implies $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Q.E.D.

Lemma 2. Let $\kappa$ be a (possibly singular) cardinal and let $f \colon \kappa \to \kappa$ be such that $\{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is bounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) = 2^\kappa > \kappa. $$

Proof. Fix $\alpha < \kappa$ such that $f(\xi) = \xi$ for all $\xi \ge \alpha$. Then for each $g \colon \kappa \to \kappa$ with $g \restriction \alpha = \operatorname{id}$ we have $f \circ g = g \circ f$ and there are $2^\kappa > \kappa$ many such functions $g$. Q.E.D.

So the remaining cases are

Q 1. Let $f \colon \omega \to \omega$ be such that $\{f^n \mid n < \omega\}$ is finite. Are there infinitely many $g \colon \omega \to \omega$ such that $f \circ g = g \circ f$?

Q 2. Let $\kappa$ be a singular cardinal. Is there some function $f \colon \kappa \to \kappa$ such that $$ \operatorname{card} (\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) < \kappa? $$

If $\operatorname{card}(X) > \omega$ is regular, the answer is yes:

Lemma 1. Let $\kappa$ be a regular, uncountable cardinal and let $f \colon \kappa \to \kappa$ be such that $S := \{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is unbounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \kappa. $$

Proof. For each $\alpha \in \kappa$ let $C_{\alpha} := \{ f^{n}(\alpha) \mid n < \omega \}$ and $$ g_{\alpha} \colon \kappa \to \kappa, \xi \mapsto \begin{cases} f(\xi) & \text{, if } \xi \in C_{\alpha} \\ \xi & \text{, otherwise}. \end{cases} $$

Then $$\begin{align*} f \circ g_{\alpha} &= f^2 \restriction C_{\alpha} \cup f \restriction (\kappa \setminus C_{\alpha}) \\ &= g_{\alpha} \circ f. \end{align*}$$

It now suffices to show that $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Let $\alpha < \kappa$. By our assumption there is some $\xi < \kappa$ such that $\sup \bigcup_{\beta \le \alpha} C_\beta < \xi$ and $f(\xi) \neq \xi$. Thus, for all $\beta \le \alpha$, $g_{\beta}(\xi) = \xi \neq f(\xi) = g_{\xi}(\xi)$. The regularity of $\kappa$ now implies $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Q.E.D.

Lemma 2. Let $\kappa$ be a (possibly singular) cardinal and let $f \colon \kappa \to \kappa$ be such that $\{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is bounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) = 2^\kappa > \kappa. $$

Proof. Fix $\alpha < \kappa$ such that $f(\xi) = \xi$ for all $\xi \ge \alpha$. Then for each $g \colon \kappa \to \kappa$ with $g \restriction \alpha = \operatorname{id}$ we have $f \circ g = g \circ f$ and there are $2^\kappa > \kappa$ many such functions $g$. Q.E.D.

So the remaining cases are

Q 1. Let $f \colon \omega \to \omega$ be such that $\{f^n \mid n < \omega\}$ is finite. Are there infinitely many $g \colon \omega \to \omega$ such that $f \circ g = g \circ f$?

This case has now been handled by Martin Goldstern and Will Sawin in separate answers. So the only remaining question is:

Q 2. Let $\kappa$ be a singular cardinal. Is there some function $f \colon \kappa \to \kappa$ such that $$ \operatorname{card} (\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) < \kappa? $$


Let me provide, as a first approach to Q 2., the details of my previous claim in the comment section:

Lemma 3. Let $\kappa$ be a cardinal such that $\operatorname{cf}(\kappa) > \omega$ and let $f \colon \kappa \to \kappa$ be such that $S := \{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is unbounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \operatorname{cf}(\kappa). $$

Proof. The argument is a slight refinement of the previous proof of Lemma 1:

For each $\alpha \in \kappa$ let $C_{\alpha} := \{ f^{n}(\alpha) \mid n < \omega \}$ and $$ g_{\alpha} \colon \kappa \to \kappa, \xi \mapsto \begin{cases} f(\xi) & \text{, if } \xi \in C_{\alpha} \\ \xi & \text{, otherwise}. \end{cases} $$

Then $$\begin{align*} f \circ g_{\alpha} &= f^2 \restriction C_{\alpha} \cup f \restriction (\kappa \setminus C_{\alpha}) \\ &= g_{\alpha} \circ f. \end{align*}$$

We now recursively construct a strictly increasing sequence $(\alpha_\beta \mid \beta < \operatorname{cf}(\kappa))$ such that, for all $\beta < \operatorname{cf}(\kappa)$, $f \circ g_{\alpha_\beta} = g_{\alpha_\beta} \circ f$:

Given $(\alpha_\beta \mid \beta < \gamma)$ for some $\gamma < \operatorname{cf}(\kappa)$ note that $\bigcup_{\beta < \gamma} C_{\alpha_\beta}$ is not cofinal in $\kappa$. Hence there is some $\xi > \sup \bigcup_{\beta < \gamma} C_{\alpha_\beta}$ such that $f(\xi) \neq \xi$. Let $\xi$ be minimal with this property and let $\alpha_\gamma := \xi$. As before we see that $f \circ g_{\alpha_\gamma} = g_{\alpha_\gamma} \circ f$ and $g_{\alpha_\gamma} \not \in \{ g_{\alpha_\beta} \mid \beta < \gamma \}$. Hence the resulting sequence $(g_{\alpha_\beta} \mid \beta < \operatorname{cf}(\kappa))$ is as desired. Q.E.D.

deleted 30 characters in body
Source Link
Stefan Mesken
  • 1.1k
  • 6
  • 17

If $\operatorname{card}(X) > \omega$ is regular, the answer is yes:

Lemma 1. Let $\kappa$ be a regular, uncountable cardinal and let $f \colon \kappa \to \kappa$ be such that $S := \{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is unbounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \kappa. $$

Proof. For each $\alpha \in \kappa$ let $C_{\alpha} := \{ f^{n}(\alpha) \mid n < \omega \}$ and $$ g_{\alpha} \colon \kappa \to \kappa, \xi \mapsto \begin{cases} f(\xi) & \text{, if } \xi \in C_{\alpha} \\ \xi & \text{, otherwise}. \end{cases} $$

Then $$\begin{align*} f \circ g_{\alpha} &= f^2 \restriction C_{\alpha} \cup f \restriction (\kappa \setminus C_{\alpha}) \\ &= g_{\alpha} \circ f. \end{align*}$$

It now suffices to show that $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Let $\alpha < \kappa$. By our assumption there is some $\xi < \kappa$ such that $\sup \bigcup_{\beta \le \alpha} C_\beta < \xi$ and $f(\xi) \neq \xi$. Thus, for all $\beta \le \alpha$, $g_{\beta}(\xi) = \xi \neq f(\xi) = g_{\xi}(\xi)$. The regularity of $\kappa$ now implies $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Q.E.D.

Lemma 2. Let $\kappa$ be a regular(possibly singular) cardinal and let $f \colon \kappa \to \kappa$ be such that $\{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is bounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \kappa. $$$$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) = 2^\kappa > \kappa. $$

Proof. Fix $\alpha < \kappa$ such that $f(\xi) = \xi$ for all $\xi \ge \alpha$. Then for each $g \colon \kappa \to \kappa$ with $g \restriction \alpha = \operatorname{id}$ we have $f \circ g = g \circ f$ and there are $2^\kappa > \kappa$ many such functions $g$. Q.E.D.

So the remaining cases are

Q 1. Let $f \colon \omega \to \omega$ be such that $\{f^n \mid N < \omega\}$$\{f^n \mid n < \omega\}$ is finite. Are there infinitely many $g \colon \omega \to \omega$ such that $f \circ g = g \circ f$?

Q 2. Let $\kappa$ be a singular cardinal. Is there some function $f \colon \kappa \to \kappa$ such that $$ \operatorname{card} (\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) < \kappa? $$

If $\operatorname{card}(X) > \omega$ is regular, the answer is yes:

Lemma 1. Let $\kappa$ be a regular, uncountable cardinal and let $f \colon \kappa \to \kappa$ be such that $S := \{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is unbounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \kappa. $$

Proof. For each $\alpha \in \kappa$ let $C_{\alpha} := \{ f^{n}(\alpha) \mid n < \omega \}$ and $$ g_{\alpha} \colon \kappa \to \kappa, \xi \mapsto \begin{cases} f(\xi) & \text{, if } \xi \in C_{\alpha} \\ \xi & \text{, otherwise}. \end{cases} $$

Then $$\begin{align*} f \circ g_{\alpha} &= f^2 \restriction C_{\alpha} \cup f \restriction (\kappa \setminus C_{\alpha}) \\ &= g_{\alpha} \circ f. \end{align*}$$

It now suffices to show that $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Let $\alpha < \kappa$. By our assumption there is some $\xi < \kappa$ such that $\sup \bigcup_{\beta \le \alpha} C_\beta < \xi$ and $f(\xi) \neq \xi$. Thus, for all $\beta \le \alpha$, $g_{\beta}(\xi) = \xi \neq f(\xi) = g_{\xi}(\xi)$. The regularity of $\kappa$ now implies $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Q.E.D.

Lemma 2. Let $\kappa$ be a regular cardinal and let $f \colon \kappa \to \kappa$ be such that $\{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is bounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \kappa. $$

Proof. Fix $\alpha < \kappa$ such that $f(\xi) = \xi$ for all $\xi \ge \alpha$. Then for each $g \colon \kappa \to \kappa$ with $g \restriction \alpha = \operatorname{id}$ we have $f \circ g = g \circ f$ and there are $2^\kappa > \kappa$ many such functions $g$. Q.E.D.

So the remaining cases are

Q 1. Let $f \colon \omega \to \omega$ be such that $\{f^n \mid N < \omega\}$ is finite. Are there infinitely many $g \colon \omega \to \omega$ such that $f \circ g = g \circ f$?

Q 2. Let $\kappa$ be a singular cardinal. Is there some function $f \colon \kappa \to \kappa$ such that $$ \operatorname{card} (\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) < \kappa? $$

If $\operatorname{card}(X) > \omega$ is regular, the answer is yes:

Lemma 1. Let $\kappa$ be a regular, uncountable cardinal and let $f \colon \kappa \to \kappa$ be such that $S := \{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is unbounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \kappa. $$

Proof. For each $\alpha \in \kappa$ let $C_{\alpha} := \{ f^{n}(\alpha) \mid n < \omega \}$ and $$ g_{\alpha} \colon \kappa \to \kappa, \xi \mapsto \begin{cases} f(\xi) & \text{, if } \xi \in C_{\alpha} \\ \xi & \text{, otherwise}. \end{cases} $$

Then $$\begin{align*} f \circ g_{\alpha} &= f^2 \restriction C_{\alpha} \cup f \restriction (\kappa \setminus C_{\alpha}) \\ &= g_{\alpha} \circ f. \end{align*}$$

It now suffices to show that $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Let $\alpha < \kappa$. By our assumption there is some $\xi < \kappa$ such that $\sup \bigcup_{\beta \le \alpha} C_\beta < \xi$ and $f(\xi) \neq \xi$. Thus, for all $\beta \le \alpha$, $g_{\beta}(\xi) = \xi \neq f(\xi) = g_{\xi}(\xi)$. The regularity of $\kappa$ now implies $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Q.E.D.

Lemma 2. Let $\kappa$ be a (possibly singular) cardinal and let $f \colon \kappa \to \kappa$ be such that $\{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is bounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) = 2^\kappa > \kappa. $$

Proof. Fix $\alpha < \kappa$ such that $f(\xi) = \xi$ for all $\xi \ge \alpha$. Then for each $g \colon \kappa \to \kappa$ with $g \restriction \alpha = \operatorname{id}$ we have $f \circ g = g \circ f$ and there are $2^\kappa > \kappa$ many such functions $g$. Q.E.D.

So the remaining cases are

Q 1. Let $f \colon \omega \to \omega$ be such that $\{f^n \mid n < \omega\}$ is finite. Are there infinitely many $g \colon \omega \to \omega$ such that $f \circ g = g \circ f$?

Q 2. Let $\kappa$ be a singular cardinal. Is there some function $f \colon \kappa \to \kappa$ such that $$ \operatorname{card} (\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) < \kappa? $$

deleted 30 characters in body
Source Link
Stefan Mesken
  • 1.1k
  • 6
  • 17

If $\operatorname{card}(X)$$\operatorname{card}(X) > \omega$ is regular, the answer is yes:

Lemma 1. Let $f \colon \omega \to \omega$. Then $$ \operatorname{card}(\{ g \colon \omega \to \omega \mid f \circ g = g \circ f \}) \ge \aleph_{0}. $$

Proof. See here. Q.E.D.

Lemma 2. Let $\kappa$ be a regular, uncountable cardinal and let $f \colon \kappa \to \kappa$ be such that $S := \{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is unbounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \kappa. $$

Proof. For each $\alpha \in \kappa$ let $C_{\alpha} := \{ f^{n}(\alpha) \mid n < \omega \}$ and $$ g_{\alpha} \colon \kappa \to \kappa, \xi \mapsto \begin{cases} f(\xi) & \text{, if } \xi \in C_{\alpha} \\ \xi & \text{, otherwise}. \end{cases} $$

Then $$\begin{align*} f \circ g_{\alpha} &= f^2 \restriction C_{\alpha} \cup f \restriction (\kappa \setminus C_{\alpha}) \\ &= g_{\alpha} \circ f. \end{align*}$$

It now suffices to show that $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Let $\alpha < \kappa$. By our assumption there is some $\xi < \kappa$ such that $\sup \bigcup_{\beta \le \alpha} C_\beta < \xi$ and $f(\xi) \neq \xi$. Thus, for all $\beta \le \alpha$, $g_{\beta}(\xi) = \xi \neq f(\xi) = g_{\xi}(\xi)$. The regularity of $\kappa$ now implies $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Q.E.D.

Lemma 32. Let $\kappa$ be a regular cardinal and let $f \colon \kappa \to \kappa$ be such that $\{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is bounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \kappa. $$

Proof. Fix $\alpha < \kappa$ such that $f(\xi) = \xi$ for all $\xi \ge \alpha$. Then for each $g \colon \kappa \to \kappa$ with $g \restriction \alpha = \operatorname{id}$ we have $f \circ g = g \circ f$ and there are $2^\kappa > \kappa$ many such functions $g$. Q.E.D.

So the remaining casecases are

Q 1. Let $f \colon \omega \to \omega$ be such that $\{f^n \mid N < \omega\}$ is finite. Are there infinitely many $g \colon \omega \to \omega$ such that $f \circ g = g \circ f$?

Q 2. Let $\kappa$ be a singular cardinal. Is there some function $f \colon \kappa \to \kappa$ such that $$ \operatorname{card} (\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) < \kappa? $$

If $\operatorname{card}(X)$ is regular, the answer is yes:

Lemma 1. Let $f \colon \omega \to \omega$. Then $$ \operatorname{card}(\{ g \colon \omega \to \omega \mid f \circ g = g \circ f \}) \ge \aleph_{0}. $$

Proof. See here. Q.E.D.

Lemma 2. Let $\kappa$ be a regular, uncountable cardinal and let $f \colon \kappa \to \kappa$ be such that $S := \{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is unbounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \kappa. $$

Proof. For each $\alpha \in \kappa$ let $C_{\alpha} := \{ f^{n}(\alpha) \mid n < \omega \}$ and $$ g_{\alpha} \colon \kappa \to \kappa, \xi \mapsto \begin{cases} f(\xi) & \text{, if } \xi \in C_{\alpha} \\ \xi & \text{, otherwise}. \end{cases} $$

Then $$\begin{align*} f \circ g_{\alpha} &= f^2 \restriction C_{\alpha} \cup f \restriction (\kappa \setminus C_{\alpha}) \\ &= g_{\alpha} \circ f. \end{align*}$$

It now suffices to show that $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Let $\alpha < \kappa$. By our assumption there is some $\xi < \kappa$ such that $\sup \bigcup_{\beta \le \alpha} C_\beta < \xi$ and $f(\xi) \neq \xi$. Thus, for all $\beta \le \alpha$, $g_{\beta}(\xi) = \xi \neq f(\xi) = g_{\xi}(\xi)$. The regularity of $\kappa$ now implies $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Q.E.D.

Lemma 3. Let $\kappa$ be a regular cardinal and let $f \colon \kappa \to \kappa$ be such that $\{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is bounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \kappa. $$

Proof. Fix $\alpha < \kappa$ such that $f(\xi) = \xi$ for all $\xi \ge \alpha$. Then for each $g \colon \kappa \to \kappa$ with $g \restriction \alpha = \operatorname{id}$ we have $f \circ g = g \circ f$ and there are $2^\kappa > \kappa$ many such functions $g$. Q.E.D.

So the remaining case is

Q. Let $\kappa$ be a singular cardinal. Is there some function $f \colon \kappa \to \kappa$ such that $$ \operatorname{card} (\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) < \kappa? $$

If $\operatorname{card}(X) > \omega$ is regular, the answer is yes:

Lemma 1. Let $\kappa$ be a regular, uncountable cardinal and let $f \colon \kappa \to \kappa$ be such that $S := \{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is unbounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \kappa. $$

Proof. For each $\alpha \in \kappa$ let $C_{\alpha} := \{ f^{n}(\alpha) \mid n < \omega \}$ and $$ g_{\alpha} \colon \kappa \to \kappa, \xi \mapsto \begin{cases} f(\xi) & \text{, if } \xi \in C_{\alpha} \\ \xi & \text{, otherwise}. \end{cases} $$

Then $$\begin{align*} f \circ g_{\alpha} &= f^2 \restriction C_{\alpha} \cup f \restriction (\kappa \setminus C_{\alpha}) \\ &= g_{\alpha} \circ f. \end{align*}$$

It now suffices to show that $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Let $\alpha < \kappa$. By our assumption there is some $\xi < \kappa$ such that $\sup \bigcup_{\beta \le \alpha} C_\beta < \xi$ and $f(\xi) \neq \xi$. Thus, for all $\beta \le \alpha$, $g_{\beta}(\xi) = \xi \neq f(\xi) = g_{\xi}(\xi)$. The regularity of $\kappa$ now implies $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Q.E.D.

Lemma 2. Let $\kappa$ be a regular cardinal and let $f \colon \kappa \to \kappa$ be such that $\{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is bounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \kappa. $$

Proof. Fix $\alpha < \kappa$ such that $f(\xi) = \xi$ for all $\xi \ge \alpha$. Then for each $g \colon \kappa \to \kappa$ with $g \restriction \alpha = \operatorname{id}$ we have $f \circ g = g \circ f$ and there are $2^\kappa > \kappa$ many such functions $g$. Q.E.D.

So the remaining cases are

Q 1. Let $f \colon \omega \to \omega$ be such that $\{f^n \mid N < \omega\}$ is finite. Are there infinitely many $g \colon \omega \to \omega$ such that $f \circ g = g \circ f$?

Q 2. Let $\kappa$ be a singular cardinal. Is there some function $f \colon \kappa \to \kappa$ such that $$ \operatorname{card} (\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) < \kappa? $$

Source Link
Stefan Mesken
  • 1.1k
  • 6
  • 17
Loading