10
$\begingroup$

I'm being asked to prove that if $k∈ \Bbb Z$, $k+1>k$. Judging from our instructions, it appears (I am unsure) as though I cannot use the law of induction to solve this. A hint gives that the proof depends on $1∈\Bbb N$. I was thinking of approaching this by using if $k∈\Bbb N$ then $x+k∈\Bbb N$. Problem is, we were not given $k∈\Bbb N.$ Is this solvable without induction?

We are given associativity, commutivity, and the identity elements for addition and multiplication, the additive inverse, the properties of $=$, and basic set theory and logic.

Order for the integers is given by Let $m,n,p∈\Bbb Z$. If $m<n$ and $n<p$, $m<p$.

Also assumed, and possibly relevant is if $x∈\Bbb Z$, then $x∈\Bbb N$ or $-x∈ \Bbb N$ or $x=0$.

$\endgroup$
  • 3
    $\begingroup$ You'd need to expand on what definitions you're working from. $\endgroup$ – Pat Devlin Jan 22 '17 at 2:00
  • 4
    $\begingroup$ What is your definition of "$>$"? And to @TheCount 's point, here's some guidance on MathJax $\endgroup$ – Joffan Jan 22 '17 at 2:10
  • 3
    $\begingroup$ Can't you substract $k$ in the inequation and assume that $1 > 0$? $\endgroup$ – joseabp91 Jan 22 '17 at 2:13
  • 1
    $\begingroup$ I think that some of the comments above are asking for a definition of $x>y$. In my answer, I am using $x>y$ defined as $x-y\in\mathbf{N}$, but it's not necessarily the only way to define it. I do not think your "if $m<n$ etc." works as a definition of $>$ (without some extra work) because it already seems to assume that $>$ is defined. $\endgroup$ – Anonymous Jan 22 '17 at 3:17
  • 1
    $\begingroup$ @Wildcard this is degenerating, so I'll drop off after this comment (please do not take it as rudeness). However: note that the 0 and the 1 that people introduce when axiomatizing the integers have no meaning except being, respectively, the additive and multiplicative identity. Of course, you need formal logic on top of the axioms etc. But the essence is, you can't base yourself on "intuition" when working at the level the original question was asked. $\endgroup$ – Anonymous Jan 22 '17 at 10:18
12
$\begingroup$

As stated in the comments, the answer may depend to some extent on what set of axioms for the integers you are using; it also depends on the exact definition of $"a>b"$. But under most axiomatizations, assuming that $"a>b"$ is defined as $"(a-b)\in \mathbb{N}"$ (where $\mathbb{N}$ is the set of positive integers), something like the following proof by contradiction would work:

$[(k+1)\ngtr k]~~~ \equiv~~~~ [(k+1)-k \notin \mathbb{N}]~~~$(definition of $a>b$)

$\implies~~~ [(1+k)-k \notin \mathbb{N}]~~~$ (commutativity of addition)

$\implies~~~[1+(k-k) \notin \mathbb{N}]~~~$ (associativity of addition)

$\implies~~~[1\notin \mathbb{N}]$

Note that $1\in\mathbb{N}$ is often not part of the axioms of the integers, and in general must itself be proved. The original question suggests it has "already" been proved, so here we can take it as a given. Otherwise, a rough outline of the proof that $1\in\mathbb{N}$ would be (under most axiomatizations of the integers, such as the one here, that I particularly like):

  1. Prove that for any integer $a$ we have $a\cdot 0=0$. Proof sketch: $0=a\cdot 0 - a\cdot 0$ $= a\cdot (0+0) - a\cdot 0$ $=a\cdot 0$.
  2. Prove that for any integer $a$ we have $-a=a\cdot(-1)$. Proof sketch: using the above $0 = a \cdot (1+(-1)) = a+ a\cdot(-1)$.
  3. Combine the above with the axiom of closure of $\mathbb{N}$ under multiplication to obtain $-1\notin\mathbb{N}$.
  4. Exploit the trichotomy axiom (every integer $a$ must satisfy exactly one of the following three: either $a\in\mathbb{N}$, or its additive inverse $-a\in\mathbb{N}$, or $a=0$ i.e. $a$ is an additive identity) to deduce that $1\neq 0$ since otherwise for one $a\in\mathbb{N}$ we'd have $a=a\cdot 1= a\cdot 0=0$.
  5. Exploit the trichotomy axiom again to conclude that since $1\neq 0$ and $-1\notin\mathbb{N}$, then $1\in\mathbb{N}$.
