# The inclusion map from the integers to the reals and universal properties of the floor and ceiling functions

Jordan Bell
April 29, 2016

## 1 Categories

If $X$ is a set, by a partial order on $X$ we mean a binary relation $\leq$ on $X$ that is reflexive, antisymmetric, and transitive, and we call $(X,\leq)$ a poset. If $(X,\leq)$ is a poset, we define it to be a category whose objects are the elements of $X$, and for $x,y\in X$,

 $\mathrm{Hom}(x,y)=\begin{cases}\{(x,y)\}&x\leq y\\ \emptyset&\neg(x\leq y).\end{cases}$

In particular, $\mathrm{id}_{x}=(x,x)$.

Let $U:\mathbb{Z}\to\mathbb{R}$ be the inclusion map. If $(j,k)\in\mathrm{Hom}(j,k)$, define $U(j,k)=(Uj,Uk)\in\mathrm{Hom}(Uj,Uk)$.

 $U\mathrm{id}_{j}=U(j,j)=(Uj,Uj)=\mathrm{id}_{Uj}.$

If $(j,k)\in\mathrm{Hom}(j,k)$ and $(k,l)\in\mathrm{Hom}(k,l)$, then $(k,l)\circ(j,k)=(j,l)$ and

 $U(k,l)\circ U(j,k)=(Uk,Ul)\circ(Uj,Uk)=(Uj,Ul)=U(j,l)=U((j,l)\circ(j,k)).$

This shows that $U:(\mathbb{Z},\leq)\to(\mathbb{R},\leq)$ is a functor.

## 2 Galois connections

If $(A,\leq)$ and $(B,\leq)$ are posets, a function $G:A\to B$ is said to be order-preserving if $a\leq a^{\prime}$ implies $G(a)\leq G(a^{\prime})$. A Galois connection from $A$ to $B$ is an order-preserving function $G:A\to B$ and an order-preserving function $H:B\to A$ such that

 $\textrm{G(a)\leq b if and only if a\leq H(b)},\qquad a\in A,\quad b\in B.$

We say that $G$ is the left-adjoint of $H$ and that $H$ is the right-adjoint of $G$.

Let $I:\mathbb{Z}\to\mathbb{R}$ be the inclusion map. Define $F:\mathbb{R}\to\mathbb{Z}$ by $F(x)=\lfloor x\rfloor$. For $n\in\mathbb{Z}$ and $x\in\mathbb{R}$, suppose $I(n)\leq x$. Then $F(I(n))\leq F(x)$. But $F(I(n))=n$, so $n\leq F(x)$. Suppose $n\leq F(x)$. Then $I(n)\leq I(F(x))\leq x$. Therefore $F:\mathbb{R}\to\mathbb{Z}$, $F(x)=\lfloor x\rfloor$ is the right-adjoint of $I:\mathbb{Z}\to\mathbb{R}$:11 1 See Roland Backhouse, Galois Connections and Fixed Point Calculus, http://www.cs.nott.ac.uk/~psarb2/G53PAL/FPandGC.pdf, p. 14; Samson Abramsky and Nikos Tzevelekos, Introduction to Categories and Categorical Logic, http://arxiv.org/abs/1102.1313, p. 44, §1.5.1.

 $I(n)\leq x\iff n\leq F(x),\qquad n\in\mathbb{Z},\quad x\in\mathbb{R}.$

Define $C:\mathbb{R}\to\mathbb{Z}$ by $C(x)=\lceil x\rceil$. For $n\in\mathbb{Z}$ and $x\in\mathbb{R}$, suppose $C(x)\leq n$. Then $I(C(x))\leq I(n)$. But $I(C(x))\geq x$, so $x\leq I(n)$. Suppose $x\leq I(n)$. Then $C(x)\leq C(I(n))$. But $C(I(n))=n$, so $C(x)\leq n$. Therefore $C:\mathbb{R}\to\mathbb{Z}$, $C(x)=\lceil x\rceil$ is the left-adjoint of $I:\mathbb{Z}\to\mathbb{R}$:

 $C(x)\leq n\iff x\leq I(n),\qquad x\in\mathbb{R},\quad n\in\mathbb{Z}.$
###### Lemma 1.

For $x\geq 0$,

 $\lfloor\sqrt{\lfloor x\rfloor}\rfloor=\lfloor\sqrt{x}\rfloor.$
###### Proof.

For $k\in\mathbb{Z}_{\geq 0}$ and $y\in\mathbb{R}_{\geq 0}$,

 $\displaystyle k\leq\lfloor\sqrt{\lfloor y\rfloor}\rfloor$ $\displaystyle\iff I(k)\leq\sqrt{\lfloor y\rfloor}$ $\displaystyle\iff k^{2}\leq\lfloor y\rfloor$ $\displaystyle\iff k^{2}\leq y$ $\displaystyle\iff k\leq\sqrt{y}$ $\displaystyle\iff k\leq\lfloor\sqrt{y}\rfloor.$

###### Lemma 2.

If $x\in\mathbb{R}$ and $n\in\mathbb{Z}_{\geq 1}$, then

 $\left\lfloor\frac{\lfloor x\rfloor}{n}\right\rfloor=\left\lfloor\frac{x}{n}% \right\rfloor.$
###### Proof.

