# Thread: Understanding a "Proof that recursion defines a function"

1. ## Understanding a "Proof that recursion defines a function"

Proof that recursion defines a function (from: Recursive definition - Wikipedia, the free encyclopedia)

Suppose one has a pair of functions f and g on the natural numbers such that f(0)=0 and f(n+1)=g(f(n)) for all n. We want to construct, for any natural number n, a subset F(n) of N x N such that:

(1) for all natural numbers a between 0 and n: there exists a unique natural number b such that (a, b) is in F(n);

(2) (0, f(0)) is in F(n);

(3) for all natural numbers a, where a is between 0 and n-1: if (a, f(a)) is in F then (a+1, g(f(a))) is in F(n).

Clearly {(0, f(0))} satisfies (2) and (3).

Suppose these properties hold for n. Consider F(n+1)=F(n)U{(n,g(n))}. Then this set satisfies all 3 properties (1), (2), (3). By induction we have such a set for any natural number n. Let F be the set theoretic union of all the F(n), where the union is taken over all natural numbers n.

---
After pondering a good while here is my interpretation of the proof. I state my case positively not because I am certain that I am right but because I want to clear about what I think.

So what we want is to define a function f that delivers a particular subset F(n) of N x N. It would be nice to have a “regular function” like f(n) = 2n but instead we are being given a recursive function defined by f(0)=0 and f(n+1)=g(f(n)).

Unfortunately it took me a long time to comprehend the meaning of that last statement. I now believe that what it says is … what it says … that f(n) is defined recursively by a base value f(0)=0, and a function g which delivers a next value of “f”, f(n+1), as a function of a previous value of “f “, f(n), that is f(n+1) = g(f(n)). Where does the value of f(n) come from? … from a recursive iteration of values starting from a base case, in this instance, f(0+1) = g(f(0)).

It took me a while to realize that a regular function f(n) can be replaced by a recursive function f(n) but to do so you must come up with a base value and a suitable unique function g(n) that does the job of correctly delivering f(n+1) as a function of f(n). Comprehending g(f(n)) was a real revelation.

I don’t believe there is any set way of finding g(n) for a given regular function f(n), or for a set F(n) subset of N x N, but once you have a candidate a proof by induction allows you to see if it works.

Now, I believe that not all subsets of N x N can be defined recursively (probably not “regularly” either – is there another name for a “regular” function?) so F(n) must have certain properties .

(1) for all natural numbers a between 0 and n: there exists a unique natural number b such that (a, b) is in F(n);

This says that every element “a” of f’s domain set must have a unique correspondent “b” in f’s codomain. Note that while all values of f’s domain set must have a corresponding value in the codomain, not all values in the codomain need be the correspondent of a value in the domain set, i.e. the range set will often be a proper subset of the codomain but can equal to the codomain.

(2) (0, f(0)) is in F(n);

This is just the given base case.

(3) for all natural numbers a, where a is between 0 and n-1: if (a, f(a)) is in F then (a+1, g(f(a))) is in F(n).

This is just f(0)=0 and f(n+1)=g(f(n)), used to generate the ordered pairs of F(n). The domain is restricted on the lower end as greater than 0 because there is no defined precursor of 0 to apply to g. The domain is restricted at the higher end because (n-1) is the argument that must be applied to g if it is to return a value for f(n).

Clearly {(0, f(0))} satisfies (2) and (3).

(2) is clearly satisfied, (3) is apparently satisfied not to be bothered since 0 is not between 0 and n.

Suppose these properties hold for n. Consider F(n+1)=F(n)U{(n,g(n))}. Then this set satisfies all 3 properties (1), (2), (3). By induction we have such a set for any natural number n. Let F be the set theoretic union of all the F(n), where the union is taken over all natural numbers n.

Assuming the three properties hold, i.e.

(1) that for any natural number greater than 0 and less than n there exists a unique f(n),

(2) that for n = 0 specifically, f(0) exists

