1

Sometimes a sequence $(s_n)_{n \in \mathbf{N}}$, where $\mathbf{N}$ is the set of natural numbers, is defined as follows: (a) let $s_0 = ...$; (b) for $n \geq0$ assume that $s_0, s_1, s_2, \dots, s_n$ have already been defined; then define $s_{n+1}$ in terms of$s_0, s_1, s_2, \dots, s_n$ by .....

What is a precise statement of the mathematical theorem justifying that "complete recursion" (an analog of "complete" induction)? Where might one find it stated in the literature along with a proof?

I ask this because so often even the definition of the factorial function is wrongly based upon too weak a theorem. [Justifying the usual definition requires not "ordinary" recursion, but rather "primitive recursion" — start with a set $X$, an element $c \in X$, and a function $G : X \times \mathbf{N} \rightarrow X$; then the theorem on primitive recursion asserts the existence of a unique function $f : \mathbf{N} \rightarrow X$ such that $f(0) = c$ and, for each $n \in \mathbf{N}$, $f(n+1) = G(n, f(n))$.]

The issue is mainly being able to say what kind of function or relation replaces such $G$ when one is dealing with a "function" that has a variable number of arguments.

Here's an attempt at such a thorem. Is this valid? And is there some place specific in the literature where it appears?

Theorem. Let $X$ be a set, let $c \in X$, and let $G : \bigcup_{n=1}^{\infty} X^{n} \rightarrow X$ be a given map (where $X^{n}$ denotes the $n$-fold Cartesian product of $X$ with itself). Then there is a unique map $f : \mathbf{N} \rightarrow X$ such that $f(0) = c$ and, for each $n \in \mathbf{N}$, we have $f(n+1) = G(f(0), f(1), f(2), \dots, f(n))$.

