I was got into a logical paradox. Can you resolve this paradox?

An endofunction is a function whose domain and codomain is the same.

For a positive integer $n$, define $R_n$ be a function which maps any endofunction $f$ to $f^{(n)}$, where $f^{(n)}$ denotes a function created by iterating $f$, $n$-times.

Now let $S$ denote a successor function defined on $N$. (the set of natural numbers. $S$ is function just adding 1)

Then we think about the expression $(R_3 \circ\ R_2)(S)$, in two different ways.

First way:

$(R_3 \circ\ R_2)(S) = R_3 \circ\ (R_2(S))$ = $R_3$ (a function adding 2)
= a function iterating “adding 2” three times = a function adding 6

Second way:

Let $f$ be an arbitrary endofunction and let’s see what happens for
$(R_3 \circ\ R_2) \circ\ f$.

$R_3 \circ\ R_2$ means iterating $R_2$ three times.

$R_2 \circ\ f = f \circ\ f \quad$ (first time)
$R_2 \circ\ (f \circ\ f) = (f \circ\ f) \circ\ (f \circ\ f) \quad$ (Second time)
$R_2 \circ\ ((f \circ\ f) \circ\ (f \circ\ f)) = ((f \circ\ f) \circ\ (f \circ\ f)) \circ ((f \circ\ f) \circ\ (f \circ\ f)) = R_8(f) \quad$ (third time)

Since $f$ was arbitrary, we conclude that $(R_3 \circ\ R_2)(S) = R_8(S) = {}$ a function adding 8

So first way gave us “adding 6” and second way gave us “adding 8”. Can you solve this paradox?

  • 1
    $\begingroup$ There's no paradox here, just a question about what the notation means. When you write a notation it means a particular thing and not something else. One of the sides of your "paradox" is a "something else". But there's already an answer explaining this. $\endgroup$
    – David K
    Commented Nov 20, 2023 at 7:03
  • $\begingroup$ Yes, it is not paradox now... $\endgroup$
    – imida k
    Commented Nov 20, 2023 at 9:31

1 Answer 1


Your "second way" is not correct, because $R_3 \circ R_2$ does not mean iterate $R_2$ three times at all. That would be denoted $R_3(R_2)$.

Instead, $R_3 \circ R_2$ is, by the definition of composition, the unique function that satisfies the equation $(R_3 \circ R_2)(f) = R_3(R_2(f))$ for all $f$. And $R_3$ acts by "iterating" its argument, $R_2(f)$, three times.

So, when $R_2(S)$ denotes the "add two" function $R_2(S): \mathbb{N} \rightarrow \mathbb{N}$, iterating that three times gives the "add six" function. Consequently, $(R_2 \circ R_1)(S)$ is unambiguously $S^{(6)}$, and not $S^{(8)}$.

  • $\begingroup$ Loosely I've thought R3∘R2 and R3(R2) are the same, but in fact it was not! $\endgroup$
    – imida k
    Commented Nov 20, 2023 at 9:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .