How to justify: for every integer $r$ in $[1, k-1]$, there is an integer $j$ in $[0, k-1]$, such that $r + j = k$
I'm a beginner working through a basic number theory textbook, attempting every exercise.
In developing a solution I found that I don't know how to do one step.
I want to justify the following:
For every integer $r$ in the range $[1, k-1]$, we can find an integer $j$ in the range $[0, k-1]$, such that $r + j = k$.
How do I justify this / prove this?
Part of the problem I'm having is that it is obviously true, and that actually makes it harder for my brain to break down into rigorous argument steps.
My apologies if this is trivially easy. I've struggled and can't see it.
2 answers
This is a common problem when you transition from presentations of mathematics for a general audience to presentations aimed at potential mathematicians. You realize that many of the concepts you've been taking for granted for years were never actually clearly defined. Concepts like natural numbers, integers, rationals, real numbers, polynomials, functions, sets, graphs, and many others. (As a warning, another issue at this point is to take the first "real" definition you find as the only definition. There are many distinct but equivalent ways of presenting these or any mathematical concept.) Of course, another issue is the introduction of more rigorous proofs and the corresponding logical manipulations required. I suspect in this case you are having trouble articulating a proof of an existential statement in a satisfying manner.
For simplicity, I'll reduce you statement to one about natural numbers rather than integers. We can then rewrite it as:
For all naturals $k$ and naturals $r$ such that $1 \leq r \leq k$, there exists a natural $j$ such that $0 \leq j \leq k$ and $r + j = k+1$.
As mentioned, there are many ways to define or characterize the naturals. They can be axiomatized with, for example, Peano Arithmetic (PA), or directly defined within set theories. In all cases, the key claim is induction.
Induction states that given some property of natural numbers $P$, if $P$ holds for $0$ (write this as $P(0)$) and for all natural numbers $n$, $P(n)$ implies $P(n+1)$, then $P$ holds for all natural numbers.
We can prove the statement above by induction.
Proof: Let $P(k)$ be the property that for all naturals $r$ such that $1 \leq r \leq k$, there exists a natural $j$ such that $0 \leq j \leq k$ and $r + j = k + 1$.
We first need to prove $P(0)$. There are no $r$ such that $1 \leq r \leq 0$, so $P(0)$ holds vacuously.
Next, assume $P(k)$ holds and now we want to establish $P(k+1)$. We proceed by cases.
In the first case, assume we're given a natural $r$ such that $1 \leq r \leq k$. Then certainly $1 \leq r \leq k + 1$. Further, we can use $P(k)$ to get a $j$ such that $0 \leq j \leq k$ and $r + j = k + 1$. We then have that $1 \leq j + 1 \leq k + 1$ and $r + (j + 1) = (k + 1) + 1$ which proves $P(k+1)$ in this case.
For the second case, assume $r = k + 1$. This also clearly satisfies $1 \leq r \leq k + 1$. Choosing $j = 1$ gives us a $j$ such that $r + j = (k + 1) + 1$ with $0 \leq j \leq k + 1$. Proving $P(k+1)$ in this case.
There are no other choices of $r$ satisfying $1 \leq r \leq k+1$ so these are all the cases. By induction, we've shown that $P(k)$ holds for all $k$. $\square$
Why did I present this proof? I could have instead just used high-level properties of integer arithmetic. For example, here's another proof, for integers rather than naturals.
Proof: To prove for all integers $k$ and $r$ such that $1 \leq r \leq k$, there exists a $j$ such that $0 \leq j \leq k$ and $r + j = k + 1$, we simply need to provide for each $k$ and $r$ an appropriate $j$. Once we have such a $j$, we need to verify that it satisfies the conditions under the given assumptions. In this case, we can easily solve for $j$, namely $j = k + 1 - r$. This expression is (anti-)monotonic in $r$ so the min/max values of $j$ are determined by the max/min values of $r$. We see that the minimum value of $j$ is $k + 1 - k = 1$ and the maximum value is $k + 1 - 1 = k$, so $j$ is in the desired range. $\square$
Arguably, it would be clearer to make the dependence of $j$ on $k$ and $r$ explicit and write something like $r + j(k, r) = k + 1$ with $j$ being explicitly a function of $k$ and $r$. Not having a good grasp on this dependence in proving existential statements is a common issue.
The point of my first, induction-based proof is that it illustrates the key fact about naturals that we need in general. For proving a property about all naturals we can always fall back to induction, though it may not be the most elegant proof. In my second proof, I explicitly and implicitly used many (unproven) facts about integer arithmetic. What would you do if you wanted to prove my claim about monotonicity, or that $r + j = k + 1$ is equivalent to $j = k + 1 - r$, or that $k - k = 0$ or $0 + k = k$? Some presentations of natural numbers/integers take some of these properties as axiomatic or as easy consequences properties of addition, but why should I need to take something like the commutativity of addition as an axiom? In other presentations, we can prove these properties via induction and essentially any others of the form "property $P$ holds for all naturals $n$".
To be clear, my first proof is also using unproven facts. If we wrote $S(n) = n + 1$, we'd see that most of the time we would not need facts about addition in general but only about this successor function. Of course, those facts would still need to be proven, typically via induction.
0 comment threads
Looks like some kind of "brain training". Looks very basic, but basic things can be very tricky if posed in a way you are not used to think.
The way to tackle those things is to transform what is given into a representation you are used to work with.
Lets go:
$r+j=k$ is equivalent to $j=k-r$. The nearly invisible advantage is that the later is a function for the unknown $j$ based on the given parameters $k, r$.
Now, $r\in [1, k-1]$ rewrites to $-r \in [(1-k), -1]$.
Adding $k$ results to $j:=k-r\in[1,k-1]\subset [0,k-1]$.
0 comment threads
0 comment threads