(3) that a function g(n) exists such that f(n+1)=g(f(n)), so that when (a, f(a)) is in F then (a+1, g(f(a))) is in F(n),

.... granting those properties .... by induction F(n) is a set defined by recursion.

Induction itself is justified foundationally by a recursive union of sets expressed by F(n+1)=F(n)U{(n,g(n))}.

F(n+1) is the set of ordered pairs comprising F(n) in union with the next/successive ordered pairs defined by (n, g(n)) and reduced to a set theoretic union (a set comprised of all of the elements found within the recursively generated sets comprising F(n)U{(n,g(n))} ).

Hopefully I have this explanation correct because this understanding the role of g(n) with respect to f(n) in particular seems to make many things much more clear.

2. ## Re: Understanding a "Proof that recursion defines a function"

Do you understand what "defines a function" means? In order that "f" be a function it only be necessary that a given value of "a" produce a single value of f(a). $x^2+ y^2= 25$ does NOT "define a function" by y= f(x) because if x= 3, y can be either 4 or -4: $3^2+ 4^2= 9+ 16= 25$ and $3^2+ (-4)^2= 9+ 16= 25$.

But if you are given a function g(x) and then say that f(0)= a and then f(n+1)= g(f(n)), we see:
1) f(0)= a is a given specific number. If we claim that, also, f(0)= b, we can immediately assert, from the definition, that b= a.

2) Suppose that, for some integer k, f(k) is a specific, given number, say f(k)= m. Then f(k+1)= g(f(k))= g(m). Since g is a function, g(m) is a specific number and, therefore, so is f(k+1).
By induction those two statement show that f(n) is a specific number for any positive integer, n.

For example, suppose we define f(0)= 3 and $g(x)= x^2- 2$. Then f(1)= g(f(0))= g(3)= 9- 2= 7, f(2)= g(f(1))= g(7)= 49- 2= 47, f(3)= g(47)= 2207, etc. What ever n is, we keep repeating that until we reach f(n). At each step we are applying g to a specific number and, since g is a function, get a specific number as a result. Eventually we get to the specific number that is f(n).

3. ## Re: Understanding a "Proof that recursion defines a function"

Thank you Hallsof Ivy. I believe I get the picture.

I do understand what a function is ... essentially a "relation" that passes the vertical test, each object in the domain set corresponds to only one element in the codomain.

My questions have never been about how to use PMI on proving basic problems like:

Prove:

