構成的ZF集合論の解釈
module interpretation-of-czf where open import bottom-type open import natural-number open import sigma-type open import sum-type open import unit-type
構成的ZF集合論(CZF)を解釈する。
集合の型Vを定義する:
data V : Set₁ where sup : (A : Set) → (A → V) → V
carrier : V → Set carrier (sup A _) = A fun : (S : V) → carrier S → V fun (sup _ f) = f
集合間の等価性を帰納的に定義する。
_∼_ : V → V → Set sup A f ∼ sup B g = (∀ x → Σ[ y ∈ B ] (f x ∼ g y)) × (∀ y → Σ[ x ∈ A ] (f x ∼ g y))
これは同値関係である。
refl-∼ : ∀ S → S ∼ S refl-∼ (sup A f) .fst x = x , refl-∼ (f x) refl-∼ (sup A f) .snd y = y , refl-∼ (f y) sym-∼ : ∀ {S T} → S ∼ T → T ∼ S sym-∼ {S = sup A f} {T = sup B g} (e₁ , e₂) = H , I where H : ∀ x → Σ[ y ∈ A ] (g x ∼ f y) H x = e₂ x .fst , sym-∼ (e₂ x .snd) I : ∀ y → Σ[ x ∈ B ] (g x ∼ f y) I y = e₁ y .fst , sym-∼ (e₁ y .snd) trans-∼ : ∀ {S T U} → S ∼ T → T ∼ U → S ∼ U trans-∼ {S = sup A f} {sup B g} {sup C h} (e₁ , e₂) (d₁ , d₂) = H , I where H : ∀ x → Σ[ y ∈ C ] (f x ∼ h y) H x = d₁ (e₁ x .fst) .fst , (trans-∼ (e₁ x .snd) (d₁ _ .snd)) I : ∀ y → Σ[ x ∈ A ] (f x ∼ h y) I y = e₂ (d₂ y .fst) .fst , (trans-∼ (e₂ _ .snd) (d₂ y .snd))
_∈_ : V → V → Set S ∈ T = Σ[ y ∈ carrier T ] (S ∼ fun T y) _⊆_ : V → V → Set S ⊆ T = ∀ (x : carrier S) → fun S x ∈ T inclusion-mem : ∀ {x y : V} {S T} → S ⊆ T → ∀ x → x ∈ S → x ∈ T inclusion-mem {S = S} {T} S⊆T x (y , e) = k .fst , trans-∼ e (k .snd) where k : fun S y ∈ T k = S⊆T y mem-inclusion : ∀ {x y : V} {S T} → (∀ x → x ∈ S → x ∈ T) → S ⊆ T mem-inclusion {S = S} {T} p x = k .fst , k .snd where k : fun S x ∈ T k = p (fun S x) (x , refl-∼ _)
おそらく、「すべての量化が有界である」ような論理式は小さい型(Set型の項)として解釈できると思われる。
empty-set : V empty-set = sup ⊥ λ () empty-set-axiom : ∀ x → x ∈ empty-set → ⊥ empty-set-axiom _ (y , _) = y bin-union : V → V → V bin-union S T = sup (carrier S + carrier T) λ where (inl x) → fun S x (inr y) → fun T y union : V → V union S = sup (Σ[ i ∈ carrier S ] carrier (fun S i)) λ where (i , x) → fun (fun S i) x union→ : ∀ {x S} → x ∈ union S → Σ[ T ∈ carrier S ] (x ∈ fun S T) union→ ((i , x) , e) = i , (x , e) union← : ∀ {x S} → Σ[ T ∈ carrier S ] (x ∈ fun S T) → x ∈ union S union← (i , (x , e)) = (i , x) , e singleton : V → V singleton S = sup Unit (λ _ → S) pair : V → V → V pair S T = sup (Unit + Unit) λ where (inl _) → S (inr _) → T successor : V → V successor S = bin-union S (singleton S) N : V N = sup ℕ f where f : ℕ → V f zero = empty-set f (suc n) = successor (f n)
以下のrestricted-separationではV → Set₁ではなくV → Setを使っていることが重要である。
restricted-separation : V → (V → Set) → V restricted-separation S P = sup (Σ[ x ∈ carrier S ] (P (fun S x))) λ where (x , _) → fun S x