# the (seeming) loop caused by defining Natural numbers through inductive sets.

I'm a first year student in mathematics, and we recently defined Natural numbers as following:

"For all numbers, a number is an element of the set Natural numbers, if and only if it is an element of every inductive set". An inductive set is defined as "A subset of the Real numbers that contains 1 and for each element, that element + 1 is also an element of the set'.

One's natural instinct is to ask why not define $$\mathbb{N}$$ = {1, 2, 3 ...} which is easy to dismiss because we cannot define an infinite set in Roster notation when there is no set builder notation. We have not yet defined what natural numbers are and therefore these numbers are not related by any means (The only property that they share is being Natural which yet has no definition in our stack. even if one wishes to define this set inductively, through something call a successor function if I'm not mistaken, the domain of the said function must be the natural numbers which...defeats the purpose? Someone might argue for a definition through sequences, which...can one have sequences before defining Natural numbers?).

I suppose the reason why we are being so rigorous in defining natural numbers in such way is that we wish to prove things by induction. When we prove through induction we basically define a set like M to be the subset of $$\mathbb{N}$$ of all numbers who satisfy P(n) which P(n) is usually our the algebraic conclusion in our theorem. We prove 1 $$\in$$ M and $$\forall n (n+1 \in M)$$. From this we conclude M = $$\mathbb{N}$$.

This triviality is in need of proving, so we naturally (no pun intended) resort to making a more rigorous definition of $$\mathbb{N}$$ in order to be able to use induction. We define inductive sets, then define a Natural number as said above, see that according to definition $$\forall \hspace{1mm} inductive A, \hspace{1mm}(\mathbb{N} \subseteq A)$$.

So it is sufficient to know a subset of Natural numbers is inductive to prove they are equal (which we apply in M for the above). It is easy now to prove that 1, 2, 3 and so on are natural numbers individually, and I don't know if I'm being nitpicky about this, but I have the following concern: when we prove things through induction we essentially have in mind that we want to prove that a theorem holds for {1, 2, ...} and that happens to be called $$\mathbb{N}$$. We can't have {1, 2, 3, ...} because of the reasons above so we take $$\mathbb{N}$$ as nothing but a name and define it as we did above. we can prove that 1 $$\in \mathbb{N}$$ and so on, but that is a stretch of it being equal to the infinite set of {1, 2, 3, ...}. Instantly, it seems ridiculous to call it a stretch for it not being equal to something that we cannot define or is defined through something we earlier defined. does it suffice to say {n| n $$\in \mathbb{N}$$} = {1, 2, 3, ...}, or we should find a separate way to define the algebraic form of Natural numbers and then prove it to be equal to the $$\mathbb{N}$$ we defined above through inductive sets. It also seems that we can prove 1 $$\in \mathbb{N}$$, 2 $$\in \mathbb{N}$$ and ... . But it seems that proving {1, 2, ...} to be equal to $$\mathbb{N}$$ is (in addition to needing to define {1, 2, ..} in a way it makes sense) in itself in need of induction for proving.

I would be most thankful if someone would help clarify my perspective.

• I'll answer your question if you toss in some paragraph breaks in logical places. ^_^ You're asking a good question but it's hard to read as is.
– user694818
Jan 22, 2021 at 18:40
• Of course! I'm sorry for the inconvenience, Hope it's better now. Jan 22, 2021 at 19:05
• It seems your professor needs a rigorous definition of the real numbers before he has defined the natural numbers. How did they do that? None of the definitions of real numbers I know can do that. Jan 23, 2021 at 8:21
• We didn't define Real numbers, but rather introduced it as a set that satisfies 14 principles that are partitioned in 3 categories. Principles of Addition, multiplication and order and lastly completeness. Jan 23, 2021 at 10:37
• @quarague is probably saying something along the lines of my answer. In case my answer is still not clear to you, the point is that anyone can write down any random axiomatization they like, but it is meaningless until one can justify that it actually is satisfied by some model. In the case of the axiomatization you are talking about, there is no way to justify the existence of a model without using the structure of $ℕ$ together with induction. So it becomes a totally pointless exercise to 'construct' naturals based on that axiomatization because it only works if a model exists... Jan 25, 2021 at 6:02

"Induction" is actually a much more general concept, and here, it's being applied specifically to $$\mathbb{N} \subset \mathbb{R}$$ in a way that rather obfuscates what's going on.

A notion of the "natural numbers" arises in this way from any sufficiently-large structure with a nice enough relation on it. For example, we can conduct exactly the same construction as you originally did, but in the universe of sets. There is a nice relation on the universe of sets, $$\in$$, and we can define an "inductive set" $$I$$ to be a set which contains the empty set $$\emptyset$$ and which also has the property that for every set $$x \in I$$, $$I$$ also contains $$\{x\}$$. Then the analogous "natural numbers" is the intersection of all the inductive sets, i.e. $$\{\emptyset, \{\emptyset\}, \{\{\emptyset\}\}, \dots\}$$.

