↑ Top


Inverses

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


{-# OPTIONS --without-K --exact-split --safe #-}
module Base.Functions.Inverses where

-- Imports from Agda and the Agda Standard Library ---------------------------------------------
open import Agda.Primitive    using () renaming ( Set to Type )
open import Data.Product      using ( _,_ ; Σ-syntax )
open import Level             using ( Level ; _⊔_ )
open import Relation.Binary.PropositionalEquality
                              using ( _≡_ ; sym ; refl )
open import Relation.Unary    using ( Pred ; _∈_ )

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

private variable α β : Level

We begin by defining an data type that represents the semantic concept of inverse image of a function.


module _ {A : Type α }{B : Type β } where

 data Image_∋_ (f : A  B) : B  Type (α  β) where
  eq : {b : B}  (a : A)  b  f a  Image f  b

 open Image_∋_

 Range : (A  B)  Pred B (α  β)
 Range f b = ∃[ a  A ] (f a)  b

 range : (A  B)  Type (α  β)
 range f = Σ[ b  B ] ∃[ a  A ](f a)  b

 Image⊆Range : (f : A  B)   b  Image f  b  b  Range f
 Image⊆Range f b (eq a x) = a , (sym x)

 Range⊆Image : (f : A  B)   b  b  Range f  Image f  b
 Range⊆Image f b (a , x) = eq a (sym x)

 Imagef∋f : {f : A  B}{a : A}  Image f  (f a)
 Imagef∋f = eq _ refl

 f∈range : {f : A  B}(a : A)  range f
 f∈range {f} a = (f a) , (a , refl)

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}  Image f  b    A
 Inv f (eq a _) = a


 [_]⁻¹ : (f : A  B)  range f   A
 [ f ]⁻¹ (_ , (a , _)) = a

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


 InvIsInverseʳ : {f : A  B}{b : B}(q : Image f  b)  f(Inv f q)  b
 InvIsInverseʳ (eq _ p) = sym p

 ⁻¹IsInverseʳ : {f : A  B}{bap : range f}  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 a certain 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 a)  a
 ⁻¹IsInverseˡ = refl

← Base.Functions.Preliminaries Base.Functions.Injective →