I am trying to understand the construction of $\mathbb{R}$ with slopes / quasi-isomorphism, as shown here
at some point, the following property is used :
$$\forall p \in \mathbb{Z},\forall q \in \mathbb{Z}\setminus\lbrace{0\rbrace},\exists ! r \in \mathbb{N} \text{ st. } 2p-|q|\leq2qr\leq2p+|q|$$
which is denoted by $$r=p:q$$
and the following property
$$|p/q-p:q|<\frac12$$
with $p/q$ denotes the euclidian division,
Can anyone help me proving these two results ?
Thanks a lot
T.D.
On
The following general theory can be used to forge the proofs that the OP is inerested in.
Recall the definition of integer intervals. If $a \lt b$ the interval $[a,b]$ is said to have length $b - a$; it contains $b - a + 1$ elements.
Recall that for each $n \gt 0$ we can define the congruence class of modulo $n$ integers containing an integer $c$,
$\tag 1 [c]_n = \{c + kn \; | \; k \in \Bbb Z\}$
We state the following without proof.
Proposition 1: Let $n \gt 0$. For every $c \in \Bbb Z$ and every integer interval $[a,b]$ of length $n$,
$\tag 2 \text{#}(\,[c]_n \cap [a,b] \,) = 1 \text{ or } 2$
Moreover, $\text{#}(\,[c]_n \cap [a,b] \,) = 2$ implies $[c]_n \cap [a,b] = \{a,b\}$.
In the OP's reference link is the statement
$\tag 3 |\frac{p}{q} −p:q| \lt \frac{1}{2}$
This is incorrect - the inequality is not always strict and should be replaced by $\le$. As an aside, it is a bit disheartening to see the fraction $\frac{p}{q}$ since the idea is to construct the real numbers directly from the integers.
Example: If $p = 1$ and $q = 2$ then
$\quad 2p-|q| \le 2qr \le 2p+|q|$
reduces to
$\quad 0 \le 4r \le 4$
and has two solutions, $r = 0$ or $r = 1$.
First we'll prove the existence of such $r$. We will then can prove uniqueness for this $r$
The Euclidean Algorithm in $\mathbb{Z}$ tells us that for every $p,q \in \mathbb{Z}$ with $q \neq 0$ there exists unique $k,r \in \mathbb{Z}$ such that $p =kq + r'$ with $0 \leq r' < q$.
Now suppose that $q>0$ (The case when $q<0$ is analogous), then the inequality in the definition becomes
$$2p-q \leq 2pr' < 2p +q$$
Taking $r = k$ or $r = k + 1$ you can see that they're satisfied.
Now note that either $0 \leq 2r' \leq q$ or $q < 2r'<2q$.
In the first case we have that \begin{align} 2p-q &= 2(qk +r') -q = 2qk + 2r' - q = q(2k-1) + 2r' \\ & \leq q(2k-1) + q = 2qk \leq 2qk + 2r' +q = 2p +q \end{align}
Now, for the second case \begin{align} 2p-q &= 2(qk +r') -q = 2qk + 2r' -q = q(2k -1) + 2r' \\ &< q(2k-1) + 2q = q(2k+1) < 2q(k+1) = 2qk + 2q \\ &< 2qk + 2r' + q = 2(qk +r') + q = 2p +q \end{align}
We have that \begin{align} |p/q - p:q|< \dfrac{1}{2} &\iff 2|p/q - p:q| < 1 \\ & \iff 2|q| |p/q - p:q| = 2|q(p:q)-p| < |q| \end{align} We know that if $x = qk + r'$ with $0 \leq r' < q$, then $r = p:q = k$ or $k+1$ (for positive $q$, in the negative case you have $k-1$ instead).
Suppose that $p:q = k$. Then $2r' \leq |q|$ and $$2|q(p:q) - p| = 2|qk -p| =2|qk - (qk + r)| = |2r'| \leq |q|$$
Suppose that $p:q = k +1$. Then $q <r' \leq 2q$ and $$2|q(p:q) - p| = 2|q(k+1) -p| =2|qk + q - p| = 2|q-r'| \leq |q|$$
Suppose that $p:q = k-1$. Then $-q < 2r' <-2q$. $$2|q(p:q) - p| = 2|q(k-1) -p| =2|qk - q - p| = 2|-q-r'| \leq |q|$$
Now for the uniqueness part :
Suppose that $r_0$ and $r_1$ satisfy this inequalities and that $r_0 \neq r_1$, then $|r_0 - r_1|\geq 1$, multiply both sides by $2q$ and note that this implies that $r_0$ and $r_1$ are at least $2q$ units apart but between $2p-q$ and $2p+q$ there are only $2q$ numbers, a contradiction.
Whence $|r_0-r_1<1\implies r_0=r_1$