# HG changeset patch # User Shinji KONO # Date 1595309667 -32400 # Node ID d2cb5278e46d9ea615e7604b4dfda8167fa52fc6 # Parent 0a116938a564c0ebe8042a9fcc7873765fd7356c ... diff -r 0a116938a564 -r d2cb5278e46d OD.agda --- a/OD.agda Tue Jul 21 02:39:09 2020 +0900 +++ b/OD.agda Tue Jul 21 14:34:27 2020 +0900 @@ -76,7 +76,7 @@ -- -- ==→o≡ is necessary to prove axiom of extensionality. -data One : Set n where +data One {n : Level } : Set n where OneObj : One -- Ordinals in OD , the maximum diff -r 0a116938a564 -r d2cb5278e46d filter.agda --- a/filter.agda Tue Jul 21 02:39:09 2020 +0900 +++ b/filter.agda Tue Jul 21 14:34:27 2020 +0900 @@ -184,11 +184,11 @@ -- -- -data Two : Set n where +data Two : Set where i0 : Two i1 : Two -data Three : Set n where +data Three : Set where j0 : Three j1 : Three j2 : Three @@ -198,7 +198,7 @@ import OPair open OPair O -record PFunc : Set (suc n) where +record PFunc {n : Level} : Set (suc n) where field dom : Nat → Set n map : (x : Nat ) → dom x → Two @@ -206,53 +206,279 @@ open PFunc -data Findp : List Three → (x : Nat) → Set n where +data Findp : List Three → (x : Nat) → Set where v0 : {n : List Three} → Findp ( j0 ∷ n ) Zero v1 : {n : List Three} → Findp ( j1 ∷ n ) Zero vn : {n : List Three} {d : Three} → {x : Nat} → Findp n x → Findp (d ∷ n) (Suc x) -FPFunc→PFunc : List Three → PFunc -FPFunc→PFunc fp = record { dom = λ x → findp fp x ; map = λ x p → find fp x p ; meq = λ {x} {p} {q} → feq fp } where - findp : List Three → (x : Nat) → Set n - findp n x = Findp n x - find : (n : List Three ) → (x : Nat) → Findp n x → Two - find (j0 ∷ _) 0 v0 = i0 - find (j1 ∷ _) 0 v1 = i1 - find (d ∷ n) (Suc x) (vn {n} {d} {x} p) = find n x p - lemma : (h : Three) → (n : List Three) → {x : Nat} {p : Findp n x } → find n x p ≡ find (h ∷ n) (Suc x) (vn p) - lemma j0 n {x} {p} = refl - lemma j1 n {x} {p} = refl - lemma j2 n {x} {p} = refl - feq : (n : List Three) → {x : Nat} {p q : Findp n x } → find n x p ≡ find n x q - feq n {0} {v0} {v0} = refl - feq n {0} {v1} {v1} = refl - feq [] {Suc x} {()} - feq (h ∷ n) {Suc x} {vn p} {vn q} = subst₂ (λ j k → j ≡ k ) (lemma h n) (lemma h n) (feq n {x} {p} {q}) +findp : List Three → (x : Nat) → Set +findp n x = Findp n x + +find : (n : List Three ) → (x : Nat) → Findp n x → Two +find (j0 ∷ _) 0 v0 = i0 +find (j1 ∷ _) 0 v1 = i1 +find (d ∷ n) (Suc x) (vn {n} {d} {x} p) = find n x p + +Findp=n : (h : Three) → (n : List Three) → {x : Nat} {p : Findp n x } → find n x p ≡ find (h ∷ n) (Suc x) (vn p) +Findp=n j0 n {x} {p} = refl +Findp=n j1 n {x} {p} = refl +Findp=n j2 n {x} {p} = refl + +findpeq : (n : List Three) → {x : Nat} {p q : Findp n x } → find n x p ≡ find n x q +findpeq n {0} {v0} {v0} = refl +findpeq n {0} {v1} {v1} = refl +findpeq [] {Suc x} {()} +findpeq (h ∷ n) {Suc x} {vn p} {vn q} = subst₂ (λ j k → j ≡ k ) (Findp=n h n) (Findp=n h n) (findpeq n {x} {p} {q}) + +3List→PFunc : List Three → PFunc +3List→PFunc fp = record { dom = λ x → findp fp x ; map = λ x p → find fp x p ; meq = λ {x} {p} {q} → findpeq fp } + +_3⊆b_ : (f g : List Three) → Bool +[] 3⊆b [] = true +[] 3⊆b (j2 ∷ g) = [] 3⊆b g +[] 3⊆b (_ ∷ g) = true +(j2 ∷ f) 3⊆b [] = f 3⊆b [] +(j2 ∷ f) 3⊆b (_ ∷ g) = f 3⊆b g +(j0 ∷ f) 3⊆b (j0 ∷ g) = f 3⊆b g +(j1 ∷ f) 3⊆b (j1 ∷ g) = f 3⊆b g +_ 3⊆b _ = false + +_3⊆_ : (f g : List Three) → Set +f 3⊆ g = (f 3⊆b g) ≡ true + +_3∩_ : (f g : List Three) → List Three +[] 3∩ (j2 ∷ g) = j2 ∷ ([] 3∩ g) +[] 3∩ g = [] +(j2 ∷ f) 3∩ [] = j2 ∷ f 3∩ [] +f 3∩ [] = [] +(j0 ∷ f) 3∩ (j0 ∷ g) = j0 ∷ ( f 3∩ g ) +(j1 ∷ f) 3∩ (j1 ∷ g) = j1 ∷ ( f 3∩ g ) +(_ ∷ f) 3∩ (_ ∷ g) = j2 ∷ ( f 3∩ g ) + +3∩⊆f : { f g : List Three } → (f 3∩ g ) 3⊆ f +3∩⊆f {[]} {[]} = refl +3∩⊆f {[]} {j0 ∷ g} = refl +3∩⊆f {[]} {j1 ∷ g} = refl +3∩⊆f {[]} {j2 ∷ g} = 3∩⊆f {[]} {g} +3∩⊆f {j0 ∷ f} {[]} = refl +3∩⊆f {j1 ∷ f} {[]} = refl +3∩⊆f {j2 ∷ f} {[]} = 3∩⊆f {f} {[]} +3∩⊆f {j0 ∷ f} {j1 ∷ g} = 3∩⊆f {f} {g} +3∩⊆f {j1 ∷ f} {j0 ∷ g} = 3∩⊆f {f} {g} +3∩⊆f {j0 ∷ f} {j0 ∷ g} = 3∩⊆f {f} {g} +3∩⊆f {j1 ∷ f} {j1 ∷ g} = 3∩⊆f {f} {g} +3∩⊆f {j2 ∷ f} {j0 ∷ g} = 3∩⊆f {f} {g} +3∩⊆f {j2 ∷ f} {j1 ∷ g} = 3∩⊆f {f} {g} +3∩⊆f {j0 ∷ f} {j2 ∷ g} = 3∩⊆f {f} {g} +3∩⊆f {j1 ∷ f} {j2 ∷ g} = 3∩⊆f {f} {g} +3∩⊆f {j2 ∷ f} {j2 ∷ g} = 3∩⊆f {f} {g} + +3∩sym : { f g : List Three } → (f 3∩ g ) ≡ (g 3∩ f ) +3∩sym {[]} {[]} = refl +3∩sym {[]} {j0 ∷ g} = refl +3∩sym {[]} {j1 ∷ g} = refl +3∩sym {[]} {j2 ∷ g} = cong (λ k → j2 ∷ k) (3∩sym {[]} {g}) +3∩sym {j0 ∷ f} {[]} = refl +3∩sym {j1 ∷ f} {[]} = refl +3∩sym {j2 ∷ f} {[]} = cong (λ k → j2 ∷ k) (3∩sym {f} {[]}) +3∩sym {j0 ∷ f} {j0 ∷ g} = cong (λ k → j0 ∷ k) (3∩sym {f} {g}) +3∩sym {j0 ∷ f} {j1 ∷ g} = cong (λ k → j2 ∷ k) (3∩sym {f} {g}) +3∩sym {j0 ∷ f} {j2 ∷ g} = cong (λ k → j2 ∷ k) (3∩sym {f} {g}) +3∩sym {j1 ∷ f} {j0 ∷ g} = cong (λ k → j2 ∷ k) (3∩sym {f} {g}) +3∩sym {j1 ∷ f} {j1 ∷ g} = cong (λ k → j1 ∷ k) (3∩sym {f} {g}) +3∩sym {j1 ∷ f} {j2 ∷ g} = cong (λ k → j2 ∷ k) (3∩sym {f} {g}) +3∩sym {j2 ∷ f} {j0 ∷ g} = cong (λ k → j2 ∷ k) (3∩sym {f} {g}) +3∩sym {j2 ∷ f} {j1 ∷ g} = cong (λ k → j2 ∷ k) (3∩sym {f} {g}) +3∩sym {j2 ∷ f} {j2 ∷ g} = cong (λ k → j2 ∷ k) (3∩sym {f} {g}) + +3⊆-[] : { h : List Three } → [] 3⊆ h +3⊆-[] {[]} = refl +3⊆-[] {j0 ∷ h} = refl +3⊆-[] {j1 ∷ h} = refl +3⊆-[] {j2 ∷ h} = 3⊆-[] {h} + +3⊆trans : { f g h : List Three } → f 3⊆ g → g 3⊆ h → f 3⊆ h +3⊆trans {[]} {[]} {[]} f