Skip to content

構成的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