All that is needed for this construction to work is that there is some nice operation that produces a bigger thing from a smaller thing, and that there is somewhere to start. In your example, the starting place was $$1$$; in my sets example, it was $$\emptyset$$. In your example, the operation was $$x \mapsto x+1$$; in my example, it was $$x \mapsto \{x\}$$.

In this way, we can basically "build a thing that looks like the natural numbers" anywhere we want. (There are some technical restrictions.) The natural numbers aren't really this privileged subset of the real numbers, though they can certainly be defined that way. Rather, they are the abstract concept of the smallest place where you can keep making something bigger forever. Your course has identified one rather natural way that this abstract concept shows up in the reals, and it has shown you a method that will let you identify instances of that concept in other places. The method is extremely general, because it didn't rely on anything: it just said "this is what it means to be inductive; now take the intersection of all the inductive things".

The crucial reason we're interested in $$\mathbb{N}$$ is because it's the fundamental thing you can do induction on. Induction on your conception of "$$\mathbb{N}$$ as a subset of the reals" is all very well, but is a bit weird. It is much better to think of induction as happening on "anything you can climb up", i.e. "anything with an operation that makes things bigger". If a property $$P$$ is such that "$$P$$ is true on everything less than $$x$$" always implies "$$P$$ is true for $$x$$" whenever $$x$$ is in your inductive structure, then $$P$$ is true for everything in the inductive structure.

The natural numbers happen to be especially nice because if you're working in the natural numbers, then there's nothing outside the inductive structure (by the definition of the naturals as the smallest inductive structure), so this actually tells you that $$P$$ is true everywhere. By contrast, showing $$P$$ is true for the real number 1, and that if $$P$$ is true for all real naturals less than $$x$$ then $$P$$ is true for $$x$$, you deduce a fact that is true for all real naturals but probably not for all reals.

