↑ Top


Inverses for functions with structure

This is the Setoid.Functions.Inverses module of the agda-algebras library.


{-# OPTIONS --without-K --exact-split --safe #-}

module Setoid.Functions.Inverses where

-- Imports from Agda and the Agda Standard Library --------------------
open import Agda.Primitive    using ( _⊔_ ; Level ) renaming ( Set to Type )
open import Function          using ( id )   renaming ( Func to _⟶_ )
open import Data.Product      using ( _,_ ; Σ-syntax )
                              renaming ( proj₁ to fst ; proj₂ to snd ; _×_ to _∧_)
open import Relation.Unary    using ( Pred ; _∈_ )
open import Relation.Binary   using ( Setoid ; _Preserves_⟶_ )

-- Imports from agda-algebras -----------------------------------------
open import Overture using ( ∣_∣ ; ∥_∥ ; ∃-syntax )

private variable α ρᵃ β ρᵇ : Level

module _ {𝑨 : Setoid α ρᵃ}{𝑩 : Setoid β ρᵇ} where

 open Setoid 𝑨 using()  renaming ( Carrier to A ; _≈_ to _≈₁_ )
                        renaming ( refl to refl₁ ; sym to sym₁ ; trans to trans₁ )
 open Setoid 𝑩 using()  renaming ( Carrier to B ; _≈_ to _≈₂_ )
                        renaming ( refl to refl₂ ; sym to sym₂ ; trans to trans₂ )

 open _⟶_ {a = α}{ρᵃ}{β}{ρᵇ}{From = 𝑨}{To = 𝑩} renaming (f to _⟨$⟩_ )

We begin by defining two data types that represent the semantic concept of the image of a function. The first of these is for functions on bare types, while the second is for functions on setoids.


 data Img_∋_ (f : A  B) : B  Type (α  β  ρᵇ) where
  eq : {b : B}  (a : A)  b ≈₂ (f a)  Img f  b


 data Image_∋_ (F : 𝑨  𝑩) : B  Type (α  β  ρᵇ) where
  eq : {b : B}  (a : A)  b ≈₂ (F ⟨$⟩ a)  Image F  b

 open Image_∋_

 IsInRange : (𝑨  𝑩)  Pred B (α  ρᵇ)
 IsInRange F b = ∃[ a  A ] (F ⟨$⟩ a) ≈₂ b

 Image⊆Range :  {F b}  Image F  b  b  IsInRange F
 Image⊆Range (eq a x) = a , (sym₂ x)

 IsInRange→IsInImage :  {F b}  b  IsInRange F  Image F  b
 IsInRange→IsInImage (a , x) = eq a (sym₂ x)

 Imagef∋f :  {F a}  Image F  (F ⟨$⟩ a)
 Imagef∋f = eq _ refl₂

 -- Alternative representation of the range of a Func as a setoid

 -- the carrier
 _range : (𝑨  𝑩)  Type (α  β  ρᵇ)
 F range = Σ[ b  B ] ∃[ a  A ](F ⟨$⟩ a) ≈₂ b

 _image : (F : 𝑨  𝑩)  F range  B
 (F image) (b , (_ , _)) = b

 _preimage : (F : 𝑨  𝑩)  F range  A
 (F preimage) (_ , (a , _)) = a

 f∈range :  {F}  A  F range
 f∈range {F} a = (F ⟨$⟩ a) , (a , refl₂)

 ⌜_⌝ : (F : 𝑨  𝑩)  A  F range
  F  a = f∈range{F} a

 Ran : (𝑨  𝑩)  Setoid (α  β  ρᵇ) ρᵇ
 Ran F = record  { Carrier = F range
                 ; _≈_ = λ x y  ((F image) x) ≈₂ ((F image) y)
                 ; isEquivalence = record  { refl = refl₂
                                           ; sym = sym₂
                                           ; trans = trans₂
                                           }
                 }

 RRan : (𝑨  𝑩)  Setoid (α  β  ρᵇ) (ρᵃ  ρᵇ)
 RRan F = record  { Carrier = F range
                  ; _≈_ = λ x y   ( (F preimage) x ) ≈₁ ( (F preimage) y )
                                    ( (F image) x) ≈₂ ( (F image) y )

                  ; isEquivalence =
                     record  { refl = refl₁ , refl₂
                             ; sym = λ x  (sym₁  x ) , (sym₂  x )
                             ; trans = λ x y  (trans₁  x   y ) , (trans₂  x   y )
                             }
                  }

 _preimage≈image :  F r  F ⟨$⟩ (F preimage) r ≈₂ (F image) r
 (F preimage≈image) (_ , (_ , p)) = p


 Dom : (𝑨  𝑩)  Setoid α ρᵇ
 Dom F = record  { Carrier = A
                 ; _≈_ = λ x y  F ⟨$⟩ x ≈₂ F ⟨$⟩ y
                 ; isEquivalence = record  { refl = refl₂
                                           ; sym = sym₂
                                           ; trans = trans₂
                                           }
                 }

An inhabitant of Image f ∋ b is a dependent pair (a , p), where a : A and p : b ≡ f a is a proof that f maps a to b. Since the proof that b belongs to the image of f is always accompanied by a witness a : A, we can actually compute a (pseudo)inverse of f. For convenience, we define this inverse function, which we call Inv, and which takes an arbitrary b : B and a (witness, proof)-pair, (a , p) : Image f ∋ b, and returns the witness a.


 inv : (f : A  B){b : B}  Img f  b  A
 inv _ (eq a _) = a

 Inv : (F : 𝑨  𝑩){b : B}  Image F  b  A
 Inv _ (eq a _) = a

 Inv' : (F : 𝑨  𝑩){b : B}  b  IsInRange F  A
 Inv' _ (a , _) = a

 [_]⁻¹ : (F : 𝑨  𝑩)  F range  A
 [ F ]⁻¹ = F preimage

 ⟦_⟧⁻¹ : (F : 𝑨  𝑩)  Ran F  Dom F
  F ⟧⁻¹ = record { f = F preimage ; cong = λ {x}{y}  c{x}{y} }
  where
  c : (F preimage) Preserves
       (Setoid._≈_ (Ran F))  (Setoid._≈_ (Dom F))
  c {x}{y} ix≈iy = Goal
   where
   Goal : F ⟨$⟩ ((F preimage) x) ≈₂ F ⟨$⟩ ((F preimage) y)
   Goal = trans₂ ((F preimage≈image) x) (trans₂ ix≈iy (sym₂ ((F preimage≈image) y)))

We can prove that Inv f is the range-restricted right-inverse of f, as follows.


 invIsInvʳ : {f : A  B}{b : B}(q : Img f  b)  (f (inv f q)) ≈₂ b
 invIsInvʳ (eq _ p) = sym₂ p

 InvIsInverseʳ : {F : 𝑨  𝑩}{b : B}(q : Image F  b)  (F ⟨$⟩ (Inv F q)) ≈₂ b
 InvIsInverseʳ (eq _ p) = sym₂ p

 ⁻¹IsInverseʳ : {F : 𝑨  𝑩}{bap : F range}  (F ⟨$⟩ ([ F ]⁻¹ bap )) ≈₂  bap 
 ⁻¹IsInverseʳ {bap = (_ , (_ , p))} = p

Of course, the “range-restricted” qualifier is needed because Inf f is not defined outside the range of f.

In the following sense, Inv f is also a (range-restricted) left-inverse.


 InvIsInverseˡ :  {F a}  Inv F {b = F ⟨$⟩ a} Imagef∋f ≈₁ a
 InvIsInverseˡ = refl₁

 ⁻¹IsInverseˡ :  {F a}  [ F ]⁻¹ (f∈range{F} a) ≈₁ a
 ⁻¹IsInverseˡ = refl₁

← Setoid.Functions.Basic Setoid.Functions.Injective →