# Terminability of an algorithm and existence of an infinite sequence

It is perfectly clear that when the familiar Gram-Schmidt algorithm is performed on a finite set of linearly independent vectors, the algorithm terminates and we get an orthogonal set of vectors. Fine.

Now they apply the algorithm to a countable set of linearly independent vectors in a Hilbert space recursively and get a countable orthogonal set of vectors. But the problem here is that this algorithm will never terminate, hence we cannot get the truly infinite collection of orthogonal vectors in finite time.

And now that I think about it, for any sequence that is defined via recursive relation (e.g. Fibonacci sequence), we shouldn't be able to write down a formal generating function because we don't have the truly infinite sequence!

So my question is: Does there exist an axiom in ZFC that allows me to say that there is truly an infinite collection satisfying the recursive relation?

• Usually such problems can be solved by either power set axiom or replacement axiom (plus axiom of infinity, of course). For example power set gives you the set $\mathbb{R}^{<\omega}$ of all finite real sequences. Consider the subset $Y$ of all finite sequences that start with $0,1$ and satisfy the recurrence relation until wherever they end. Show by induction that $Y$ contains a unique sequence of each length (and therefore if $s\in Y$, any initial segment of $s$ is also in $Y$). Then $\bigcup Y$ is the desired infinite sequence (we regard a function as a set of ordered pairs).
– Lxm
Jun 28 at 16:09

$$\mathsf{ZFC}$$ set theory proves the following theorem:

Let $$X$$ be a set, let $$X^{<\omega}$$ denote the set of all finite sequences of elements of $$X$$ , let $$[n]$$ denote $$\{0,1,2,…,n-1\}$$ for $$n\in \omega$$. Suppose $$g:X^{<\omega}\to X$$ then there exists a unique function $$f:\omega \to X$$ such that $$f(n)=g(f\restriction [n])$$ for all $$n \in \omega$$.

Defining $$g:\mathbb{N}^{<\omega}\to \mathbb{N}$$ as $$0$$ for sequences of length $$0$$, $$1$$ for sequences of length $$1$$, and $$\sigma(n-1)+\sigma(n-2)$$ for sequences, $$\sigma$$, of length $$>2$$. One gets that $$f$$ is the fibonacci sequence.

One can prove the theorem by building partial approximations and then gluing them up together to form a single function. Details can be found in any set theory book, e.g. Jech-Hrbáček, under the name of the "recursion theorem".

Infact $$\mathsf{ZFC}$$ can prove much stronger versions of this theorem, again details can be found in any introductory axiomatic set-theory book.

• The second sentence of the theorem seems incomplete: $g$ should satisfy some hypothesis. Jun 28 at 16:26
• @GregMartin Sorry, I don't understand. I said that $g$ is a function from $X^{<\omega}\to X$. What is incomplete? Jun 28 at 16:28
• Okay, I had misunderstood the statement. I think a more natural hypothesis would be that there are partial functions $f_n\colon[n]\to X$ that satisfy compatibility conditions among them. Jun 28 at 16:48