### Preliminaries

This is the Overture.Basic module of the Agda Universal Algebra Library.

#### Logical foundations

An Agda program typically begins by setting some options and by importing types from existing Agda libraries. Options are specified with the `OPTIONS` pragma and control the way Agda behaves by, for example, specifying the logical axioms and deduction rules we wish to assume when the program is type-checked to verify its correctness. Every Agda program in agda-algebras begins with the following line.

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

```

These options control certain foundational assumptions that Agda makes when type-checking the program to verify its correctness.

Note that if we wish to type-check a file that imports another file that still has some unmet proof obligations, we must replace the `--safe` flag with `--allow-unsolved-metas`, but this is never done in (publicly released versions of) the agda-algebras.

#### Agda modules

The `OPTIONS` pragma is usually followed by the start of a module. For example, the [Base.Functions.Basic][] module begins with the following line, and then a list of imports of things used in the module.

```
module Overture.Basic where

-- Imports from Agda and the Agda Standard Library -----------------------------------------------
open import Agda.Primitive    using () renaming ( Set to  Type ; lzero to  ℓ₀ )
open import Data.Product      using ( _,_ ; ∃ ; Σ-syntax ; _×_ )
renaming ( proj₁ to fst ; proj₂ to snd )
open import Function.Base     using ( _∘_ ; id )
open import Level             using ( Level ; suc ; _⊔_ ; lift ; lower ; Lift )
open import Relation.Binary   using ( Decidable )
open import Relation.Binary   using ( IsEquivalence ; IsPartialOrder )
open import Relation.Nullary  using ( Dec ; yes ; no ; Irrelevant )

open import Relation.Binary.PropositionalEquality using ( _≡_ ; refl ; sym ; trans )

private variable α β : Level

ℓ₁ : Level
ℓ₁ = suc ℓ₀

-- the two element type
data 𝟚 : Type ℓ₀ where 𝟎 : 𝟚 ;  𝟏 : 𝟚

-- the three element type
data 𝟛 : Type ℓ₀ where 𝟎 : 𝟛 ;  𝟏 : 𝟛 ;  𝟐 : 𝟛
```

#### Projection notation

The definition of `Σ` (and thus, of `×`) includes the fields `proj₁` and `proj₂` representing the first and second projections out of the product. However, we prefer the shorter names `fst` and `snd`. Sometimes we prefer to denote these projections by `∣_∣` and `∥_∥`, respectively. We define these alternative notations for projections out of pairs as follows.

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

∣_∣ : Σ[ x ∈ A ] B x → A
∣_∣ = fst

∥_∥ : (z : Σ[ a ∈ A ] B a) → B ∣ z ∣
∥_∥ = snd

infix  40 ∣_∣

```

Here we put the definitions inside an anonymous module, which starts with the `module` keyword followed by an underscore (instead of a module name). The purpose is simply to move the postulated typing judgments—the “parameters” of the module (e.g., `A : Type α`)—out of the way so they don’t obfuscate the definitions inside the module.

Let’s define some useful syntactic sugar that will make it easier to apply symmetry and transitivity of `≡` in proofs.

```
_⁻¹ : {A : Type α} {x y : A} → x ≡ y → y ≡ x
p ⁻¹ = sym p

infix  40 _⁻¹

```

If we have a proof `p : x ≡ y`, and we need a proof of `y ≡ x`, then instead of `sym p` we can use the more intuitive `p ⁻¹`. Similarly, the following syntactic sugar makes abundant appeals to transitivity easier to stomach.

```
_∙_ : {A : Type α}{x y z : A} → x ≡ y → y ≡ z → x ≡ z
p ∙ q = trans p q

𝑖𝑑 : (A : Type α ) → A → A
𝑖𝑑 A = λ x → x

infixl 30 _∙_
```

#### Sigma types

```
infix 2 ∃-syntax

∃-syntax : ∀ {A : Type α} → (A → Type β) → Set (α ⊔ β)
∃-syntax = ∃

syntax ∃-syntax (λ x → B) = ∃[ x ∈ A ] B
```

#### Pi types

The dependent function type is traditionally denoted with an uppercase pi symbol and typically expressed as `Π(x : A) B x`, or something similar. In Agda syntax, one writes `(x : A) → B x` for this dependent function type, but we can define syntax that is closer to standard notation as follows.

