Bijective Functions & Inverses In Agda: A Formal Proof

Aug 10, 2025 by Mei Lin 55 views

Bijective Functions Imply Inverses in Agda: A Deep Dive

Hey guys! Let's dive into a fascinating topic in functional programming and formal verification using Agda. We're going to explore the relationship between bijective functions and their inverses, specifically focusing on how to prove that a bijective function implies the existence of an inverse function within Agda's standard library. This is a crucial concept in many areas of mathematics and computer science, and Agda, with its powerful type system, provides an excellent environment to formalize these ideas.

Understanding Bijective Functions and Inverses

Let's start with the basics. A bijective function, also known as a one-to-one correspondence, is a function that is both injective (one-to-one) and surjective (onto). Injective means that each element of the function's codomain is mapped to by at most one element of its domain. Surjective means that every element in the codomain is mapped to by at least one element in the domain. Combining these two properties, a bijective function creates a perfect pairing between elements of its domain and codomain. Think of it like matching socks – each sock has exactly one pair, and no socks are left unpaired.

Now, what about inverses? The inverse of a function, if it exists, essentially reverses the mapping. If a function f maps a to b, then its inverse function f⁻¹ maps b back to a. For an inverse to exist, the original function must be bijective. This makes sense because if the function wasn't injective, we wouldn't know which element in the domain to map back to, and if it wasn't surjective, there would be elements in the codomain with no corresponding element in the domain to map back from. The existence and properties of inverses are fundamental in many mathematical structures and have significant implications in areas like cryptography and data manipulation. The concept of inverses also allows us to define reversible computations, which are crucial in building reliable and predictable systems. By understanding the conditions under which inverses exist, we can design algorithms and data structures that are more efficient and robust. Furthermore, the formalization of these concepts in a proof assistant like Agda allows us to guarantee the correctness of our code and the underlying mathematical principles.

The Challenge: Proving Bijective Implies Inverse in Agda

The Agda standard library provides a formal definition of bijective functions and inverse relations. The challenge lies in formally proving the lemma: “If a function f is bijective, then there exists a function f⁻¹ that is its inverse.” This might sound straightforward, but the intricacies of Agda's type system, especially when dealing with generalized variables, can make the proof quite involved.

The core issue arises when trying to define the type of the inverse function inv-f : B -> A. Agda needs to be able to infer the types precisely, and when dealing with generalized variables (variables whose types are not explicitly stated), this can become tricky. We need to ensure that the inverse function maps elements from the codomain B back to the domain A in a way that respects the equivalence relations defined on these sets. This involves not only defining the function itself but also proving that it satisfies the properties of an inverse, namely that f (f⁻¹ b) ≈ b and f⁻¹ (f a) ≈ a for all b in B and a in A, where ≈ represents the appropriate equivalence relation. These properties are crucial for establishing the inverse relationship and ensuring that the function behaves as expected. The difficulty in specifying the type of inv-f stems from the need to capture the dependencies between the domain and codomain elements and the equivalence relations that govern them. Without a clear and precise type definition, Agda cannot guarantee the correctness of the inverse function, and the proof will fail. This highlights the importance of careful type-driven development in Agda, where types serve as a guide for constructing correct and reliable programs and proofs.

The Agda Code: A Step-by-Step Breakdown

Let's examine the Agda code provided, breaking it down step by step to understand the proof construction:

