Tom de Jong, 31 May 2024.
(Following a suggestion by Martín Escardó.)

We consider the large ordinal of small ordinals as a locally small algebraic
dcpo which does not have a small basis (even impredicatively).


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

open import MLTT.Spartan

open import UF.PropTrunc
open import UF.Size
open import UF.Univalence

module DomainTheory.Examples.Ordinals
        (pt : propositional-truncations-exist)
        (ua : Univalence)
        (sr : Set-Replacement pt)
        (𝓤 : Universe)

open PropositionalTruncation pt

open import MLTT.List

open import UF.Base
open import UF.FunExt
open import UF.Subsingletons
open import UF.UA-FunExt

 fe' : FunExt
 fe' = Univalence-gives-FunExt ua

 fe : Fun-Ext
 fe {𝓤} {𝓥} = fe' 𝓤 𝓥

 pe' : PropExt
 pe' = Univalence-gives-PropExt ua

 pe : Prop-Ext
 pe {𝓤} = pe' 𝓤

open import DomainTheory.Basics.Dcpo pt fe 𝓤 hiding (⟨_⟩)
open import DomainTheory.Basics.SupComplete pt fe 𝓤
open import DomainTheory.Basics.WayBelow pt fe 𝓤
open import DomainTheory.BasesAndContinuity.Bases pt fe 𝓤
open import DomainTheory.BasesAndContinuity.Continuity pt fe 𝓤

open import Ordinals.Arithmetic fe'
open import Ordinals.ArithmeticProperties ua
open import Ordinals.OrdinalOfOrdinals ua
open import Ordinals.OrdinalOfOrdinalsSuprema ua
open import Ordinals.Type
open import Ordinals.Underlying

open suprema pt sr


The ordinals in a given universe 𝓤 form a dcpo whose carrier lives in the
successor universe 𝓤 ⁺. The ordinal relation lives in 𝓤, and so the dcpo of
ordinals is large, but locally small. It has suprema for all families of
ordinals indexed by types in 𝓤.


Ordinals-DCPO : DCPO {𝓤 } {𝓤}
Ordinals-DCPO = Ordinal 𝓤 , _⊴_ ,
                (underlying-type-is-set fe' (OO 𝓤) ,
                 ⊴-is-prop-valued , (⊴-refl , ⊴-trans , ⊴-antisym)) ,
                 I α δ  (sup α) , sup-is-least-upper-bound α)

Ordinals-DCPO-is-sup-complete : is-sup-complete Ordinals-DCPO
Ordinals-DCPO-is-sup-complete =
  {  = sup ;
    ⋁-is-sup = sup-is-least-upper-bound

open sup-complete-dcpo Ordinals-DCPO Ordinals-DCPO-is-sup-complete


The dcpo of ordinals is algebraic. This follows from three facts:
(1) Every ordinal α is equal to the supremum of the successors of its initial
    segments, i.e. α = sup (λ a → (α ↓ a) +ₒ 𝟙ₒ)
(2) Every successor ordinal, i.e. every ordinal of the form β +ₒ 𝟙ₒ is compact.
(3) The family in (1) can be "directified" by taking finite joins which
    preserves compactness.


successor-ordinals-are-compact : (α : Ordinal 𝓤)
                                is-compact Ordinals-DCPO (α +ₒ 𝟙ₒ)
successor-ordinals-are-compact α I β δ l =
 ∥∥-functor  (i , b , eq₂)  ⦅3⦆ (i , b , (eq₁  eq₂))) ⦅2⦆
   ⦅1⦆ : Σ s   sup β  , α  sup β  s
   ⦅1⦆ = ⊴-gives-≼ (α +ₒ 𝟙ₒ) (sup β) l α (successor-increasing α)
   s :  sup β 
   s = pr₁ ⦅1⦆
   eq₁ : α  sup β  s
   eq₁ = pr₂ ⦅1⦆
   ⦅2⦆ :  Σ i  I , Σ b   β i  , sup β  s  β i  b 
   ⦅2⦆ = initial-segment-of-sup-is-initial-segment-of-some-component β s
   ⦅3⦆ : (Σ i  I , Σ b   β i  , α  β i  b)
        Σ i  I , (α +ₒ 𝟙ₒ)  β i
   ⦅3⦆ (i , b , refl) = i , upper-bound-of-successors-of-initial-segments (β i) b

 module _ (α : Ordinal 𝓤) where
  family :  α   Ordinal 𝓤
  family a = (α  a) +ₒ 𝟙ₒ

Ordinals-DCPO-is-algebraic' : structurally-algebraic Ordinals-DCPO
Ordinals-DCPO-is-algebraic' =
  { index-of-compact-family = λ α  List  α 
  ; compact-family = λ α  directify (family α)
  ; compact-family-is-directed = λ α  directify-is-directed (family α)
  ; compact-family-is-compact = λ α  directify-is-compact
                                       (family α)
                                        a  successor-ordinals-are-compact (α  a))
  ; compact-family-∐-= = eq
    eq : (α : Ordinal 𝓤)
         Ordinals-DCPO (directify-is-directed (family α))  α
    eq α =  Ordinals-DCPO (directify-is-directed (family α)) =⟨ I 
           sup (family α)                                     =⟨ II 
      II = (supremum-of-successors-of-initial-segments pt sr α) ⁻¹
      I = sups-are-unique _⊴_
           (poset-axioms-of-dcpo Ordinals-DCPO) (family α)
           (directify-sup' (family α)
             ( Ordinals-DCPO δ) (∐-is-sup Ordinals-DCPO δ))
           (sup-is-least-upper-bound (family α))
        δ : is-Directed Ordinals-DCPO (directify (family α))
        δ = directify-is-directed (family α)

Ordinals-DCPO-is-algebraic : is-algebraic-dcpo Ordinals-DCPO
Ordinals-DCPO-is-algebraic =  Ordinals-DCPO-is-algebraic' 


Unlike many other examples, such as the dpcos in the Scott model of PCF, or
Scott's D∞, the dpco of ordinals, while algebraic, does not have a small
(compact) basis. If it did, we could take the join of all the basis elements to
obtain a greatest ordinal, which does not exist.


Ordinals-DCPO-has-no-small-basis : ¬ (has-unspecified-small-basis Ordinals-DCPO)
Ordinals-DCPO-has-no-small-basis h =

Ordinals-DCPO-has-no-small-compact-basis :
 ¬ (has-unspecified-small-compact-basis Ordinals-DCPO)
Ordinals-DCPO-has-no-small-compact-basis h =
  (∥∥-functor  (B , β , scb)  B , β , compact-basis-is-basis _ β scb) h)