Question about the Axiom of Dependent Choice

[lugita15]

The Axiom of Dependent Choice, a weaker version of the Axiom of Choice, states that for any nonempty set X and any entire binary relation R on X, there is a sequence (x_n) in X such that x_n R x_n+1 for each n in N.

My question is, what would happen if you restricted the relations to functions, i.e. for any nonempty set X and any function f from X to X, there is a sequence (x_n) in X such that f(x_n) = x_n+1 for each n in N? Would that be equivalent to the Axiom of Dependent Choice, or would it be weaker? If it's weaker, how weak is it? Is it provable in ZF?

Any help would be greatly appreciated.

Thank You in Advance.

 

[Erland]

It is provable in ZF. Prove first by induction that given x in X: for each natural number n, there exists a unique sequence x_0, x_1, x_2,...,x_n such that x_0=x and f(x_k)=x_{k+1} for all k=0,1,..,n-1. By the uniqueness of this, we can take the union of these sequences for all n i N and obtain a sequence of the desired type.

 

[lugita15]

It is provable in ZF. Prove first by induction that given x in X: for each natural number n, there exists a unique sequence x_0, x_1, x_2,...,x_n such that x_0=x and f(x_k)=x_{k+1} for all k=0,1,..,n-1. By the uniqueness of this, we can take the union of these sequences for all n i N and obtain a sequence of the desired type.

If that proof were valid, wouldn't it be trivial to prove the recursion theorem?

 

[Erland]

If that proof were valid, wouldn't it be trivial to prove the recursion theorem?

You mean this theorem?
Since a sequence is the same thing as a function defined on N, your weaker version of ADC is just another way of expressing this theorem, and it can be proved in ZF in the way I indicated. But I just indicated the proof, I wouldn't say it is trivial.

 

[lugita15]

You mean this theorem?

Yes, that's the recursion theorem, although Wikipedia only proves the uniqueness part. The existence part is much harder to prove.

Since a sequence is the same thing as a function defined on N, your weaker version of ADC is just another way of expressing this theorem, and it can be proved in ZF in the way I indicated. But I just indicated the proof, I wouldn't say it is trivial.

Actually, the recursion theorem is only about functions from N to N, not any functions from N to X. But even for that limited case, it still requires a considerably harder proof than your purported proof for the N to X case. See pages 4 and 5 of this link for a proof of the recursion theorem, and see page 2 for an explanation of why your simple proof wouldn't work.

 

[Erland]

Actually, the recursion theorem is only about functions from N to N, not any functions from N to X.

According to the Wikipedia link, the recursion theorem is about functions from N to an arbitrary nonempty set X. The link you gave also uses an arbitrary nonempty set A.

But even for that limited case, it still requires a considerably harder proof than your purported proof for the N to X case. See pages 4 and 5 of this link for a proof of the recursion theorem, and see page 2 for an explanation of why your simple proof wouldn't work.

No, the proof I sketched is valid, but I only gave a sketch. It does not use definition by induction. I can spell it out if necessary.

The author of the paper in the link you gave is right that it is important to distinguish between proof by induction and definition by induction, but he is mistaken about the first proof of the Addition Theorem. He is right that we also need to prove the uniqueness of the function p_n for each n, but, as he points out, this is not hard to fix.

But the other flaw he thinks he sees does not exist. He thinks that definition with induction is used, which is not the case (at least not after the uniqueness is fixed). He has actually foreseen the objection and addresses it at page 3:

I know that some readers would object to this by saying that we are, in the course of our proof by induction, assuming that the set p_n exists. But this is just an attempt to cleverly disguise a definition by induction.

Of course, just saying that it is an attempt to disguise is no valid argument. He also refers to Henkin and Enderton, and I have not read those papers/books, but the author must have misunderstood them. For the objection is valid, and I will spell it in more detail below, but first I want to address what he calls "further evidence" (p. 3.).

He notes that the postulates "0 not in S(N)" and that S is one-to-one are not used in the attempted proof, and says that the recursion theorem in general is false for systems satisfying the induction postulate, but not the two postulates just mentioned. I agree, but this does not mean that the addition theorem does not hold for such systems. In fact, it does, and this actually is proved by the attempted (and correct) proof. This is not so surpricing. For example, it holds for the additive group Z_n, with s(n) defined as n+1, for which the induction postulate holds but not "0 not in S(N)".

