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 on X that is reflexive, antisymmetric, and transitive, and we call (X,) a poset. If (X,) is a poset, we define it to be a category whose objects are the elements of X, and for x,yX,

Hom(x,y)={{(x,y)}xy¬(xy).

In particular, idx=(x,x).

Let U: be the inclusion map. If (j,k)Hom(j,k), define U(j,k)=(Uj,Uk)Hom(Uj,Uk).

Uidj=U(j,j)=(Uj,Uj)=idUj.

If (j,k)Hom(j,k) and (k,l)Hom(k,l), then (k,l)(j,k)=(j,l) and

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

This shows that U:(,)(,) is a functor.

2 Galois connections

If (A,) and (B,) are posets, a function G:AB is said to be order-preserving if aa implies G(a)G(a). A Galois connection from A to B is an order-preserving function G:AB and an order-preserving function H:BA such that

G(a)b if and only if aH(b),aA,bB.

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

Let I: be the inclusion map. Define F: by F(x)=x. For n and x, suppose I(n)x. Then F(I(n))F(x). But F(I(n))=n, so nF(x). Suppose nF(x). Then I(n)I(F(x))x. Therefore F:, F(x)=x is the right-adjoint of I::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)xnF(x),n,x.

Define C: by C(x)=x. For n and x, suppose C(x)n. Then I(C(x))I(n). But I(C(x))x, so xI(n). Suppose xI(n). Then C(x)C(I(n)). But C(I(n))=n, so C(x)n. Therefore C:, C(x)=x is the left-adjoint of I::

C(x)nxI(n),x,n.
Lemma 1.

For x0,

x=x.
Proof.

For k0 and y0,

ky I(k)y
k2y
k2y
ky
ky.

Lemma 2.

If xR and nZ1, then

xn=xn.
Proof.

For k,

kF(I(F(x))/I(n)) I(k)I(F(x))/I(n)
I(k)I(n)I(F(x))
I(kn)I(F(x))
knF(x)
I(kn)x
I(k)x/I(n)
kF(x/I(n)).

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

Lemma 3.

If nZ1 and mZ, then

mn=m+n-1n.
Proof.

For k,

kF(I(m+n-1)/I(n)) I(k)I(m+n-1)/I(n)
I(k)I(n)I(m+n-1)
knm+n-1
kn-n+1m
kn-n<m
I(k-1)<I(m)/I(n)
k-1<C(I(m)/I(n))
kC(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,b1, a>b. Let

v0=a,v1=b.

Let

a1=v0/v1,v2=v0-a1v1.

For m2, if vm0 then let

am=vm-1/vm,vm+1=vm-1-amvm.

Then 0vm+1<vm.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

v0=83,v1=14.

Then

a1=83/14=5,v2=83-514=13.

Then

a2=v1/v2=14/13=1,v3=v1-a2v2=14-113=1.

Then

a3=v2/v3=13/1=13,v4=v2-a3v3=13-131=0.

As v3=1 and v4=0,

gcd(83,14)=1.

Written as a continued fraction, we get

1483=[0;5,1,13].

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

v0=168,v1=43.

Then

a1=168/43=3,v2=v0-a1v1=168-343=39.

Then

a2=43/39=1,v3=v1-a2v2=43-139=4.

Then

a3=v2/v3=39/4=9,v4=v2-a3v3=39-94=3.

Then

a4=v3/v4=4/3=1,v5=v3-a4v4=4-13=1.

Then

a5=v4/v5=3/1=3,v6=v4-a5v5=3-31=0.

As v5=1 and v6=0,

gcd(168,43)=1.

Written as a continued fraction, we get

43168=[0;3,1,9,1,3].

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

v0=1463,v1=84.

Then

a1=1463/84=17,v2=1463-1784=35.

Then

a2=84/35=2,v3=84-235=14.

Then

a3=35/14=2,v4=35-214=7.

Then

a4=14/72,v5=14-27=0.

As v4=7 and v5=0,

gcd(1463,84)=7.

Written as a continued fraction, we get

841463=[0;17,2,2,2].