nLab decimal number

Redirected from "long division".
Contents

Context

Arithmetic

Algebra

Category theory

Homological algebra

homological algebra

(also nonabelian homological algebra)

Introduction

Context

Basic definitions

Stable homotopy theory notions

Constructions

Lemmas

diagram chasing

Schanuel's lemma

Homology theories

Theorems

Constructivism, Realizability, Computability

Contents

Idea

Talk about the decimal number system for integers and decimal fractions, and then infinite sequences of decimals as a terminal coalgebra for an endofunctor.

Natural numbers

As a free monoid

Define a set of digits DD, and the free monoid D *D^* on DD with unit ϵ\epsilon, quotiented by an equivalence relation. Then define a function ss on D *D^* such that D *,ϵ,sD^*,\epsilon,s is a natural numbers object.

Long division algorithm

Let [0,9] *[0, 9]^* be the free monoid on the closed interval [0,9][0, 9], which represents the list of digits in the decimal numeral representation of the natural numbers, with length function len:[0,9] *\mathrm{len}:[0, 9]^* \to \mathbb{N}. There is a surjection f:[0,9] *f:[0, 9]^* \to \mathbb{N} defined as

f(a) i=0 len(a)1a i10 len(a)i1f(a) \coloneqq \sum_{i = 0}^{\mathrm{len}(a) - 1} a_i 10^{\mathrm{len}(a) - i - 1}

representing the numerical value of the list of digits.

The algorithm is as follows: Let a:[0,9] *a:[0, 9]^* and b:[0,9] *b:[0, 9]^* be lists of digits, with f(a)f(a) the dividend and f(b)f(b) the divisor. If len(a)<len(b)\mathrm{len}(a) \lt \mathrm{len}(b), then f(a)÷f(b)=0f(a) \div f(b) = 0 and f(a)%f(b)=f(a)f(a)\ \%\ f(b) = f(a). Otherwise, we iterate for len(a)\mathrm{len}(a) times before stopping:

For each iteration i:[0,len(a)]i:[0, \mathrm{len}(a)], let q iq_i be the quotient extracted from the algorithm at iteration ii, let d id_i be the dividend at iteration ii, let r ir_i be the remainder at iteration ii, and let c ic_i be the next digit of the quotient, with the restriction that 0r i0 \leq r_i and r i<f(b)r_i \lt f(b)

We set initial conditions to be

q 10q_{-1} \coloneqq 0
r 1 i=0 len(b)2a i10 len(b)i2r_{-1} \coloneqq \sum_{i = 0}^{\mathrm{len}(b) - 2} a_i 10^{\mathrm{len}(b) - i - 2}

The successive conditions are defined inductively as

d i+110r i+a i+len(b)d_{i + 1} \coloneqq 10 r_i + a_{i + \len(b)}
r i+1d i+1mc i+1=10r i+a i+len(b)mc i+1r_{i + 1} \coloneqq d_{i + 1} - m c_{i + 1} = 10 r_i + a_{i + \len(b)} - m c_{i + 1}
q i+110q ic i+1q_{i + 1} \coloneqq 10 q_{i} - c_{i + 1}

Order theoretic definitions

Integers

work in progress…

Finite decimals

See below, but define in terms of an initial algebra instead of a terminal coalgebra.

Infinite decimals

Consider the category of intervals IntInt, i.e., linearly ordered sets with identified elements 11 and 00, and let

F:IntIntF: Int \to Int

be the endofunctor which takes an interval XX to 0i<10X\bigvee_{0 \leq i \lt 10} X, the the interval obtained by taking ten copies of XX and identifying the 11 of the (i1)(i-1)-th copy with the 00 of the ii-th copy, for 0<i<100 \lt i \lt 10. The real interval [0,1][0, 1] becomes a coalgebra if we identify 0i<10X\bigvee_{0 \leq i \lt 10} X with [0,10][0, 10] and consider the multiplication-by-10 map [0,1][0,10][0, 1] \to [0, 10] as giving a coalgebra structure.

Theorem

The interval [0,1][0, 1] is terminal in the category of such coalgebras.

Proof (sketch)