To see that definition by induction is not used in the attempted proof, we can rephrase it a little. Let R be the binary relation which consists of all ordered pairs (n,A) such that n ε N and such that A is a function from N to N satisfying (i) and (ii), with A instead of p_n, for this n. This is a well defined binary relation.
Now, let E be the set of all n ε N such that there exists a unique A such that (n,A) ε R. It is then meaningful to try to use induction to prove that E=N. That the attempted proof works for the base case n=0 is not an issue.
The induction hypothesis is that n ε E, that is, there exists a unique A such that (n,A) ε R. We must then prove that then, s(n) ε E, that is, there exists a unique A' such that (s(n),A') ε R. We put A' = {(m,r) ε N × N | r = s(A(m))}. This is a well defined relation, and it is clear that A' is function from N to N and that A'(m)=s(A(m)) for all m ε N. This is precisely the same thing as defining p_s(n)(m)=s(p_n(m)), which is therefore perfectly allowed, contrary to what the author says. Just as the author, we now easily check that A' satisfies (i) and (ii), and conclude that (s(n),A') ε R.
We can also prove that this A' is unique by assuming that there are two functions A' and A'' from N to N satisfying (i) and (ii) for s(n), and then use (i) and (ii) to prove that A'(m)=A''(m) for all m ε N. Thus s(n) ε E.
Now, by induction, E=N. This means that to every n ε N, there is a unique A such that (n,A) ε R. But this means that R is actually a function from N to the set B of all functions from N to N, and we can write R(n)=A instead of (n,A) ε R (n ε N, A ε B). (Actually, R and all the A:s are only graphs of functions, but this is causes no difficulties here.). We can now define a function p: N × N → N, by p(n,m)=R(n)(m). Then, (A) and (B) clearly holds for this p, and the author already proved that this p is unique.

Nowhere in this proof is definition by induction used, so, the author was mistaken about this, and if you want, I can spell out my alternative proof of the recursion theorem so that we see that there is no definitioin with induction there either (although the author's proof of the recursrion theorem is also OK).

EDIT: I think that the author's (Blackburn) confusion is caused by that he thinks that to write p_s(n)(m)=s(p_n(m)), we must assume that we already have a function which maps n to p_n for all n ε N, and that would, of course, be circular. It is not so. At this stage of the proof, we only talk about two functions p_n and p_s(n) for some fixed n, we assume nothing about the existence of such functions for other n, and certainly nothing about a function which maps n to p_n for all n ε N.

In fact, if we note that in the proof above, the proof of the uniqueness of each p_n can be broken out from the induction part of the proof and carried through separately, then the above proof is a special case of the following more general scheme:

Let X be an arbitrary nonempty set, and let a ε X, let R be a relation in (that is, a subset of) N × X, and let g: X → X be a function.
Assume that

i) to each n ε N, there is at most one x ε X such that (n,x) ε R,
ii) (0,a) ε R
iii) For all n ε N and x ε X: if (n,x) ε R, then (s(n),g(x)) ε R.

Then there is a unique function f : N → N such that
a) f(0)=a,
b) For all n ε N, f(s(n))=g(f(n)).

Proof: By induction using a) and b), it is easy to prove that such a function f is unique if it exists.
To prove the existence, we prove that R is such a function. If R is a function with domain N, then it follows from ii) and iii) that it satisfies a) and b), so we must prove that R is such function. By i), R is a function, so it suffices to prove that dom(R) = N. This is done by induction:

By i) (0,a) ε R, so 0 ε in dom(R).
Assume that n ε dom R. We must prove that then, s(n) ε dom(R) also holds.
By the induction hypothesis, there is an x ε X such that (n,x) ε R. Hence, by ii), (s(n),g(x)) ε R, so s(n) ε dom(R).

By induction, dom(R) = N, and the proposition is proved.

And there is no definition by induction in this proof, right?

 

[lugita15]

According to the Wikipedia link, the recursion theorem is about functions from N to an arbitrary nonempty set X. The link you gave also uses an arbitrary nonempty set A.

Yes, you're right (although I think most other statements of the recursion theorem talk about function from N to N)

No, the proof I sketched is valid, but I only gave a sketch. It does not use definition by induction. I can spell it out if necessary.

Yes, I'd be interested in seeing it.

But the other flaw he thinks he sees does not exist. He thinks that definition with induction is used, which is not the case (at least not after the uniqueness is fixed).

Definition of induction IS being used. We're defining p₀ explicitly and then defining p_n+1 in terms of p_n for each n. That is exactly what definition by induction is. and although although definition by induction may seem intuitively clear, it's actually not. There's a subtlety, because you haven't actually defined p_n yet, so you can't define p_n+1 in terms of it.

Of course, just saying that it is an attempt to disguise is no valid argument. He also refers to Henkin and Enderton, and I have not read those papers/books, but the author must have misunderstood them.

No, the author is expressing the standard view in the literature, so if you think it's mistaken, you might want to publish a paper on it. By the way, I've attached the Henkin paper, in case you're interested.

He notes that the postulates "0 not in S(N)" and that S is one-to-one are not used in the attempted proof, and says that the recursion theorem in general is false for systems satisfying the induction postulate, but not the two postulates just mentioned. I agree, but this does not mean that the addition theorem does not hold for such systems. In fact, it does, and this actually is proved by the attempted (and correct) proof.

But the attempted proof uses definition by induction, and how can you justify that without proving the recursion theorem?

And yes, you're right that the addition theorem holds whenever induction holds, but the reason it holds is not because of the attempted proof.

By the way, if you're willing to concede that the recursion theorem isn't true in general for systems that only satisfy induction, then what would you find wrong with the following proof?

Theorem: For any system (N, s, +) satisfying induction, a function F from X to X, and an element B of X, there exists a unique function f: N to X such that f(0) = B and f(s(i)) = F(f(i)).
Proof: Uniqueness is trivial. Let E be the set of natural numbers n such that there is a unique function f_n: {0, ..., n} to X satisfying the conditions specified for i<n. It's obvious that 0 is in E. If n is in E, then let f_n+1 be the composition of F and f_n. Since f_n is well-defined and unique, f_n+1 is also well-defined and unique. Thus n+1 is in E. Therefore, by induction, E = N, and we can define f(n) = f_n(n).

Surely you must object to that proof, right?

