Proof: (related to "Recursively Defined Arithmetic Functions, Recursion") 

• By hypothesis, $N\in\mathbb N$ is a given natural number.
• It is sufficient to show that the arithmetic function $f:\mathbb N\to\mathbb C$ defined by specifying the value of $f(m)$ for all $m\le N$ and for all $n > N$ with a given recursion formula $f(n)=\mathcal R(f(m)\mid m < n)$ is well-defined (i.e. unique) for all natural numbers.
• Assume, $f$ defined like this is not well-defined for some natural numbers.
  • Because of the well-ordering principle, there is the smallest natural number $N_0\in\mathbb N$ for which $f$ is not well-defined.
  • But then for $m < N_0$ the values $f(m)$ are well-defined and $f(N_0)=\mathcal R(f(m)\mid m < N_0).$
  • This is a contradiction.
• Therefore, $f$ is well-defined for all natural numbers.

| | | | created: 2020-07-12 10:13:27 | modified: 2020-07-12 10:14:29 | by: | references: [977]