module Data.Set.Material where

The cumulative hierarchy🔗

This module defines the cumulative hierarchy of material sets, as a recursive higher inductive type, following §10.5 of the HoTT book. We then prove that our model V (at any universe level) is a model of the theory IZF: it validates the axioms of empty set, pairing, union, infinity, replacement, separation, power set, and

Our higher inductive type is generated by the constructor set, together with the extensionality constructor ext, and the necessary set-truncation.

data V ℓ : Type (lsuc ℓ) where
  set : (A : Type ℓ) → (A → V ℓ) → V ℓ
  ext
    : ∀ {A B : Type ℓ} (f : A → V ℓ) (g : B → V ℓ)
    → ((a : A) → ∄ fibre g (f a) ∄)
    → ((b : B) → ∄ fibre f (g b) ∄)
    → set A f ≡ set B g
  squash : is-set (V ℓ)

The type V resembles a W-type: the constructor set corresponds to the “supremum” of a family of sets, where the “branching factor” of the family is allowed to be any type in the universe Of course, if we could take the supremum of V-many sets, we could reproduce Russell’s paradox, so Agda rightly forces us to put V in successor universe.

The mere fibres in the extensionality constructor, as we’ll see in a bit, are exactly the normal forms of the propositions and You should think of ext as an instance of the axiom of extensionality, specialised for values which are “explicit” sets: If every element is somewhere in and every is somewhere in then and present the same sets.

As usual for higher inductive types, we have an elimination principle into families of propositions, which allows us to ignore all the higher constructors. If holds of assuming that it holds for every value of then it holds for any set.

V-elim-prop
  : ∀ {ℓ ℓ'} (P : V ℓ → Type ℓ')
  → (∀ x → is-prop (P x))
  → (∀ {A} (f : A → V ℓ) → (∀ x → P (f x)) → P (set A f))
  → ∀ x → P x
The implementation of V-elim-prop is entirely routine.
V-elim-prop P p-prop p-set (set A x) = p-set x λ a → V-elim-prop P p-prop p-set (x a)
V-elim-prop P p-prop p-set (ext f g x y i) =
  is-prop→pathp (λ i → p-prop (ext f g x y i))
    (p-set f λ a → V-elim-prop P p-prop p-set (f a))
    (p-set g λ a → V-elim-prop P p-prop p-set (g a)) i
V-elim-prop P p-prop p-set (squash x y p q i j) =
  is-prop→squarep (λ i j → p-prop (squash x y p q i j))
    (λ _ → go x) (λ i → go (p i)) (λ i → go (q i)) (λ _ → go y) i j
  where go = V-elim-prop P p-prop p-set

Setting this recursion principle aside for a moment, we must define the membership relation between material sets. Here, we must handle the set constructor and the ext constructor, since squash is taken care of by mapping into Prop, which is a set.

On the sets, we define membership exactly as we have for the extensionality constructor.

is-member : ∀ {ℓ} → V ℓ → V ℓ → Prop (lsuc ℓ)
is-member e (set A f) = el ∄ fibre f e ∄ squash
is-member e (ext {A} {B} f g p q i) =
  n-ua {X = el _ squash} {Y = el _ squash} (prop-ext squash squash from to) i where

The extensionality constructor requires that we show a logical equivalence (since we’re mapping into propositions) between the mere fibres of and over under the assumption of and

    from : ∄ fibre f e ∄ → ∄ fibre g e ∄
    to   : ∄ fibre g e ∄ → ∄ fibre f e ∄

In one direction, assume we’re given Since we’re mapping into a proposition, we may take where We may then use to get a fibre of over i.e., a pair where We wanted to construct a fibre of over we have and

The other half of the equivalence is symmetric.

    from w = do
      (a , fa=e)  ← w
      (b , gb=fa) ← p a
      pure (b , gb=fa ∙ fa=e)

    to w = do
      (b , gb=e)  ← w
      (a , fa=gb) ← q b
      pure (a , fa=gb ∙ gb=e)

Having completed the construction of the membership proposition, we define an instance of Membership for the set-theoretic universe. This will allow us to use the overloaded membership operator to mean membership of material sets, and similarly for non-membership (∉) and subset (⊆).

instance
  Membership-V : ∀ {ℓ} → Membership (V ℓ) (V ℓ) (lsuc ℓ)
  Membership-V = record { _∈_ = λ x y → ⌞ is-member x y ⌟ }