The induction hypothesis is that n ε E, that is, there exists a unique A such that (n,A) ε R. We must then prove that then, s(n) ε E, that is, there exists a unique A' such that (s(n),A') ε R. We put A' = {(m,r) ε N × N | r = s(A(m))}. This is a well defined relation

No, it's not. You're defining A' in terms of A. And no, saying that we're assuming in the induction hypothesis that A exists doesn't change things. The point is, we're using a potentially nonexistent object to define A'. Henkin's discussion of nonstandard models may clarify things.

This is precisely the same thing as defining p_s(n)(m)=s(p_n(m)), which is therefore perfectly allowed, contrary to what the author says.

Yes, it is the same thing, and just as invalid.

Nowhere in this proof is definition by induction used, so, the author was mistaken about this,

Using A and A' instead of p_n and p_n+1 doesn't change anything. Don't you admit that defining p_0 and then defining p_n+1 in terms of p_n is definition by induction?

and if you want, I can spell out my alternative proof of the recursion theorem so that we see that there is no definitioin with induction there either

Yes, I'd very much appreciate that.

EDIT: Somehow attaching the Henkin paper didn't work the first time. I just attached it.

 

[lugita15]

EDIT: I think that the author's (Blackburn) confusion is caused by that he thinks that to write p_s(n)(m)=s(p_n(m)), we must assume that we already have a function which maps n to p_n for all n ε N

No, the author doesn't think that at all. The author is just saying that to write p_s(n)(m)=s(p_n(m)), we need to already have the function p_n for that fixed n, and we don't.

Let X be an arbitrary nonempty set, and let a ε X, let R be a relation in (that is, a subset of) N × X, and let g: X → X be a function.
Assume that

i) to each n ε N, there is at most one x ε X such that (n,x) ε R,
ii) (0,a) ε R
iii) For all n ε N and x ε X: if (n,x) ε R, then (s(n),g(x)) ε R.

Then there is a unique function f : N → N such that
a) f(0)=a,
b) For all n ε N, f(s(n))=g(f(n)).

Proof: By induction using a) and b), it is easy to prove that such a function f is unique if it exists.
To prove the existence, we prove that R is such a function. If R is a function with domain N, then it follows from ii) and iii) that it satisfies a) and b), so we must prove that R is such function. By i), R is a function, so it suffices to prove that dom(R) = N. This is done by induction:

By i) (0,a) ε R, so 0 ε in dom(R).
Assume that n ε dom R. We must prove that then, s(n) ε dom(R) also holds.
By the induction hypothesis, there is an x ε X such that (n,x) ε R. Hence, by ii), (s(n),g(x)) ε R, so s(n) ε dom(R).

By induction, dom(R) = N, and the proposition is proved.

And there is no definition by induction in this proof, right?

Yes, I don't see any definition by induction in this proof. But I'm not exactly sure what the point of this proof is. All you're showing is that if R is an inductively defined function on an inductive subset of N, then R is an inductively defined function on all of N, which is pretty trivial because induction states that any inductive subset of N is equal to N.

By the way, your conditions on R are pretty similar to the definition of acceptable on page 4 of the link, except the conditions there have a qualifier "if 0 is in the domain of R" and "if s(n) is in the domain of R".

 

[verty]

Actually, the recursion theorem is only about functions from N to N, not any functions from N to X. But even for that limited case, it still requires a considerably harder proof than your purported proof for the N to X case. See pages 4 and 5 of this link for a proof of the recursion theorem, and see page 2 for an explanation of why your simple proof wouldn't work.

I don't see what the fuss is about in that linked article, for me the given "incorrect" proof goes through, it leaves no room for doubt. This is the essence of a proof, after all. If there is a problem, the problem is with the rigorization, that axiomatic set theory struggles to represent the proof in an efficient way. Note I don't say, it fails to represent the non-proof. But the author asserts that the proof is a non-proof. I quote: "The error is fatal..., we shall have to scrap the proof and start again". Rubbish! At most, he would need to scrap the rigorization and start again.

He has two complaints, that the existence induction assumes existence as part of the induction hypothesis, and that the existence induction fails to show uniqueness. I see no problem.

 

[lugita15]

I don't see what the fuss is about in that linked article, for me the given "incorrect" proof goes through, it leaves no room for doubt. This is the essence of a proof, after all.

Well, there's lots of things that are intuitively obvious, but contain more subtlety than meets the eye. The Jordan curve theorem (you can't get draw a path from the inside of a continuous curve to the outside without crossing the curve) is a pretty obvious fact, and the difficulty in proving it isn't that the intuition behind it is hard to make rigorous, but rather that the intuitive justification elides over some serious complications, like space-filling curves.

We face a similar situation here: it is true that definition by induction (AKA recursion) does work, but why the reason it works is not quite the reason we intuitively think it works. One way to see this is that there are systems (certain nonstandard models of arithmetic) in which induction holds but the recursion theorem does not; see the Henkin paper I attached in earlier post. If definition by induction worked for the obvious reason that we think it does, then the recursion theorem could be proven just as easily in those systems.

If there is a problem, the problem is with the rigorization, that axiomatic set theory struggles to represent the proof in an efficient way.

