Prove $k+1>k $ where $k$ is an integer
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$.
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):
- 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$.
- 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)$.
- Combine the above with the axiom of closure of $\mathbb{N}$ under multiplication to obtain $-1\notin\mathbb{N}$.
- 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$.
- Exploit the trichotomy axiom again to conclude that since $1\neq 0$ and $-1\notin\mathbb{N}$, then $1\in\mathbb{N}$.
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 "$=$".
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$ belongs to $M$
- If $k$ belongs to $M$ then $k'$ belongs to $M$, $k'$ being sucessor of $k$.