1 + 2 + 3 + .... + n = 1/2(n(n+1), or

If h > -1, prove (1+h)n = 1 + h

I can, with greater or lesser ingenuity, do problems like that.

My original question was on how a fundamental theorem defined addition:

Proving a fundamental Theorem using PMI

Responses to that inquiry led to illuminating posts but ones that were pushing my limits of how to comprehend, the terse, precise notation of higher level mathematics. (That is OK, I dig in.)

Anyway, I failed to connect the abstract notation with the essence of using PMI for such problems as I stated above.

The interpretation of the proof outlined in this post is an attempt to connect what I know of solving basic PMI problems with the abstract propositions used to establish PMI and the basic theorems used to establish the basis of mathematics.

It might have been helpful to say that, on my own, I am trying to fill in gaps in my math education by reading Bruce Merserve’s book “Fundamental Concepts of Algebra” . Sorry.

Your post confirms concretely what I finally have come to understand abstractly, thank you again. I am going to try and work my way back through the posts of Devenco and Johng to my original question and see if it is still a question. Good day.

4. ## Re: Understanding a "Proof that recursion defines a function"

Your questions are good ones, and the answers are not quite as simple as one might hope.

First off, your concerns are essentially "foundational" in nature: if we are going to build "a place where mathematics starts", we have to decide "which tools we're allowed to use". The short, pithy answer to this, is Zermelo-Fraenkel set theory (usually with "The Axiom of Choice", often called ZFC for short), and a second-order logic (first order logic doesn't posses the "quantification strength" of second-order logic, so it's more cumbersome when we start to deal with sets of functions, which is desirable in, for example, calculus).

Some mathematicians feel we are on "safer ground" with a first-order logic approach, things begin to get wonky when talking about the subsets of infinite sets, and our intuitions cannot always be trusted. However, certain mathematical statements such as:

The real numbers, up to isomorphism, form the only complete archimedean ordered field.

require second-order logic to even be true, as the least upper bound property (completeness) requires second-order logic to even formulate (the closest statements one can make in first-order logic are satisfied by an entire class of fields, called real-closed fields). Without going too much into what all this "really means", suffice to say first-order logics lack a certain "expressive power" to say things we can still conceive of as being "intuitively true".

Most logic systems, even in the teaching of mathematics, are presented "informally", by relating them to similar concepts in "natural language". So "and" is used instead of the formal "$\wedge$", and "or" (non-exclusive) is used instead of the formal "$\vee$". That is, an attempt is made to establish an informal correspondence between the formal apparatus of logic, and "the way we think and talk". One is expected to INTERNALIZE this correspondence, so that when one writes one's internal thoughts to communicate them to others, one's intended meaning is unambiguous.

For example, in (some) formal logic(s) $p \vee \neg p$ is a tautology (theorem that is always true, regardless of $p$), in normal language we say: "either something is the case, or something is not the case".

***********************

I mention all this (and really, it's not 100% accurate, or even all that detailed) to indicate that "the machinery behind the curtain", that we use in proofs in mathematics, is itself rather complex, and there are actually MANY possible ways we might go about deciding what "the atoms of truth" are. The mere statement of the rules sets (and thus functions, relations, subsets, and the whole nine yards) must follow (in the "standard formulation") are bizarrely intricate, and non-intuitive. In practice, most mathematicians settle for a "naive view", where exactly what sets are isn't gone into, but various ways we can manipulate them are well-understood (and certain entities are taken as "established" to be sets, such as the natural numbers, for example), so we can talk about unions, intersections, subsets and power sets intelligently.

**********************

Ok, so the natural numbers started out as something we abstracted from counting things. It is likely that we actually began distinguishing amounts by comparison: "your pile is bigger than mine". When comparing similar things (such as apples), one is "the smallest difference". In many, many cultures, this is symbolized by a plain-looking mark, such as:

|

Now one could just indicate "larger amounts" by making "more symbols":

||, |||, ||||, etc.

but this gets cumbersome. It is more efficient to create "an address" for a number, like 321 which is "three of hundreds, two of tens, and one left over". Again this is just a "symbol" representing a "group of symbols" representing "a number of objects".

The problem lies, not in creating "names" for numbers (this is fairly easy to do, and almost every culture can name an arbitrarily large natural number), but in deciding how to talk about ALL (natural) numbers, all at once. For what we wish to do, is establish rules of computation, that are as general as possible (if I add 2 and 3, and you add 2 and 3, we want our answers to be "the same", with perhaps a "translation factor" of symbology involved). We want arithmetic to be portable, reliable, and communicable.

There are indeed, several ways we might begin to go about this. Intuitvely, though, since we often use numerals to "tag" collections (the first elephant, the second elephant, the third...), we might want natural numbers to form some kind of "distinguished" collection (like an ordered collection of things from which we have abstracted away the "thingness"). If this is agreed-upon, we at least have a place to start:

A set $N$.

This set is (begins as) ordered: we have a "beginning" number, and for each number, a "next" number. It really doesn't matter if we take the ORDER as given, and then define a successor number by the order, or if we take the successor function as given, and define the order by IT, we get to the same place, at the end.

Furthermore, it's not just (totally, or LINEARLY) ordered, it's "well-ordered": every subset has a "bottom" (a least element under the order). Again, I want to stress that there's no point in "proving" this, it's where we START. This is taken "axiomatically" as true (it is equivalent to the PMI, since each can be used to prove the other). So, you can have your choice: start with a (minimal) well-ordered infinite set, or a minimal inductively-defined set (for which induction is atuomatically true), each choice will give you the other.

We call the minimal element of all of $N$, 0 or 1 (depending on whose idea of the natural numbers you're using, I'll use 0 in this example). The minimal element of $N - \{0\}$ is then called the successor of 0. And so on. I leave it to you to decide if this defines a function from $N$ to $N - \{0\}$, and whether or not this function is 1-1, and onto.

Conversely, if we HAVE such a successor function, we can define an order by:

$0 < k$ for all $k \in N - \{0\}$ (*)

$s(k) < s(m)$ if and only if $k < m$. (**)

For example, to show $s(s(0)) < s(s(s(0)))$, note by (**) we have $s(0) < s(s(0))$, and again $0 < s(0)$, so this is true. It is rather tedious to show this is actually an order (you can try to do this if you want), and even more tiring to show it is a well-ordering.

**********************************

You might enjoy reading this: http://www.ling.ohio-state.edu/~poll.../induction.pdf

Which outlines a somewhat different approach than what you are reading.

5. ## Re: Understanding a "Proof that recursion defines a function"

Thank you Deveno for your detailed response you can be sure that I read it closely and have included it in my set of math notes. Below are some notes and comments (in red). Thanks again.

Re: Understanding a "Proof that recursion defines a function"
Your questions are good ones, and the answers are not quite as simple as one might hope.

First off, your concerns are essentially "foundational" in nature: if we are going to build "a place where mathematics starts", we have to decide "which tools we're allowed to use". The short, pithy answer to this, is Zermelo-Fraenkel set theory (usually with "The Axiom of Choice", often called ZFC for short), and a second-order logic (first order logic doesn't posses the "quantification strength" of second-order logic, so it's more cumbersome when we start to deal with sets of functions, which is desirable in, for example, calculus).

Mnemonic: foundation, ZFC vs 2nd order logic, 2nd vs 1st order logic

Some mathematicians feel we are on "safer ground" with a first-order logic approach, things begin to get wonky when talking about the subsets of infinite sets, and our intuitions cannot always be trusted. However, certain mathematical statements such as:

The real numbers, up to isomorphism, form the only complete archimedean ordered field.

require second-order logic to even be true, as the least upper bound property (completeness) requires second-order logic to even formulate (the closest statements one can make in first-order logic are satisfied by an entire class of fields, called real-closed fields). Without going too much into what all this "really means", suffice to say first-order logics lack a certain "expressive power" to say things we can still conceive of as being "intuitively true".

Memonic: Limits of 1st order logic

Most logic systems, even in the teaching of mathematics, are presented "informally", by relating them to similar concepts in "natural language". So "and" is used instead of the formal "∧", and "or" (non-exclusive) is used instead of the formal "∨". That is, an attempt is made to establish an informal correspondence between the formal apparatus of logic, and "the way we think and talk". One is expected to INTERNALIZE this correspondence, so that when one writes one's internal thoughts to communicate them to others, one's intended meaning is unambiguous.

For example, in (some) formal logic(s) p∨¬p is a tautology (theorem that is always true, regardless of p), in normal language we say: "either something is the case, or something is not the case".

I have some understanding of ZFC from spending time earlier this year reading over and researching a .pdf found on the internet.

“FUNDAMENTALS OF ZERMELO-FRAENKEL SET THEORY, by TONY LIAN. I didn’t understand everything but enough to know what you are saying.

Regarding 1st vs 2nd order logic, the following allows me to at least peek over the window sill, and that is enough for now.

(From wikipedia) Mathematical induction as an inference rule can be formalized as a second-order axiom. The axiom of inductionis, in logical symbols, where P is any predicate and k and n are both natural numbers.

In words, the basis P(0) and the inductive step (namely, that the inductive hypothesis P(k) implies P(k + 1)) together imply that P(n) for any natural number n. The axiom of induction asserts that the validity of inferring thatP(n) holds for any natural number n from the basis and the inductive step.

Note that the first quantifier in the axiom ranges over predicates rather than over individual numbers. This is a second-order quantifier, which means that this axiom is stated in second-order logic. Axiomatizing arithmetic induction in first-order logic requires an axiom schema containing a separate axiom for each possible predicate. The article Peano axioms contains further discussion of this issue.

***********************

I mention all this (and really, it's not 100% accurate, or even all that detailed) to indicate that "the machinery behind the curtain", that we use in proofs in mathematics, is itself rather complex, and there are actually MANY possible ways we might go about deciding what "the atoms of truth" are. The mere statement of the rules sets (and thus functions, relations, subsets, and the whole nine yards) must follow (in the "standard formulation") are bizarrely intricate, and non-intuitive. In practice, most mathematicians settle for a "naive view", where exactly what sets are isn't gone into, but various ways we can manipulate them are well-understood (and certain entities are taken as "established" to be sets, such as the natural numbers, for example), so we can talk about unions, intersections, subsets and power sets intelligently.

Yes, with some understanding of where the bottom lies I now feel comfortable focusing on the “naïve view”development of basic properties based on Peano’s axioms. Thanks for your help and explanation.

**********************

Ok, so the natural numbers started out as something we abstracted from counting things. It is likely that we actually began distinguishing amounts by comparison: "your pile is bigger than mine". When comparing similar things (such as apples), one is "the smallest difference". In many, many cultures, this is symbolized by a plain-looking mark, such as:

|

Now one could just indicate "larger amounts" by making "more symbols":

||, |||, ||||, etc.

but this gets cumbersome. It is more efficient to create "an address" for a number, like 321 which is "three of hundreds, two of tens, and one left over". Again this is just a "symbol" representing a "group of symbols" representing "a number of objects".

The problem lies, not in creating "names" for numbers (this is fairly easy to do, and almost every culture can name an arbitrarily large natural number), but in deciding how to talk about ALL (natural) numbers, all at once. For what we wish to do, is establish rules of computation, that are as general as possible (if I add 2 and 3, and you add 2 and 3, we want our answers to be "the same", with perhaps a "translation factor" of symbology involved). We want arithmetic to be portable, reliable, and communicable.

Memonic: Comparison, symbolic equivalence, generation of names, talking about the whole set of number symbols, universal rules for computation.

There are indeed, several ways we might begin to go about this. Intuitvely, though, since we often use numerals to "tag" collections (the first elephant, the second elephant, the third...), we might want natural numbers to form some kind of "distinguished" collection (like an ordered collection of things from which we have abstracted away the "thingness"). If this is agreed-upon, we at least have a place to start:

A set N.

This set is (begins as) ordered: we have a "beginning" number, and for each number, a "next" number. It really doesn't matter if we take the ORDER as given, and then define a successor number by the order, or if we take the successor function as given, and define the order by IT, we get to the same place, at the end.

The natural/counting numbers, the set AND its order, are granted as a seminal point of comprehension. It seems most honest to me to recognize this primacy and define a successor function as a property but I see doing the reverse gives an equivalent result.

Furthermore, it's not just (totally, or LINEARLY) ordered, it's "well-ordered": every subset has a "bottom" (a least element under the order). Again, I want to stress that there's no point in "proving" this, it's where we START. This is taken "axiomatically" as true (it is equivalent to the PMI, since each can be used to prove the other). So, you can have your choice: start with a (minimal) well-ordered infinite set, or a minimal inductively-defined set (for which induction is atuomatically true), each choice will give you the other.

(From Wikipedia)

A totally ordered set is said to be well ordered (or have a well-founded order) iff every nonempty subset of has a least element. …

Every non-empty well-ordered set has a least element. Every element s of a well-ordered set, except a possible greatest element, has a unique successor (next element), namely the least element of the subset of all elements greater than s. - Wikipedia

Me. For example , given the set (1, 2, 3, 4, 5) the successor to (1, 2) is the least element of (3, 4, 5).

We call the minimal element of all of N, 0 or 1 (depending on whose idea of the natural numbers you're using, I'll use 0 in this example). The minimal element of N−{0} is then called the successor of 0. And so on. I leave it to you to decide if this defines a function from N to N−{0}, and whether or not this function is 1-1, and onto.

I decide that a well ordered infinite set does establish a successor function that IS a one-to- one correspondence, injective and surjective, s:N -> N –{0}

Conversely, if we HAVE such a successor function, we can define a < k for all k ∈ N−{0} (*)

s(k) < s(m) if and only if k < m. (**)

For example, to show s(s(0)) < s(s(s(0))), note by (**) we have s(0) < s(s(0)), and again 0 < s(0), so this is true. It is rather tedious to show this is actually an order (you can try to do this if you want), and even more tiring to show it is a well-ordering.

I am not sure how you would even show let alone prove an order or ordering other than to demonstrate a pattern, which is just what you did with s(s(0)) < s(s(s(0))).

Putting this into a word pattern does give a greater “comprehension” but quickly becomes untenable. A word pattern might be (and you could probably define it in terms of copy and paste operations):

The successor to the base is less than the base by definition , the successor to the successor of the base case is less than the successor to the base case by induction, the successor to the successor of the successor of the base case is less than the successor to the successor of the base case by induction, the successor to the successor of the successor to the successor of the base case is less than the successor to the successor of the successor to the base by induction …

If I even kept that much straight.

**********************************

You might enjoy reading this: http://www.ling.ohio-state.edu/~poll.../induction.pdf

Which outlines a somewhat different approach than what you are reading.

I am looking at your reference but to be honest I think my main concentration is going to be to take what I have learned about the foundations of math and the meaning of a successor function and recursion and try and advance farther into understanding how to prove some of the basic theorems establishing the fundamental properties of numbers so that I can advance into understanding the theory of polynomials and equations, the next chapters in Merserve’s book.

Thank you for your help and your lengthy labor. Good day

6. ## Re: Understanding a "Proof that recursion defines a function"

Indeed, one can "get lost" in the natural numbers, studying ways they might be a little different if we change our assumptions about them. The main things to take away from this are:

1. One can form a set which "acts" like how we "think" about natural numbers.

2. On this set, induction is a valid form of proof.

3. This set can be used to define functions recursively (that is, we get a complete description a function from an inductive definition).

4. It is possible to define an addition, and a multiplication such that:

4a) Addition is associative and commutative.

4b) Addition possesses an identity (zero).

4c) Multiplication is associative and commutativite.