Well, what notion do you think axiomatic set theory fails to capture? Throughout history, there have been notions that were intuitively clear but which a given theory was unable to formalize, until someone came up with a way to express the notion. A good example is the ancestral. What does the word "descendant" mean? For instance, what does it mean for John to be a descendant of Bill? Well, it means that John is either a child of Bill, or a child of a child of Bill, or a child of a child of a child of Bill, and so on. But what does "and so on" mean? That was hard to formalize, until logician Gottlob Frege in the late nineteenth century solved this problem as follows: let us call a set of people "hereditary" if it contains the child of x whenever it contains x. Then "John is a descendant of Bill" means "John is an element of every hereditary set containing Bill." (That definition may not make intuitive sense at first glance, but if you stare at it long enough, you should see that it works: any child of Bill is a descendant of Bill, any grandchild of Bill is a descendant of Bill, etc.) [EDIT: We also need the condition that John is not Bill, since you can't be a descendant of yourself.]

So are you referring to another such informal notion here?

Note I don't say, it fails to represent the non-proof. But the author asserts that the proof is a non-proof. I quote: "The error is fatal..., we shall have to scrap the proof and start again". Rubbish! At most, he would need to scrap the rigorization and start again.

Well, do you think there's some other rigorization in some other formal theory that can formalize the reasoning?

 

[Erland]

Lugita: I'll post "my" proof tomorrow, because it night in Sweden now. This proof is however not my own invention.

No, the author is expressing the standard view in the literature, so if you think it's mistaken, you might want to publish a paper on it. By the way, I've attached the Henkin paper, in case you're interested.

Thank you, it is a very interesting paper :)

But what you write about the literature is not true, at least not for Henkin. On the contrary, Theorem II p. 330 in this paper is the addition theorem for induction models, and Henkin's proof is essentially the same as the one that Blackburn says is flawed. He sees certainly no problem with defining h_s(x) in terms of h_x.
It is remarkable that Blackburn refers to this paper without discovering this (otherwise, he should at least have made a comment about it).

And why should there be a problem? What is proved in the induction step is that if h_x exists, then so does h_s(x). Whether h_x actually exists or not is irrelevant.
And why do you accept induction at all? How can you use n ε E to prove s(n) ε E, when actually n might not lie in E?
Or, to take another example, suppose we want to prove that a certain condition P(x) is contradictory. We then assume that we have an x such that P(x) holds, and let's say that we define an element y in terms of x, and then continue to derive a contradiction, and thus conclude that P(x) is false. By your way of reasoning, this would be invalid, since we never established that such a thing as x actually exists, (which it actually doesn't). Yet, this kind of reasoning is standard in mathematics.

But the attempted proof uses definition by induction, and how can you justify that without proving the recursion theorem?

It doesn't use definition with induction. To define something with induction means setting up equations of the type (i) f(0)=a and (ii) f(s(n))=g(f(n)) (for some a and g) and just assuming that there is a unique function f satisfying (i) and (ii). This is not how it is done in the (claimed incorrect) proof of the addition theorem, beacuse in this proof, that assumption is actually proved.

And yes, you're right that the addition theorem holds whenever induction holds, but the reason it holds is not because of the attempted proof.

By the way, if you're willing to concede that the recursion theorem isn't true in general for systems that only satisfy induction, then what would you find wrong with the following proof?

Theorem: For any system (N, s, +) satisfying induction, a function F from X to X, and an element B of X, there exists a unique function f: N to X such that f(0) = B and f(s(i)) = F(f(i)).
Proof: Uniqueness is trivial. Let E be the set of natural numbers n such that there is a unique function f_n: {0, ..., n} to X satisfying the conditions specified for i<n. It's obvious that 0 is in E. If n is in E, then let f_n+1 be the composition of F and f_n. Since f_n is well-defined and unique, f_n+1 is also well-defined and unique. Thus n+1 is in E. Therefore, by induction, E = N, and we can define f(n) = f_n(n).

Surely you must object to that proof, right?

Yes, because it uses the total ordering relation <, which does not exist in general induction models.

However, "my" proof does actually use <, because it doesn't use just the axioms for a Peano Model, but the set theoretic definition of natural number called contemporary standard here, which is a particular Peano model in which < is simply defined as ε (set membership relation).

Yes, I don't see any definition by induction in this proof.

But the (claimed incorrect) proof of the addition theorem is special case of this:

Let X be the set of all functions from N to N, let a be the function given by a(m)=m for all m ε N, let the R be the set of all (n,x) ε N × X such that the functiuon x satisfies (i) and (ii) for n (at page 1 in Blackburn), and define g: X → X by g(x)(m)=s(x(m)) for all x ε X and m ε N.

We can show that i) in my propostion holds for this, and in the proof claimed incorrect, it is proved that ii) and iii) holds, giving a function f : N → X (not N → N, which I errounesly wrote in my previous post) satifying a) and b). This function f here maps n to p_n for all n ε N.

So, if you accept my proposition and its proof, you must also accept that the attempted proof of the addition theorem is valid.

 

[Erland]

But the attempted proof uses definition by induction, and how can you justify that without proving the recursion theorem?

This confusion may be partly semantical. One can possibly call the definitions of objects a_n in a sequence, where a_n+1 is definied in terms of a_n for all n, a definition by induction. But even so, this is in no way problematic. It follows by simple induction on this that each element a_n, taken for itself, exists.

But what is usually called a definition by induction is when we use this to define a function f, defined on N, such that f(n)=a_n for all n. A function is a kind of set, and it is not obvious that such a set exists. This is what needs to proved, and this is done by (the proof of) the recursion theorem (and in some cases with weaker assumptions, such as in the proof of the addition theorem for general induction models).