• Thank you! This gives such an interesting view on induction. The trouble now is that I imagined Natural numbers were essential to the core idea of induction and we, therefore defined it in that way. Obviously, that definition has given me great trouble because how can we conclude the thing we define to be the set N, completely captures the notion of {1, 2, 3 ...}. Can we define {1, 2, 3, ...} independently from using N (defined using inductive sets). Overall, I suppose the true enigma for me is (if we imagine we have defined R with all its principles), how do we define Natural numbers? Jan 22, 2021 at 23:15
• Well, what do you mean by "completely captures the notion of {1,2,3,…}"? If you come up with a property that you know the naturals ought to have, you will find that you can prove it of this characterisation as the intersection of all inductive sets. This is a common thing in maths: come up with something you want to define, then come up with a possible definition, then play around to see if your definition makes sense and has the properties you wanted of it. It turns out that the inductive-sets characterisation of N does have all the properties anyone ever wants of N. Jan 23, 2021 at 8:20
• But without a more formal definition of what you think {1,2,3,…} ought to mean, then your question is a bit meaningless. The closest you could come to an answer is to use some other formalism like Peano arithmetic to define the natural numbers, and then show that the two definitions are isomorphic, using induction. (This is generally a great way to show you've got the right definition for something: define it in two completely different ways with different motivations, and show that the definitions are actually defining the same object.) Jan 23, 2021 at 8:22

The important feature that the formal definition gives is that it specifies what is in not in $$\mathbb N$$ as much as it specifies what is. For instance, you have an intuitive notion that $$\pi\notin\mathbb N$$. The definition lets us confirm that logically. Even though there are some inductive sets that contain $$\pi$$ (heck, all of $$\mathbb R$$ is an inductive set), there are also inductive sets that do not (like $$\mathbb Q$$). You can also point out inductive sets that don't contain negative numbers or rational numbers with a denominator greater than 1, and by the time you're done you can say things like $$\{1,2,3,...\}$$ in a mathematical statement without having to sheepishly add "You know what I mean".

The same issue comes up when the natural numbers are defined by the Peano axioms, where we don't have addition defined ahead of time. It's important there because it is essential to know that there isn't some special "inaccessible" natural number that we might call $$\infty$$ that can't be reached by counting up from $$1$$. The Peano axioms settle this with a slightly different notion of induction, but it is the same idea that we can have a set with an infinite number of elements but still be able to prove truths about all of them with a finite amount of work.

• Thank you. That is a good view. The thing is, if we do want to picky (I have honestly lost my ability to distinguish between a needless nitpicky-ness, and one that a good mathematician is 'supposed to have'), the concept of "by the time one is done" I believe, should not be used. if we can exclude infinitely many things from the natural numbers, why prove Induction through defining inductive sets instead of saying proving P(1), and that for all n, if P(n) then P(n+1) provides a situation of 'self-counting' that by the time it's done, the theorem holds for all natural numbers? Jan 22, 2021 at 23:22
• I ran out of space; do excuse my inability to write densely and efficiently. I'll add that it seems like the problem of self-counting is in a way, transported to the idea of succession in that N (defined in the way we did) mysteriously becomes {1, 2, 3, ...} through either again a 'self-counting' that is a feature of inductive sets, or an infinite process of elimination. I imagine this is why principle of Induction (unless you start from complete induction or well-ordering) is a principle. I imagined what we did was a 'proof', now I'm not quite certain if it was more of a justification. Jan 22, 2021 at 23:26
• I actually take back my statement about N becoming {1, 2, 3, ...} as I realized that even in the sets that are defined algebraically like {$x^2$| x $\in$ N } we can't really say the set of {1, 4, 9, ...} is equal to "the set of all squares of Natural numbers" (it's better to make an example of set like R since we haven't yet defined natural numbers but the point stands). one might always ask "how do you know $n_0$ is an element of the set" and you argue P($n_0$). It's just the property of Roster notation to always seem...incomplete. I'm sorry for ranting here and questioning the obvious. Jan 23, 2021 at 0:06

There is a serious problem in the definition you have been given! Basically, it is circular!! One cannot construct $$ℝ$$ unless one already has a set $$ℕ$$ with constants $$0,1∈ℕ$$ and binary operations $$+,·$$ on $$ℕ$$ such that $$(ℕ,0,1,+,·)$$ satisfies PA, and PA includes induction! For an actually proper mathematical construction of $$(ℝ,0,1,+,·)$$ from $$(ℕ,0,1,+,·)$$, you can consult Spivak's "Calculus". So whoever gave you this circular 'definition' of natural numbers clearly does not know that it actually does nothing from a proper foundational perspective. And if foundations are not the point, then there is absolutely no reason to talk about inductive sets!

Patrick has hinted at, but not really explained, the true meaning of the idea of inductive sets. This is a matter of set theory. Historically, some people did not like having to axiomatize $$ℕ$$ via all the axioms of PA, and sought to reduce everything to set theory. They did so via introducing the notion of an inductive set. Formally, a set $$S$$ is inductive iff $$∅∈S ∧ ∀x{∈}S\ ( \ x∪\{x\}∈S \ )$$. The problem is, there is no way to prove the existence of an inductive set without using some assumption of the same kind! So they decided to simply add an axiom (to the set theory they were building) that just baldly asserts the existence of an inductive set. Though such an assumption cannot be justified non-circularly, it does get us somewhere, because from that and other set-theoretic axioms we can prove that there is an inductive set that satisfies induction! $$\def\ind{\text{Ind}}$$

Namely, define $$\ind(S)$$ to denote that $$S$$ is inductive. Let $$I$$ be such that $$\ind(I)$$ (by the axiom that an inductive set exists). Let $$N = \{ x : x∈I ∧ ∀S\ ( \ \ind(S) ⇒ x∈S ) \ \}$$. Then we can prove that $$∀S\ ( \ \ind(S) ⇒ N⊆S \ )$$. From this we get $$∀S{⊆}N\ ( \ \ind(S) ⇒ S=N \ )$$, which is what we call induction in set theory. Note that the specific initial element and successor operation we use in the definition of an inductive set is not essential, except that it must be definable. In the above definition we used initial element $$∅$$ and successor operation $$( \ x ↦ x∪\{x\} \ )$$. However, if you study set theory later you will see that it is most convenient to use this particular choices, and one reason is that you can define for every $$k,m∈N$$ that $$k iff $$k∈m$$.

• Thank you. I see your point. In our course, we assumed knowing the definition of the operations + and ×, then we assumed having a none-empty set called R that satisfies 14 principles (the last one being the completeness principle). I imagined that is a different way of creating a numerical system after which one defines $\mathbb{N}$. Is that an invalid approach? Anyways, the course's goal was not to define $\mathbb{R}$ nor $\mathbb{N}$, but to introduce student's to the notion of correct mathematical writing using accessible subjects, hence not being too detailed nor careful in definitions. Jan 23, 2021 at 6:54
• @RezaEvergreen: As I had explained in my post, such an approach is simply nonsensical because we cannot construct the reals without already having the naturals satisfying induction, so it is utterly meaningless to later define naturals as part of the reals via the notion of "inductive set". Instead, one should use the axiomatization of PA that I linked to. Jan 23, 2021 at 7:01
• @user21820 "we cannot construct the reals without already having the naturals satisfying induction" That's not really true. We could have an axiomatic framework which postulates the existence of a complete ordered field, and then show that that's unique up to isomorphism, and then at that point could build the natural numbers within it. I vaguely recall seeing this approach taken by some reasonably-popular analysis text ... Jan 23, 2021 at 7:33
• @NoahSchweber: You know what I mean by "construct"; assuming that the reals exist (i.e. satisfies some axiomatization) is not the same as constructing... Jan 23, 2021 at 11:36
• @NoahSchweber: By the way, without the natural numbers, just how do you prove that all complete ordered fields are isomorphic? Jan 23, 2021 at 12:29