Rigorous definition of iteration of logarithm We usually use the recursion theorem to define rigorously the iterated (by composition) $f^n$ of a function, 
I want to give a rigorous definition of $\log^{n}x= \log(log^{n-1}x)$ (here there is a composition not power). In this case not for all $n$ the $\log$ exists (the domain of $\log^n$ depends on $n$). The problem is how to use the recursion theorem or is there a way to give a formal definition?
We have the same question when we define the family of operators $D^n$ where $D$ is the derivative operator.
 A: You could use an extended definition of $\log$ as follows:
$$\log_{\#}:\Bbb R\cup\{\#\}\to \Bbb R\cup\{\#\},\quad \log_{\#}(x)=\begin{cases} \log(x), &\text{for $x>0$}\\ \#,&\text{for $x\le 0$ or $x=\#$}\end{cases}.$$
The function $\log_{\#}$ basically behaves like $\log$, but has matching domain and co-domain, and returns a placeholder value $\#$ (use here whatever you want) where $\log(x)$ would not be defined otherwise. There is no problem in applying the Recursion Theorem (see the version in the post of @Joe) to this extended function. For each fixed $a\in\Bbb R$ you then obtain the existence of a function
$$f_a(n)=\log_{\#}^n(a).$$
Every such function will return constantly $\#$ after some finite $n\in\Bbb N$. You can then interpret this as a restriction of the domain. E.g. you can define
$$D_a:=\{n\in\Bbb N\mid f_a(x) \not=\#\}$$
as the "domain" of the recursively defined functions $f_a(n)$. E.g. $D_a=\{0\}$ for $a\le 0$ or $D_a=\{0,1\}$ for $a\in(0,1]$.

Update
Here is another way to approach your problem, maybe this is more satisfying to you. Consider the set 
$$\mathcal F:=\{\text{$f$ function} \mid \exists\alpha\in\Bbb R:\mathrm{dom}(f)=(\alpha,\infty)\}.$$
This set contains all the "interesting" functions, especially it containes $\log$ and all the iterates $\log^n$ (that we still have to define).
We define a function $h:\mathcal F\to\mathcal F$ as follows: given $f\in\mathcal F$ with $\mathrm{dom}(f)=(\alpha,\infty)$, then
$$h(f)= f\circ\log|_{\smash{(e^\alpha,\infty)}}.$$
Here, $\log|_{\smash{(e^\alpha,\infty)}}$ denotes the restriction of $\log$ to the domain $(e^\alpha,\infty)$. Note that the concatenation of $f$ with the restricted $\log$ is valid because for $x\in(e^\alpha,\infty)$ we have $\log(x)\in(\alpha,\infty)=\mathrm{dom}(f)$. Further, $h(f)$ is a function with domain $(e^\alpha,\infty)$, and therefore $h(f)\in\mathcal F$.
Now, by the Recursion Theorem there is a unique function $H:\Bbb N\to\mathcal F$ with
$$H(1)=\log,\qquad H(n+1)=h(H(n)).$$
Finally, we can define $\log^n:=H(n)$.
A: You can define the iterated logarithm $\log^n$ by:
$\log^1(x) = \log(x)$
$\log^n(x) = \log(\log^{n-1}(x)) \quad n \ge 2$
Then as functions $\mathbb{R} \rightarrow \mathbb{R}$, $\log^1$ has domain $(0, \infty)$; $\log^2$ has domain $(1, \infty)$; $\log^3$ has domain $(e, \infty)$; $\log^4$ has domain $(e^e, \infty)$. Using the tetration notation $^na$, the domain of $\log^n$ is $^{n-2}e$. All of the iterations have range $(-\infty, \infty)$.
A: gandalf61 Does a great job of properly defining the iterated logarithm, but asv is hung up on the recursion theorem. Notice that the recursion theorem is NOT satisfied by the iterated logarithm.

The Recursion Theorem: Given a set $X$, and elment $a \in X$, and a function $f:X\rightarrow X$, there exists a unique $F: \mathbb{N} \rightarrow X$ such that $F(0)=a$ and $F(n+1) = f(F(n))$

If we were to try and define the iterated logarithm through the recursion theorem, we run into an immediate problem. We want to set $f = \log$, but notice that $\log : \mathbb{R}_{>0} \rightarrow \mathbb{R}$. In particular, for any set $S \subset\mathbb{R}_{>0}$, there is some $x \in S$ such that $\log(x) \not \in S$. Thus, there is no way to set the domain and codomain of $\log$ to be the same set. This goes against the requirement of the recusion theorem that the function $f$ has the same domain and codomain.
gandalf61's definition also points out this problem: for each iteration of the iterated logarithm, you must change the domain of the function. See their answer for the proper way to do this. 
A: It is indeed not possible to apply the recursive function theorem to the logarithm function. Instead, you can use the function $\log ex$ ($=\log x+1$).
But the classical iterated logarithm, denoted as $\log^*(x)$ is defined as the number of times you can iterate the logarithm from a starting $x$ as long as the result exceeds $1$.