Now to "my" proof of the recursion theorem (which is not really mine, but I am not sure whom to give the credit).

First, some notation. For each n ε N, put N_n={k ε N | k≤n}. Note that for this to be well defined, we need the relation ≤ on N. It is not obviuos that such a relation exists in general Peano models. If we want to prove this from Peano's axioms alone, we need probably prove the recursion theorem first, and this would, of course, be circular.
I will however, not prove the theorem for a general Peano model, but for a particular one, based upon the set theoretic definition of natural number called the contemporary standard here.
This has the advantage that < can be simply defined as ε (set membership relation) on N.
Another advantage is that this proof, with some changes, can be generalized to cover definitions by transfinite induction for ordinal numbers.
To prove the recursion theorem for general Peano models, we can use the theorem for this particular model to prove that every Peano model is isomorphic with this one, whence the theorem must hold for all Peano models.

We also generalize the theorem a little:

THEOREM:

Let X be a set, and let a ε X. Let g: N × X → X be a function.

Then, there exists a unique function f: N → X such that:

i) f(0)=a,
ii) f(s(k))=g(k,f(k)), for all k ε N.

PROOF: First, we prove the following by induction:

For each n ε N, there exists a unique function f_n: N_n → X such that i) holds and that ii) holds for all k < n (with f_n instead of f).

This clearly holds for n=0, just put f₀(0)=a. This is the only possibility for f₀. ( ii) is vacuously satisfied here).

Assume that there is a unique function f_n: N_n → X which satisfies i), and ii) for k < n. Now, define the function f_s(n): N_s(n) → X, by

a) f_s(n)(k)=f_n(k), if k ≤ n, and
b) f_s(n)(s(n))=g(n,f_n(n)).

Since i), and ii) for k < n, hold for f_n, the same is true for f_s(n), by a), and then b) gives that f_s(n) satisfies ii) for k=n. So, f_s(n) has the desired properties.
Assume now f'_n: N_s(n) → X is any function satisfying i), and ii) for k ≤ n. Let f'_n be the restriction of f'_s(n) to N_n. Clearly, f'_n satisfies i), and ii) for k < n. But, by the induction hypothesis, f_n is the only function with these properties. Thus, f'_n=f_n, which means that
f'_s(n)(k)=f_s(n)((k) for all k ≤ n. That this holds also for k = s(n) follows from this and that ii) holds for both f'_s(n) and f_s(n) for k=n.
Thus f'_s(n)=f_s(n), that is, f_s(n) is the only function with the desired properties.
Thus, the claim holds for s(n).

The desired conclusion now follows by induction.

Now, for all m,n ε N with m<n, let f_n^m be the restriction of f_n to N_m. It is clear that f_n^m satisfies i), and ii) for k < m, which by the uniqueness just proved, implies that f_n^m=f_m.

Now, we define the function f: X → X by f(n) = f_n(n) for all n ε N.
Then f(0)=f₀(0)=a, so i) holds, and for all k ε N, f(s(k))=f_s(k)(s(k))=g(k,f_s(k)(k))=g(k,f_s(k)^k(k))=(by the above)=g(k,f_k(k))=g(k,f(k)), that is: f(s(k)=g(k,f(k)), so ii) holds for all k ε N.

So, f has the desired properties.

I leave it to the reader to prove with induction using i) and ii) that f is the only function with these properties, which concludes the proof of the theorem.

 

[Erland]

I will here give another proof of the recursion theorem, a proof I constructed some 25 years ago. It has the advantage over the proof in my previous post that it works for arbitrary Peano models (so < is not used), but on the other hand I don't see how it can be generalized to cover transfinite induction. It has similarities with the proof in Blackburn's paper.

The formulation of the theorem is the same as in my previous post, but here we assume that (N,0,s) is an arbitrary Peano model.

The proof is as follows:

Let M be the set of all binary relations R on N × X which satisfy:

i') (0,a) ε R, and
ii') for all k ε N: if (k,x) ε R, then (s(k),g(k,x)) ε R.

It is easy to see that N × X ε M, so M is nonempty.

Next, let R ε M. we prove by induction that n ε dom(R) for all n ε N:

By i'), (0,a) ε R, so 0 ε dom(R)

Assume that k ε dom(R). Then, there is an x ε X such that (k,x) ε R. Hence, by ii'), (s(k),g(k,x)) ε R, so s(k) ε dom R.

It follows by induction that n ε dom(R) for all n ε N, which means that dom(R)=N. Since R ε M was arbitrary, this holds for all R ε M.

Now, let T be the intersection of all relations in M. Then T is a binary relation on N × M. By i'), (0,a) ε R for all R ε M, so (0,a) ε T. Also, if (k,x) ε T, then (k,x) ε R, for all R ε M, so by ii'), (s(k),g(k,x)) ε R for all R ε M, so (s(k),g(k,x)) ε T.

So, T satisfies i') and ii'), which means that T ε M. By the above, this implies that dom(T)=N.

Now, we prove the following by induction:

For each n ε N, there exists an R_n ε M (depending upon n, but not claimed to be unique) such that there is a unique u ε X such that (n,u) ε R_n.