For $k\in\mathbb{Z}$,

 $\displaystyle k\leq F(I(F(x))/I(n))$ $\displaystyle\iff I(k)\leq I(F(x))/I(n)$ $\displaystyle\iff I(k)I(n)\leq I(F(x))$ $\displaystyle\iff I(kn)\leq I(F(x))$ $\displaystyle\iff kn\leq F(x)$ $\displaystyle\iff I(kn)\leq x$ $\displaystyle\iff I(k)\leq x/I(n)$ $\displaystyle\iff k\leq F(x/I(n)).$

This means that $F(I(F(x))/I(n))=F(x/I(n))$. ∎

###### Lemma 3.

If $n\in\mathbb{Z}_{\geq 1}$ and $m\in\mathbb{Z}$, then

 $\left\lceil\frac{m}{n}\right\rceil=\left\lfloor\frac{m+n-1}{n}\right\rfloor.$
###### Proof.

For $k\in\mathbb{Z}$,

 $\displaystyle k\leq F(I(m+n-1)/I(n))$ $\displaystyle\iff I(k)\leq I(m+n-1)/I(n)$ $\displaystyle\iff I(k)I(n)\leq I(m+n-1)$ $\displaystyle\iff kn\leq m+n-1$ $\displaystyle\iff kn-n+1\leq m$ $\displaystyle\iff kn-n $\displaystyle\iff I(k-1) $\displaystyle\iff k-1 $\displaystyle\iff k\leq C(I(m)/I(n)).$

This means

 $F(I(m+n-1)/I(n))=C(I(m)/I(n)).$

## 3 The Euclidean algorithm and continued fractions

Let $a,b\in\mathbb{Z}_{\geq 1}$, $a>b$. Let

 $v_{0}=a,\quad v_{1}=b.$

Let

 $a_{1}=\lfloor v_{0}/v_{1}\rfloor,\quad v_{2}=v_{0}-a_{1}v_{1}.$

For $m\geq 2$, if $v_{m}\neq 0$ then let

 $a_{m}=\lfloor v_{m-1}/v_{m}\rfloor,\quad v_{m+1}=v_{m-1}-a_{m}v_{m}.$

Then $0\leq v_{m+1}.22 2 See Marius Iosifescu and Cor Kraaikamp, Metrical Theory of Continued Fractions, p. 1, Chapter 1.

For example, let $a=83$, $b=14$. Then

 $v_{0}=83,\quad v_{1}=14.$

Then

 $a_{1}=\lfloor 83/14\rfloor=5,\quad v_{2}=83-5\cdot 14=13.$

Then

 $a_{2}=\lfloor v_{1}/v_{2}\rfloor=14/13\rfloor=1,\quad v_{3}=v_{1}-a_{2}v_{2}=1% 4-1\cdot 13=1.$

Then

 $a_{3}=\lfloor v_{2}/v_{3}\rfloor=\lfloor 13/1\rfloor=13,\quad v_{4}=v_{2}-a_{3% }v_{3}=13-13\cdot 1=0.$

As $v_{3}=1$ and $v_{4}=0$,

 $\gcd(83,14)=1.$

Written as a continued fraction, we get

 $\frac{14}{83}=[0;5,1,13].$

For example, let $a=168$, $b=43$. Then

 $v_{0}=168,\quad v_{1}=43.$

Then

 $a_{1}=\lfloor 168/43\rfloor=3,\quad v_{2}=v_{0}-a_{1}v_{1}=168-3\cdot 43=39.$

Then

 $a_{2}=\lfloor 43/39\rfloor=1,\quad v_{3}=v_{1}-a_{2}v_{2}=43-1\cdot 39=4.$

Then

 $a_{3}=\lfloor v_{2}/v_{3}\rfloor=\lfloor 39/4\rfloor=9,\quad v_{4}=v_{2}-a_{3}% v_{3}=39-9\cdot 4=3.$

Then

 $a_{4}=\lfloor v_{3}/v_{4}\rfloor=\lfloor 4/3\rfloor=1,\quad v_{5}=v_{3}-a_{4}v% _{4}=4-1\cdot 3=1.$

Then

 $a_{5}=\lfloor v_{4}/v_{5}\rfloor=\lfloor 3/1\rfloor=3,\quad v_{6}=v_{4}-a_{5}v% _{5}=3-3\cdot 1=0.$

As $v_{5}=1$ and $v_{6}=0$,

 $\gcd(168,43)=1.$

Written as a continued fraction, we get

 $\frac{43}{168}=[0;3,1,9,1,3].$

For example, let $a=1463$ and $b=84$. Then

 $v_{0}=1463,\quad v_{1}=84.$

Then

 $a_{1}=\lfloor 1463/84\rfloor=17,\quad v_{2}=1463-17\cdot 84=35.$

Then

 $a_{2}=\lfloor 84/35\rfloor=2,\quad v_{3}=84-2\cdot 35=14.$

Then

 $a_{3}=\lfloor 35/14\rfloor=2,\quad v_{4}=35-2\cdot 14=7.$

Then

 $a_{4}=\lfloor 14/7\rfloor 2,\quad v_{5}=14-2\cdot 7=0.$

As $v_{4}=7$ and $v_{5}=0$,

 $\gcd(1463,84)=7.$

Written as a continued fraction, we get

 $\frac{84}{1463}=[0;17,2,2,2].$