murray
  • 778
  • 3
  • 16
  • What's $f_{n+1}$ in your first paragraph? Am I right in assuming that you would be happy with a theorem justifying that $f(n)=G(n,f\upharpoonright n)$ is a way to define a function $f:\mathbb N\rightarrow\mathbb N$? In this case, you can find a proof in (for example) Kunen's Set Theory book. I guess you can also look at Jech's set theory book or many others. – martin.koeberl Mar 18 '17 at 01:09
  • I'm not sure I get the differences between primitive, ordinary and complete recursion. Is primitive stronger than ordinary? – martin.koeberl Mar 18 '17 at 01:10
  • The theorem on "Primitive" recursion can be proved as a consequence of the theorem on "ordinary" recursion. Primitive recursion is used (typically, only implicitly) to define the factorial function recursively; the reason is that $(n+1)!$ depends not just upon $n!$ but also upon $n$ [the set $X = \mathbf{N}$ and the function $G : \mathbf{N} \times X \rightarrow X$ is multiplication]. – murray Mar 18 '17 at 15:13
  • @martin.koebert: in the original post, $f_{n+1}$ should have been $s_{n+1}$; typo has been fixed. – murray Mar 18 '17 at 15:21
  • @martin.koebert: In your 1st comment, does $f \upharpoonright n$ mean the $n$-tuple $(f(0), f(1), \dots, f(n-1))$? If so, then that's what I need. – murray Mar 18 '17 at 15:35
  • Your theorem looks good. To prove it, note first that there is such a thing just satisfying the theorem for $n\leq 0$ (the function with domain ${0}$ mapping $0$ to $c$, and then prove that if a function $s:n\rightarrow X$ ($n$ is the set of all natural numbers less than $n$) satisfies the Theorem up to $n$, then there is a unique continuation to $\bar s:n+1\rightarrow X$ satisfying the Theorem. (By explicitly constructing it using $s$ and $G$.) By induction, it follows that this partial recursive function is unique for every $n$. We can take the union of these to get the desired $f$. – martin.koeberl Mar 18 '17 at 16:30
  • @martin.koebert: The basic idea of the proof outline looks the same as for proving the theorem on ordinary recursion (for a map $f : \mathbf{N} \rightarrow X$), namely, to get the partial functions and then taker their union, – murray Mar 19 '17 at 00:41
  • Yes, and that idea works because it's not really stronger. See my answer for a different approach. – martin.koeberl Mar 19 '17 at 02:59

1 Answers1

1

I claim that complete recursion is not more powerful than ordinary recursion. To see this, I'll use ordinary recursion to prove the theorem about complete recursion.

So suppose $G:X^{<\omega}\rightarrow X$, for some set $X$, and $c\in X$ are given. We want to find a function $f\colon\mathbb N\rightarrow X$ such that for all $n\in\mathbb N$: $$ f(n+1)=G(f\upharpoonright n),$$ (where $f\upharpoonright n$ is the restriction of $f$ to a function with domain $n=\{0,1,\dots,n-1\}$ (and $0=\emptyset$)).

To do this, let $Y=X^{<\omega}$ and define $G':Y\rightarrow Y$ by $$G'(x_1,\dots,x_n)=(x_1,\dots,x_n)^\smallfrown G(x_1,\dots,x_n),$$ (where $^\smallfrown$ denotes concatenation of sequences). Now, define $f':\mathbb N\rightarrow Y$ by ordinary recursion so that $f'(0)=(c)$ (that is, a tuple of length $1$ with coordinate $c$) and for $n\in\mathbb N$: $$f'(n+1)=G'(f'(n)).$$

We now have to see how to get our desired $f$ from $f'$. I will prove by induction that if we define $f(n)$ to be the last coordinate of $f'(n)$, then $f$ is as desired, so $f(0)=c$ and $f(n+1)=G(f\upharpoonright n)$ for all $n\in\mathbb N$.

We show something stronger, namely that for all $n\in\mathbb N$ we have that $$f'(n)=f\upharpoonright n+1.$$ This is obvious for $n=0$. Assume it holds true for some $n$ and note that $$ f'(n+1)=G'(f'(n))=G'(f\upharpoonright n+1)=(f\upharpoonright n+1)^\smallfrown G(f\upharpoonright n+1)=f\upharpoonright n+2,$$ where the first equality follows from the definition of $f'$, the second by induction hypothesis, the third by definition of $G'$ and the last by definition of $f$. Thus, by induction, the above representation of $f'(n)$ is proved.

Now, it is easy to see that $f$ is as desired: $f(0)=c$ by definition and that $f(n+1)=G(f\upharpoonright n)$ for all $n\in\mathbb N$ can be seen from above equation.

EDIT: Sorry, I forgot to say anything about uniqueness. The proof for this is (I imagine) the same as for the ordinary recursion theorem. If you had two functions $f,g$ both satisfying the recursive definition, note that there'd be a least place $n$ where they differ. Now, $n\neq 0$ because $f(0)=c=g(0)$. Thus $n>0$ and $f\upharpoonright n=g\upharpoonright n$. But we then have $f(n)=G(f\upharpoonright n)=G(g\upharpoonright n)=g(n)$, contradicting the assumption that there were two such functions. (You can also prove by induction that $f\upharpoonright n=g\upharpoonright n$ for all $n\in\mathbb N$.)

martin.koeberl
  • 914
  • 6
  • 13
  • Yes, I do already know that complete recursion (and, for that matter, primitive recursion) are consequences of ordinary recursion. It's just that, for mathematical proofs, one wants to have a formally stated theorem that accords with the way recursion is so often used informally (i.e., "Suppose that $s_0, s_1, \dots, s_n$ have already been constructed. Then define $s_{n+1}$ by ... ." – murray Mar 19 '17 at 22:18
  • Well, your question says statement and proof. You already have the statement in your question. Also you say the definition of the factorial function is based on a too weak theorem. Not really true, because one implies the other. Also, if you don't know the statement, how can you that it is implied by another theorem? I'm confused about what you're looking for. – martin.koeberl Mar 19 '17 at 22:58
  • I don't know the meaning of the "small frown" symbol in $G'(x_1,\dots,x_n)=(x_1,\dots,x_n)^\smallfrown G(x_1,\dots,x_n)$. (And I've seldom seen before the up-harpoon that you're using for restriction, which most often in the literature, at least outside of set theory itself, is denoted just by a vertical bar, with the subset to which the function is restricted as a subscript.). – murray Mar 19 '17 at 23:26
  • Well, in set theory it's really common, and that's the area I'm working in. The small frown stands for concatenation of sequences, for example, $(2,0)^\smallfrown (3,5)=(2,0,3,5)$. Also, throughout the proof I'm identifying functions with domain $n$ for some natural number, with sequences of the same length, enumerating the range. For example $(2,0)$ is identified with the function $f$ having domain ${0,1}=2$ and $f(0)=2$ and $f(1)=0$. – martin.koeberl Mar 20 '17 at 00:31
  • @martin.koebert: Thanks for the clarification about small frown; it had to be that, from the context, but I needed to check. I've seen the small frown used for textual concatanation, i.e., juxtaposition of strings, but not for such ordered tuple concatenation. (At least this many years later I don't recall seeing it in places where I first learned set theory, including Bourbaki, Gödel, Suppes, Halmos, Bernays, Kelley's "General Topology" appendix.) – murray Mar 20 '17 at 02:56
  • 1
    I''m a bit embarrassed to find the theorem I stated, along with copious hints for a proof exactly like the one in the accepted answer, appears as an exercise in a book I wrote 45 years ago! – murray Mar 20 '17 at 19:06
  • May I ask what is $X^{<\omega}$? I don't see you define $X^{<\omega}$ in your proof. – Akira Sep 07 '18 at 03:05