For n=0, we can take R₀ as the union of {(0,a)} and (N-{0}) × X. This R₀ satisfies i'), and if (k,x) ε N, s(k)≠0, so (s(k),g(k,x)) ε R₀, so R₀ satisfies ii'). Also, there is a unique u ε X such that (0,u) ε R₀, namely, u=a. Thus, this R₀ has the desired properties.

Next, assume that the claim is true for n, so that we can choose an R_n ε M such that there is a unique u ε X such that (n,u) ε R_n. By ii') for R_n, (s(n), g(n,u)) ε R_n.
Now, let R_s(n) = R_n - ({s(u)} × (X - {g(n,u)})).
Since (0,a) ε R_n and s(u)≠0, (0,a) ε R_s(n), so R_s(n) satisfies i').
Next, let k ε N and assume that (k,x) ε R_s(n). Then also (k,x) ε R_n, and hence (s(k),g(k,x)) ε R_n. If k ≠ n, then s(k)≠s(n), so that also (s(k),g(k,x)) ε R_s(n). If, instead, k=n, then we must have x=u, and it follows from the definition of R_s(n), since (s(u),g(n,u)) ε R_n, that (s(n),v)) ε R_s(n) if and only if v=g(n,u). Thus, in both cases (s(k),g(k,x)) ε R_s(n), which means that R_s(n) satifies ii').
Thus, R_s(n) ε M, and we also obtained that there is a unique v ε X such that (s(n),v) ε R_s(n), namely, v=g(n,u).
Thus, the claim is true for s(n).

By induction, the claim is true for all n ε N.

Now, let n ε N. Since dom(T)=N, there is an x ε X such that (n,x) ε T. By the above, there is an R_n ε M such that there is a unique u ε X such that (n,u) ε R_n. Since T is a subset of R_n, (n,x) ε R_n, which implies that x=u. If also (n,y) ε T, then, by same argument, and the same R_n, y=u, so x=y.
This means that there is a unique x in X such that (n,x) ε T.
Since n ε N was arbitrary, this holds for all n ε N.

This means that T is actually a function (more precisely, the graph of a function), from N to X. We rename this function as f. That f satisfies i) and ii) (see my preceding post), follows easily from this and i') and ii') for T.

Thus, we have found a function with the desired properties, which concludes the proof.

 

[verty]

Well, there's lots of things that are intuitively obvious, but contain more subtlety than meets the eye. The Jordan curve theorem (you can't get draw a path from the inside of a continuous curve to the outside without crossing the curve) is a pretty obvious fact, and the difficulty in proving it isn't that the intuition behind it is hard to make rigorous, but rather that the intuitive justification elides over some serious complications, like space-filling curves.

We face a similar situation here: it is true that definition by induction (AKA recursion) does work, but why the reason it works is not quite the reason we intuitively think it works. One way to see this is that there are systems (certain nonstandard models of arithmetic) in which induction holds but the recursion theorem does not; see the Henkin paper I attached in earlier post. If definition by induction worked for the obvious reason that we think it does, then the recursion theorem could be proven just as easily in those systems.

This is why I think it works, because when you have defined by induction every input to the function and the corresponding outputs, there is nothing left to define. To say that the function can fail to be so defined is in a way similar to saying that a quantity smaller than any finite quantity can fail to be equal to zero. A reasonable person would say the function is so defined and that the proof is sufficient to prove the result to the reader. Therefore I call it a sufficient proof. A proof can't fail to prove something because the language it is written in thinks it isn't a proof. If it has the quality of proving the fact to the reader, it is surely a proof. The proof that the author (Blackburn) had problems with had this quality, that it proved the result. So his assertion that it was incorrect, fatally flawed and would need to be scrapped, jars against the senses, I thought.

 

[verty]

Hmm, reading the Henkin paper, I see that S() is not assumed to be the standard successor function. I was thinking of "models" in terms of logic, logical models. But here it was about models of peano arithmetic, where S can be a different function. So there was a confusion of the meaning of "models" whereby I assumed that axioms might change but S() was still the usual successor function. That leaves no room for the proof to fail.

I haven't thought about the case when S is a different function. Sorry.

-edit-

I think I understand now. If the sequence [0, S(0), S(S(0)), ...] fails to cover the whole of N, the function will fail to be defined by the recursive definition. What is needed is for this chain to cover the whole of N. This was implicit when S was the usual successor function.

 

[Erland]

Reading more in Henkin's article, I see that he hints a proof of the recursion theorem similar to the one given by me in Post 13 here (p. 329 f.). So, I wasn't first with that one either, but that is hardly surpricing.

 

[lugita15]

And yes, you're right that the addition theorem holds whenever induction holds, but the reason it holds is not because of the attempted proof.

By the way, if you're willing to concede that the recursion theorem isn't true in general for systems that only satisfy induction, then what would you find wrong with the following proof?

Theorem: For any system (N, s, +) satisfying induction, a function F from X to X, and an element B of X, there exists a unique function f: N to X such that f(0) = B and f(s(i)) = F(f(i)).
Proof: Uniqueness is trivial. Let E be the set of natural numbers n such that there is a unique function f_n: {0, ..., n} to X satisfying the conditions specified for i<n. It's obvious that 0 is in E. If n is in E, then let f_n+1 be the composition of F and f_n. Since f_n is well-defined and unique, f_n+1 is also well-defined and unique. Thus n+1 is in E. Therefore, by induction, E = N, and we can define f(n) = f_n(n).

Surely you must object to that proof, right?

