Infinite recursion of function defined with respect to "every $n$"

74 Views Asked by At

I have very little formal mathematical training, so I apologize in advance for what may seem like basic issues in this question's phrasing.

I am trying to determine whether I can make a certain inference from the following biconditionals:

$$ g_1(x) = f(x) $$ $$ g_n(x) = f(g_{n-1}(x)) $$ $$ h(x) = g_n(x) \text{ for every n} $$

In layman's terms, this is an attempt to formally define a scenario where $h(x) \iff f(f(f(f...f(x))))$.

My problem has to do with the wording "for every $n$." Do the above biconditionals permit the following inferences?

$$ h(x) \to f(h(x)) $$

or, more radically:

$$ h(x) \to h(h(h(h...h(x)))) $$

The reason I am having difficulty is that the definition of $h(x)$ is “for every $n$,” so I don’t see how $h()$ can be infinitely recursive. Wouldn't the existence of one more $f()$--and, of course, infinitely more $h(x)$'s--imply that $h(x)$ is not, in fact, "for every $n$"?

Again, I plead ignorance if this is a poorly formulated question. Feel free to edit or comment if I can make my difficulty clearer.

1

There are 1 best solutions below

2
On BEST ANSWER

"you 1-know p when you know p. You n-know p when you know that you (n − 1)-know p. You omega know p when you n-know p, for every n." I am trying to determine, based on this definition, whether it's true that you omega-know that you omega-know, if you omega-know.

Your question would have been a lot clearer if you had just said this first!

Anyway, no, this doesn't follow without more assumptions about the "know" operator. If $p$ is a proposition write $K(p)$ for the proposition that one knows $p$, and inductively write $K^n(p)$ for the proposition that one knows that one knows etc. $p$, so write $K^{\omega}(p)$ for the proposition that one $\omega$-knows $p$.

Then your question is whether $K^{\omega}(p)$ implies $K^{\omega}(K^{\omega}(p))$, and this just doesn't follow without more assumptions. The latter is equivalent to $K^n(K^{\omega}(p))$ for all $n$ but assuming only $K^{\omega}(p)$ doesn't even imply $K(K^{\omega}(p))$, again not without more assumptions. In fact we can meaningfully make use of ordinal notation here, writing $K^n(K^{\omega}(p))$ as $K^{\omega+n}(p)$ and $K^{\omega}(K^{\omega}(p))$ as $K^{\omega + \omega}(p)$. In general by transfinite induction we can make sense of $K^{\alpha}(p)$ for $\alpha$ an arbitrary ordinal and all of these states of knowledge are distinct without more hypotheses.