Theorem: Composition of Computably Uniformly Continuous Real-Valued Functions is Computably Uniformly Continuous

Let $D \subseteq \R^n$ and $E \subseteq \R^m$ be subsets of real cartesian space.
Let $f : D \to \R$ be computably uniformly continuous.
Let $g_1, g_2, \dotsc, g_n : E \to \R$ be computably uniformly continuous.
Suppose that, for every $\bsx \in E$:
:$\tuple {\map {g_1} \bsx, \map {g_2} \bsx, \dotsc, \map {g_n} \bsx} \in D$
Then $h : E \to \R$ defined as:
:$\map h {x_1, \dotsc, x_m} = \map f {\map {g_1} {x_1, \dotsc, x_m}, \dotsc, \map {g_n} {x_1, \dotsc, x_m}}$
is computably uniformly continuous.

Proof:
By definition of computably uniformly continuous, for each of:
:$f, g_1, \dotsc, g_n$
there exists a total recursive function $d_f : \N \to \N$ such that, for all $k \in \N$ and $\bsx, \bsy \in \Dom f$:
:$\norm {\bsx - \bsy} < \dfrac 1 {\map {d_f} k + 1} \implies \size {\map f \bsx - \map f \bsy} < \dfrac 1 {k + 1}$
Define $d_h : \N \to \N$ as:
:$\map {d_h} k = \map \max {\map {d_{g_1}} {n \map {d_f} k + \paren {n - 1}}, \dotsc, \map {d_{g_n}} {n \map {d_f} k + \paren {n - 1}}}$
By definition of general max operation, it is obtained by substitution using the binary max operation.
Thus, by:
* Maximum Function is Primitive Recursive
* Multiplication is Primitive Recursive
* Addition is Primitive Recursive
* Constant Function is Primitive Recursive
* Primitive Recursive Function is Total Recursive Function
we have that $d_h$ is a total recursive function.
Let $k \in \N$ and $\bsx, \bsy \in E$ satisfy:
:$\norm {\bsx - \bsy} < \dfrac 1 {\map {d_h} k + 1}$
By Max Operation Yields Supremum of Parameters/General Case, and the definition of supremum:
:$\map {d_h} k \ge \map {d_{g_i}} {n \map {d_f} k + \paren {n - 1}}$
for every $1 \le i \le n$.
Therefore:
:$\dfrac 1 {\map {d_h} k + 1} \le \dfrac 1 {\map {d_{g_i}} {n \map {d_f} k + \paren {n - 1}} + 1}$
Hence:
:$\norm {\bsx - \bsy} < \dfrac 1 {\map {d_{g_i}} {n \map {d_f} k + \paren {n - 1}} + 1}$
for every $1 \le i \le n$.
By assumption on $d_{g_i}$:
:$\size {\map {g_i} \bsx - \map {g_i} \bsy} < \dfrac 1 {n \map {d_f} k + \paren {n - 1} + 1} = \dfrac 1 {n \paren {\map {d_f} k + 1}}$
for every $1 \le i \le n$.
Then:
{{begin-eqn}}
{{eqn | l = \norm {\tuple {\map {g_1} \bsx, \dotsc, \map {g_n} \bsx} - \tuple {\map {g_1} \bsy, \dotsc, \map {g_n} \bsy} }
      | r = \norm {\tuple {\map {g_1} \bsx - \map {g_1} \bsy, \dotsc, \map {g_n} \bsx - \map {g_n} \bsy} }
      | c = {{Defof|Vector Subtraction}}
}}
{{eqn | r = \norm {\tuple {\map {g_1} \bsx - \map {g_1} \bsy, 0, \dotsc, 0} + \dotso + \tuple {0, \dotsc, 0, \map {g_n} \bsx - \map {g_n} \bsy} }
      | c = {{Defof|Vector Addition}}
}}
{{eqn | o = \le
      | r = \norm {\tuple {\map {g_1} \bsx - \map {g_1} \bsy, 0, \dotsc, 0} } + \dotso + \norm {\tuple {0, \dotsc, 0, \map {g_n} \bsx - \map {g_n} \bsy} }
      | c = Triangle Inequality for Vectors in Euclidean Space
}}
{{eqn | r = \size {\map {g_1} \bsx - \map {g_1} \bsy} + \dotso + \size {\map {g_n} \bsx - \map {g_n} \bsy}
}}
{{eqn | o = <
      | r = \dfrac 1 {n \paren {\map {d_f} k + 1} } + \dotso \dfrac 1 {n \paren {\map {d_f} k + 1} }
      | c = Above inequality
}}
{{eqn | r = \dfrac 1 {\map {d_f} k + 1}
      | c = There are $n$ terms in the sum
}}
{{end-eqn}}
Additionally, by assumption:
:$\tuple {\map {g_1} \bsx, \dotsc, \map {g_n} \bsx} \in D$
:$\tuple {\map {g_1} \bsy, \dotsc, \map {g_n} \bsy} \in D$
Therefore, by assumption on $d_f$:
:$\size {\map f {\map {g_1} \bsx, \dotsc, \map {g_n} \bsx} - \map f {\map {g_1} \bsy, \dotsc, \map {g_n} \bsy}} < \dfrac 1 {k + 1}$
Thus, by definition of $h$:
:$\size {\map h \bsx - \map h \bsy} < \dfrac 1 {k + 1}$
As $k, \bsx, \bsy$ were arbitrary, $h$ is computably uniformly continuous by definition.
{{qed}}
Category:Computability Theory
nmj98hp7grv5ku9yerk8yyoanvlrztl