The integers

Content created by Egbert Rijke, Fredrik Bakke, Jonathan Prieto-Cubides, Fernando Chu, Bryan Lu and malarbol.

Created on 2022-01-26.
Last modified on 2024-02-27.

module elementary-number-theory.integers where
Imports
open import elementary-number-theory.equality-natural-numbers
open import elementary-number-theory.natural-numbers

open import foundation.action-on-identifications-functions
open import foundation.coproduct-types
open import foundation.dependent-pair-types
open import foundation.embeddings
open import foundation.empty-types
open import foundation.equality-coproduct-types
open import foundation.equivalences
open import foundation.function-types
open import foundation.homotopies
open import foundation.identity-types
open import foundation.injective-maps
open import foundation.negated-equality
open import foundation.negation
open import foundation.propositions
open import foundation.retractions
open import foundation.sections
open import foundation.sets
open import foundation.unit-type
open import foundation.universe-levels

open import structured-types.types-equipped-with-endomorphisms

Idea

The type of integers is an extension of the type of natural numbers including negative whole numbers.

Definitions

The type of integers

 : UU lzero
 =  + (unit + )

{-# BUILTIN INTEGER  #-}

Inclusion of the negative integers

in-neg :   
in-neg n = inl n

neg-one-ℤ : 
neg-one-ℤ = in-neg zero-ℕ

is-neg-one-ℤ :   UU lzero
is-neg-one-ℤ x = (x  neg-one-ℤ)

Zero

zero-ℤ : 
zero-ℤ = inr (inl star)

is-zero-ℤ :   UU lzero
is-zero-ℤ x = (x  zero-ℤ)

Inclusion of the positive integers

in-pos :   
in-pos n = inr (inr n)

one-ℤ : 
one-ℤ = in-pos zero-ℕ

is-one-ℤ :   UU lzero
is-one-ℤ x = (x  one-ℤ)

Inclusion of the natural numbers

int-ℕ :   
int-ℕ zero-ℕ = zero-ℤ
int-ℕ (succ-ℕ n) = in-pos n

is-injective-int-ℕ : is-injective int-ℕ
is-injective-int-ℕ {zero-ℕ} {zero-ℕ} refl = refl
is-injective-int-ℕ {succ-ℕ x} {succ-ℕ y} refl = refl

Induction principle on the type of integers

ind-ℤ :
  {l : Level} (P :   UU l) 
  P neg-one-ℤ  ((n : )  P (inl n)  P (inl (succ-ℕ n))) 
  P zero-ℤ 
  P one-ℤ  ((n : )  P (inr (inr (n)))  P (inr (inr (succ-ℕ n)))) 
  (k : )  P k
ind-ℤ P p-1 p-S p0 p1 pS (inl zero-ℕ) = p-1
ind-ℤ P p-1 p-S p0 p1 pS (inl (succ-ℕ x)) =
  p-S x (ind-ℤ P p-1 p-S p0 p1 pS (inl x))
ind-ℤ P p-1 p-S p0 p1 pS (inr (inl star)) = p0
ind-ℤ P p-1 p-S p0 p1 pS (inr (inr zero-ℕ)) = p1
ind-ℤ P p-1 p-S p0 p1 pS (inr (inr (succ-ℕ x))) =
  pS x (ind-ℤ P p-1 p-S p0 p1 pS (inr (inr (x))))

The successor and predecessor functions on ℤ

succ-ℤ :   
succ-ℤ (inl zero-ℕ) = zero-ℤ
succ-ℤ (inl (succ-ℕ x)) = inl x
succ-ℤ (inr (inl star)) = one-ℤ
succ-ℤ (inr (inr x)) = inr (inr (succ-ℕ x))

pred-ℤ :   
pred-ℤ (inl x) = inl (succ-ℕ x)
pred-ℤ (inr (inl star)) = inl zero-ℕ
pred-ℤ (inr (inr zero-ℕ)) = inr (inl star)
pred-ℤ (inr (inr (succ-ℕ x))) = inr (inr x)

ℤ-Type-With-Endomorphism : Type-With-Endomorphism lzero
pr1 ℤ-Type-With-Endomorphism = 
pr2 ℤ-Type-With-Endomorphism = succ-ℤ

The negative of an integer

neg-ℤ :   
neg-ℤ (inl x) = inr (inr x)
neg-ℤ (inr (inl star)) = inr (inl star)
neg-ℤ (inr (inr x)) = inl x

Properties

The type of integers is a set

is-set-ℤ : is-set 
is-set-ℤ = is-set-coproduct is-set-ℕ (is-set-coproduct is-set-unit is-set-ℕ)

ℤ-Set : Set lzero
pr1 ℤ-Set = 
pr2 ℤ-Set = is-set-ℤ

The successor and predecessor functions on ℤ are mutual inverses

abstract
  is-retraction-pred-ℤ : is-retraction succ-ℤ pred-ℤ
  is-retraction-pred-ℤ (inl zero-ℕ) = refl
  is-retraction-pred-ℤ (inl (succ-ℕ x)) = refl
  is-retraction-pred-ℤ (inr (inl _)) = refl
  is-retraction-pred-ℤ (inr (inr zero-ℕ)) = refl
  is-retraction-pred-ℤ (inr (inr (succ-ℕ x))) = refl

  is-section-pred-ℤ : is-section succ-ℤ pred-ℤ
  is-section-pred-ℤ (inl zero-ℕ) = refl
  is-section-pred-ℤ (inl (succ-ℕ x)) = refl
  is-section-pred-ℤ (inr (inl _)) = refl
  is-section-pred-ℤ (inr (inr zero-ℕ)) = refl
  is-section-pred-ℤ (inr (inr (succ-ℕ x))) = refl

abstract
  is-equiv-succ-ℤ : is-equiv succ-ℤ
  pr1 (pr1 is-equiv-succ-ℤ) = pred-ℤ
  pr2 (pr1 is-equiv-succ-ℤ) = is-section-pred-ℤ
  pr1 (pr2 is-equiv-succ-ℤ) = pred-ℤ
  pr2 (pr2 is-equiv-succ-ℤ) = is-retraction-pred-ℤ

equiv-succ-ℤ :   
pr1 equiv-succ-ℤ = succ-ℤ
pr2 equiv-succ-ℤ = is-equiv-succ-ℤ

abstract
  is-equiv-pred-ℤ : is-equiv pred-ℤ
  pr1 (pr1 is-equiv-pred-ℤ) = succ-ℤ
  pr2 (pr1 is-equiv-pred-ℤ) = is-retraction-pred-ℤ
  pr1 (pr2 is-equiv-pred-ℤ) = succ-ℤ
  pr2 (pr2 is-equiv-pred-ℤ) = is-section-pred-ℤ

equiv-pred-ℤ :   
pr1 equiv-pred-ℤ = pred-ℤ
pr2 equiv-pred-ℤ = is-equiv-pred-ℤ

The successor function on ℤ is injective and has no fixed points

is-injective-succ-ℤ : is-injective succ-ℤ
is-injective-succ-ℤ {x} {y} p =
  inv (is-retraction-pred-ℤ x)  ap pred-ℤ p  is-retraction-pred-ℤ y

has-no-fixed-points-succ-ℤ : (x : )  succ-ℤ x  x
has-no-fixed-points-succ-ℤ (inl zero-ℕ) ()
has-no-fixed-points-succ-ℤ (inl (succ-ℕ x)) ()
has-no-fixed-points-succ-ℤ (inr (inl star)) ()

The negative function is an involution

neg-neg-ℤ : neg-ℤ  neg-ℤ ~ id
neg-neg-ℤ (inl n) = refl
neg-neg-ℤ (inr (inl star)) = refl
neg-neg-ℤ (inr (inr n)) = refl

abstract
  is-equiv-neg-ℤ : is-equiv neg-ℤ
  pr1 (pr1 is-equiv-neg-ℤ) = neg-ℤ
  pr2 (pr1 is-equiv-neg-ℤ) = neg-neg-ℤ
  pr1 (pr2 is-equiv-neg-ℤ) = neg-ℤ
  pr2 (pr2 is-equiv-neg-ℤ) = neg-neg-ℤ

equiv-neg-ℤ :   
pr1 equiv-neg-ℤ = neg-ℤ
pr2 equiv-neg-ℤ = is-equiv-neg-ℤ

abstract
  is-emb-neg-ℤ : is-emb neg-ℤ
  is-emb-neg-ℤ = is-emb-is-equiv is-equiv-neg-ℤ

emb-neg-ℤ :   
pr1 emb-neg-ℤ = neg-ℤ
pr2 emb-neg-ℤ = is-emb-neg-ℤ

neg-pred-ℤ : (k : )  neg-ℤ (pred-ℤ k)  succ-ℤ (neg-ℤ k)
neg-pred-ℤ (inl x) = refl
neg-pred-ℤ (inr (inl star)) = refl
neg-pred-ℤ (inr (inr zero-ℕ)) = refl
neg-pred-ℤ (inr (inr (succ-ℕ x))) = refl

neg-succ-ℤ : (x : )  neg-ℤ (succ-ℤ x)  pred-ℤ (neg-ℤ x)
neg-succ-ℤ (inl zero-ℕ) = refl
neg-succ-ℤ (inl (succ-ℕ x)) = refl
neg-succ-ℤ (inr (inl star)) = refl
neg-succ-ℤ (inr (inr x)) = refl

pred-neg-ℤ :
  (k : )  pred-ℤ (neg-ℤ k)  neg-ℤ (succ-ℤ k)
pred-neg-ℤ (inl zero-ℕ) = refl
pred-neg-ℤ (inl (succ-ℕ x)) = refl
pred-neg-ℤ (inr (inl star)) = refl
pred-neg-ℤ (inr (inr x)) = refl

Nonnegative integers

is-nonnegative-ℤ :   UU lzero
is-nonnegative-ℤ (inl x) = empty
is-nonnegative-ℤ (inr k) = unit

is-nonnegative-eq-ℤ :
  {x y : }  x  y  is-nonnegative-ℤ x  is-nonnegative-ℤ y
is-nonnegative-eq-ℤ refl = id

is-zero-is-nonnegative-ℤ :
  {x : }  is-nonnegative-ℤ x  is-nonnegative-ℤ (neg-ℤ x)  is-zero-ℤ x
is-zero-is-nonnegative-ℤ {inr (inl star)} H K = refl

is-nonnegative-succ-ℤ :
  (k : )  is-nonnegative-ℤ k  is-nonnegative-ℤ (succ-ℤ k)
is-nonnegative-succ-ℤ (inr (inl star)) p = star
is-nonnegative-succ-ℤ (inr (inr x)) p = star

is-prop-is-nonnegative-ℤ : (x : )  is-prop (is-nonnegative-ℤ x)
is-prop-is-nonnegative-ℤ (inl x) = is-prop-empty
is-prop-is-nonnegative-ℤ (inr x) = is-prop-unit

is-nonnegative-ℤ-Prop :   Prop lzero
pr1 (is-nonnegative-ℤ-Prop x) = is-nonnegative-ℤ x
pr2 (is-nonnegative-ℤ-Prop x) = is-prop-is-nonnegative-ℤ x

The positive integers

is-positive-ℤ :   UU lzero
is-positive-ℤ (inl x) = empty
is-positive-ℤ (inr (inl x)) = empty
is-positive-ℤ (inr (inr x)) = unit

is-prop-is-positive-ℤ : (x : )  is-prop (is-positive-ℤ x)
is-prop-is-positive-ℤ (inl x) = is-prop-empty
is-prop-is-positive-ℤ (inr (inl x)) = is-prop-empty
is-prop-is-positive-ℤ (inr (inr x)) = is-prop-unit

is-positive-ℤ-Prop :   Prop lzero
pr1 (is-positive-ℤ-Prop x) = is-positive-ℤ x
pr2 (is-positive-ℤ-Prop x) = is-prop-is-positive-ℤ x

is-set-is-positive-ℤ : (x : )  is-set (is-positive-ℤ x)
is-set-is-positive-ℤ (inl x) = is-set-empty
is-set-is-positive-ℤ (inr (inl x)) = is-set-empty
is-set-is-positive-ℤ (inr (inr x)) = is-set-unit

is-positive-ℤ-Set :   Set lzero
pr1 (is-positive-ℤ-Set z) = is-positive-ℤ z
pr2 (is-positive-ℤ-Set z) = is-set-is-positive-ℤ z

positive-ℤ : UU lzero
positive-ℤ = Σ  is-positive-ℤ

is-set-positive-ℤ : is-set positive-ℤ
is-set-positive-ℤ = is-set-Σ is-set-ℤ is-set-is-positive-ℤ

positive-ℤ-Set : Set lzero
pr1 positive-ℤ-Set = positive-ℤ
pr2 positive-ℤ-Set = is-set-positive-ℤ

int-positive-ℤ : positive-ℤ  
int-positive-ℤ = pr1

is-positive-int-positive-ℤ :
  (x : positive-ℤ)  is-positive-ℤ (int-positive-ℤ x)
is-positive-int-positive-ℤ = pr2

is-nonnegative-is-positive-ℤ : {x : }  is-positive-ℤ x  is-nonnegative-ℤ x
is-nonnegative-is-positive-ℤ {inr (inr x)} H = H

is-positive-eq-ℤ : {x y : }  x  y  is-positive-ℤ x  is-positive-ℤ y
is-positive-eq-ℤ {x} refl = id

is-positive-one-ℤ : is-positive-ℤ one-ℤ
is-positive-one-ℤ = star

one-positive-ℤ : positive-ℤ
pr1 one-positive-ℤ = one-ℤ
pr2 one-positive-ℤ = is-positive-one-ℤ

is-positive-succ-ℤ : {x : }  is-nonnegative-ℤ x  is-positive-ℤ (succ-ℤ x)
is-positive-succ-ℤ {inr (inl star)} H = is-positive-one-ℤ
is-positive-succ-ℤ {inr (inr x)} H = star

is-positive-int-ℕ :
  (x : )  is-nonzero-ℕ x  is-positive-ℤ (int-ℕ x)
is-positive-int-ℕ zero-ℕ H = ex-falso (H refl)
is-positive-int-ℕ (succ-ℕ x) H = star

Properties of nonnegative integers

nonnegative-ℤ : UU lzero
nonnegative-ℤ = Σ  is-nonnegative-ℤ

int-nonnegative-ℤ : nonnegative-ℤ  
int-nonnegative-ℤ = pr1

is-nonnegative-int-nonnegative-ℤ :
  (x : nonnegative-ℤ)  is-nonnegative-ℤ (int-nonnegative-ℤ x)
is-nonnegative-int-nonnegative-ℤ = pr2

is-injective-int-nonnegative-ℤ : is-injective int-nonnegative-ℤ
is-injective-int-nonnegative-ℤ {pair (inr x) star} {pair (inr .x) star} refl =
  refl

is-nonnegative-int-ℕ : (n : )  is-nonnegative-ℤ (int-ℕ n)
is-nonnegative-int-ℕ zero-ℕ = star
is-nonnegative-int-ℕ (succ-ℕ n) = star

nonnegative-int-ℕ :   nonnegative-ℤ
pr1 (nonnegative-int-ℕ n) = int-ℕ n
pr2 (nonnegative-int-ℕ n) = is-nonnegative-int-ℕ n

nat-nonnegative-ℤ : nonnegative-ℤ  
nat-nonnegative-ℤ (pair (inr (inl x)) H) = zero-ℕ
nat-nonnegative-ℤ (pair (inr (inr x)) H) = succ-ℕ x

is-section-nat-nonnegative-ℤ :
  (x : nonnegative-ℤ)  nonnegative-int-ℕ (nat-nonnegative-ℤ x)  x
is-section-nat-nonnegative-ℤ (pair (inr (inl star)) star) = refl
is-section-nat-nonnegative-ℤ (pair (inr (inr x)) star) = refl

is-retraction-nat-nonnegative-ℤ :
  (n : )  nat-nonnegative-ℤ (nonnegative-int-ℕ n)  n
is-retraction-nat-nonnegative-ℤ zero-ℕ = refl
is-retraction-nat-nonnegative-ℤ (succ-ℕ n) = refl

is-equiv-nat-nonnegative-ℤ : is-equiv nat-nonnegative-ℤ
pr1 (pr1 is-equiv-nat-nonnegative-ℤ) = nonnegative-int-ℕ
pr2 (pr1 is-equiv-nat-nonnegative-ℤ) = is-retraction-nat-nonnegative-ℤ
pr1 (pr2 is-equiv-nat-nonnegative-ℤ) = nonnegative-int-ℕ
pr2 (pr2 is-equiv-nat-nonnegative-ℤ) = is-section-nat-nonnegative-ℤ

is-equiv-nonnegative-int-ℕ : is-equiv nonnegative-int-ℕ
pr1 (pr1 is-equiv-nonnegative-int-ℕ) = nat-nonnegative-ℤ
pr2 (pr1 is-equiv-nonnegative-int-ℕ) = is-section-nat-nonnegative-ℤ
pr1 (pr2 is-equiv-nonnegative-int-ℕ) = nat-nonnegative-ℤ
pr2 (pr2 is-equiv-nonnegative-int-ℕ) = is-retraction-nat-nonnegative-ℤ

equiv-nonnegative-int-ℕ :   nonnegative-ℤ
pr1 equiv-nonnegative-int-ℕ = nonnegative-int-ℕ
pr2 equiv-nonnegative-int-ℕ = is-equiv-nonnegative-int-ℕ

is-injective-nonnegative-int-ℕ : is-injective nonnegative-int-ℕ
is-injective-nonnegative-int-ℕ {x} {y} p =
  ( inv (is-retraction-nat-nonnegative-ℤ x)) 
  ( ap nat-nonnegative-ℤ p) 
  ( is-retraction-nat-nonnegative-ℤ y)

decide-is-nonnegative-ℤ :
  {x : }  (is-nonnegative-ℤ x) + (is-nonnegative-ℤ (neg-ℤ x))
decide-is-nonnegative-ℤ {inl x} = inr star
decide-is-nonnegative-ℤ {inr x} = inl star

is-zero-is-nonnegative-neg-is-nonnegative-ℤ :
  (x : )  is-nonnegative-ℤ x  is-nonnegative-ℤ (neg-ℤ x)  is-zero-ℤ x
is-zero-is-nonnegative-neg-is-nonnegative-ℤ (inr (inl star)) nonneg nonpos =
  refl

Properties of positive integers

The positivity predicate on integers is decidable

decide-is-positive-ℤ : {x : }  (is-positive-ℤ x) + is-nonnegative-ℤ (neg-ℤ x)
decide-is-positive-ℤ {inl x} = inr star
decide-is-positive-ℤ {inr (inl x)} = inr star
decide-is-positive-ℤ {inr (inr x)} = inl star

decide-is-positive-is-nonzero-ℤ :
  (x : )  (x  zero-ℤ) 
  (is-positive-ℤ x) + is-positive-ℤ (neg-ℤ x)
decide-is-positive-is-nonzero-ℤ (inl x) H = inr star
decide-is-positive-is-nonzero-ℤ (inr (inl x)) H = ex-falso (H refl)
decide-is-positive-is-nonzero-ℤ (inr (inr x)) H = inl star

This remains to be fully formalized.

The nonpositive integers

is-nonpositive-ℤ :   UU lzero
is-nonpositive-ℤ x = is-nonnegative-ℤ (neg-ℤ x)

Positive integers are not nonpositive

not-is-nonpositive-is-positive-ℤ :
  (x : )  is-positive-ℤ x  ¬ (is-nonpositive-ℤ x)
not-is-nonpositive-is-positive-ℤ (inr (inl x)) x-is-pos _ = x-is-pos
not-is-nonpositive-is-positive-ℤ (inr (inr x)) x-is-pos neg-x-is-nonneg =
  neg-x-is-nonneg

An integer that is not positive is nonpositive

is-nonpositive-not-is-positive-ℤ :
  (x : )  ¬ (is-positive-ℤ x)  is-nonpositive-ℤ x
is-nonpositive-not-is-positive-ℤ x H with decide-is-positive-ℤ {x}
... | inl K = ex-falso (H K)
... | inr K = K

Relation between successors of natural numbers and integers

succ-int-ℕ : (x : )  succ-ℤ (int-ℕ x)  int-ℕ (succ-ℕ x)
succ-int-ℕ zero-ℕ = refl
succ-int-ℕ (succ-ℕ x) = refl

The negative function is injective

is-injective-neg-ℤ : is-injective neg-ℤ
is-injective-neg-ℤ {x} {y} p = inv (neg-neg-ℤ x)  ap neg-ℤ p  neg-neg-ℤ y

An integer is zero if its negative is zero

is-zero-is-zero-neg-ℤ : (x : )  is-zero-ℤ (neg-ℤ x)  is-zero-ℤ x
is-zero-is-zero-neg-ℤ (inr (inl star)) H = refl

See also

Recent changes