0
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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 ...

$\endgroup$
0
$\begingroup$

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\}$.

$\endgroup$
4
  • $\begingroup$ Rather than being by definition, wouldn't it follow from the existence of the identity bijection? $\endgroup$
    – Joe
    Nov 4, 2021 at 22:46
  • $\begingroup$ @Joe I haven't learned set theory axiomatically. But in many books on informal set theory, the definition of "$|S| = n$" is "there exists a bijection $f \colon \{1, 2, \dots, n\} \to S$. $\endgroup$
    – Mason
    Nov 5, 2021 at 0:13
  • $\begingroup$ Yes, but $|\{1,\ldots,n\}|=n$ is not part of the definition you just gave, so to show that we need to show that there is a bijection from $\{1,\ldots,n\}$ to itself, which is trivial, the identity function from $\{1,\ldots,n\}$ to itself, but we technically need to show that. $\endgroup$
    – Joe
    Nov 5, 2021 at 0:51
  • $\begingroup$ @Joe Yes that is true. $\endgroup$
    – Mason
    Nov 5, 2021 at 0:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .