MHB Can We Prove the Inductive Set Contains Only Natural Numbers?

[mathmari]

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:

 

[mathmari]

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:

 

[I like Serena]

Hey mathmari!

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

 

[mathmari]

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

 

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

 

[mathmari]

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?

 

[mathmari]

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?

 

[mathmari]

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:

 

[I like Serena]

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?