Extensionality🔗

We can now prove our material sets satisfy the axiom of extensionality: if and are subsets of eachother, they must be the same set. By induction (now using our elimination principle), it suffices to show this when and are literal sets.

extensionality : ∀ {ℓ} (A B : V ℓ) → A ⊆ B → B ⊆ A → A ≡ B
extensionality = wrapper where

By our ext constructor, it will suffice to show that together with the symmetric condition on

  worker
    : ∀ {A B} (f : A → V _) (g : B → V _)
    → ((a : V _) → a ∈ set A f → a ∈ set B g)
    → ((a : V _) → a ∈ set B g → a ∈ set A f)
    → set A f ≡ set B g
  worker f g f<g g<f = ext f g
    (λ a → f<g (f a) (inc (a , refl)))
    (λ b → g<f (g b) (inc (b , refl)))

We have an assumption of so it suffices to show i.e. to find an such that Nothing stops us from taking

Presentations🔗

Above, we have referred to an inhabitant as a literal set. Using our eliminator into propositions, we can establish that every set is merely equal to one of the form In this section, we’ll show that every set is a literal set, without the propositional truncation, by defining a notion of presentation, and showing that each set has exactly one presentation.

Whereas any pair could be said to “present” a set — the literal —, we shall only say “presentation” when is an embedding into the universe of material sets. Note that any presentation has an underlying set which we call the type of members of the associated set. Put explicitly, a presentation for a set consists of the following data:

record Presentation {ℓ} (X : V ℓ) : Type (lsuc ℓ) where
  field
    members  : Type ℓ
    elem     : members → V ℓ
    embeds   : is-embedding elem

    presents : X ≡ set members elem

We start by showing that presentations are unique. It’ll suffice to do this for a presentation of a literal, material set Write and for the presentations. Since they both present the same set, by extensionality for material sets, we have equivalences Since and are embeddings, we can drop the truncations around their fibres.

  v' : set A f ⊆ set S h × set S h ⊆ set A f
  v' = Equiv.from (identity-system-gives-path V-identity-system) v

  u' : set A f ⊆ set T g × set T g ⊆ set A f
  u' = Equiv.from (identity-system-gives-path V-identity-system) u

  eqv : ∀ x → fibre g x ≃ fibre h x
  eqv x = prop-ext (gm x) (hm x)
    (λ fib → ∄-∄-proj (hm x) (v' .fst x (u' .snd x (inc fib))))
    (λ fib → ∄-∄-proj (gm x) (u' .fst x (v' .snd x (inc fib))))

This pointwise equivalence between fibres extends to an equivalence between types: Since every function induces an equivalence a fibrewise equivalence of functions induces an equivalence between their domains.

  T≃S : T ≃ S
  T≃S =
    T                 ≃⟹ Total-equiv g ⟩≃
    ÎŁ (V ℓ) (fibre g) ≃⟹ ÎŁ-ap-snd eqv ⟩≃
    ÎŁ (V ℓ) (fibre h) ≃⟹ Total-equiv h e⁻Âč ⟩≃
    S                 ≃∎

By construction, the equivalence between domains commutes with the functions we started with. Adjusting this for univalence, we get an identification between the types of members, and over this, an identification between the embeddings into Since the other two components are propositions, that is exactly what we needed to establish uniqueness of presentations.

  g≡h : PathP (λ i → ua T≃S i → V ℓ) g h
  g≡h = ua→ λ a → sym (Equiv.to (eqv _) (a , refl) .snd)

  open Presentation
  done : P1 ≡ P2
  done i .members = ua T≃S i
  done i .elem = g≡h i
  done i .embeds =
    is-prop→pathp (λ i → Π-is-hlevel 1 λ x → is-prop-is-prop {A = fibre (g≡h i) x}) gm hm i
  done i .presents = is-prop→pathp
    (λ i → V.squash (set A f) (set (ua T≃S i) (g≡h i))) u v i

We now construct a presentation for any given material set. We’re free to assume is a literal set. Factor through its image as

using image resizing to work around the following slight size issue: the traditional construction of images lives in the largest universe between the domain and codomain of the function. Since and the image of would live in which would preclude it from being the type of members of a set.

presentation : ∀ {ℓ} (X : V ℓ) → Presentation X
presentation {ℓ} =
  V-elim-prop' Presentation Presentation-is-prop λ f _ → present f
  where

