# Show that the set is inductive

• MHB
Gold Member
MHB
Hey! 😊

I am looking the following:

Prove that for $m,n\in \mathbb{N}$, $m>n$ it holds that $m-n\in \mathbb{N}$.
Hint: Consider $A=\left \{n\in \mathbb{N}\mid \forall m\in \mathbb{N}, m>n:m-n \in \mathbb{N}\right \}$ and show that $A$ is inductive.

I have done the following:

To show that $A$ is inductive we have to show that $1\in A$ and that if $n\in A$ then also $n+1\in A$, right?

We have that $1\in A$ since $\forall m\in \mathbb{N}$ with $m>1$ we have that $m-1 \in \mathbb{N}$. Can we just say that?

Let $n\in A$. That means that $\forall m\in \mathbb{N}$ with $m>n$ we have that $m-n \in \mathbb{N}$

We have that $n+1\in A$ since $m-(n+1)=(m-n)+1$ We have that $m-n\in \mathbb{N}$ and the successor is also in $\mathbb{N}$.

Is that correct and complete? :unsure:

HOI
Hey! 😊

I am looking the following:

Prove that for $m,n\in \mathbb{N}$, $m>n$ it holds that $m-n\in \mathbb{N}$.
Hint: Consider $A=\left \{n\in \mathbb{N}\mid \forall m\in \mathbb{N}, m>n:m-n \in \mathbb{N}\right \}$ and show that $A$ is inductive.

I have done the following:

To show that $A$ is inductive we have to show that $1\in A$ and that if $n\in A$ then also $n+1\in A$, right?

We have that $1\in A$ since $\forall m\in \mathbb{N}$ with $m>1$ we have that $m-1 \in \mathbb{N}$. Can we just say that?
How does it follow that $m-1 \in \mathbb{N}$? That would be true if $1\in N$ but that is what you are trying to prove.

Let $n\in A$. That means that $\forall m\in \mathbb{N}$ with $m>n$ we have that $m-n \in \mathbb{N}$

We have that $n+1\in A$ since $m-(n+1)=(m-n)+1$ We have that $m-n\in \mathbb{N}$ and the successor is also in $\mathbb{N}$.

Is that correct and complete? :unsure:

Gold Member
MHB
How does it follow that $m-1 \in \mathbb{N}$? That would be true if $1\in N$ but that is what you are trying to prove.

Ok... So what I am supposed to do now? I got stuck right now. :unsure:

Homework Helper
MHB
Hey mathmari!

Which definitions and axioms do you have for $\mathbb N$, the operator $>$, and the operator $-$? 🤔

Gold Member
MHB
Which definitions and axioms do you have for $\mathbb N$, the operator $>$, and the operator $-$? 🤔

For the above proof do we need that these three sets are inductive? :unsure:

There is also an other hint, to look at the idea of proof for $(n, n+1)\cap \mathbb{N}=\emptyset$.

Last edited by a moderator:
HOI
For the above proof do we need that these three sets are inductive? :unsure:
The problem asks you to PROVE that N is inductive!
Also you do NOT have to prove that 1 is in A- you were asked to prove that N is inductive, not A.

There is also an other hint, to look at the idea of proof for $(n, n+1)\cap \mathbb{N}=\emptyset$.

Gold Member
MHB
The problem asks you to PROVE that N is inductive!
Also you do NOT have to prove that 1 is in A- you were asked to prove that N is inductive, not A.

I thought that we have to prove that $A$ is inductive, because of the given hint.

So we have to show that $\mathbb{N}$ is inductive?

HOI
No, I misread the problem. It does, indeed, specifically say "prove A is inductive". Sorry about that.

One thing you will need, for x and y in N, exactly how is "n- m" defined?

Gold Member
MHB
One thing you will need, for x and y in N, exactly how is "n- m" defined?

We have to define - m and then we get the sum n+(-m), or not?

Or do we set n-m=s and so we consider n=s+m?

Gold Member
MHB
I thought about that again and I did the following:

$1\in A$ : Let $m > 1$ and $m-1=r \Rightarrow m = 1 + r$ for some $r \in \mathbb{N}$ . We have that since $\mathbb{N}$ is an inductive set and $r\in \mathbb{N}$ then $r+1\in \mathbb{N}$, i.e. $m\in \mathbb{N}$.

Let $n\in A$. Then let $m > n$ and $m = n + r$ for some $r \in \mathbb{N}$ then $m \in \mathbb{N}$. We want to prove that $n+1\in A$, i.e. that if $m' > n+1$ and $m' = (n+1) + r$ for some $r \in \mathbb{N}$ then $m'\in \mathbb{N}$.

From $m'>n+1$ we have that $m'-1>n$. So we get that $m'-1\in A$. Then $m'-1=n+r$ for some $r\in \mathbb{N}$, so $m'=(n+1)+r$, for the same $r\in \mathbb{N}$ and so $n+1\in A$.

I think that it is somehow confusing what I have done... :unsure:

Homework Helper
MHB
There are multiple definitions for the set of natural numbers $\mathbb N$.
The first formal set given on wiki is:
The five Peano axioms:
1. 0 is a natural number.
2. Every natural number has a successor which is also a natural number.
3. 0 is not the successor of any natural number.
4. If the successor of x equals the successor of y, then x equals y.
5 The axiom of induction: If a statement is true of 0, and if the truth of that statement for a number implies its truth for the successor of that number, then the statement is true for every natural number.

Some forms of the Peano axioms have 1 in place of 0. In ordinary arithmetic, the successor of x is x+1.
🧐

Furthermore, it defines a comparison operator:
A total order on the natural numbers is defined by letting $a\le b$ if and only if there exists another natural number $c$ where $a+c=b$.
The other comparison operators are then defined using this definition.
This definition assumes that $0$ is an element of $\mathbb N$. If it is excluded, then we must use a modified version of this definition.
🧐

This references addition ($+$) for which we need a definition as well, which is given as:
One can recursively define an addition operator on the natural numbers by setting a + 0 = a and a + S(b) = S(a + b) for all a, b. Here, S should be read as "successor".
🧐

I didn't immediately see a definition for the difference operator ($-$) for natural numbers.
Let's make it:
The difference $a-b$ is defined as the number $c$ such that $a=b+c$ provided that such a number $c$ exists in $\mathbb N$. Otherwise the difference is undefined.
Note that there is no such thing as $-b$, since it is not an element of $\mathbb N$ for positive $b$. So we cannot define the difference $a-b$ as the usual $a+(-b)$.
🧐

Can we find a proof in which we only use these definitions and axioms? 🤔