integer (changes) in nLab

Showing changes from revision #42 to #43: Added | Removed | Changed

Contents

Idea

An integer is a number that is a natural number or the negative of one.

The ring ℤ\mathbb{Z} of all integers may defined as the free group on one generator or as the initial ring.

In keeping with a historical point of view in which integers are natural numbers with a sign attached, one may write

ℤ={n,−n|n∈ℕ,0=−0}={…,−3,−2,−1,0,1,2,3,…}. \mathbb{Z} = \{n, -n | n \in \mathbb{N}, 0 = -0\} = \{ \ldots, -3, -2, -1, 0, 1, 2, 3, \ldots \} \,.

From an nPOV, one may consider this as follows: ℤ\mathbb{Z} is a filtered colimit of sets

ℕ→1+(−)ℕ→1+(−)ℕ→1+(−)…\mathbb{N} \stackrel{1 + (-)}{\to} \mathbb{N} \stackrel{1 + (-)}{\to} \mathbb{N} \stackrel{1 + (-)}{\to} \ldots

whereby −n∈ℤ-n \in \mathbb{Z} is represented by the element 00 in the n thn^{th} copy of ℕ\mathbb{N} appearing in this diagram (starting the count at the 0 th0^{th} copy). The resulting induced map to the colimit

ℕ×ℕ≅∑ m∈ℕℕ→ℤ:(m,n)↦n−m\mathbb{N} \times \mathbb{N} \cong \sum_{m \in \mathbb{N}} \mathbb{N} \to \mathbb{Z}: (m, n) \mapsto n-m

imparts a monoid (in fact a group) structure on ℤ\mathbb{Z} descended from the monoid structure on ℕ×ℕ\mathbb{N} \times \mathbb{N}; compare double-entry bookkeeping in medieval mathematics (partita doppia).

As a group, ℤ\mathbb{Z} is abelian and is the Grothendieck group of the monoid (or semigroup) ℕ\mathbb{N} of natural numbers.

The monoid of natural numbers is naturally even a rig – in fact the initial rig – and this multiplicative structure extends to ℤ\mathbb{Z} to make it a ring – in fact the initial ring.

Properties

• The integers form a commutative ring.

• The integers have decidable equality and decidable order.

• The trivial ring is a tight apartness ring and a discrete ring.

• The integers are a strictly weakly ordered ring and a lattice-ordered ring.

• The integers are a metric space and a normed space.

• The integers are a Euclidean domain

• The integers satisfy the Archimedean property, making it into an Archimedean integral domain.

Bijection of the integers with the natural numbers

The integers are in bijection with the natural numbers. Both the integers and the natural numbers are submonoids? of the rational numbers, with pointed monoid monomorphisms i ℤ:ℤ↪ℚi_\mathbb{Z}:\mathbb{Z} \hookrightarrow \mathbb{Q} and i ℕ:ℕ↪ℚi_\mathbb{N}:\mathbb{N} \hookrightarrow \mathbb{Q} preserving addition, zero, and one. Let us take the relation on the rational numbers

x:ℚ,y:ℚ⊢|x+x+12|= ℚy+12x:\mathbb{Q}, y:\mathbb{Q} \vdash \left| x + x + \frac{1}{2} \right| =_\mathbb{Q} y + \frac{1}{2}

The relation

x:ℤ,y:ℕ⊢|i ℤ(x+x)+12|= ℚi ℕ(y)+12x:\mathbb{Z}, y:\mathbb{N} \vdash \left| i_\mathbb{Z}(x + x) + \frac{1}{2} \right| =_\mathbb{Q} i_\mathbb{N}(y) + \frac{1}{2}

is a one-to-one correspondence, meaning that the integers are in bijection with the natural numbers.

 Sequential Cauchy completeness

Let x:ℕ→ℤx:\mathbb{N} \to \mathbb{Z} be a sequence of integers, and let b:ℤb:\mathbb{Z} be an integer. Then, there is a limit relation defined as