Since is a set, by propositional resizing, its identity type can be made to live in the smallest universe, meaning we can construct the image of as an The rest of the construction is then straightforward: the type of members is the image of the embedding comes from the image factorisation.

The nontrivial part is showing the logical equivalence between mere fibres of and mere fibres of this follows from the map being a surjection.

  present : {A : Type ℓ} (f : A → V ℓ) → Presentation (set A f)
  present {A} f = done where
    module Im = Replacement (is-set→locally-small V.squash) f

    path : set A f ≡ set Im.Image Im.embed
    path = ext _ _ (λ a → inc (Im.inc a , refl)) λ b → do
      (f⁻Âčb , p) ← Im.inc-is-surjective b
      pure (f⁻Âčb , ap Im.embed p)

    done : Presentation (set A f)
    done .Presentation.members  = Im.Image
    done .Presentation.elem     = Im.embed
    done .Presentation.embeds   = Im.embed-is-embedding
    done .Presentation.presents = path

We wrap this data up in a convenient interface, the module of members of a material set. Other than unpacking the data of the presentation, we also make explicit the equivalence between membership in and fibres of presentation.

module Members {ℓ} (X : V ℓ) where
  open Presentation (presentation X) public

  memb : ∀ {x} → x ∈ X ≃ fibre elem x
  memb {x = x} = prop-ext (is-member _ X .is-tr) (embeds _)
    (λ a → ∄-∄-proj (embeds _) (subst (x ∈_) presents a))
    (λ a → subst (x ∈_) (sym presents) (inc a))

  module memb {x} = Equiv (memb {x})

  contains : ∀ {i} → elem i ∈ X
  contains = memb.from (_ , refl)

  contains' : ∀ {i x} → x ≡ elem i → x ∈ X
  contains' p = subst (_∈ X) (sym p) contains

Modelling IZF🔗

We now establish that the axioms of intuitionistic ZF hold in our model. These are twofold: first constructing a given set, then showing that this set satisfies its associated axiom.

Before that, let’s get the terminology in order: A material set is an inhabitant of if that was unclear. A class is a family of propositions on by propositional resizing, any class is equivalent to one in We may say that a class is a material set if we are given with Finally, we will denote the presentation of a material set by

Empty set🔗

The empty set is implemented by the empty type. No set is an empty of the empty type, since from the type one can project a value of

module _ {ℓ} where
  ∅V : V ℓ
  ∅V = set (Lift ℓ ⊄) (λ ())

  empty-set : (x : V ℓ) → x ∉ ∅V
  empty-set x = ∄-∄-rec (hlevel 1) (λ ())

Pairing🔗

The axiom of pairing says that, given material sets we can make a set whose elements are exactly and Its implementation is indexed by the type of booleans, mapping (arbitrarily) true to and false to

  pair : V ℓ → V ℓ → V ℓ
  pair a b = set (Lift ℓ Bool) λ (lift x) → if x then a else b

The proof that is essentially the implementation of binary coproducts in terms of arbitrary sum types.

  pairing : ∀ {a b x} → x ∈ pair a b ≃ ∄ (x ≡ a) ⊎ (x ≡ b) ∄
  pairing = prop-ext squash squash
    (∄-∄-rec squash λ where
      (lift true , p) → inc (inl (sym p))
      (lift false , p) → inc (inr (sym p)))
    (∄-∄-rec squash λ where
      (inl x) → inc (lift true , sym x)
      (inr x) → inc (lift false , sym x))

Union🔗

The union of a material set is the first construction in which we employ the presentation machinery. If is the set we want to union over, let be its embedding into The “branching factor” of our union is given by a pair where is a member of and is a member of element named by

  ⋃V : V ℓ → V ℓ
  ⋃V F =
    set (ÎŁ F.members λ a → Members.members (F.elem a))
      λ { (a , w) → Members.elem (F.elem a) w }
    where module F = Members F

We must show that iff is an element of an element of This is essentially reassociation modulo the equivalence

  union : ∀ {x F} → x ∈ ⋃V F ≃ ∃ (V ℓ) λ u → x ∈ u × u ∈ F
  union {x} {F} = prop-ext hlevel! squash
    (∄-∄-map λ { ((i , j) , p) →
        Members.elem F i
      , Members.contains' (Members.elem F i) (sym p)
      , Members.contains F
      })