{-# OPTIONS --cubical-compatible --safe #-}

module BijectiveImpliesInverse where
open import Data.Product.Base as Product
open import Function.Definitions
open import Level using (Level)
open import Relation.Binary.Core using (Rel)
open import Relation.Binary.Bundles using (Setoid)
open import Relation.Binary.Definitions using (Reflexive; Symmetric; Transitive)
open import Relation.Nullary.Negation.Core using (¬_; contraposition)

open import Function.Definitions
open import Relation.Binary.Definitions
------------------------------------------------------------------------
-- Bijective

bijective⇒inverseᵇ : ∀ {A B : Set} {f} {ℓ₁ ℓ₂} (≈₁ : Rel A ℓ₁) (≈₂ : Rel B ℓ₂) →
                     Reflexive ≈₂ →
                     Symmetric ≈₁ →
                     Symmetric ≈₂ →
                     Transitive ≈₁ →
                     Transitive ≈₂ →
                     Bijective ≈₁ ≈₂ f →
                     ∃ \f⁻¹ -> Inverseᵇ ≈₁ ≈₂ f f⁻¹

bijective⇒inverseᵇ {A} {B} {f} {ℓ₁} {ℓ₂} ≈₁ ≈₂ ref sym1 sym2 trans1 trans2 (inj , surj) =
  inv-f , (l , r)
  where
  inv-f : B -> A
  inv-f x with surj x
  ... | (y , _) = y
  

  l : Inverseˡ ≈₁ ≈₂ f inv-f
  l {y} {x} x=inv-fy with surj y
  ... | (x , p) = p x=inv-fy

  aux : ∀ y -> ≈₂ (f (inv-f y)) y
  aux y with surj y
  ... | (x , p) = p (inj ref)

  aux2 : ∀ x -> ≈₁ (inv-f (f x)) x
  aux2 x with surj (f x)
  ... | (z , p) = inj (p (inj ref))

  inv-f-cong : ∀ y1 y2 -> ≈₂ y1 y2 -> ≈₁ (inv-f y1) (inv-f y2)
  inv-f-cong y1 y2 eq = inj (trans2 (aux y1) (trans2 eq (sym2 (aux y2))))
  
  r : Inverseʳ ≈₁ ≈₂ f inv-f
  r {x} {y} y=fx with surj (f x)
  ... | (z , p) = trans1 (inv-f-cong y (f x) y=fx) (aux2 x)

Module Setup and Imports

The code starts with the usual Agda module declaration and imports necessary libraries. We're using features from Data.Product.Base, Function.Definitions, Level, Relation.Binary.Core, Relation.Binary.Bundles, Relation.Binary.Definitions, and Relation.Nullary.Negation.Core. These libraries provide the foundational definitions for products, functions, levels (for universe polymorphism), binary relations, setoids (sets with equivalence relations), and various relation properties like reflexivity, symmetry, and transitivity. Think of these imports as bringing in the necessary tools for our proof-building workshop.

The `bijective⇒inverseᵇ` Lemma

The heart of the code is the bijective⇒inverseᵇ lemma. Let's break down its type signature:

bijective⇒inverseᵇ : ∀ {A B : Set} {f} {ℓ₁ ℓ₂} (≈₁ : Rel A ℓ₁) (≈₂ : Rel B ℓ₂) →
                     Reflexive ≈₂ →
                     Symmetric ≈₁ →
                     Symmetric ≈₂ →
                     Transitive ≈₁ →
                     Transitive ≈₂ →
                     Bijective ≈₁ ≈₂ f →
                     ∃ \f⁻¹ -> Inverseᵇ ≈₁ ≈₂ f f⁻¹

This type signature states that for any sets A and B, any function f (implicitly typed as A -> B), and any equivalence relations ≈₁ on A and ≈₂ on B, if we have proofs that ≈₂ is reflexive, ≈₁ and ≈₂ are symmetric, ≈₁ and ≈₂ are transitive, and f is bijective with respect to ≈₁ and ≈₂, then there exists a function f⁻¹ that is the inverse of f with respect to ≈₁ and ≈₂. Phew! That's a lot to unpack, but it precisely captures the mathematical statement we're trying to prove. It's like laying out all the conditions and the desired outcome before starting a complex recipe.

Proof Construction: Defining the Inverse Function

The proof starts by pattern matching on the Bijective hypothesis, which is represented as a pair (inj, surj) where inj is the proof of injectivity and surj is the proof of surjectivity. The crucial step is defining the inverse function inv-f:

inv-f : B -> A
inv-f x with surj x
... | (y , _) = y

This definition leverages the surjectivity proof. Since surj proves that for every x in B, there exists a y in A such that f y ≈₂ x, we can define inv-f x to be this y. We use Agda's with abstraction to pattern match on the result of surj x, obtaining the y and the proof _ (we don't need the proof here, just the y). This is where the magic happens – we're using the existence guarantee provided by surjectivity to construct the inverse function. It's like having a map that guarantees a route back, and we're simply following that route.

