2
$\begingroup$

I an learning proofs with $\mathbb{N}$. Here are my axioms:

a)If $m,n \in\mathbb N$ then $m + n \in\mathbb N$

b)If $m,n \in\mathbb N$ then $mn \in\mathbb N$

c) $0 \notin\ \mathbb N$

d) For every $m \in\mathbb Z$, we have $m \in\mathbb N$ or $m = 0$ or $-m \in\mathbb N$

Definition: $m > n \Leftrightarrow m - n \in\mathbb N$.

By the way, I would greatly appreciate if someone could please explain to me why this is. My strategy is to use a contradiction.

Proposition 1: (that I have proven)

For $m \in\mathbb Z$, one and only one of the following is true: $m \in\mathbb N$, $-m \in\mathbb N$, $m = 0$.

I have proven $1 \in\mathbb N$ and: Let $m,n,p \in\mathbb Z$. If $m < n$ and $n < p$ then $m < p$ by deriving $p - m = (p - n) + (n - m) \in\mathbb N$.

I have also proven: For each $n \in\mathbb N$ there exists $m \in\mathbb N$ such that $m > n$

Proposition 2:

Let $m,n \in\mathbb Z$. If $m \le n \le m$ then $m = n$.

I get confused because of the equality within the $\leq$. How could I approach this? By separating $<$ and $=$ ?

Any hints would be greatly appreciated.

$\endgroup$
8
  • 1
    $\begingroup$ Hint: $m-n\in \mathbb{Z}$. Now proceed with a result you have proven. $\endgroup$
    – Extremal
    Commented Feb 17, 2015 at 2:45
  • $\begingroup$ As for $m\leq n \leq m$, that means that $m\leq n$ and $n\leq m$. Since $m=m$, you have that $n$ is sandwiched inbetween, and therefore must also equal $m$. (If you don't believe that statement, then consider what happens if $n>m$ or if $n<m$ and arrive at a contradiction) $\endgroup$
    – JMoravitz
    Commented Feb 17, 2015 at 3:30
  • $\begingroup$ To prove anything about $\;m \le n\;$, you would need to know its definition in terms of $\;>\;$, but you haven't provided us with one. Is it $\;\lnot(m > n)\;$? Or $\;n > m \;\lor\; n = m\;$? $\endgroup$ Commented Feb 17, 2015 at 6:43
  • $\begingroup$ @MarnixKlooster Hi! Thank you for your feedback. I have edited my original post to include the definition. $\endgroup$
    – Johnathan
    Commented Feb 17, 2015 at 20:31
  • 1
    $\begingroup$ @Johnathan Then you cannot prove this, until you're given (or you've chosen) a definition. Note that @AaronMaroja's answer assumes the definition is $\;m \le n \;\equiv\; \lnot(m>n)\;$, when he says that "$m > n$ [...] is a contradiction", viz. with his assumption $m \le n$. $\endgroup$ Commented Feb 18, 2015 at 6:30

3 Answers 3

1
$\begingroup$

First proposition

  • If $m \in \mathbb N$ and $-m \in \mathbb N$ then $ 0 \in \mathbb N$, absurd.

  • If $m \in \mathbb N$ and $ m = 0$, absurd.

  • Similar to $-m$.

Therefore it folows the affirmation.

Second proposition

If $m \leq n \leq m$ then $m - n \in \mathbb Z$ and by the first proposition only one of those $3$ holds, then if $m - n \in \mathbb N$ then $m>n$ by definition, which is a contradiction. Similar if $n-m \in \mathbb N$.

Thus the only possibility is $m - n = 0$.

$\endgroup$
5
  • $\begingroup$ @Johnathan Feel free to ask if you have any questions. $\endgroup$ Commented Feb 17, 2015 at 22:31
  • $\begingroup$ Thank you very much for your input. Sorry for the late reply. Ok, so if $m,n \in\mathbb Z$, then I understand that $m+(−n) \in\mathbb Z$ and that the result is exclusively 0, a natural number or its inverse is a natural number. I am confused on how you derive your contradiction from: $m -n \in\mathbb N$ then $m>n$ by definition. Sorry for the confusion. :) $\endgroup$
    – Johnathan
    Commented Feb 21, 2015 at 0:32
  • $\begingroup$ As $m\leq n$ by hypothesis then if $m> n$ you have a contradiction. $\endgroup$ Commented Feb 21, 2015 at 0:59
  • $\begingroup$ I think I understand! Is it a contradiction relative to the proposition? For example, $m > n$ contradicts $m \le n$, and similarly, $n > m$ contradicts $n \le m$, right? Hence, m = n is the only option that keeps the proposition true, right? Wow! It's so simple! Thank you! :) $\endgroup$
    – Johnathan
    Commented Feb 21, 2015 at 2:05
  • $\begingroup$ $m - n = 0$ is the only ´possibility, that's right! $\endgroup$ Commented Feb 21, 2015 at 2:06
1
$\begingroup$

For your reference, here is a more 'logical' version of Aaron Maroja's argument, spelling out all steps in full formal detail, and referring only to the axioms, not to e.g. your proposition 1.

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \unicode{x201c}\mbox{#2}\unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\followsfrom}{\Leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $As discussed in the comments for this question, the answer to your question

I get confused because of the equality within the $\leq$. How could I approach this? By separating $<$ and $=$ ?

is: by applying the definition of $\;\le\;$. And since you've not been provided with such a definition, we will use $$ m \le n \;\equiv\; \lnot(m>n) $$


We can now start at the most complex side of the theorem, and calculate as follows:

$$\calc m \le n \le m \calcop\equiv{definition of $\;\le\;$, twice; definition of $\;<\;$, twice} \lnot(m - n \in \mathbb N) \;\land\; \lnot (n - m \in \mathbb N) \calcop\then{axiom $\ref d$, twice -- the only way forward using only the axioms} (m - n = 0 \;\lor\; -(m - n) \in \mathbb N) \;\land\; (n - m = 0 \;\lor\; -(n - m) \in \mathbb N) \calcop\equiv{arithmetic: simplify; logic: extract common disjunct} m = n \;\lor\; (n - m \in \mathbb N \;\land\; m - n \in \mathbb N) \calcop{\tag{*} \then}{axiom $\ref a$ -- this is the key step in this proof} m = n \;\lor\; (n - m) + (m-n) \in \mathbb N \calcop\equiv{arithmetic: simplify} m = n \;\lor\; 0 \in \mathbb N \calcop\equiv{axiom $\ref c$; logic: simplify} m = n \endcalc$$


Note that except for the key step $\ref *$, all the steps in the above calculation are almost forced by the desire to simplify, and keeping our goal in mind.

$\endgroup$
-1
$\begingroup$

Suppose $m \ne n$. That means: $m < n < m$. Then by definition, $m−n∈N$ and $n-m∈N$. By axiom (a): $0=m-n+n-m∈N$. Came to contradiction by axiom (c), so $m$ is indeed equal to $n$.

$\endgroup$
2
  • 2
    $\begingroup$ If $m \ne n$, then I can understand that (WLOG) $n < m$, or vice versa. I don't understand, however, how you could have $m < n < m$? That would imply that $m \ne m$. $\endgroup$
    – daOnlyBG
    Commented Feb 17, 2015 at 4:10
  • $\begingroup$ Notice that $\neg (a \wedge b)$ is equivalent to $\neg a \vee \neg b$. So you can't say that $m< n$ and $n< m$, that is $m < n < m$. The correct would be $m>n$ or $m < n$. $\endgroup$ Commented Feb 17, 2015 at 21:19

You must log in to answer this question.

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