Reciprocal of Computable Real Sequence is Computable/Lemma

From ProofWiki
Jump to navigation Jump to search

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:


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.


Retrieved from "https://proofwiki.org/w/index.php?title=Reciprocal_of_Computable_Real_Sequence_is_Computable/Lemma&oldid=650639"