isLimit(x,b)≔∀ϵ:ℤ +.∃N:ℕ.∀n:ℕ.(n≥N)→(|x(n)−b|<ϵ)\mathrm{isLimit}(x, b) \coloneqq \forall \epsilon:\mathbb{Z}_+.\exists N:\mathbb{N}.\forall n:\mathbb{N}.(n \geq N) \to (\vert x(n) - b \vert \lt \epsilon)

This relation is a functional relation, making the integers a sequentially Hausdorff space.

A modulus of Cauchy convergence is a function M:ℤ +→ℕM:\mathbb{Z}_+ \to \mathbb{N} with a witness

p(M,x):∀ϵ:ℤ +.∀m:ℕ.∀n:ℕ.((m≥M(ϵ))∧(n≥M(ϵ)))→(|x(m)−x(n)|<ϵ)p(M, x):\forall \epsilon:\mathbb{Z}_+.\forall m:\mathbb{N}.\forall n:\mathbb{N}.((m \geq M(\epsilon)) \wedge (n \geq M(\epsilon))) \to (\vert x(m) - x(n) \vert \lt \epsilon)

ℤ\mathbb{Z} is sequentially Cauchy complete if every sequence with a modulus of Cauchy convergence has a unique limit. But ℤ\mathbb{Z} is sequentially Cauchy complete, because the only sequences with a unique limit are those sequences for which there exists a natural number N:ℕN:\mathbb{N} such that for all natural numbers m≥Nm \geq N and n≥Nn \geq N, x(m)=x(n)x(m) = x(n). The sequence xx has many moduli of Cauchy convergence MM, where the natural number NN is given by N=M(1)N = M(1).

Since the integers are the initial Archimedean integral domain, the integers are also the initial sequentially Cauchy complete Archimedean integral domain. Every other sequentially Cauchy complete Archimedean integral domain is provably an ordered field and has the HoTT book real numbers ℝ\mathbb{R} as an integral subdomain. That means, in the context of the limited principle of omniscience, the category of sequentially Cauchy complete Archimedean integral domains is equivalent to the walking arrow, with objects ℤ\mathbb{Z} and ℝ\mathbb{R} and homomorphism h:ℤ→ℝh:\mathbb{Z} \to \mathbb{R}.

Cauchy completeness

Given a Tarski universe (U,T)(U, T) and a small type AA whose type reflection T(A)T(A) is a directed set, let x:T(A)→ℤx:T(A) \to \mathbb{Z} be a net of integers, and let b:ℤb:\mathbb{Z} be an integer. Then, there is a limit relation defined as

isLimit(x,b)≔∀ϵ:ℤ +.∃N:T(A).∀n:T(A).(n≥N)→(|x(n)−b|<ϵ)\mathrm{isLimit}(x, b) \coloneqq \forall \epsilon:\mathbb{Z}_+.\exists N:T(A).\forall n:T(A).(n \geq N) \to (\vert x(n) - b \vert \lt \epsilon)

This relation is a functional relation, making the integers a Hausdorff space.

A modulus of UU-Cauchy convergence is a function M:ℤ +→T(A)M:\mathbb{Z}_+ \to T(A) with a witness

p(M,x):∀ϵ:ℤ +.∀m:T(A).∀n:T(A).((m≥M(ϵ))∧(n≥M(ϵ)))→(|x(m)−x(n)|<ϵ)p(M, x):\forall \epsilon:\mathbb{Z}_+.\forall m:T(A).\forall n:T(A).((m \geq M(\epsilon)) \wedge (n \geq M(\epsilon))) \to (\vert x(m) - x(n) \vert \lt \epsilon)

ℤ\mathbb{Z} is UU-Cauchy complete if every net with a modulus of UU-Cauchy convergence has a unique limit. But ℤ\mathbb{Z} is UU-Cauchy complete, because the only UU-nets with a unique limit are those nets for which there exists an element N:T(A)N:T(A) such that for all elements m≥Nm \geq N and n≥Nn \geq N, x(m)=x(n)x(m) = x(n). The net xx has many moduli of UU-Cauchy convergence MM, where the element NN is given by N=M(1)N = M(1).

Since the integers are the initial Archimedean integral domain, the integers are also the initial UU-Cauchy complete Archimedean integral domain. Every other UU-Cauchy complete Archimedean integral domain is provably an ordered field and has the UU-Dedekind real numbers ℝ\mathbb{R} as an integral subdomain.

 Dedekind completeness

