Reciprocal of Computable Real Sequence is Computable/Lemma
Lemma for Reciprocal of Computable Real Sequence is Computable
Let $\sequence {x_m}$ be a computable real sequence.
Suppose that, for all $m \in \N$:
- $x_m \ne 0$
There exists a total recursive function $\psi : \N \to \N$ such that, for all $m, p \in \N$ and $\alpha \in \R$, if:
- $p \ge \map \psi m$
and:
- $\size {x_m - \alpha} \le \dfrac 1 {p + 1}$
it follows that:
- $\size \alpha > \dfrac {\size {x_m}} 2$
Proof
By definition of computable real sequence, there exists a total recursive $f : \N^2 \to \N$ such that, for all $m, n \in \N$:
- $\dfrac {k_{m,n} - 1} {n + 1} < x_m < \dfrac {k_{m,n} + 1} {n + 1}$
where $\map f {m, n}$ codes the integer $k_{m,n}$.
We define $\psi : \N \to \N$ as:
- $\map \psi m = \map {\mu n} {\size {k_{m,n}} > 1}$
which is partial recursive by:
- Absolute Value of Integer is Primitive Recursive
- Ordering Relations are Primitive Recursive
- Constant Function is Primitive Recursive
- Minimization on Relation Equivalent to Minimization on Function
In order to show that $\psi$ is total, we will show that:
- $\size {k_{m,n}} > 1$
is satsified when $\dfrac 1 {n + 1} \le \dfrac {\size {x_m}} 2$.
We have:
\(\ds \size {x_m}\) | \(\le\) | \(\ds \size {\dfrac {k_{m,n} } {n + 1} } + \size {x_m - \dfrac {k_{m,n} } {n + 1} }\) | Triangle Inequality for Real Numbers | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \dfrac {\size {k_{m,n} } } {n + 1}\) | \(\ge\) | \(\ds \size {x_m} - \size {x_m - \dfrac {k_{m,n} } {n + 1} }\) | |||||||||||
\(\ds \) | \(>\) | \(\ds \size {x_m} - \dfrac 1 {n + 1}\) | Assumption on $k_{m,n}$ | |||||||||||
\(\ds \) | \(\ge\) | \(\ds \size {x_m} - \dfrac {\size {x_m} } 2\) | Proposed inequality | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {\size {x_m} } 2\) | ||||||||||||
\(\ds \) | \(\ge\) | \(\ds \dfrac 1 {n + 1}\) | Proposed inequality |
Therefore, we have:
- $\size {k_{m,n} } > 1$
By Sequence of Reciprocals is Null Sequence:
- $\dfrac 1 {n + 1} \to 0$ as $n \to \infty$
so there is always $n$ sufficiently large so that:
- $\dfrac 1 {n + 1} \le \dfrac {\size {x_m}} 2$
It follows that $\psi : \N \to \N$ is a total recursive function.
$\Box$
We need to show that the result holds for $\psi$.
Let $m, p \in \N$ and $\alpha \in \R$ satisfy:
- $p \ge \map \psi m$
- $\size {x_m - \alpha} \le \dfrac 1 {p + 1}$
We have that:
- $n = \map \psi m$
satisfies:
- $\size {k_{m,n}} \ge 2$
by the definition of $\psi$.
By assumption:
- $\dfrac {k_{m,n} - 1} {n + 1} < x_m < \dfrac {k_{m,n} + 1} {n + 1}$
Work In Progress You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by completing it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{WIP}} from the code. |