# How to justify why succession and addition cannot be circularly defined like this?

I am reading Tao's Analysis I, in which he states:

One may be tempted to [define the successor of $$n$$ as] $$n + 1$$. . . but this would introduce a circularity in our foundations, since the notion of addition will be defined in terms of the successor operation.

Say we did define $$S(n) = n + 1$$, and we define addition the following way: for any natural $$m$$, we define $$0+m = m$$, and if for some natural $$n$$, we have defined $$n+m$$, then we can define $$S(n) + m = S(n+m)$$. (I am assuming that the number system is defined as the usual $$\mathbb{N} = \{0,1,2,3,. . . \}$$, and that the distinguished $$\mathbf{0}$$ is $$0$$ when talking about the possibility of defining the successor as $$n+1$$, as such presupposes that $$1$$ belongs to our system of numbers). All we have in this structure is this set of numbers, which element thereof is $$\mathbf{0}$$, and how succession and addition are (attempted to be) defined, without further assumptions.

Although it certainly seems illogical in the extreme to define addition and succession in terms of each other in the above manner, I am trying to justify, beyond any shadow of a doubt, why neither of these things are defined by the above scheme. So far, I have the following 2 arguments (which seem insufficient to me):

1. for $$S(1)$$, if we look at the plain meaning of our definitions, $$S(1) = 1 + 1 = S(0+1) = S(1)$$, and we are right back where we started, getting nothing. (We knew that $$S(0) = 1$$ because our definitions allow us to conclude that $$S(0) = 0 + 1 = 1$$). However, this is unsatisfactory to me because it is not clear to me that this is the only way to reason about the value of $$S(1)$$.

2. By these definitions, because we have never even mentioned an element of $$\mathbb{N}$$ apart from $$0$$ and $$1$$, how could we possibly have defined an injective mapping from $$\mathbb{N}$$ to $$\mathbb{N}$$ as our successor function? This is unconvincing to me because how do we know that there isn't a more complex, intricate way this mapping has been defined, which I cannot conceive of?

I still want something beyond these arguments, because how can we be assured that a complex interplay between everything we have defined hasn't somehow still allowed us to deduce the value of the addition and successor function for all elements of its domain?

I am a programmer, and it is common to define functions in terms of each other in mutually recursive fashion- so the mere fact that addition is defined in terms of itself, or addition and succession are defined in terms of each other, isn't sufficient reasoning to me as such recursively happens all the time; it is just that with the appropriate base cases, each of the functions can always determine their values, even though they are defined in terms of each other.

This is why I ask that even though succession and addition are here defined in terms of each other, how we can be assured that if we define them as above, it is impossible to deduce the value of these functions for every element of their domain? I of course intuitively feel that it is impossible to do so, but I'm not exactly sure why.

• Comments have been moved to chat; please do not continue the discussion here. Before posting a comment below this one, please review the purposes of comments. Comments that do not request clarification or suggest improvements usually belong as an answer, on Mathematics Meta, or in Mathematics Chat. Comments continuing discussion may be removed. Commented May 25 at 20:39

One may be tempted to [define the successor of $$n$$ as] $$n+1$$ . . . but this would introduce a circularity in our foundations, since the notion of addition will be defined in terms of the successor operation.

Technically you can have $$+$$ as a primitive notion, and define $$S(n) = n+1$$ (see this wikipedia section), or have $$S$$ as a primitive notion, and define $$+$$ via $$S(n)$$, but not both at the same time. A primitive notion , by definition, cannot be defined upon another primitive notion. Trying to define both $$+$$ and $$S$$ in terms of each other will make both of them non-primitive, and results in circularity, as said by Tao, because you cannot arrive at a statement consisting of only primitive notions.

$$S(1) = 1 + 1 = S(0+1) = S(1)$$

This is an example of why doing both would introduce circularity. You either have to accept that $$S(1)$$ is a definition, or that $$1+1$$ is a definition, depending on what you choose to be primitive among $$+$$ and $$S$$

I am a programmer, and it is common to define functions in terms of each other in mutually recursive fashion

A function "defined" by recursive relation requires a proof of existence and uniqueness, which is often omitted since it's usually considered to be trivial. For example the definition of the factorial

$$n! = (n-1)! \cdot n \quad \text{if } n > 0$$ $$0! = 1$$

requires an implicit proof of that there exists a unique function $$f(n)$$ over $$\mathbb{N}$$, such that $$f(0) = 1$$ and $$\forall n \in \mathbb{N}, f(n) > 0 \rightarrow f(n) = n\cdot f(n-1)$$.

Such thing cannot be applied to a primitive function, because you cannot prove its existence.

• without a careful knowledge of primitive terms (I am currently learning this), what is an appeal to logical intuition on why we can't define primitive notions in terms of each other? As when we define 2 mutually recursive functions in terms of each other, can't both of these functions be primitive terms and still have the mutual recursion work? Commented May 25 at 3:40
• "As when we define 2 mutually recursive functions in terms of each other" Regarding this matter. First of all the mutually recursively defined functions that you see in computer science depends on the notion of the natural number set, because you need to define their inputs in the first place. Secondly, defining function without restriction leads to paradoxes. For example, let $f(x) = g(x) + 1$, $g(x) = f(x) + 1$ is a mutual recursion, but it does not makes sense because $f(x) = f(x) + 2$. This is called unrestricted comprehension. As such, we forbid such kind of definition. Commented May 25 at 4:19
• @PrincessMia Therefore, instead of allowing a function to be freely defined in such a manner, we prove that there exists a function that satisfies a certain statement". And, additionally, we prove that such a function is unique. This is usually done with the help of the recursion theorem Commented May 25 at 4:23
• @PrincessMia however, to define the set of natural numbers, we neccessarily need some function to exist in the first place, to derive other natural numbers, otherwise, we're stuck with $0$ and $1$, or we have to include an axiom for each natural number, which doesn't make sense either. As it is not possible to prove the existence of such a function, we admit that it exists. Commented May 25 at 4:32
• @PrincessMia so when you define a function recursively, you implicitly implies there's a proof that such function exists. Therefore you cannot define a primitive function recursively, because it is admitted to exist in the first place. You cannot prove something exist by admitting that it exists, hence the circularity Commented May 25 at 4:42

There is no circularity here. The existence of the addition function on $$N$$ is actually a theorem derived from Peano's Axioms (762 lines of formal proof available on request). $$S(x) = x+1$$ is a corollary of that theorem.