4d) Multiplication possesses an identity (one).

4e) Multiplication distributes over addition (a(b+c) = (ab) + (ac)).

The properties (4) (which can be proven using (2) and (3)) form the basis for creating other mathematical structures which we have long been familiar with: the integers, the rational numbers, polynomials, and the real numbers. This entire thread is in essence a justification as to why the (4)'s are reasonable.

There is another property (the Archimedean property) which is *not* a consequence of the (4), but *does* follow from (2): for every natural number $n$, there is another natural number $k$ such that $n < k$. Basically this says this order means we don't have "clusters" of natural numbers indistinguishably close (via the order), nor "infinitely large" natural numbers, it's a kind of "uniformity" condition. The need for this becomes more apparent when we start talking about "approximation", which turns out to be a rather subtle concept.

Regarding your "word-pattern" analogy: formally, a procedure for evaluating the truth of a statement, is an algorithm. What I am saying, with my definition of the order, is that the algorithm that decides:

"Is $k < n$?"

TERMINATES (for any pair $k,n$), and never "loops forever". To prove this, of course, we must use the inductive nature of the successor function.

I wish you luck in your continued exploration: the study of equations is one of the oldest, and most fruitful, fields of knowledge humanity has ever embarked upon.

7. ## Re: Understanding a "Proof that recursion defines a function"

Thanks for the outline and the point about using induction to prove that a recursive formula is not cyclic. I have learned much.

8. ## Re: Understanding a "Proof that recursion defines a function"

Rereading all of these responses a week later yields further insights, I expect the same things will happen next week. Danke.