# Peano axiom of induction with "no junk"

In this Wikipedia treatment of Peano Axioms, if you go down to the first picture you'll see a circle of dominoes and a straight line of dominoes:

The caption says the straight line of dominoes

The chain of light dominoes, starting with the nearest, can represent $$\mathbb{N}$$, however, axioms 1–8 are also satisfied by the set of all light and dark dominoes. The 9th axiom (induction) limits $$\mathbb{N}$$ to the chain of light pieces ("no junk") as only light dominoes will fall when the nearest is toppled.

First, how are the dark satisfied by axioms 1-8? And then the "no junk" idea. Intuitively, I am assuming they say the straight line dominoes is "no junk" because of the fact that even though successor function $$S$$ is defined as a mapping from $$\mathbb{N}$$ to $$\mathbb{N}$$ and is injective, in fact, its image does not include $$0$$. Therefore, the circular dominoes represent a succession that would eventually "come around" and some great $$n_{\Omega}$$ must have $$0$$ as its successor. However, the successor as a straight line would not have this problem, i.e., its $$n_{\Omega}$$ would just have an $$S(n_{\Omega})$$. Or have I got this totally wrong? If so can someone explain the "no junk" idea better?

• $0$ is not in the circle, so that loop never "reaches" or "comes around" to $0$. Imagine you have the usual natural numbers, and then you add two symbols, $\star$ and $\sharp$, and you define the successor function to be the usual one of the input is a usual natural number, and $S(\star)=\sharp$ and $S(\sharp)=\star$, and you .call all of them "naturals". Then it is indeed true that the successor of a "natural" is a "natural", that $S$ is an injection, that $0$ is not in the range of $S$. So it satisfies axioms 1-8. Mar 16, 2023 at 3:13
• Interesting, but what then is meant by "no junk"? Mar 16, 2023 at 3:18
• That there aren't any additional "naturals" outside of $0$, $1$, $2$, $3,\ldots$. Because by the induction axiom, that list contains all naturals. In my example, $\star$ and $\sharp$ are "junk": they aren't required to satisfy the first 8 axioms. Mar 16, 2023 at 3:31
• The circular arrangement is just one that allows extraneous elements. There are others. (For example. take the naturals, and then add a "blue integers" after all the naturals). But what you need to verify is that the set and function thus defined satisfies the listed properties, nothing more and nothing less. There is no "going on forever"and no "last"in the first eight axioms. It is the induction axiom that places the strongest restrictions on the structure. Mar 16, 2023 at 4:49
• I think a large part of your difficulty comes from misinterpreting the caption (which could be phrased more clearly). When it says, “axioms 1–8 are also satisfied by the set of all light and dark dominoes”, it doesn’t mean that the set of light dominoes and the set of dark dominoes each separately satisfy those axioms. It means that light and dark together satisfy them. Also of course the light by themselves satisfy all the axioms. Mar 16, 2023 at 5:07

The set of all the dominoes in the picture satisfies axioms 1-8. (The caption says this, if properly interpreted. The dark dominoes by themselves do not satisfy axiom 8. They satisfy axiom 1 only if you arbitrarily pick one dark domino to be 0.)

That is, if “natural number” means “light or dark domino”, then axioms 1-8 hold. 0 is the first light domino—none of the dark dominoes are 0. It is obvious that axioms 1-5 hold. Also 6 holds because the successor of a domino is a domino, and 7 holds because every domino except 0 has a unique predecessor.

Note that the successor and predecessor of a domino of one color is always of the same color. So 0 has no predecessor, light or dark. That’s axiom 8.

Finally, induction fails: the set of light dominoes contains 0, and is closed under successor, but is not the set of all dominoes.

The dark dominoes are “junk”. By this, the article just means that if we get rid of them, axioms 1-8 continue to hold, and induction now also holds.

• It should perhaps also be noted that you cannot actually exclude all conceivable junk from your natural numbers, because the incompleteness theorem gives rise to nonstandard models of arithmetic (which necessarily contain "junk," or else they would be the standard model). The induction axiom really only gets rid of very simple cases like the circular dominoes. Mar 17, 2023 at 5:07
• @Kevin To be clear, this is for Peano arithmetic as a first-order theory. The Wikipedia article introduces the domino analogy in connection with the second-order theory, where you don't have this issue. The article discusses both the second-order and first-order theories, their relationship, and their histories. Mar 17, 2023 at 5:13
• This is true enough, but I wish the article mentioned that there's no free lunch with second-order theories. It seems to gloss over this point. Mar 17, 2023 at 5:34
• I understand "junk" as "things that are not accounted for", ie, "components that are not connected to 0 by the successor operation".
– Stef
Mar 17, 2023 at 9:20
• @Stef Yes, that's another way of saying, informally, what I said informally in my last paragraph. Mar 17, 2023 at 14:30