Let Ω\Omega be the type of all propositions, so that the foundations is impredicative. A Dedekind cut is an pair (L,U)(L, U) of predicates such that

• there exists an integer a:ℤa:\mathbb{Z} such that L(a)L(a)
• there exists an integer b:ℤb:\mathbb{Z} such that U(b)U(b)
• for all integers a:ℤa:\mathbb{Z}, L(a)L(a) if and only if there exists an integer b:ℤb:\mathbb{Z} such that a<ba \lt b and L(b)L(b)
• for all integers b:ℤb:\mathbb{Z}, U(b)U(b) if and only if there exists an integer a:ℤa:\mathbb{Z} such that a<ba \lt b and U(a)U(a)
• for all integers a:ℤa:\mathbb{Z}, it is not true that L(a)L(a) and U(a)U(a)
• for all integers a:ℤa:\mathbb{Z} and b:ℤb:\mathbb{Z}, if a<ba \lt b, then L(a)L(a) and U(b)U(b).

There is a Dedekind cut for every integer a:ℤa:\mathbb{Z}, given by L a(b)≔b<aL_a(b) \coloneqq b \lt a and U a(b)≔a<bU_a(b) \coloneqq a \lt b. There are no other Dedekind cuts on the integers. Thus, the integers are Dedekind complete.

Since the integers are the initial Archimedean integral domain, the integers are also the initial Dedekind complete Archimedean integral domain. The only other Dedekind complete Archimedean integral domain is the Dedekind real numbers ℝ\mathbb{R}. That means, if there is a type of all propositions, the category of Dedekind complete Archimedean integral domains is equivalent to the walking arrow, with objects ℤ\mathbb{Z} and ℝ\mathbb{R} and homomorphism h:ℤ→ℝh:\mathbb{Z} \to \mathbb{R}.

Terminology

The underlying sets ℤ\mathbb{Z} and ℕ\mathbb{N} are isomorphic. Some subcultures of mathematics (and not only set theorists) use the term ‘integer’ synonymously for a natural number. Computer scientists distinguish between ‘unsigned integers’ (natural numbers) and ‘signed integers’ (integers as described here). Translations can also cause confusion with the term ‘whole number’.

In number theory, one generalises integers to algebraic integers, an instance of the red herring principle. Accordingly, some number theorists will call the integers ‘rational integers’ to clarify; ℤ\mathbb{Z} is the ring of integers in the number field ℚ\mathbb{Q} of rational numbers. (Compare, for example, Gaussian integers and Gaussian numbers.)

The symbol ‘ℤ\mathbb{Z}’ derives from the German word ‘Zahlen’, which is a generic word for ‘numbers’. (Compare Dedekind's use of that word in the title of his famous book on the foundations of real numbers.)

• infinite cyclic group

• even number, odd number

• natural number, rational number, real number

• algebraic integer

• ring of integers

• cyclotomic integer

• geometry modeled on the formal dual, Spec(Z), of the ring of integers is arithmetic geometry

• integers object in a topos

• rational zero theorem

• integers type

References

The first characterization of the integers as an ordered integral domain appeared in:

• Hermann Grassmann, Lehrbuch der Arithmetik für höhere Lehranstalten, Berlin: Enslin, 1861. (Google Books)

though the name “ordered integral domain” does not appear in the text.

History:

• Leo Corry, A Brief History of Numbers, Oxford University Press (2015) [[ISBN:9780198702597](https://global.oup.com/academic/product/a-brief-history-of-numbers-9780198702597)]

See also:

• Wikipedia, Integer

Formalization in univalent foundations of mathematics (homotopy type theory with the univalence axiom):

• Univalent Foundations Project, Rem. 6.10.7 Homotopy Type Theory -- Univalent Foundations of Mathematics (2013) [[web](http://homotopytypetheory.org/book/), pdf]

and specifically in Agda:

• UniMath project, agda-unimath/elementary-number-theory.integers

and specifically in cubical Agda

• 1lab, Data.Int