# Recursive Equations: Satisfiability and Defineability

I'm reading a functional programming book that comes from a very heavy mathematical perspective and I got stuck on trying to understand and expand a statement about recursive equations. It states:

Some systems of recursive equations do not define functions; for example

$f n = f (n + 1)$.

Every constant function satisfies the equations for $f$, but none is defined by it.

Can someone explain and expand this last sentence please?

• My reading of this would be that although every constant function satisfies $f(n)=f(n+1)$, this recursive equation does not lead to a specific constant function. As an example, $f(x)=42$ would satisfy the recursive equation $f(n)=f(n+1)$, but you could not define the function $f(x)=42$ by the recursion $f(n)=f(n+1)$ as this recursion leads to an infinite number of constant functions and not just $f(x)=42$. – Mufasa Feb 23 '16 at 20:36
• @Mufasa, yes this makes sense now. – M.K. Feb 23 '16 at 20:39

It has nothing to do with recursion or functions per se; while $x = 2$ or $3x=0$ "define" numbers (2 and 0 respectively), the equations $0\cdot x=0$, $x=x$ and $0\cdot x=17$ do not (either because no solution exists as in $0\cdot x=17$ or the solutions are not unique).
In your example $f(x)=f(x+1)$, the underlying relation is the "greater than" relation, which is not well founded and indeed no unique solution for that equation exists (as stated all constant functions satisfy the equation) and thus it does not qualify as a "definition".