Yes, because it uses the total ordering relation <, which does not exist in general induction models.

I'm still thinking about rest of your posts, but for now let me just respond to this part. Here is a definition of <: A hereditary set is a set which contains s(i) whenever it contains i. m ≤ n means that n is an element of every hereditary set that contains m. m < n means that m ≤ n but m ≠ n. What is wrong with that?

 

[Erland]

I'm still thinking about rest of your posts, but for now let me just respond to this part. Here is a definition of <: A hereditary set is a set which contains s(i) whenever it contains i. m ≤ n means that n is an element of every hereditary set that contains m. m < n means that m ≤ n but m ≠ n. What is wrong with that?

It will not be an order relation in general. For example, in the additive group Z_n (for which induction holds), x≤y holds for all x,y ε Z_n with this definition. Only if we have a Peano model (for which all Peano's axioms hold) will < be a strict total order relation with 0 as its smallest element. Assuming this, your proof is valid.

 

[Erland]

I have been thinking a lot about this during the last few days, and tried to find out exactly what the problem is. It is actually quite subtle, so it is not surpricing that misunderstandings occur.

Let's take a look at the addition theorem again. It says that:

There exists a unique function h: N × N → N such that, for all m ε N:

i) h(m,0)=m
ii) For all n ε N, h(m,s(n))=s(h(m,n)).

We then usually write m+n instead of h(m,n).

Notice that h is a function of two variables, and that in proving this theorem, it might be possible to use induction/recursion on the first variable or the second variable or both. It is important to keep these things apart. We partly follow Henkin.

Let us now attempt a proof (only a sketch):

We divide the proof in three parts:

Part I:

Fix m ε N. Define h_m: N → N, by

i') h_m(0)=m
ii') h_m(s(n))=s(h_m(n)), for all n ε N

Part II:

Define h by h(m,n)=h_m(n), for all m,n ε N.

It is easy to verify that this h satisfies i) and ii). Thus there exists such a function.

Part III:

It easy to verify by induction on n (the second variable) that if g: N × N → N is any function satisfying i) and ii), then, for all m ε N, g(m,n)=h_m(n)=h(m,n), so that h is a unique function with the desired properties.

This completes the attempted proof.

Part I of this attempt uses definition by induction, on n. Let us temporarily accept Part I. Then we certainly have no problems with part II and III. Part II does not use induction in any form, and Part III is simply a proof by induction on n, and this in unquestionable.
Also, there is no induction on m in this attempted proof, both the definition by induction in Part I and the proof by induction in Part III are on n.

The problem lies in Part I. In what sense is a function defined there? A function from N to N is a set, a subset of the cartesian product N × N. The most common way of defining a set is to give a condition which all its elements and only those, shall satisfy. In this case, this means that we want some condition P(n,k) such that for every pair (n,k) ε N × N, (n,k) ε h_m (that is: h_m(n)=k) if and only if P(n,k) holds. Once we have such a condition, we can try to verify that the set (relation) h_m so defined is a function defined on all of N which satisfies i') and ii'), and if we verify this, we are done. Such a verification can itself constitute a proof by induction on n and we can use i') and ii') themselves to find each h_m(n): after the verification that h_m is function, we verify first P(0,m), which means that m ε dom(h_m) and that h_m satisfies i'), and then that, for all n ε N, P(n,k) implies P(s(n),s(k)) for all k ε N, which means that if n ε dom(h_m) then so does s(m), and h_m satisfies ii'). Thus one can say that, in this case, we have transformed a definition by induction to a proof by induction.

But here, we are not given any condition P(n,k) of this kind, and it is in not obvious how to find one, nor are we given any other way to define h_m which is valid in ZF.

So, it is not obvious, within the framework of ZF, that there exists a function h_m satisfying the conditions in Part I. The attempted proof is therefore incomplete.
It is precisely in this kind of situations the recursion theorem can be used. This theorem is stated and proved in previous posts in this thread. It is clear that the recursion theorem can be applied in Part I to obtain such a function h_m for each m ε N. We empasize again that the recursion here is on n.
So, we can easily complete the proof by putting a reference to the recursion theorem in Part I.

We now have proved the addition theorem, but, since we invoked the recursion theorem in the proof, we have only proved it for Peano models (for which all Peano's axioms hold), since the recursion theorem only hold for such models. The recursion theorem does not hold for general induction models (where only the induction axiom is assumed to hold), and therefore, our proof of the addition theorem is invalid for such models.

But in fact, the addition theorem holds for general induction models. Henkin gives a proof, and Blackburn gives the same proof (not saying that it is supposed to hold for general induction models) although less detailed than Henkin, and claims that it is flawed. But is it really flawed? Let's take a look at it. Again, we give just a sketch. We divide it into four parts:

Part I:

It is easy to verify by induction on n that to each m ε N, there exists at most one function h_m: N → N which satifies i') and ii') in the previous proof. (Blackburn leaves this part out, but remarks that it easily can be added.)

Part II:

We now define:

i'') h₀(n)=n, for all n ε N
ii'') h_s(m)(n)=s(h_m(n)), for all n ε N and m ε N.

This is well defined, by the uniqueness proved in Part I.

Using i'') and ii') we can now prove by induction on m that each h_m satisfies i') and ii'), and by Part I, each such h_m is the only function with these properties.

Part III. The same as Part II of the preceding proof.

Part IV: The same as Part III of the preceding proof.

