--- author: - Bruno Paiva - Ayberk Tosun date-started: 2025-02-03 --- \begin{code} {-# OPTIONS --safe #-} open import UF.FunExt module EffectfulForcing.Internal.PaperIndex (fe : Fun-Ext) where open import EffectfulForcing.Internal.Correctness renaming (⌜dialogue⌝ to dialogueᵀ) open import EffectfulForcing.Internal.ExtensionalEquality open import EffectfulForcing.Internal.External renaming (B【_】 to 【_】𝒟; B⟦_⟧ to ⟦_⟧𝒟) hiding (main-lemma) open import EffectfulForcing.Internal.Internal renaming (B-type〖_〗 to 〖_〗𝒟ᵀ; B-context【_】 to 【_】𝒟ᵀ; ⌜_⌝ to ⟦_⟧𝒟ᵀ; ⌜dialogue-tree⌝ to dialogue-treeᵀ; ⌜Kleisli-extension⌝ to Kleisli-extensionᵀ; ⌜η⌝ to ηᵀ; ⌜β⌝ to βᵀ; ⌜kleisli-extension⌝ to kleisli-extensionᵀ; ⌜B-functor⌝ to 𝒟-functorᵀ; ⌜generic⌝ to genericᵀ) open import EffectfulForcing.Internal.InternalModCont fe hiding (baire) open import EffectfulForcing.Internal.InternalModUniCont fe renaming (main-lemma to main-lemmaᵤ) open import EffectfulForcing.Internal.Subst open import EffectfulForcing.Internal.SystemT open import EffectfulForcing.MFPSAndVariations.Church open import EffectfulForcing.MFPSAndVariations.ContinuityProperties fe open import EffectfulForcing.MFPSAndVariations.Continuity using (is-uniformly-continuous; BT; _=⟪_⟫_; _=⟦_⟧_; embedding-C-B; embedding-𝟚-ℕ; Cantor; Baire) renaming (is-continuous to is-continuous∙) open import EffectfulForcing.MFPSAndVariations.Dialogue renaming (D to Dial; B-functor to 𝒟-functor) hiding (decode) open import EffectfulForcing.MFPSAndVariations.SystemT using (type;〖_〗; ι; _⇒_) open import EffectfulForcing.MFPSAndVariations.LambdaCalculusVersionOfMFPS renaming (B〖_〗 to 〖_〗𝒟) using (Kleisli-extension) open import MLTT.Sigma open import MLTT.Spartan \end{code} \section{(2) A System T Primer} We define some aliases below to ensure consistency with the notation in the paper. This also serves as a dictionary for looking up the notation used in the formalization. \begin{code} Termᵀ : Cxt → type → 𝓤₀ ̇ Termᵀ Γ σ = T Γ σ Termᵀ₀ : type → 𝓤₀ ̇ Termᵀ₀ σ = T₀ σ Typeᵀ : 𝓤₀ ̇ Typeᵀ = type Ctxᵀ : 𝓤₀ ̇ Ctxᵀ = Cxt Definition-1 : 𝓤₀ ̇ Definition-1 = Σ Γ ꞉ Ctxᵀ , Σ σ ꞉ Typeᵀ , Termᵀ Γ σ Definition-2a : Typeᵀ → 𝓤₀ ̇ Definition-2a = 〖_〗 Definition-2b : Ctxᵀ → 𝓤₀ ̇ Definition-2b = 【_】 Definition-2c : {Γ : Ctxᵀ} {σ : Typeᵀ} → Termᵀ Γ σ → (【 Γ 】 → 〖 σ 〗) Definition-2c = ⟦_⟧ Definition-3 : {Γ : Ctxᵀ} → ℕ → Termᵀ Γ ι Definition-3 = numeral Proposition-4 : {Γ : Ctxᵀ} (γ : 【 Γ 】) (n : ℕ) → n = ⟦ numeral n ⟧ γ Proposition-4 γ n = ⟦numeral⟧ γ n ⁻¹ \end{code} \section{(3) Oracless Effectful Forcing} \begin{code} Definition-5 : (I : 𝓤 ̇) → (O : 𝓥 ̇) → (X : 𝓦 ̇) → 𝓤 ⊔ 𝓥 ⊔ 𝓦 ̇ Definition-5 = Dial 𝒟 : 𝓤₀ ̇ → 𝓤₀ ̇ 𝒟 X = Dial ℕ ℕ X Definition-6 : {I : 𝓤 ̇} {O : 𝓥 ̇} {X : 𝓦 ̇} → Dial I O X → (I → O) → X Definition-6 = dialogue Definition-7a : {I : 𝓤 ̇} {O : 𝓥 ̇} {X : 𝓦 ̇} → ((I → O) → X) → 𝓤 ⊔ 𝓥 ⊔ 𝓦 ̇ Definition-7a {𝓤} {𝓥} {𝓦} {I} {O} {X} f = Σ d ꞉ Dial I O X , ((α : I → O) → f α = dialogue d α) Definition-7b : {O : 𝓥 ̇} {X : 𝓦 ̇} → ((ℕ → O) → X) → 𝓥 ⊔ 𝓦 ̇ Definition-7b = is-continuous₁ Definition-7c : {O : 𝓥 ̇} {X : 𝓦 ̇} → ((ℕ → O) → X) → 𝓥 ⊔ 𝓦 ̇ Definition-7c = is-uniformly-continuous₁ \end{code} \begin{code} Definition-9 : {X Y : 𝓤₀ ̇} → (X → 𝒟 Y) → 𝒟 X → 𝒟 Y Definition-9 = kleisli-extension Definition-10 : {X Y : 𝓤₀ ̇} → (X → Y) → 𝒟 X → 𝒟 Y Definition-10 = 𝒟-functor Definition-11 : {X : 𝓤₀ ̇} {σ : Typeᵀ} → (X → 〖 σ 〗𝒟) → 𝒟 X → 〖 σ 〗𝒟 Definition-11 = Kleisli-extension \end{code} Dialogue interpretation of types, contexts, and terms of System T are given in, respectively, `Definition-12a`, `Definition-12b`, and `Definition-12c` below. \begin{code} Definition-12a : Typeᵀ → 𝓤₀ ̇ Definition-12a = 〖_〗𝒟 Definition-12b : Ctxᵀ → 𝓤₀ ̇ Definition-12b = 【_】𝒟 Definition-12c : {Γ : Ctxᵀ} {σ : Typeᵀ} → Termᵀ Γ σ → (【 Γ 】𝒟 → 〖 σ 〗𝒟) Definition-12c = ⟦_⟧𝒟 Definition-13 : 𝒟 ℕ → 𝒟 ℕ Definition-13 = generic Definition-14 : Termᵀ₀ ((ι ⇒ ι) ⇒ ι) → 𝒟 ℕ Definition-14 = dialogue-tree Definition-15 : (σ : Typeᵀ) → (ℕ → ℕ) → 〖 σ 〗 → 〖 σ 〗𝒟 → Type Definition-15 σ = R {σ} Theorem-16 : (α : ℕ → ℕ) (t : Termᵀ₀ ((ι ⇒ ι) ⇒ ι)) → ⟦ t ⟧₀ α = dialogue (dialogue-tree t) α Theorem-16 α t = dialogue-tree-correct t α \end{code} \section{(4) Dialogue Trees in System T} \subsection{(4.1) Church-Encoded Trees in System T} \begin{code} 𝒟ᵀ : Typeᵀ → Typeᵀ → Typeᵀ 𝒟ᵀ A σ = ⌜B⌝ σ A _ : (A : Typeᵀ) (σ : Typeᵀ) → 𝒟ᵀ A σ = ((σ ⇒ A) ⇒ (((ι ⇒ A) ⇒ ι ⇒ A) ⇒ A)) _ = λ A σ → refl {𝓤₀} {Typeᵀ} {((σ ⇒ A) ⇒ (((ι ⇒ A) ⇒ ι ⇒ A) ⇒ A))} Definition-17a : Typeᵀ → Typeᵀ → Typeᵀ Definition-17a A = 𝒟ᵀ A Definition-17b : (A : Typeᵀ) (σ : Typeᵀ) → Termᵀ₀ (σ ⇒ 𝒟ᵀ A σ) Definition-17b A σ = ηᵀ Definition-17c : (A : Typeᵀ) (σ : Typeᵀ) → Termᵀ₀ ((ι ⇒ 𝒟ᵀ A σ) ⇒ ι ⇒ 𝒟ᵀ A σ) Definition-17c A σ = βᵀ \end{code} The internal Kleisli extension. \begin{code} Definition-18 : (A : Typeᵀ) → Termᵀ₀ ((ι ⇒ 𝒟ᵀ A ι) ⇒ 𝒟ᵀ A ι ⇒ 𝒟ᵀ A ι) Definition-18 A = kleisli-extensionᵀ \end{code} The internal functor action. \begin{code} Definition-19 : (A : Typeᵀ) → Termᵀ₀ ((ι ⇒ ι) ⇒ 𝒟ᵀ A ι ⇒ 𝒟ᵀ A ι) Definition-19 A = 𝒟-functorᵀ \end{code} The generalised internal Kleisli extension. \begin{code} Definition-20 : (A : Typeᵀ) (σ : Typeᵀ) → Termᵀ₀ ((ι ⇒ 〖 σ 〗𝒟ᵀ A) ⇒ 𝒟ᵀ A ι ⇒ 〖 σ 〗𝒟ᵀ A) Definition-20 σ A = Kleisli-extensionᵀ \end{code} The internal dialogue translation. \begin{code} Definition-21a : Typeᵀ → Typeᵀ → Typeᵀ Definition-21a A σ = 〖 σ 〗𝒟ᵀ A Definition-21b : Typeᵀ → Ctxᵀ → Ctxᵀ Definition-21b A Γ = 【 Γ 】𝒟ᵀ A Definition-21c : (A : Typeᵀ) → (Γ : Ctxᵀ) → (σ : Typeᵀ) → Termᵀ Γ σ → Termᵀ (【 Γ 】𝒟ᵀ A) (〖 σ 〗𝒟ᵀ A) Definition-21c A Γ σ = ⟦_⟧𝒟ᵀ \end{code} The internal generic sequence. \begin{code} Definition-22 : (A : Typeᵀ) → Termᵀ₀ (𝒟ᵀ A ι ⇒ 𝒟ᵀ A ι) Definition-22 A = genericᵀ \end{code} The internal dialogue tree operator. \begin{code} Definition-23 : (A : Typeᵀ) → Termᵀ₀ ((ι ⇒ ι) ⇒ ι) → Termᵀ₀ (𝒟ᵀ A ι) Definition-23 A = dialogue-treeᵀ \end{code} \subsection{(4.2) Avoiding Function Extensionality} Hereditary extensional equality. \begin{code} Definition-24 : (σ : Typeᵀ) → 〖 σ 〗 → 〖 σ 〗 → 𝓤₀ ̇ Definition-24 σ = _≡_ {σ} \end{code} Some properties of hereditary extensionality equality \begin{code} Lemma-25a : {σ : Typeᵀ} {a b c : 〖 σ 〗} → a ≡ b → b ≡ a Lemma-25a = ≡-symm Lemma-25b : {σ : Typeᵀ} {a b c : 〖 σ 〗} → a ≡ b → b ≡ c → a ≡ c Lemma-25b = ≡-trans data is-type-one : Typeᵀ → 𝓤₀ ̇ where ι-is-type-one : is-type-one ι ⇒-is-type-one : {σ : Typeᵀ} → is-type-one σ → is-type-one (ι ⇒ σ) Lemma-25c : {σ : Typeᵀ} → is-type-one σ → (a : 〖 σ 〗) → a ≡ a Lemma-25c ι-is-type-one n = refl Lemma-25c (⇒-is-type-one h) f {x} {y} e = transport (λ z → f x ≡ z) (ap f e) (Lemma-25c h (f x)) Lemma-26 : {σ : Typeᵀ} → (t : T₀ σ) → ⟦ t ⟧₀ ≡ ⟦ t ⟧₀ Lemma-26 = ≡-refl₀ \end{code} \subsection{(4.3) Correctness of the Syntactic Translation} The encode function, which is called `church-encode` here. \begin{code} Definition-27 : (A : Typeᵀ) → 𝒟 ℕ → 〖 𝒟ᵀ A ι 〗 Definition-27 A = church-encode \end{code} The dialogue correctness logical relation. \begin{code} Definition-28 : (σ : Typeᵀ) → 〖 σ 〗𝒟 → ({A : Typeᵀ} → Termᵀ₀ (〖 σ 〗𝒟ᵀ A)) → 𝓤₀ ̇ Definition-28 σ = Rnorm Lemma-29 : (σ : Typeᵀ) (t s : {A : Typeᵀ} → Termᵀ₀ (〖 σ 〗𝒟ᵀ A)) (x : 〖 σ 〗𝒟) → ({A : Typeᵀ} → ⟦ t ⟧₀ ≡[ (〖 σ 〗𝒟ᵀ A) ] ⟦ s ⟧₀) → Rnorm x t → Rnorm x s Lemma-29 σ t s x = Rnorm-respects-≡ Lemma-30 : (A : Typeᵀ) (d : 𝒟 ℕ) (f₁ : ℕ → 𝒟 ℕ) (f₂ : ℕ → 〖 𝒟ᵀ A ι 〗) → ((i : ℕ) → church-encode (f₁ i) ≡[ 𝒟ᵀ A ι ] f₂ i) → church-encode (kleisli-extension f₁ d) ≡[ 𝒟ᵀ A ι ] ⟦ kleisli-extensionᵀ ⟧₀ f₂ (church-encode d) Lemma-30 A = church-encode-kleisli-extension Corollary-31 : (A : Typeᵀ) (d : 𝒟 ℕ) (f₁ f₂ : ℕ → ℕ) → f₁ ≡ f₂ → church-encode (𝒟-functor f₁ d) ≡[ 𝒟ᵀ A ι ] ⟦ 𝒟-functorᵀ ⟧₀ f₂ (church-encode d) Corollary-31 A d f₁ f₂ h = ≡-symm {𝒟ᵀ A ι} (church-encode-is-natural d (≡-symm {ι ⇒ ι} h)) Lemma-32 : {σ : Typeᵀ} (f : ℕ → 〖 σ 〗𝒟) (n : 𝒟 ℕ) (g : {A : Typeᵀ} → Termᵀ₀ (ι ⇒ (〖 σ 〗𝒟ᵀ A))) (m : {A : Typeᵀ} → T₀ (𝒟ᵀ A ι)) → ((x : ℕ) → Rnorm (f x) (g · numeral x)) → Rnorm n m → Rnorm (Kleisli-extension f n) (Kleisli-extensionᵀ · g · m) Lemma-32 f n g m h i = Rnorm-kleisli-lemma f g h n m i Lemma-33 : {Γ : Ctxᵀ} {σ : Typeᵀ} (γ₁ : 【 Γ 】𝒟) (γ₂ : {A : Typeᵀ} → Sub₀ (【 Γ 】𝒟ᵀ A)) (t : Termᵀ Γ σ) → Rnorms γ₁ γ₂ → Rnorm (⟦ t ⟧𝒟 γ₁) (close ⟦ t ⟧𝒟ᵀ γ₂) Lemma-33 = Rnorm-lemma Lemma-34 : (A : Typeᵀ) (t : Termᵀ₀ ((ι ⇒ ι) ⇒ ι)) → ⟦ dialogue-treeᵀ t ⟧₀ ≡[ 𝒟ᵀ A ι ] church-encode (dialogue-tree t) Lemma-34 A t = dialogue-tree-agreement t {A} \end{code} The internal dialogue operator. \begin{code} Definition-35 : Termᵀ₀ ((𝒟ᵀ ((ι ⇒ ι) ⇒ ι) ι) ⇒ (ι ⇒ ι) ⇒ ι) Definition-35 = dialogueᵀ Lemma-36 : (d : 𝒟 ℕ) (α : ℕ → ℕ) → dialogue d α = ⟦ dialogueᵀ ⟧₀ (church-encode d) α Lemma-36 d α = dialogues-agreement d α \end{code} Correctness of `dialogue-treeᵀ`. \begin{code} Theorem-37 : (t : T₀ ((ι ⇒ ι) ⇒ ι)) (α : ℕ → ℕ) → ⟦ t ⟧₀ α = dialogue (dialogue-tree t) α Theorem-37 = dialogue-tree-correct \end{code} \section{(5) Computing moduli of continuity internally} Max question along a path. \begin{code} max-q = max-question Definition-38 : 𝒟 ℕ → (ℕ → ℕ) → ℕ Definition-38 = max-q \end{code} Internal max question along a path. \begin{code} max-qᵀ = max-questionᵀ Definition-39 : Termᵀ₀ (𝒟ᵀ ι ι ⇒ (ι ⇒ ι) ⇒ ι) Definition-39 = max-qᵀ \end{code} External and internal modulus operators. \begin{code} church-encode-≡ : {A : Typeᵀ} (d : 𝒟 ℕ) → church-encode d ≡[ 𝒟ᵀ A ι ] church-encode d church-encode-≡ {A} (η n) η≡ β≡ = η≡ refl church-encode-≡ {A} (β ϕ i) {η₁} {η₂} η≡ {β₁} {β₂} β≡ = β≡ aux refl where aux : {i j : ℕ} → i = j → church-encode (ϕ i) η₁ β₁ ≡[ A ] church-encode (ϕ j) η₂ β₂ aux {i} {i} refl = church-encode-≡ (ϕ i) η≡ β≡ Lemma-40 : (d : 𝒟 ℕ) (α : ℕ → ℕ) → max-q d α = ⟦ max-qᵀ ⟧₀ (church-encode d) α Lemma-40 d α = max-question⋆-agreement d α ∙ (max-questionᵀ-agreement-with-max-question⋆ (church-encode-≡ d) (Lemma-25c (⇒-is-type-one ι-is-type-one) α)) ⁻¹ Definition-41a : 𝒟 ℕ → (ℕ → ℕ) → ℕ Definition-41a = modulus Definition-41b : Termᵀ₀ (𝒟ᵀ ι ι ⇒ (ι ⇒ ι) ⇒ ι) Definition-41b = modulusᵀ Definition-42 : ((ℕ → ℕ) → ℕ) → (ℕ → ℕ) → ℕ → 𝓤₀ ̇ Definition-42 f α m = m is-a-modulus-of-continuity-for f at α Lemma-44 : (t : Termᵀ₀ ((ι ⇒ ι) ⇒ ι)) (α : ℕ → ℕ) → ⟦ max-qᵀ · dialogue-treeᵀ t ⟧₀ α = max-question (dialogue-tree t) α Lemma-44 t α = ⟦ max-qᵀ · dialogue-treeᵀ t ⟧₀ α =⟨ Ⅰ ⟩ max-question₀ (dialogue-tree t) α =⟨ Ⅱ ⟩ max-question (dialogue-tree t) α ∎ where Ⅰ = main-lemma t α Ⅱ = max-question₀-agreement (dialogue-tree t) α ⁻¹ Theorem-45 : (t : Termᵀ₀ ((ι ⇒ ι) ⇒ ι)) (α : ℕ → ℕ) → ⟦ modulusᵀ · (dialogue-treeᵀ t) ⟧₀ α is-a-modulus-of-continuity-for ⟦ t ⟧₀ at α Theorem-45 = internal-mod-cont-correct₀ \end{code} \section{(6) Extending it to uniform continuity} \begin{code} Definition-46 : Cantor → Baire Definition-46 = embedding-C-B Definition-47 : 𝒟 ℕ → Dial ℕ 𝟚 ℕ Definition-47 = prune max-q₂ = max-boolean-question max-q₂ᵀ = max-boolean-questionᵀ Definition-48 : Dial ℕ 𝟚 ℕ → ℕ Definition-48 = max-boolean-question Definition-49 : Termᵀ₀ (𝒟ᵀ ι ι ⇒ ι) Definition-49 = max-q₂ᵀ Lemma-50 : (d : 𝒟 ℕ) → max-q₂ (prune d) = ⟦ max-q₂ᵀ ⟧₀ (church-encode d) Lemma-50 d = max-q₂ (prune d) =⟨ Ⅰ ⟩ max-boolean-question⋆ (church-encode d) =⟨ Ⅱ ⟩ ⟦ max-q₂ᵀ ⟧₀ (church-encode d) ∎ where Ⅰ = max-boolean-question⋆-agreement d Ⅱ = max-boolean-questionᵀ-agreement (church-encode-≡ d) ⁻¹ \end{code} The external and internal modulus of uniform continuity operators. \begin{code} Definition-51a : Dial ℕ 𝟚 ℕ → ℕ Definition-51a = modulusᵤ Definition-51b : Termᵀ₀ ((ι ⇒ ι) ⇒ ι) → Termᵀ₀ ι Definition-51b = modulusᵤᵀ {〈〉} \end{code} The definition of the notion of modulus of uniform continuity. \begin{code} Definition-52 : ℕ → ((ℕ → 𝟚) → ℕ) → 𝓤₀ ̇ Definition-52 = _is-a-modulus-of-uniform-continuity-for_ \end{code} It is easy to prove Lemma 53 from the paper in Agda. However, we are not deriving Theorem 55 from it in the formalization. \begin{code} Lemma-53 : (d : Dial ℕ ℕ ℕ) → modulusᵤ (prune d) is-a-modulus-of-uniform-continuity-for (dialogue (prune d)) Lemma-53 d = transport (λ - → - is-a-modulus-of-uniform-continuity-for dialogue (prune d)) (p ⁻¹) φ where c : is-uniformly-continuous (dialogue (prune d)) c = eloquent-functions-are-UC (dialogue (prune d)) ((prune d) , λ _ → refl) bt : BT ℕ bt = pr₁ c m : ℕ m = succ (maximumᵤ bt) p : modulusᵤ (prune d) = m p = succ (max-boolean-question (prune d)) =⟨ I ⟩ succ (maximumᵤ bt) ∎ where I = ap succ (max-boolean-question-is-maximum-mod-of d) φ : m is-a-modulus-of-uniform-continuity-for dialogue (prune d) φ α α′ r = pr₂ c α α′ γ where ρ : α =⦅ succ (maximum (sequentialize bt)) ⦆ α′ ρ = transport (λ - → α =⦅ - ⦆ α′) (ap succ (maximumᵤ′-equivalent-to-maximumᵤ bt)) r ξ : α =⟪ sequentialize bt ⟫ α′ ξ = =⦅⦆-implies-=⟪⟫ α α′ (sequentialize bt) ρ ζ : α =⟪ sequentialize bt ⟫₀ α′ ζ = =⟪⟫-implies-=⟪⟫₀ α α′ (sequentialize bt) ξ γ : α =⟦ bt ⟧ α′ γ = =⟪⟫₀-implies-=⟦⟧ α α′ bt ζ Lemma-54 : (t : Termᵀ₀ ((ι ⇒ ι) ⇒ ι)) → ⟦ max-q₂ᵀ · (dialogue-treeᵀ t) ⟧₀ = max-q₂ (prune (dialogue-tree t)) Lemma-54 t = main-lemmaᵤ t Theorem-55 : (t : Termᵀ₀ (baire ⇒ ι)) → ⟦ modulusᵤᵀ t ⟧₀ is-a-modulus-of-uniform-continuity-for (⟦ t ⟧₀ ∘ embedding-C-B) Theorem-55 t α α′ p = internal-uni-mod-correct₀ t (embedding-C-B α) (embedding-C-B α′) q r † where q : is-boolean-point (embedding-C-B α) q = to-baire-gives-boolean-point α r : is-boolean-point (embedding-C-B α′) r = to-baire-gives-boolean-point α′ † : embedding-C-B α =⦅ ⟦ modulusᵤᵀ t ⟧₀ ⦆ embedding-C-B α′ † = =⦅⦆-ap ⟦ modulusᵤᵀ t ⟧₀ embedding-𝟚-ℕ α α′ p \end{code}