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}$ :¹¹ 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<m$
		$\displaystyle\iff I(k-1)<I(m)/I(n)$
		$\displaystyle\iff k-1<C(I(m)/I(n))$
		$\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}<v_{m}$ .²² 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].