If a uniquness for all functions exist shouldn't there be uniquness to recursion?

Question

What I'm specifically saying is every function is definitely unique, as they may be nearly equivalent to another function, for example.

Let's make a table of values for $^{x}2$

(0,1) (1,2) (2,4) (3,16) (4,65536)

The recursive relation is of course, $a_2=2^{a_1}$, if $^{x}2$ is described as this recursively is it possible to describe these points in others ways that don't simplify to $a_2=2^{a_1}$

This may sound obvious, but if every function is unique analytically, than is a recursive function unique.

So does $^{x}2$ have a unique recursive function, or are there other ways of describing it recursively,without simplifiying it to $a_2=2^{a_1}$?

I'm having trouble explaining this, hopefully this could be clarified!

Answer 1

I think I know what you're trying to say, but I'm also not sure if it is possible to say with any rigor. I think that you essentially want to essentially know whether "simplification" is in some sense "complete": so that if two recurrence relations which appear in different forms always give the same outputs given the same inputs, then they can both be simplified down to a single, "standard" form.

---

There is a weaker statement of your question which is answerable.

If two functions appear different but always give the same outputs for the same inputs, then is it true that the two functions are always equal?

The answer to this question is yes. There is nothing particularly deep about this fact; in fact it is simply a consequence of the definition. [Warning: this definition is very technical. If you want to understand it completely you should read the last line first, and then the rest in order, very slowly.]

We say the ordered triple $(D,C,R)$ is a function if

• $R$ is a relation from $D$ to $C$, that is, $R$ consists of ordered pairs $(d,c)$ such that $d\in D$ and $c\in C$.
• $R$ is total, that is, for any $d\in D$ there is a $c\in C$ such that $(d,c)\in R$
• $R$ is single-valued, that is, for any $d\in D$, there is not more than one $c\in C$ such that $(d,c)\in R$.

For ease of reading, we give the function a name $f$, and write $f(d)=c$ instead of $(d,c)\in R$.

The point of this definition is that the form of the function is totally irrelevant: the only thing that matters is the input-output pairs.

I will briefly address something which I have been sidestepping thus far about your question. Recursion, so long as each step is uniquely specified [i.e. you're not solving for, say, $a_7$ using anything like $(a_7)^2=a_6$] is no more powerful than function notation. And if each step is not uniquely specified, you have bigger problems :)

By this I mean: recursion takes every natural number and (somehow) turns it into a number in the reals. This is an operation that is completely captured by the formal definition of a function. That is why I have shifted from recursive language to functional language. From this abstract perspective, there is no difference at all.

---

However, the question you actually asked is much, much, much harder. For instance, consider the following special case of your question:

Suppose $f(x)= x+\displaystyle\max_{\zeta(s)=0}\Re(s)$, where $\zeta(s)$ is the analytic continuation of $\displaystyle \sum_{k=0}^\infty \frac{1}{k^s}$. Is this function equal to $f(x)=x+\frac12$?

This question is equivalent to the Riemann Hypothesis, a century-old unsolved problem with a million dollar bounty for its proof.

You may notice I am still using functional language, although we have descended from the lofty place we were before. This is because from an algorithmic viewpoint, functions are a special case of recursion. Given any function, you can write $a_n=f(n)$; this is a zeroth-order recurrence relation. The point is that even in the function case— at the zeroth level of complexity— the question is still impossibly hard.

(In fact, nearly every unsolved problem in mathematics can be "turned into" a function in a similar way— although some would require a lot more cleverness than others.)

---

If questions about algorithms, reducibility, and fundamental complexity really turn you on, you might be interested in Descriptive Set Theory. If your question has any satisfying answer, it'll probably be found there. Fair warning, a lot of DST is very technical. If you want to go this route you might consider asking another question looking for a reference. I would give you one myself, but I have not in the field much, and so I don't know what books would be accessible to beginners.

Answer 2

Any relation that produces this sequence can of course be 'ultimately' simplified to $a_{n+1}=2^{a_n}$ just because this is how consecutive elements in the sequence are related. You do not however specify which identities are 'allowed' in a simplification. There are analytic functions that vanish on all integers, $\sin(\pi x)$ for example, so $a_{n+1}=2^{a_n}+\sin(\pi a_n)$ will produce the same sequence because all $a_n$ are integers, but as functions $2^x$ and $2^x+\sin(\pi x)$ do not reduce to each other. Also, in general there is no algorithm to determine if two analytic expressions represent the same function, or can be reduced to each other based on a given list of identities.