Proving the Inverse Properties

Now, we need to show that inv-f is indeed an inverse of f. This means proving both the left and right inverse laws:

Left Inverse Law: f (inv-f y) ≈₂ y for all y in B
Right Inverse Law: inv-f (f x) ≈₁ x for all x in A

The code provides proofs for these laws, named l (left inverse) and r (right inverse). Let's look at the proof of the left inverse law:

l : Inverseˡ ≈₁ ≈₂ f inv-f
l {y} {x} x=inv-fy with surj y
... | (x , p) = p x=inv-fy

This proof again uses the surjectivity proof surj y. By definition, surj y gives us a pair (x, p) where x is an element in A and p is a proof that f x ≈₂ y. The proof p is exactly what we need to show that f (inv-f y) ≈₂ y, since inv-f y is defined to be this x. This proof elegantly uses the definition of the inverse function and the surjectivity property to establish the left inverse law. It’s like showing that if you follow the map back, you indeed end up where you started.

The right inverse law proof, r, is a bit more involved and requires some auxiliary lemmas (aux, aux2, and inv-f-cong). These lemmas help to bridge the gap between the definitions and the desired result, showcasing the intricacies of working with equivalence relations in Agda.

The Auxiliary Lemmas

The auxiliary lemmas play a crucial role in establishing the right inverse law. Let's briefly discuss their purpose:

aux : ∀ y -> ≈₂ (f (inv-f y)) y: This lemma proves the left inverse property directly, which is used in the subsequent lemmas.
aux2 : ∀ x -> ≈₁ (inv-f (f x)) x: This lemma is the core of the right inverse proof, showing that inv-f (f x) is equivalent to x under the relation ≈₁.
inv-f-cong : ∀ y1 y2 -> ≈₂ y1 y2 -> ≈₁ (inv-f y1) (inv-f y2): This lemma proves that inv-f respects the equivalence relation ≈₂, meaning that if y1 ≈₂ y2, then inv-f y1 ≈₁ inv-f y2. This is essential for ensuring that the inverse function behaves consistently with the equivalence relation.

These lemmas are like smaller, supporting arguments that build up to the main proof. They demonstrate the modularity of the proof and how complex statements can be broken down into simpler, more manageable components.

Overcoming the Type Specification Challenge

The initial challenge, as mentioned, was specifying the type of inv-f : B -> A due to the use of generalized variables. The solution lies in leveraging the surjectivity proof to construct the inverse function. By pattern matching on the surjectivity proof, we can extract the element in A that maps to a given element in B, effectively defining the inverse function. This approach elegantly avoids the need for explicit type annotations and allows Agda to infer the types correctly. It’s like finding the right key to unlock a door – the surjectivity proof provides the necessary information to define the inverse function without getting bogged down in type-level complexities.

Conclusion: The Power of Formal Verification

This Agda code demonstrates the power of formal verification in proving fundamental mathematical concepts. By formally proving that bijective functions imply the existence of inverses, we gain a high degree of confidence in this result. This has implications for the correctness of programs that rely on this property, especially in areas like cryptography and data manipulation. It’s like having a mathematical guarantee that your code will work as expected, which is invaluable in critical applications.

Furthermore, this exercise highlights the importance of Agda's type system in guiding proof construction. The types act as a roadmap, ensuring that each step is logically sound and leads towards the desired conclusion. The challenges encountered, such as specifying the type of the inverse function, force us to think deeply about the underlying mathematical concepts and how they can be represented in a formal system. It’s like learning a new language – the grammar and syntax can be challenging at first, but they ultimately provide a powerful framework for expressing complex ideas.

So, there you have it! We've successfully navigated the intricacies of proving that a bijective function implies the existence of an inverse in Agda. This journey showcases the beauty and power of formal verification in ensuring the correctness of mathematical and computational systems. Keep exploring, keep proving, and keep coding!