$\endgroup$
  • $\begingroup$ I hope this is indirect. $\endgroup$ – mvw Jan 22 '17 at 2:18
  • $\begingroup$ Eh, wrong symbol... fixed it (thanks @mvw). $\endgroup$ – Anonymous Jan 22 '17 at 2:19
  • 5
    $\begingroup$ You could start with 1 \in N with no negation or contradiction. $\endgroup$ – djechlin Jan 22 '17 at 3:33
  • $\begingroup$ I don't get how the first $\Rightarrow$ follows from associativity, as we have $k-(k+1)=(k-k)-1\neq(k-k)+1$. $\endgroup$ – Hermann Döppes Jan 22 '17 at 3:36
  • 1
    $\begingroup$ I tried to fix the unbalanced parens in the second and third line, but there seems to be a questionable rule enforcing edits to change at least six characters. $\endgroup$ – Sven Marnach Jan 22 '17 at 10:02
8
$\begingroup$

If you assume that $1 > 0$ is true, so it's trivial because, given $k \in \mathbb{Z}$, $$ \mbox{ the inequation } \quad k + 1 > k \qquad \mbox{ is equivalent to } \qquad 1 > 0 $$ In general, if $x , y , z \in \mathbb{R}$, $$ \mbox{ the inequation } \quad x > y \qquad \mbox{ is equivalent to } \qquad x + z > y + z $$ and you can replace "$>$" by "$\geq$", "$<$", "$\leq$" or "$=$".

$\endgroup$
  • $\begingroup$ can't this be extended to well ordered fields? $\endgroup$ – SAJW Jan 22 '17 at 2:32
  • $\begingroup$ Yes it can be done but must always maintain some properties $\endgroup$ – joseabp91 Jan 22 '17 at 2:47
  • $\begingroup$ Perhaps $1 ∈ N$, is supposed to be used to indicate that 1>0? $\endgroup$ – B. Simmons Jan 22 '17 at 3:23
  • 1
    $\begingroup$ @B.Simmons when you were given the axiomatic definition of the integers, there were some axioms defining the set of the "positive" integers, too (which is what you denote by $\mathbf{N}$). The usual way to define the relation $>$ between two integers is to say "we write x>y to mean that the sum between $x$ and the additive inverse of $y$ belongs to the set of positive integers". But you need to say somewhere what you mean by $x>y$. $\endgroup$ – Anonymous Jan 22 '17 at 3:35
  • 3
    $\begingroup$ I don't know if there is a proof of the inequation $1 > 0$, but if you assume it, you have that $k + 1 > k$ for all $k \in \mathbb{N}$ by the explanation in my answer. $\endgroup$ – joseabp91 Jan 22 '17 at 3:37
1
$\begingroup$

You should search for it in Theory of Numbers. There are axioms for proving it for Natural numbers. Peano's Axioms this can be used to prove it. I hope you solve it.

A set of $N$ objects is called a set of natural numbers if it satifies Peano's Axioms:

  • Axiom 1: $1$ belongs to $N$
  • Axiom 2: to each element $n$ belonging to $N$, there corresponds a unique element $n'$ called sucessor of $n$.
  • Axiom 3: For each n belonging to $N$, we have $n' \ne 1$.
  • Axiom 4: if $m,n$ belong to $N$ then $m' = n'$ implies that $m=n$, or $m\ne n$ implies that $m' \ne n'$.
  • Axiom 5: et $M$ be a set of elements of $N$, i.e. $M$ is a subset of $N$ then $M=N$ provided the following two conditions are satisfied
    1. $1$ belongs to $M$
    2. If $k$ belongs to $M$ then $k'$ belongs to $M$, $k'$ being sucessor of $k$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.