Given any coalgebra structure f:X 0i<10Xf: X \to \bigvee_{0 \leq i \lt 10} X, any value f(x)f(x) lands either in the nn-th tenth (the nn-th XX in 0i<10X\bigvee_{0 \leq i \lt 10} X) for 0<n100\lt n \leq 10, or at the precise spot between them, where the 11 in the nn-th copy is glued to the 00 in the (n+1)(n+1)-th for 0<n<100\lt n \lt 10. Intuitively, one could think of a coalgebra structure θ:X 0i<10\theta: X \to \bigvee_{0 \leq i \lt 10} as giving an automaton where on input x 0x_0 there is output of the form (x 1,h 1)(x_1, h_1), where h 1h_1 is one of 19 states, “0”, “1”, “2”, “3”, “4”, “5”, “6”, “7”, “8”, “9”, “either 0 or 1”, “either 1 or 2”, “either 2 or 3”, “either 3 or 4”, “either 4 or 5”, “either 5 or 6”, “either 6 or 7”, “either 7 or 8”, and “either 8 or 9”. By iteration, this generates a behavior stream (x n,h n)(x_n, h_n). Let “0”, “1”, “2”, “3”, “4”, “5”, “6”, “7”, “8”, and “9” be decimal digits DD, the h nh_n form a decimal expansion to give a number between 0 and 1, and therefore we have an interval map X[0,1]X \to [0, 1] which sends x 0x_0 to that number. Of course, if h nh_n is ever one of the “either d ld_l or d ud_u” states, for d l,d u:Dd_l,d_u:D we have a choice to resolve it as either (1 X,d l)(1_X, d_l) or (0 X,d u)(0_X, d_u) and continue the stream, but these streams are identified, and this corresponds to the identifications of decimal expansions

h 1...h n1100000...=.h 1...h n1099999...h_1... h_{n-1} 100000... = .h_1... h_{n-1}099999...
h 1...h n1200000...=.h 1...h n1199999...h_1... h_{n-1} 200000... = .h_1... h_{n-1}199999...
h 1...h n1300000...=.h 1...h n1299999...h_1... h_{n-1} 300000... = .h_1... h_{n-1}299999...
h 1...h n1400000...=.h 1...h n1399999...h_1... h_{n-1} 400000... = .h_1... h_{n-1}399999...
h 1...h n1500000...=.h 1...h n1499999...h_1... h_{n-1} 500000... = .h_1... h_{n-1}499999...
h 1...h n1600000...=.h 1...h n1599999...h_1... h_{n-1} 600000... = .h_1... h_{n-1}599999...
h 1...h n1700000...=.h 1...h n1699999...h_1... h_{n-1} 700000... = .h_1... h_{n-1}699999...
h 1...h n1800000...=.h 1...h n1799999...h_1... h_{n-1} 800000... = .h_1... h_{n-1}799999...
h 1...h n1900000...=.h 1...h n1899999...h_1... h_{n-1} 900000... = .h_1... h_{n-1}899999...

as real numbers. In this way, we produce a unique well-defined interval map X[0,1]X \to [0, 1], so that [0,1][0, 1] is the terminal coalgebra.

Let (,0,s,n,<)(\mathbb{Z},0,s,n,\lt) be the set of integers, the initial set with an element 00, a linear order <\lt, a monotone ss such that a<s(a)a \lt s(a) for all aa \in \mathbb{Z}, and an antitone nn such that n(0)=0n(0)=0 and n=snsn = s \circ n \circ s. Let \mathbb{R} be a set with a structure preserving function g:g:\mathbb{Z}\to\mathbb{R} and a function into the monotone poset f:[0,1]f:\mathbb{Z} \to [0,1]\to \mathbb{R} such that f(a)(0)=g(a)f(a)(0) = g(a) and f(a)(1)=s(g(a))f(a)(1) = s(g(a)) for all aa \in \mathbb{Z}. The set \mathbb{R} of real numbers is the initial such system. By uncurrying the function ff, one gets a function i:×[0,1]i:\mathbb{Z} \times [0,1]\to \mathbb{R}. An element (a,b):×[0,1](a,b):\mathbb{Z} \times [0,1] is called an infinite decimal representation, where the comma used to represent pairs in set theory or type theory is literally the decimal separator commonly seen in non-English speaking countries.

The arithmetic operations and topological properties on \mathbb{R} can be defined by the properties of the function algebra of \mathbb{R} and currying.

Rig theoretic definitions

Integers

[10]∶−[x]/(x=10)\mathbb{N} \cong \mathbb{N}[10] \coloneq \mathbb{N}[x]/(x=10)

Finite decimals