Investigating a proof we find that it consists of a value a value and a proof The member becomes a material set the member a material set and the values pair into a fibre i.e. a proof that

Conversely, assume we’re given material sets and The first corresponds to a fibre from which we get an index and a proof The latter corresponds to a fibre which we can transport to a fibre i.e. an index and a proof

    (∄-∄-map λ { (u , x-u , u-F) →
      let
        s' : fibre _ x
        s' = subst (λ e → fibre (Members.elem e) x)
              (sym (Members.memb.to F u-F .snd))
              (Members.memb.to u x-u)
      in (Members.memb.to F u-F .fst , s' .fst) , s' .snd })

Infinity & the natural numbers🔗

Union is by far the most complicated construction, so let’s take a breather with something simpler: infinity. We begin by defining the binary union of material sets, the map and the successor operation

  _âˆȘV_ : V ℓ → V ℓ → V ℓ
  X âˆȘV Y = ⋃V (pair X Y)

  singleton : V ℓ → V ℓ
  singleton v = set (Lift ℓ ⊀) λ _ → v

  suc-V : V ℓ → V ℓ
  suc-V x = x âˆȘV singleton x

The material set of natural numbers is built recursively from the type of natural numbers, sending zero to the empty set, and the successor constructor to the successor set.

  ℕV : V ℓ
  ℕV = set (Lift ℓ Nat) λ x → go (Lift.lower x) where
    go : Nat → V ℓ
    go zero    = ∅V
    go (suc x) = suc-V (go x)

  zero∈ℕ : ∅V ∈ ℕV
  zero∈ℕ = inc (lift zero , refl)

We can immediately conclude that the material set of natural numbers contains the empty set and is closed under successor, for if we (merely) have w/ so

  suc∈ℕ : ∀ {X} → X ∈ ℕV → suc-V X ∈ ℕV
  suc∈ℕ = ∄-∄-map λ (lift i , x) → lift (suc i) , ap₂ _âˆȘV_ x (ap singleton x)

Slightly more involved (and, strictly speaking, not necessary), we can prove that the elements of are either zero or the successor of another element of While the axiom of infinity only requires the existence of a set containing and closed under successor, our construction immediately provides the smallest such set.

  ℕ-induction
    : ∀ x → x ∈ ℕV ≃ ∄ (x ≡ ∅V) ⊎ (∃ (V ℓ) λ y → y ∈ ℕV × (x ≡ suc-V y)) ∄
  ℕ-induction x = prop-ext squash squash
    (∄-∄-map λ where
      (lift zero , w)    → inl (sym w)
      (lift (suc n) , w) → inr (inc (_ , inc (lift n , refl) , sym w)))
    (λ x → x >>= λ where
      (inl w) → pure (lift zero , sym w)
      (inr w) → do
        (pred , ix , w) ← w
        (ix , x) ← ix
        pure (lift (suc (ix .Lift.lower)) , ap₂ _âˆȘV_ x (ap singleton x) ∙ sym w))

Replacement🔗

The replacement axiom is gnarly to state in the language of FOL, but when is an object in type theory, it takes the following form: Given a map and a material set the “image” is a pure set, with equivalent to

Let be the presentation of then is the desired set.

  V-image : (r : V ℓ → V ℓ) (x : V ℓ) → V ℓ
  V-image r x = set (Members.members x) λ i → r (Members.elem x i)

This is a straightforward computation.

  replacement
    : ∀ (r : V ℓ → V ℓ) x i
    → i ∈ V-image r x
    ≃ ∃ (V ℓ) λ z → z ∈ x × (i ≡ r z)
  replacement r x i = prop-ext squash squash
    (∄-∄-map λ { (i , p) → _ , Members.contains x , sym p })
    (∄-∄-map λ { (z , z∈x , i=rz) →
      Members.memb.to x z∈x .fst ,
      ap r (Members.memb.to x z∈x .snd) ∙ sym i=rz })

Separation🔗

In contrast to the predicative theory CZF, in IZF, we have full separation: given any predicate and material set we can form the set “”. This is because our ambient type theory has propositional resizing: every proposition, no matter the universe it lives in, is equivalent to a proposition in the smallest universe.

Write for the presentation of as usual. We define a set by taking with projection function

  subset : V ℓ → (V ℓ → Ω) → V ℓ
  subset a C = set
    (ÎŁ (Members.members a) λ i → ∣ C (Members.elem a i) ∣)
    (Members.elem a ∘ fst)

By computation, an element of consists of a fibre and a witness that holds of The former corresponds to a proof of and transporting the latter along a proof that holds of

  separation : ∀ a C (x : V ℓ) → (x ∈ subset a C) ≃ (x ∈ a × x ∈ C)
  separation a C x = prop-ext squash hlevel!
    (∄-∄-rec hlevel! λ { ((j , w) , p) →
      Members.contains' a (sym p) , subst (λ e → ∣ C e ∣) p w })
    (λ { (i∈a , Ci) → inc (
      ( Members.memb.to a i∈a .fst
      , subst (λ e → ∣ C e ∣) (sym (Members.memb.to a i∈a .snd)) Ci)
      , Members.memb.to a i∈a .snd)
      })

Power sets🔗

The axiom of power sets also relies on propositional resizing in the ambient type theory. Let be a material set with its presentation — I promise that’s the last time I’ll say this.

To every predicate we can associate the class given by

which we’ve already established is separable. The reason for this dance is that is much too large to use as the branching factor of a material set; but is just perfect. By promoting a predicate on to one on V$, we can appeal to separation in our construction of power set.

  predicate→class : ∀ {a} (p : Members.members a → Ω) → V ℓ → Ω
  predicate→class {a = a} p i =
    elΩ (ÎŁ (fibre (Members.elem a) i) λ f → f .fst ∈ p)

  subset-separation
    : ∀ {a} (p : Members.members a → Ω) x
    → x ∈ subset a (predicate→class p)
    ≃ (ÎŁ (fibre (Members.elem a) x) λ f → f .fst ∈ p)
  power : V ℓ → V ℓ
  power a = set (Members.members a → Ω) λ p → subset a (predicate→class p)

  power-set : ∀ a i → i ∈ power a ≃ (i ⊆ a)
  power-set a i = done where

This construction is up there with the union in terms of complexity. Let us tackle the simpler direction first: If we must prove that By definition, the assumption means that comes from separating a subset, and the axiom of separation guarantees that these are actually subsets.

    p1 : fibre (subset a ∘ predicate→class) i → i ⊆ a
    p1 (pred , p) =
      let
        worker : subset a (predicate→class pred) ⊆ a
        worker a∈sub wit = Equiv.to (separation _ (predicate→class pred) _) wit .fst
      in subst (_⊆ a) p worker

Now the opposite direction. It needs a bit more shuffling of data, but not a lot. Given we’ll prove that the predicate corresponds, as a pure subset of to By a consequence of separation, we have an equivalence

    p2 : i ⊆ a → ∄ fibre (subset a ∘ predicate→class) i ∄
    p2 i⊆a = inc (belongs , extensionality _ _ to fro) where
      belongs : Members.members a → Ω
      belongs m = elΩ (Members.elem a m ∈ i)

Given split it into By transporting this last proof along the middle path, we conclude

      to : subset a (predicate→class belongs) ⊆ i
      to e e∈sub = subst (_∈ i)
        (Equiv.to (subset-separation belongs e) e∈sub .fst .snd)
        (out! {pa = is-member _ i .is-tr}
          (Equiv.to (subset-separation belongs e) e∈sub .snd))

In the other direction, we’re given Since we can promote this to which corresponds to a fibre It remains to show but this is equal to by concluding the argument.

      fro : i ⊆ subset a (predicate→class belongs)
      fro e e∈i = Equiv.from (subset-separation belongs _)
        ( Members.memb.to a (i⊆a _ e∈i)
        , inc (subst (_∈ i) (sym (Members.memb.to a (i⊆a _ e∈i) .snd)) e∈i))

    done = prop-ext squash hlevel! (∄-∄-rec hlevel! p1) p2

Set induction🔗

The last thing we’ll prove about is the principle of an easy consequence of our eliminator from into props. If is a proposition that holds of a material set as soon as it holds for every then holds of any material set.

  ∈-induction
    : ∀ {ℓ'} (P : V ℓ → Prop ℓ')
    → ({a : V ℓ} → ({x : V ℓ} → x ∈ a → x ∈ P) → a ∈ P)
    → (x : V ℓ) → x ∈ P
  ∈-induction P ps = V-elim-prop (λ z → z ∈ P) (λ _ → P _ .is-tr) $ λ f i →
    ps λ {x} → ∄-∄-rec! λ (a , p) → subst (_∈ P) p (i a)