The idea is that the first $$8$$ axioms describe natural numbers together with some possible "junk". Those junk may have various forms.

Axioms 1–8 are also satisfied by the set of all light and dark dominoes.

The statement above should be parsed as "axioms 1–8 are also satisfied by the set of [all light and dark dominoes]", instead of "...by the set of all light dominoes or the set of dark dominoes." The set of dark dominoes cannot satisfy axioms 1-8; in fact, any set that satisfy axioms 1-8 must be infinite.

Other answers have explained how we can view the set of all dominoes in the illustration so that they satisfy axioms 1-8. Basically, the nearest light domino is considered "$$0$$". When it is toppled, it will set off the chain reaction that will bring down all light dominoes, each domino knocking down its "successor". Moreover, we can assign each dark domino a successor, say, the next one to it clockwise.

In other words, the first 8 axioms do not pin down "the natural numbers", a notion that seems known to all modern human uniformly. The "dark dominoes" are considered "junk" that should be removed since, intuitively and naturally, the "light dominoes" represent all natural numbers. That removal is done by axiom $$9$$, "the axiom of induction".

Without axiom $$9$$, there could be various "junk". For example, we can add another line of dominoes that goes to infinity on both directions. For example, we can add arbitrarily many circles that contain different numbers of dominoes. We can even add a weird domino whose successor is itself! None of these junk can appear once axiom $$9$$ is in place.

• "Any set that satisfy axioms 1-8" must, in fact, contain a copy of the usual natural numbers, starting with the element $0$. Mar 16, 2023 at 8:33

This is not a great way to characterize the induction axiom schema. (It's not one axiom, but rather infinitely many: one for each formula $$\phi(x)$$: it says if $$\phi(0)$$ is true and the implication $$\phi(n) \rightarrow \phi(n+1)$$ is true for all $$n$$, then $$\phi(x)$$ holds for all $$x$$).

If you're interested enough in foundations of math to dive into the Peano axioms, you should be aware of the unavoidable existence of non-standard models of arithmetic: these are sets which satisfy the Peano axioms but are not just "$$\{0, 1, 2, \ldots, \}$$". It's true that the Peano axiom schema rules out the finite-length "junk" in the photo, but there is no first-order axiom schema that can rule out the possibility of "junk" altogether. See https://en.wikipedia.org/wiki/Non-standard_model_of_arithmetic.

The problem is that first-order formulas $$\phi(x)$$ are just not powerful enough to pin down the model: these are arithmetic formulas, like "$$\forall y \left \{(y = 0) || \exists z \exists r\left \{(x = y * z + r) \& (y > r)\right \} \right\}$$". They can only quantify over numbers, not sets of numbers.

Imagine there's a line of dominoes off to the side. It must be infinitely long, since every number has a successor. It can't have an initial element, since every non-zero number has a predecessor. So it's infinitely long in both directions. Each element of it must be greater than each legitimate natural number, since for any legitimate natural number $$n = 1 + 1 + \ldots + 1$$, we can prove by induction that $$\forall x \{x = 0 || x = 1 || x = 2 || \ldots || x =n || x > n \}$$, where $$0, 1, 2, \ldots, n$$ are the symbols given by adding the corresponding number of $$1$$'s. Lots more wild properties hold once you start thinking about multiplication...

Ultimately, the impossibility of having any first-order axiom schema which rules out all possible junk is related to things like like Godel's incompleteness theorem! A consequence of that theorem is the fact that there is no first-order (plus recursively enumerable: the axioms can be listed by a computer program) axiom schema for the natural numbers which is able to prove all true statements about the natural numbers!

• While it is interesting and significant to study "first-order axiom schema", the question refers to Peano's axiom $9$, the axiom of induction, which is a second-order axiom. Mar 17, 2023 at 5:31

$$0$$ isn't in the set of dark dominoes. On their own, the dark domninoes wouldn't be a model of $$\mathbb{N}$$, as they don't have a $$0$$. But combined with the light domninoes they are. They go around in circles, but they never go back to $$0$$, because they're not joined to it.

• Could you elaborate? Why is the dark circle not a model of $\mathbb{N}$? Why is one of the dark dominoes not $0$? Mar 16, 2023 at 3:21
• @147pm That's just not what they're trying to represent. If one of the dark dominoes were $0$ then it wouldn't satisfy axiom $8$ Mar 16, 2023 at 3:24