annotate src/BAlgebra.agda @ 1465:bd2b003e25ef

...
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Fri, 05 Jan 2024 13:50:21 +0900
parents 484f83b04b5d
children e8c166541c86
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
1 {-# OPTIONS --cubical-compatible --safe #-}
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 open import Level
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 open import Ordinals
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
4 import HODBase
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
5 import OD
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
6 module BAlgebra {n : Level } (O : Ordinals {n} ) (HODAxiom : HODBase.ODAxiom O) (ho< : OD.ODAxiom-ho< O HODAxiom )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
7 (AC : OD.AxiomOfChoice O HODAxiom )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
8 where
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
10 -- open import Data.Nat renaming ( zero to Zero ; suc to Suc ; ℕ to Nat ; _⊔_ to _n⊔_ )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
11 open import Relation.Binary.PropositionalEquality hiding ( [_] )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
12 open import Data.Empty
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
13 open import Data.Unit
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
14 open import Relation.Nullary
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
15 open import Relation.Binary hiding (_⇔_)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
16 open import Relation.Binary.Core hiding (_⇔_)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
17 import Relation.Binary.Reasoning.Setoid as EqR
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
18
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 open import logic
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 import OrdUtil
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
21 open import nat
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 open Ordinals.Ordinals O
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 open Ordinals.IsOrdinals isOrdinal
1300
47d3cc596d68 remove next
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1293
diff changeset
25 -- open Ordinals.IsNext isNext
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 open OrdUtil O
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
27 import ODUtil
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
28 open ODUtil O HODAxiom ho<
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
29 import ODC
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
31 -- Ordinal Definable Set
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
32
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
33 open HODBase.HOD
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
34 open HODBase.OD
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 open _∧_
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 open _∨_
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 open Bool
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
40 open HODBase._==_
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
41
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
42 open HODBase.ODAxiom HODAxiom
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
43 open OD O HODAxiom
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
44 open AxiomOfChoice AC
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
45
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
46 open _∧_
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
47 open _∨_
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
48 open Bool
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
49
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
50 L\L=0 : { L : HOD } → (L \ L) =h= od∅
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
51 L\L=0 {L} = record { eq→ = lem0 ; eq← = lem1 } where
1123
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1096
diff changeset
52 lem0 : {x : Ordinal} → odef (L \ L) x → odef od∅ x
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1096
diff changeset
53 lem0 {x} ⟪ lx , ¬lx ⟫ = ⊥-elim (¬lx lx)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1096
diff changeset
54 lem1 : {x : Ordinal} → odef od∅ x → odef (L \ L) x
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1096
diff changeset
55 lem1 {x} lt = ⊥-elim ( ¬∅∋ (subst (λ k → odef od∅ k) (sym &iso) lt ))
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1096
diff changeset
56
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
57 L\Lx=x : { L x : HOD } → x ⊆ L → (L \ ( L \ x )) =h= x
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
58 L\Lx=x {L} {x} x⊆L = record { eq→ = lem03 ; eq← = lem04 } where
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
59 lem03 : {z : Ordinal} → odef (L \ (L \ x)) z → odef x z
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
60 lem03 {z} ⟪ Lz , Lxz ⟫ with ODC.∋-p O HODAxiom AC x (* z)
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
61 ... | yes y = subst (λ k → odef x k ) &iso y
1151
8a071bf52407 Finite intersection property to Compact done
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1150
diff changeset
62 ... | no n = ⊥-elim ( Lxz ⟪ Lz , ( subst (λ k → ¬ odef x k ) &iso n ) ⟫ )
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
63 lem04 : {z : Ordinal} → odef x z → odef (L \ (L \ x)) z
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
64 lem04 {z} xz with ODC.∋-p O HODAxiom AC L (* z)
1151
8a071bf52407 Finite intersection property to Compact done
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1150
diff changeset
65 ... | yes y = ⟪ subst (λ k → odef L k ) &iso y , ( λ p → proj2 p xz ) ⟫
8a071bf52407 Finite intersection property to Compact done
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1150
diff changeset
66 ... | no n = ⊥-elim ( n (subst (λ k → odef L k ) (sym &iso) ( x⊆L xz) ))
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
67
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
68 L\0=L : { L : HOD } → (L \ od∅) =h= L
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
69 L\0=L {L} = record { eq→ = lem05 ; eq← = lem06 } where
1151
8a071bf52407 Finite intersection property to Compact done
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1150
diff changeset
70 lem05 : {x : Ordinal} → odef (L \ od∅) x → odef L x
8a071bf52407 Finite intersection property to Compact done
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1150
diff changeset
71 lem05 {x} ⟪ Lx , _ ⟫ = Lx
8a071bf52407 Finite intersection property to Compact done
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1150
diff changeset
72 lem06 : {x : Ordinal} → odef L x → odef (L \ od∅) x
8a071bf52407 Finite intersection property to Compact done
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1150
diff changeset
73 lem06 {x} Lx = ⟪ Lx , (λ lt → ¬x<0 lt) ⟫
8a071bf52407 Finite intersection property to Compact done
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1150
diff changeset
74
1182
kono
parents: 1151
diff changeset
75 ∨L\X : { L X : HOD } → {x : Ordinal } → odef L x → odef X x ∨ odef (L \ X) x
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
76 ∨L\X {L} {X} {x} Lx with ODC.∋-p O HODAxiom AC X (* x)
1182
kono
parents: 1151
diff changeset
77 ... | yes y = case1 ( subst (λ k → odef X k ) &iso y )
kono
parents: 1151
diff changeset
78 ... | no n = case2 ⟪ Lx , subst (λ k → ¬ odef X k) &iso n ⟫
kono
parents: 1151
diff changeset
79
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
80 \-⊆ : { P A B : HOD } → A ⊆ P → ( A ⊆ B → ( P \ B ) ⊆ ( P \ A )) ∧ (( P \ B ) ⊆ ( P \ A ) → A ⊆ B )
1241
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1182
diff changeset
81 \-⊆ {P} {A} {B} A⊆P = ⟪ ( λ a<b {x} pbx → ⟪ proj1 pbx , (λ ax → proj2 pbx (a<b ax)) ⟫ ) , lem07 ⟫ where
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1182
diff changeset
82 lem07 : (P \ B) ⊆ (P \ A) → A ⊆ B
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
83 lem07 pba {x} ax with ODC.p∨¬p O HODAxiom AC (odef B x)
1241
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1182
diff changeset
84 ... | case1 bx = bx
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1182
diff changeset
85 ... | case2 ¬bx = ⊥-elim ( proj2 ( pba ⟪ A⊆P ax , ¬bx ⟫ ) ax )
1151
8a071bf52407 Finite intersection property to Compact done
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1150
diff changeset
86
1293
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1284
diff changeset
87 RC\ : {L : HOD} → RCod (Power (Union L)) (λ z → L \ z )
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
88 RC\ {L} = record { ≤COD = λ {x} lt z xz → lemm {x} lt z xz ; ψ-eq = λ {x} {y} → wdf {x} {y} } where
1293
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1284
diff changeset
89 lemm : {x : HOD} → (L \ x) ⊆ Power (Union L )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1284
diff changeset
90 lemm {x} ⟪ Ly , nxy ⟫ z xz = record { owner = _ ; ao = Ly ; ox = xz }
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
91 wdf : {x y : HOD} → od x == od y → (L \ x) =h= (L \ y)
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
92 wdf {x} {y} x=y = record { eq→ = λ {p} lxp → ⟪ proj1 lxp , (λ yp → proj2 lxp (eq← x=y yp) ) ⟫
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
93 ; eq← = λ {p} lxp → ⟪ proj1 lxp , (λ yp → proj2 lxp (eq→ x=y yp) ) ⟫ }
1293
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1284
diff changeset
94
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1284
diff changeset
95
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
96 [a-b]∩b=0 : { A B : HOD } → ((A \ B) ∩ B) =h= od∅
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
97 [a-b]∩b=0 {A} {B} = record { eq← = λ lt → ⊥-elim ( ¬∅∋ (subst (λ k → odef od∅ k) (sym &iso) lt ))
451
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 450
diff changeset
98 ; eq→ = λ {x} lt → ⊥-elim (proj2 (proj1 lt ) (proj2 lt)) }
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 450
diff changeset
99
480
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 451
diff changeset
100 U-F=∅→F⊆U : {F U : HOD} → ((x : Ordinal) → ¬ ( odef F x ∧ ( ¬ odef U x ))) → F ⊆ U
1096
55ab5de1ae02 recovery
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 480
diff changeset
101 U-F=∅→F⊆U {F} {U} not = gt02 where
480
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 451
diff changeset
102 gt02 : { x : Ordinal } → odef F x → odef U x
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
103 gt02 {x} fx with ODC.∋-p O HODAxiom AC U (* x)
480
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 451
diff changeset
104 ... | yes y = subst (λ k → odef U k ) &iso y
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 451
diff changeset
105 ... | no n = ⊥-elim ( not x ⟪ fx , subst (λ k → ¬ odef U k ) &iso n ⟫ )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 451
diff changeset
106
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
107 ∪-Union : { A B : HOD } → Union (A , B) =h= ( A ∪ B )
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
108 ∪-Union {A} {B} = ( record { eq→ = lemma4 ; eq← = lemma2 } ) where
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
109 lemma4 : {x : Ordinal} → odef (Union (A , B)) x → odef (A ∪ B) x
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
110 lemma4 {x} record { owner = owner ; ao = (case1 refl) ; ox = ox } = case1 (eq← *iso== ox)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
111 lemma4 {x} record { owner = owner ; ao = (case2 refl) ; ox = ox } = case2 (eq← *iso== ox)
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 lemma2 : {x : Ordinal} → odef (A ∪ B) x → odef (Union (A , B)) x
1284
45cd80181a29 remove import zf
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1282
diff changeset
113 lemma2 {x} (case1 A∋x) = subst (λ k → odef (Union (A , B)) k) &iso ( union→ (A , B) (* x) A
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
114 ⟪ case1 refl , d→∋ A A∋x ⟫ )
1284
45cd80181a29 remove import zf
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1282
diff changeset
115 lemma2 {x} (case2 B∋x) = subst (λ k → odef (Union (A , B)) k) &iso ( union→ (A , B) (* x) B
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
116 ⟪ case2 refl , d→∋ B B∋x ⟫ )
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
117
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
118 open import zf
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
119
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
120 pred-in : (A B : HOD ) → ZPred HOD _∋_ _=h=_ (λ x → (A ∋ x) ∧ (B ∋ x))
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
121 pred-in A B = record { ψ-cong = wdf } where
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
122 wdf : (x y : HOD) → x =h= y → ((A ∋ x) ∧ (B ∋ x)) ⇔ ((A ∋ y) ∧ (B ∋ y))
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
123 wdf = λ x y x=y
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
124 → ⟪ (λ p → ⟪ subst (λ k → odef A k) (==→o≡ x=y) (proj1 p)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
125 , subst (λ k → odef B k) (==→o≡ x=y) (proj2 p) ⟫ )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
126 , (λ p → ⟪ subst (λ k → odef A k) (sym (==→o≡ x=y)) (proj1 p)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
127 , subst (λ k → odef B k) (sym (==→o≡ x=y)) (proj2 p) ⟫ ) ⟫
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
128
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
129 ∩-Select : { A B : HOD } → Select A ( λ x → ( A ∋ x ) ∧ ( B ∋ x )) (pred-in A B) =h= ( A ∩ B )
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
130 ∩-Select {A} {B} = record { eq→ = lemma1 ; eq← = lemma2 } where
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
131 lemma1 : {x : Ordinal} → odef (Select A (λ x₁ → (A ∋ x₁) ∧ (B ∋ x₁)) (pred-in A B) ) x → odef (A ∩ B) x
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
132 lemma1 {x} lt = ⟪ proj1 lt , subst (λ k → odef B k ) &iso (proj2 (proj2 lt)) ⟫
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
133 lemma2 : {x : Ordinal} → odef (A ∩ B) x → odef (Select A (λ x₁ → (A ∋ x₁) ∧ (B ∋ x₁)) (pred-in A B) ) x
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
134 lemma2 {x} lt = ⟪ proj1 lt , ⟪ d→∋ A (proj1 lt) , d→∋ B (proj2 lt) ⟫ ⟫
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
135
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
136 dist-ord : {p q r : HOD } → (p ∩ ( q ∪ r )) =h= ( ( p ∩ q ) ∪ ( p ∩ r ))
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
137 dist-ord {p} {q} {r} = record { eq→ = lemma1 ; eq← = lemma2 } where
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
138 lemma1 : {x : Ordinal} → odef (p ∩ (q ∪ r)) x → odef ((p ∩ q) ∪ (p ∩ r)) x
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
139 lemma1 {x} lt with proj2 lt
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
140 lemma1 {x} lt | case1 q∋x = case1 ⟪ proj1 lt , q∋x ⟫
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
141 lemma1 {x} lt | case2 r∋x = case2 ⟪ proj1 lt , r∋x ⟫
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
142 lemma2 : {x : Ordinal} → odef ((p ∩ q) ∪ (p ∩ r)) x → odef (p ∩ (q ∪ r)) x
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
143 lemma2 {x} (case1 p∩q) = ⟪ proj1 p∩q , case1 (proj2 p∩q ) ⟫
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
144 lemma2 {x} (case2 p∩r) = ⟪ proj1 p∩r , case2 (proj2 p∩r ) ⟫
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
145
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
146 dist-ord2 : {p q r : HOD } → (p ∪ ( q ∩ r )) =h= ( ( p ∪ q ) ∩ ( p ∪ r ))
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
147 dist-ord2 {p} {q} {r} = record { eq→ = lemma1 ; eq← = lemma2 } where
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
148 lemma1 : {x : Ordinal} → odef (p ∪ (q ∩ r)) x → odef ((p ∪ q) ∩ (p ∪ r)) x
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
149 lemma1 {x} (case1 cp) = ⟪ case1 cp , case1 cp ⟫
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
150 lemma1 {x} (case2 cqr) = ⟪ case2 (proj1 cqr) , case2 (proj2 cqr) ⟫
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
151 lemma2 : {x : Ordinal} → odef ((p ∪ q) ∩ (p ∪ r)) x → odef (p ∪ (q ∩ r)) x
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
152 lemma2 {x} lt with proj1 lt | proj2 lt
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
153 lemma2 {x} lt | case1 cp | _ = case1 cp
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
154 lemma2 {x} lt | _ | case1 cp = case1 cp
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
155 lemma2 {x} lt | case2 cq | case2 cr = case2 ⟪ cq , cr ⟫
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
156
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
157 record IsBooleanAlgebra {n m : Level} ( L : Set n)
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
158 ( _≈_ : L → L → Set m )
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
159 ( b1 : L )
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
160 ( b0 : L )
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
161 ( -_ : L → L )
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
162 ( _+_ : L → L → L )
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
163 ( _x_ : L → L → L ) : Set (n ⊔ m) where
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
164 field
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
165 +-assoc : {a b c : L } → (a + ( b + c )) ≈ ((a + b) + c)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
166 x-assoc : {a b c : L } → (a x ( b x c )) ≈ ((a x b) x c)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
167 +-sym : {a b : L } → (a + b) ≈ (b + a)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
168 x-sym : {a b : L } → (a x b) ≈ (b x a)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
169 +-aab : {a b : L } → (a + ( a x b )) ≈ a
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
170 x-aab : {a b : L } → (a x ( a + b )) ≈ a
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
171 +-dist : {a b c : L } → (a + ( b x c )) ≈ (( a + b ) x ( a + c ))
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
172 x-dist : {a b c : L } → (a x ( b + c )) ≈ (( a x b ) + ( a x c ))
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
173 a+0 : {a : L } → (a + b0) ≈ a
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
174 ax1 : {a : L } → (a x b1) ≈ a
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
175 a+-a1 : {a : L } → (a + ( - a )) ≈ b1
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
176 ax-a0 : {a : L } → (a x ( - a )) ≈ b0
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
177
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
178 record BooleanAlgebra {n m : Level} ( L : Set n) : Set (n ⊔ suc m) where
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
179 field
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
180 _≈_ : L → L → Set m
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
181 b1 : L
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
182 b0 : L
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
183 -_ : L → L
431
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
184 _+_ : L → L → L
a5f8084b8368 reorganiztion for apkg
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
185 _x_ : L → L → L
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
186 isBooleanAlgebra : IsBooleanAlgebra L _≈_ b1 b0 -_ _+_ _x_
1280
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1241
diff changeset
187
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1241
diff changeset
188 record PowerP (P : HOD) : Set (suc n) where
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1241
diff changeset
189 constructor ⟦_,_⟧
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1241
diff changeset
190 field
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1241
diff changeset
191 hod : HOD
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
192 x⊆P : hod ⊆ P
1280
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1241
diff changeset
193
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1241
diff changeset
194 open PowerP
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1241
diff changeset
195
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
196 HODBA : (P : HOD) → BooleanAlgebra {suc n} {n} (PowerP P)
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
197 HODBA P = record { _≈_ = λ x y → hod x =h= hod y ; b1 = ⟦ P , (λ x → x) ⟧ ; b0 = ⟦ od∅ , (λ x → ⊥-elim (¬x<0 x)) ⟧
1280
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1241
diff changeset
198 ; -_ = λ x → ⟦ P \ hod x , proj1 ⟧
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
199 ; _+_ = λ x y → ⟦ hod x ∪ hod y , ba00 x y ⟧ ; _x_ = λ x y → ⟦ hod x ∩ hod y , (λ lt → x⊆P x (proj1 lt)) ⟧
1280
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1241
diff changeset
200 ; isBooleanAlgebra = record {
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
201 +-assoc = λ {a} {b} {c} → record { eq→ = ba01 a b c ; eq← = ba02 a b c }
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
202 ; x-assoc = λ {a} {b} {c} →
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
203 record { eq→ = λ lt → ⟪ ⟪ proj1 lt , proj1 (proj2 lt) ⟫ , proj2 (proj2 lt) ⟫
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
204 ; eq← = λ lt → ⟪ proj1 (proj1 lt) , ⟪ proj2 (proj1 lt) , proj2 lt ⟫ ⟫ }
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
205 ; +-sym = λ {a} {b} → record { eq→ = λ {x} lt → ba05 {hod a} {hod b} lt ; eq← = ba05 {hod b} {hod a} }
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
206 ; x-sym = λ {a} {b} → record { eq→ = λ lt → ⟪ proj2 lt , proj1 lt ⟫ ; eq← = λ lt → ⟪ proj2 lt , proj1 lt ⟫ }
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
207 ; +-aab = λ {a} {b} → record { eq→ = ba03 a b ; eq← = case1 }
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
208 ; x-aab = λ {a} {b} → record { eq→ = proj1 ; eq← = λ ax → ⟪ ax , case1 ax ⟫ }
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
209 ; +-dist = λ {p} {q} {r} → dist-ord2 {hod p} {hod q} {hod r}
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
210 ; x-dist = λ {p} {q} {r} → dist-ord {hod p} {hod q} {hod r}
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
211 ; a+0 = λ {a} → record { eq→ = ba04 (hod a) ; eq← = case1 }
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
212 ; ax1 = λ {a} → record { eq→ = proj1 ; eq← = λ ax → ⟪ ax , x⊆P a ax ⟫ }
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
213 ; a+-a1 = λ {a} → record { eq→ = ba06 a ; eq← = ba07 a }
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
214 ; ax-a0 = λ {a} → record { eq→ = ba08 a ; eq← = λ lt → ⊥-elim (¬x<0 lt) }
1281
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
215 } } where
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
216 ba00 : (x y : PowerP P ) → (hod x ∪ hod y) ⊆ P
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
217 ba00 x y (case1 px) = x⊆P x px
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
218 ba00 x y (case2 py) = x⊆P y py
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
219 ba01 : (a b c : PowerP P) → {x : Ordinal} → odef (hod a) x ∨ odef (hod b ∪ hod c) x →
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
220 odef (hod a ∪ hod b) x ∨ odef (hod c) x
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
221 ba01 a b c {x} (case1 ax) = case1 (case1 ax)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
222 ba01 a b c {x} (case2 (case1 bx)) = case1 (case2 bx)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
223 ba01 a b c {x} (case2 (case2 cx)) = case2 cx
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
224 ba02 : (a b c : PowerP P) → {x : Ordinal} → odef (hod a ∪ hod b) x ∨ odef (hod c) x
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
225 → odef (hod a) x ∨ odef (hod b ∪ hod c) x
1281
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
226 ba02 a b c {x} (case1 (case1 ax)) = case1 ax
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
227 ba02 a b c {x} (case1 (case2 bx)) = case2 (case1 bx)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
228 ba02 a b c {x} (case2 cx) = case2 (case2 cx)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
229 ba03 : (a b : PowerP P) → {x : Ordinal} →
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
230 odef (hod a) x ∨ odef (hod a ∩ hod b) x → def (od (hod a)) x
1281
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
231 ba03 a b (case1 ax) = ax
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
232 ba03 a b (case2 ab) = proj1 ab
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
233 ba04 : (a : HOD) → {x : Ordinal} → odef a x ∨ odef od∅ x → odef a x
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
234 ba04 a (case1 ax) = ax
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1280
diff changeset
235 ba04 a (case2 x) = ⊥-elim (¬x<0 x)
1282
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1281
diff changeset
236 ba05 : {a b : HOD} {x : Ordinal} → odef a x ∨ odef b x → odef b x ∨ odef a x
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1281
diff changeset
237 ba05 (case1 x) = case2 x
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1281
diff changeset
238 ba05 (case2 x) = case1 x
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
239 ba06 : (a : PowerP P ) → { x : Ordinal} → odef (hod a) x ∨ odef (P \ hod a) x → def (od P) x
1282
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1281
diff changeset
240 ba06 a {x} (case1 ax) = x⊆P a ax
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1281
diff changeset
241 ba06 a {x} (case2 nax) = proj1 nax
1465
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1464
diff changeset
242 ba07 : (a : PowerP P ) → { x : Ordinal} → def (od P) x → odef (hod a) x ∨ odef (P \ hod a) x
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
243 ba07 a {x} px with ODC.∋-p O HODAxiom AC (hod a) (* x)
1282
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1281
diff changeset
244 ... | yes y = case1 (subst (λ k → odef (hod a) k) &iso y)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1281
diff changeset
245 ... | no n = case2 ⟪ px , subst (λ k → ¬ odef (hod a) k) &iso n ⟫
1464
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1300
diff changeset
246 ba08 : (a : PowerP P) → {x : Ordinal} → def (od (hod a ∩ (P \ hod a))) x → def (od od∅) x
1282
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1281
diff changeset
247 ba08 a {x} ⟪ ax , ⟪ px , nax ⟫ ⟫ = ⊥-elim ( nax ax )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 1281
diff changeset
248