# Explaining why a function is well-defined

How can I explain that a function is well-defined, if it's defined recursively by specifying $f(1)$, and a rule for finding $f(n)$ from $f(n-1)$?

My reasoning: If the function for $f(n)$ can be derived from $f(n-1)$, then the function must give a unique value for each input, which is part of what being well-defined is. And since I have $f(1)$, then I can prove any other function starting with that one, so it IS well-defined.

-
Exactly. In other words, you're using mathematical induction to prove the statement "$f(n)$ is well-defined" for all natural numbers $n$. –  Robert Israel Jun 21 '11 at 18:18
Your reasoning certainly sounds correct. If you want to prove it formally, you should use induction. That is, you want to show that there is a unique function $f: \mathbb{Z}^+ \rightarrow \mathbb{R}$ (or whatever) satisfying $f(1) = C_1$ (whatever value you've been given) and the given recursion, and you can show that there is a unique way to define $f(n)$ for all $n$ by induction on $n$. –  Pete L. Clark Jun 21 '11 at 18:19
For a superb exposition on definition by mathematical induction see Henkin's 1960 Monthly article On Mathematical Induction. –  Bill Dubuque Jun 21 '11 at 18:28
Is there a way for me to create a recursive function f(n)=(n+1)! –  Matt Jun 21 '11 at 18:47
Defining the factorial function recursively is a bit more difficult, since it cannot be done directly by appealing to the Recursion Theorem (you find yourself needing the function you want to define in the first place); some of the subtleties mentioned spring forth to give trouble. One solution I know involves functions with two variables and then a suitable trick to extract the factorial function from it. Not enough room in a comment to explain it, though, you might want to post a separate question. –  Arturo Magidin Jun 21 '11 at 19:50

"Well-defined" is a somewhat fuzzy term. But here, it seems that you want to ensure that a function that is defined at $1$ and then you have a recursive definition explaining how to obtain $f(n)$ from $f(n-1)$ does in fact lead to a function whose domain is all the natural numbers.

The answer is that this follows from the Recursion Theorem.

Recursion Theorem. Let $X$ be a set, let $a\in X$, and let $g\colon X\to X$ be a function. Then there exists a unique function $u\colon\mathbb{N}\to X$ such that $u(1)=a$ and $u(n+1) = g(u(n))$ for all $n$.

So here, $X$ is the codomain of $f$; $a$ is the value of $f(1)$; and $g$ is the function that corresponds to your rule for finding $f(n)$ from $f(n-1)$. The Recursion Theorem ensures the existence of a function whose domain is all of $\mathbb{N}$ that has the property you want.

The proof of the recursion theorem is by induction. What follows is the argument in Halmos's Naive Set Theory, pages 48-49.

Remember that we can consider a function $\mathbb{N}\to X$ as a set $u$ of ordered pairs $(n,x)$, where for each $n\in \mathbb{N}$ there is an $x$ in with $(n,x)\in u$; and if $(n,x)$ and $(n,y)$ are both in $u$, then $x=y$.

Consider the collection of all relations $A$ between $\mathbb{N}$ and $X$ that contain $(1,a)$, and such that if $(n,x)\in A$, then $(n+1,g(x))\in A$. The collection is nonempty (the total relation satisfies the properties), so we may consider the intersection of all sets in the collection. Call this intersection $u$; we need to show that $u$ is a function defined on all natural numbers.

Let $S$ be the set of all natural numbers $n$ for which there is exactly one element $x$ of $X$ such that $(n,x)\in u$. We show $S=\mathbb{N}$ by induction.

If $1\notin S$, then there exists $b\neq a$ such that $(1,b)\in u$. But then $u-\{(1,b)\}$ still contains $(1,a)$, and if it contains $(n,x)$ then it contains $(n+1,g(x))$; so $u-\{(1,b)\}$ is one of the relations in our collection, which is impossible (since it is properly contained in the intersection of all such relations). So $1\in S$.

Now suppose that $n\in S$; Then there is a unique $x\in X$ such that $(n,x)\in u$. By the properties of $u$, $(n+1,g(x))\in u$. If $n+1\notin S$, then there exists $y\in X$, $y\neq g(x)$, such that $(n+1,y)\in u$. Then consider $u-\{(n+1,y)\}$ and derive a similar contradiction. So $n+1\in S$.

By induction $S=\mathbb{N}$, so $u$ is a function from $\mathbb{N}$ to $X$, as desired.

-
Beware that there are some subtleties that are glossed over in the above sketched proof. See the paper of Henkin I cited above for full details. –  Bill Dubuque Jun 21 '11 at 18:50