```
Π : {A : Type α } (B : A → Type β ) → Type (α ⊔ β)
Π {A = A} B = (x : A) → B x

Π-syntax : (A : Type α)(B : A → Type β) → Type (α ⊔ β)
Π-syntax A B = Π B

syntax Π-syntax A (λ x → B) = Π[ x ∈ A ] B
infix 6 Π-syntax

```

In the modules that follow, we will see many examples of this syntax in action.

#### Agda’s universe hierarchy

The hierarchy of universes in Agda is structured as follows:

``````
Type α : Type (lsuc α) ,   Type (lsuc α) : Type (lsuc (lsuc α)) , etc.

``````

and so on. This means that the universe `Type α` has type `Type(lsuc α)`, and `Type(lsuc α)` has type `Type(lsuc (lsuc α))`, and so on. It is important to note, however, this does not imply that `Type α : Type(lsuc(lsuc α))`. In other words, Agda’s universe hierarchy is non-cumulative. This makes it possible to treat universe levels more precisely, which is nice. On the other hand, a non-cumulative hierarchy can sometimes make for a non-fun proof assistant. Specifically, in certain situations, the non-cumulativity makes it unduly difficult to convince Agda that a program or proof is correct.

#### Lifting and lowering

Here we describe a general `Lift` type that help us overcome the technical issue described in the previous subsection. In the Lifts of algebras section of the Base.Algebras.Basic module we will define a couple domain-specific lifting types which have certain properties that make them useful for resolving universe level problems when working with algebra types.

Let us be more concrete about what is at issue here by considering a typical example. Agda will often complain with errors like the following:

``````Birkhoff.lagda:498,20-23
α != 𝓞 ⊔ 𝓥 ⊔ (lsuc α) when checking that the expression... has type...
``````

This error message means that Agda encountered the universe level `lsuc α`, on line 498 (columns 20–23) of the file `Birkhoff.lagda`, but was expecting a type at level `𝓞 ⊔ 𝓥 ⊔ lsuc α` instead.

The general `Lift` record type that we now describe makes such problems easier to deal with. It takes a type inhabiting some universe and embeds it into a higher universe and, apart from syntax and notation, it is equivalent to the `Lift` type one finds in the `Level` module of the Agda Standard Library.

``````record Lift {𝓦 α : Level} (A : Set α) : Set (α ⊔ 𝓦) where
``````
``````    constructor lift
``````
``````    field lower : A
``````

The point of having a ramified hierarchy of universes is to avoid Russell’s paradox, and this would be subverted if we were to lower the universe of a type that wasn’t previously lifted. However, we can prove that if an application of `lower` is immediately followed by an application of `lift`, then the result is the identity transformation. Similarly, `lift` followed by `lower` is the identity.

```
lift∼lower : {A : Type α} → lift ∘ lower ≡ 𝑖𝑑 (Lift β A)
lift∼lower = refl

lower∼lift : {A : Type α} → (lower {α}{β}) ∘ lift ≡ 𝑖𝑑 A
lower∼lift = refl

```

The proofs are trivial. Nonetheless, we’ll come across some holes these lemmas can fill.

#### Pointwise equality of dependent functions

We conclude this module with a definition that conveniently represents te assertion that two functions are (extensionally) the same in the sense that they produce the same output when given the same input. (We will have more to say about this notion of equality in the Base.Equality.Extensionality module.)

```
module _ {α : Level}{A : Type α}{β : Level}{B : A → Type β } where

_≈_ :  (f g : (a : A) → B a) → Type (α ⊔ β)
f ≈ g = ∀ x → f x ≡ g x

infix 8 _≈_

≈IsEquivalence : IsEquivalence _≈_
IsEquivalence.refl   ≈IsEquivalence          = λ _ → refl
IsEquivalence.sym    ≈IsEquivalence f≈g      = λ x → sym (f≈g x)
IsEquivalence.trans  ≈IsEquivalence f≈g g≈h  = λ x → trans (f≈g x) (g≈h x)

```

The following is convenient for proving two pairs of a product type are equal using the fact that their respective components are equal.

```
≡-by-parts :  {A : Type α}{B : Type β}{u v : A × B}
→            fst u ≡ fst v → snd u ≡ snd v → u ≡ v

≡-by-parts refl refl = refl

```

Lastly, we will use the following type (instead of `subst`) to transport equality proofs.

```
transport : {A : Type α } (B : A → Type β) {x y : A} → x ≡ y → B x → B y
transport B refl = id
```