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