How to prove that there are $n$ natural numbers that are less or equal than $n$ and what properties are allowed to use in induction.

Question

Let $n \in \mathbf{N}$. I wondered how to prove that there are exactly $n$ natural numbers that are smaller or equal than $n$. This seems somewhat circular which confuses me. I guess the way to do this is by induction and using the successor, but again, the circularity that I see feels weird. So my idea would be: induction over $n$. The case $n=1$ is clear by definition and if the induction holds for $n$, then we at least have $n$ elements that are less or equal than $s(n)$, as well as $s(n)$ itself, making it at least $s(n)$ elements. If there would be another natural number $m$ with $m \leq s(n)$, then it has to hold that $m \leq n$, since we assumed it to be a different element. Hence it is one of the $n$ elements and the desired result follows.

I also wondered whether this property is allowed to use as a property in the induction and what properties are. For example, I read something like: for all $n$ the notion $A_n$ is defined. Is "is defined" a property I can proof with induction? Are there limits of what properties I can proof for $\mathbf{N}$ using induction and if so, what are they, meaning, which properties are allowed?

Answer 1

For each $n \in \mathbb{N}$, let $A_n = \{k \in \mathbb{N} : k \leq n\}$. I would interpret your statement formally as $|A_n| = n$. I think that this is actually the definition of "having $n$ elements": a set $S$ has $n$ elements means there is a bijection from $S$ to $A_n = \{1, 2, \dots, n\}$.

Answer 2

I would say much your proof is good. The structure is certainly correct, and many of the details as well. Two small remarks though:

First, I am not sure that you can do the base case simply 'by definition'. That is, is it a definition that $1$ is the only number smaller or equal to $1$? It depends on exactly what definitions and axioms you work with, but probably the base case is not so trivial. For the base case you need to show that $1 \leq 1$, and that for any number $n \neq 1$, it holds that $n \not \leq 1$.

Second, in the inductive step, you need to make sure that $s(n)$ is not one of the numbers that are smaller or equal to $n$. So, you need to show (or at least point out) that $s(n) \not < n$, so that when you add $s(n)$ to the $n$ numbers smaller or equal to $n$, you actually increase the set size by $1$ (as opposed to having $s(n)$ already in the set of numbers smaller or equal to $n$)

But yes, it is very good of you to include that part that says that if $m$ is a number other than the $n$ numbers that are smaller or equal to $n$, as well as other than $s(n)$, then $m \not \leq s(n)$. You indeed need that part to ensure that $s(n)$ is the only number that is not smaller or equal to $n$, but that is smaller or equal to $s(n)$. Well done!

Finally, note that with these small corrections, it turns out that what you do in the inductive step very much mirrors what you do in the base case: you show that there is at least one object such that .... and that there is at most one such object ...