Localisation of the rig of natural numbers at 10 [1/10]\mathbb{N}[1/10], finite decimals as canonical representatives of [1/10]\mathbb{N}[1/10], and then group completion of the additive monoid to [1/10]\mathbb{Z}[1/10].

Infinite decimals

Sequence algebra[1/10]\mathbb{N}\to\mathbb{Z}[1/10] and Cauchy sequences

Doubly infinite decimals

Let /10\mathbb{Z}/10\mathbb{Z} be the cyclic group consisting of 10 elements, and let C C_\bullet be a chain complex of abelian groups consisting of a sequence of /10\mathbb{Z}/10\mathbb{Z} indexed by \mathbb{Z}. The indices i:i:\mathbb{Z} are called place values, and ii-cochains are called digits.

A 10-adic number is a cochain such that c i=0c_i = 0 for all i<ji \lt j or c i=9c_i = 9 for all i<ji \lt j for i,j:i,j:\mathbb{Z}. A 10-adic integer is a cochain such that c i=0c_i = 0 for all i<0i \lt 0 or c i=9c_ i = 9 for all i<0i \lt 0. A real number is a cochain such that c i=c jc_i = c_j for all i>ki \gt k and j>kj \gt k for i,j,k:i,j,k:\mathbb{Z}. A decimal rational is a real 10-adic number, and an integer is a real 10-adic integer.

10-adic solenoids

The cochain complex C C_\bullet defined in the previous section has a structure of an abelian group, making it into a 10-adic solenoid.

A cyclic group GG has a canonical cyclic order [(),(),()]:(G×G×G)Ω[(-),(-),(-)]:(G \times G \times G) \to \Omega. We define the cyclic order on /10\mathbb{Z}/10\mathbb{Z} such that [0,n,1][0,n,1] is false for all n:/10n:\mathbb{Z}/10\mathbb{Z}.

For each i:i:\mathbb{Z}, there exists a cocycle f i:(C i×C i)C i+1f_i: (C_i \times C_i) \to C_{i + 1} called the digitwise carry function at place value ii, defined such that for all a,b:C ia,b:C_i, f i(a,b)=0f_i(a,b) = 0 if [a,0,a+b][a,0,a+b] is false, and f i(a,b)=1f_i(a,b) = 1 if [a,0,a+b][a,0,a+b] is true.

We define the addition without carry on the cochain complex ()():(C ×C )C (-)\oplus(-): (C_\bullet \times C_\bullet) \to C_\bullet as the addition of all digits using the abelian group operation, and we define the carry carry:(C ×C )C carry: (C_\bullet \times C_\bullet) \to C_\bullet as the digitwise carry of all digits. Then, addition ()+():(C ×C )C (-)+(-): (C_\bullet \times C_\bullet) \to C_\bullet is defined recursively as a+b=(ab)+carry(a,b)a+b = (a\oplus b)+carry(a,b).

The cochains consisting of all nns for all n:/10n:\mathbb{Z}/10\mathbb{Z} are additive identity elements of the addition operation defined above. As such, they are algebraically equal to the same chain 00 zero, the chain consisting of all zeroes. We define negation ():C C -(-): C_\bullet \to C_\bullet such that for all chains c:C c:C_\bullet, the digits in c-c are (c) i=9+c i(-c)_i = 9 + -c_i. As a result, the chain complex itself is an abelian group.

Analytic completion of Laurent series

Let 11 one denote the cochain with all digits equal to zero except at place value 00, where the digit is equal to 11. The cochain with all digits equal to zero except at place value ii is called the ii-th power of ten and is denoted as 10 i10^i.

Let us define an \mathbb{N}-action act:( +×C )C act: (\mathbb{N}^+\times C_\bullet) \to C_\bullet such that act(0,0)=0act(0,0) = 0 and act(n+1,c)=act(n,c)+cact(n + 1,c) = act(n,c) + c for all n: +n:\mathbb{N}^+ and c:C c:C_\bullet. This represents the nn-fold sum of a cochain cc.

One could also establish a ring structure on /10\mathbb{Z}/10\mathbb{Z} and construct a multiplication operation on the chain complex such that the chain complex itself with the defined abelian group structure and multiplication should be equivalent to the quotient ring of the Laurent series [[x,x 1]]/(x10)[[x,x 1]]\mathbb{Z}[[x,x^{-1}]]/(x-10)\mathbb{Z}[[x,x^{-1}]].

References

Last revised on May 13, 2022 at 00:36:10. See the history of this page for a list of all contributions to it.