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.

  • 3
    $\begingroup$ Exactly. In other words, you're using mathematical induction to prove the statement "$f(n)$ is well-defined" for all natural numbers $n$. $\endgroup$ – Robert Israel Jun 21 '11 at 18:18
  • 3
    $\begingroup$ 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$. $\endgroup$ – Pete L. Clark Jun 21 '11 at 18:19
  • $\begingroup$ For a superb exposition on definition by mathematical induction see Henkin's 1960 Monthly article On Mathematical Induction. $\endgroup$ – Bill Dubuque Jun 21 '11 at 18:28
  • $\begingroup$ Is there a way for me to create a recursive function f(n)=(n+1)! $\endgroup$ – Matt Jun 21 '11 at 18:47
  • $\begingroup$ 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. $\endgroup$ – 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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Bill Dubuque Jun 21 '11 at 18:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.