The proof is now complete.

Notice that in Part II here we use induction m, while in the preceding proof, we only used induction (both definition and proof) on n.

One might think that Part II of this proof is as invalid as Part I of the preceding proof, and that we need the recursion theorem here too (which would make the proof invalid, since we only assume that we have an induction model, for which the recursion theorem does not hold in general). Here we have induction upon m and a function, call it h', whose values are other functions: h'(m)=h_m for all m ε M, but otherwise, the two proof parts have the same structure.

Or have they? Actually, there is a major difference. Recall that in the comments after the first attempted proof, I wrote that it would have been OK if there was a condition P(n,k) which would hold if and only if h_m(n)=k, but we did not know (at that stage) that such a condition existed.
The corresponding in the second proof would be a condition Q(m,f), where m ε N and f is a function from N to N, which should hold if and only if i') and ii') hold for m, with f instead of h_m. But there certainly exists such a condition Q(m,f), we just defined it! It is perfectly well defined within the framework of ZF. This Q defines a relation h' on (i.e. a subset of) N × N^N (where N^N is the set of all functions from N to N), so that (m,f) ε h' if and only if Q(m.f).

It now follows from Part I that this h' is a function defined on a subset of N, and we write h_m instead of h'(m). Analogously to what we did in the remark after the attempted proof above, we now prove by induction, using i'') and ii''), that Q(0,id_N) (where id_N is the identity function on N, so that id_N(n)=n for all n ε N), and that for all m ε N, if Q(m,f) then Q(s(m),g), where g is the composition of s and f (given by g(n)=s(g(n)) for all n ε N) for all f ε N^N.. Analogously to above, this means that i'') and ii'') hold for these h_m:s.

So, the difference to the previous case is that here, there it is clear that there is such a condition Q(m,f), which is proved by induction to have the right properties. This proof is therefore valid, or at least it could be made valid by being more explicit, just as we were just above.

So, the addition theorem holds for general induction models. But the first proof is simpler, so if we are only interested in Peano models, we can stick with that one.

 

[verty]

Let's take a look at the addition theorem again. It says that:

There exists a unique function h: N × N → N such that, for all m ε N:

i) h(m,0)=m
ii) For all n ε N, h(m,s(n))=s(h(m,n)).

We then usually write m+n instead of h(m,n).

If s(n) is the function that chooses the smallest even number > n, then it seems that h is underspecified for odd n:

Let m be even.
s(h(m,0)) = s(m) = m+2 = h(m,2)
s(h(m,1)) = h(m,2) = m+2
h(m,1) = 0 or 1

I don't have time now but tomorrow I'll look at this again.

 

[verty]

Continuing, I think my successor function, which picks for each n the smallest even number greater than n, cannot be part of an induction model. As proof, suppose $0 \in E$ and $\forall n \in N, n \in E → s(n) \in E$, this won't imply that $\forall n, n \in E$ which is the conclusion of the induction.

So inductions must go through in any induction model. Now s' which takes 2n to 2n+1 and odd 2n+1 to 2n also fails. This implies that any infinite induction model has a successor function with no loops. The order of the elements may be rearranged but there should be no loops. So s'' which takes (0 → 2 → 1 → 3 → 5 → 4 → 6 → 8 → 7...) will give an induction model.

But then, all infinite induction models will satisfy the recursion theorem and the addition theorem. For finite induction models, the successor of the last element can be anything and the order can be mixed up, but again, both these theorems go through.

The only way I can see for the simpler addition theorem proof to fail is, I think, for this not to be the case and for functions like s or s' to be admitted. One thing Henkin mentions is that one should not assume that a function is so defined by the induction. But I can't see how that possibility can be admitted.

 

[Erland]

all infinite induction models will satisfy the recursion theorem and the addition theorem.

Correct. In fact, all infinite induction models are Peano models (satisfying all Peano's axioms) and all Peano models are isomorphic to (N,0,s).

For finite induction models, the successor of the last element can be anything and the order can be mixed up, but again, both these theorems go through.

Wrong, the recursion theorem does not hold for finite induction models. Were it so, we could by induction define a map from such a finite model onto N, which is clearly impossible.

In fact, to every induction model (N',0',s') is there exists a unique homomorpism from (N,0,s) (the standard model for the natural numbers) to (N',0',s'), and this homomorpism is onto. (See Theorems I and IV in Henkin's article.)

This means that an induction model (N',0',s') is uniquely determined by the unique homomorphism h: N → N'.

If h is one-to-one, then N' is infinite and (N',0',s') is isomorphic to (N,0,s).

If h is not one-to-one, then there is a minimal m ε N to which there is a minimal k ε N with k>m such that h(m)=h(k). Then, the restriction of h to {0,1,...,k-1} is one-to-one, and h(m+r(k-m)+s)=h(m+s) for all r ≥ 0 and 0 ≤ s < k-m.

This means that N' is finite, and (N',0',s') has the form of the digit 6, with 0' at the top, and going into a loop of length k-m from h(m) on. If m=0, then k>1 (otherwise s'(0')=0'), and (N',0',s') is isomorphic to the additive group Z_m (defining s'(n)=n+1 in this group). If k=m+1, then N' = {h(0),h(1),...,h(m)}, with s'(h(i))=h(i+1) for 0 ≤ i < m and h(i)=h(m) for i ≥ m, so it goes up to h(m) and stops there.