|
431
|
1 open import Level
|
|
|
2 open import Ordinals
|
|
|
3 module BAlgbra {n : Level } (O : Ordinals {n}) where
|
|
|
4
|
|
|
5 open import zf
|
|
|
6 open import logic
|
|
|
7 import OrdUtil
|
|
|
8 import OD
|
|
|
9 import ODUtil
|
|
|
10 import ODC
|
|
|
11
|
|
|
12 open import Relation.Nullary
|
|
|
13 open import Relation.Binary
|
|
|
14 open import Data.Empty
|
|
|
15 open import Relation.Binary
|
|
|
16 open import Relation.Binary.Core
|
|
|
17 open import Relation.Binary.PropositionalEquality
|
|
|
18 open import Data.Nat renaming ( zero to Zero ; suc to Suc ; ℕ to Nat ; _⊔_ to _n⊔_ ; _+_ to _n+_ )
|
|
|
19
|
|
|
20 open inOrdinal O
|
|
|
21 open Ordinals.Ordinals O
|
|
|
22 open Ordinals.IsOrdinals isOrdinal
|
|
|
23 open Ordinals.IsNext isNext
|
|
|
24 open OrdUtil O
|
|
|
25 open ODUtil O
|
|
|
26
|
|
|
27 open OD O
|
|
|
28 open OD.OD
|
|
|
29 open ODAxiom odAxiom
|
|
|
30 open HOD
|
|
|
31
|
|
|
32 open _∧_
|
|
|
33 open _∨_
|
|
|
34 open Bool
|
|
|
35
|
|
|
36 --_∩_ : ( A B : HOD ) → HOD
|
|
|
37 --A ∩ B = record { od = record { def = λ x → odef A x ∧ odef B x } ;
|
|
|
38 -- odmax = omin (odmax A) (odmax B) ; <odmax = λ y → min1 (<odmax A (proj1 y)) (<odmax B (proj2 y)) }
|
|
|
39
|
|
450
|
40 ∩-comm : { A B : HOD } → (A ∩ B) ≡ (B ∩ A)
|
|
|
41 ∩-comm {A} {B} = ==→o≡ record { eq← = λ {x} lt → ⟪ proj2 lt , proj1 lt ⟫ ; eq→ = λ {x} lt → ⟪ proj2 lt , proj1 lt ⟫ }
|
|
|
42
|
|
431
|
43 _∪_ : ( A B : HOD ) → HOD
|
|
|
44 A ∪ B = record { od = record { def = λ x → odef A x ∨ odef B x } ;
|
|
|
45 odmax = omax (odmax A) (odmax B) ; <odmax = lemma } where
|
|
|
46 lemma : {y : Ordinal} → odef A y ∨ odef B y → y o< omax (odmax A) (odmax B)
|
|
|
47 lemma {y} (case1 a) = ordtrans (<odmax A a) (omax-x _ _)
|
|
|
48 lemma {y} (case2 b) = ordtrans (<odmax B b) (omax-y _ _)
|
|
|
49
|
|
|
50 _＼_ : ( A B : HOD ) → HOD
|
|
|
51 A ＼ B = record { od = record { def = λ x → odef A x ∧ ( ¬ ( odef B x ) ) }; odmax = odmax A ; <odmax = λ y → <odmax A (proj1 y) }
|
|
|
52
|
|
451
|
53 ¬∅∋ : {x : HOD} → ¬ ( od∅ ∋ x )
|
|
|
54 ¬∅∋ {x} = ¬x<0
|
|
|
55
|
|
|
56 [a-b]∩b=0 : { A B : HOD } → (A ＼ B) ∩ B ≡ od∅
|
|
|
57 [a-b]∩b=0 {A} {B} = ==→o≡ record { eq← = λ lt → ⊥-elim ( ¬∅∋ (subst (λ k → odef od∅ k) (sym &iso) lt ))
|
|
|
58 ; eq→ = λ {x} lt → ⊥-elim (proj2 (proj1 lt ) (proj2 lt)) }
|
|
|
59
|
|
480
|
60 U-F=∅→F⊆U : {F U : HOD} → ((x : Ordinal) → ¬ ( odef F x ∧ ( ¬ odef U x ))) → F ⊆ U
|
|
1096
|
61 U-F=∅→F⊆U {F} {U} not = gt02 where
|
|
480
|
62 gt02 : { x : Ordinal } → odef F x → odef U x
|
|
|
63 gt02 {x} fx with ODC.∋-p O U (* x)
|
|
|
64 ... | yes y = subst (λ k → odef U k ) &iso y
|
|
|
65 ... | no n = ⊥-elim ( not x ⟪ fx , subst (λ k → ¬ odef U k ) &iso n ⟫ )
|
|
|
66
|
|
431
|
67 ∪-Union : { A B : HOD } → Union (A , B) ≡ ( A ∪ B )
|
|
|
68 ∪-Union {A} {B} = ==→o≡ ( record { eq→ = lemma1 ; eq← = lemma2 } ) where
|
|
|
69 lemma1 : {x : Ordinal} → odef (Union (A , B)) x → odef (A ∪ B) x
|
|
1096
|
70 lemma1 {x} record { owner = owner ; ao = abo ; ox = ox } with pair=∨ (subst₂ (λ j k → odef (j , k ) owner) (sym *iso) (sym *iso) abo )
|
|
|
71 ... | case1 a=o = case1 (subst (λ k → odef k x ) ( begin
|
|
|
72 * owner ≡⟨ cong (*) (sym a=o) ⟩
|
|
|
73 * (& A) ≡⟨ *iso ⟩
|
|
|
74 A ∎ ) ox ) where open ≡-Reasoning
|
|
|
75 ... | case2 b=o = case2 (subst (λ k → odef k x ) (trans (cong (*) (sym b=o)) *iso ) ox)
|
|
431
|
76 lemma2 : {x : Ordinal} → odef (A ∪ B) x → odef (Union (A , B)) x
|
|
|
77 lemma2 {x} (case1 A∋x) = subst (λ k → odef (Union (A , B)) k) &iso ( IsZF.union→ isZF (A , B) (* x) A
|
|
|
78 ⟪ case1 refl , d→∋ A A∋x ⟫ )
|
|
|
79 lemma2 {x} (case2 B∋x) = subst (λ k → odef (Union (A , B)) k) &iso ( IsZF.union→ isZF (A , B) (* x) B
|
|
|
80 ⟪ case2 refl , d→∋ B B∋x ⟫ )
|
|
|
81
|
|
|
82 ∩-Select : { A B : HOD } → Select A ( λ x → ( A ∋ x ) ∧ ( B ∋ x ) ) ≡ ( A ∩ B )
|
|
|
83 ∩-Select {A} {B} = ==→o≡ ( record { eq→ = lemma1 ; eq← = lemma2 } ) where
|
|
|
84 lemma1 : {x : Ordinal} → odef (Select A (λ x₁ → (A ∋ x₁) ∧ (B ∋ x₁))) x → odef (A ∩ B) x
|
|
|
85 lemma1 {x} lt = ⟪ proj1 lt , subst (λ k → odef B k ) &iso (proj2 (proj2 lt)) ⟫
|
|
|
86 lemma2 : {x : Ordinal} → odef (A ∩ B) x → odef (Select A (λ x₁ → (A ∋ x₁) ∧ (B ∋ x₁))) x
|
|
|
87 lemma2 {x} lt = ⟪ proj1 lt , ⟪ d→∋ A (proj1 lt) , d→∋ B (proj2 lt) ⟫ ⟫
|
|
|
88
|
|
|
89 dist-ord : {p q r : HOD } → p ∩ ( q ∪ r ) ≡ ( p ∩ q ) ∪ ( p ∩ r )
|
|
|
90 dist-ord {p} {q} {r} = ==→o≡ ( record { eq→ = lemma1 ; eq← = lemma2 } ) where
|
|
|
91 lemma1 : {x : Ordinal} → odef (p ∩ (q ∪ r)) x → odef ((p ∩ q) ∪ (p ∩ r)) x
|
|
|
92 lemma1 {x} lt with proj2 lt
|
|
|
93 lemma1 {x} lt | case1 q∋x = case1 ⟪ proj1 lt , q∋x ⟫
|
|
|
94 lemma1 {x} lt | case2 r∋x = case2 ⟪ proj1 lt , r∋x ⟫
|
|
|
95 lemma2 : {x : Ordinal} → odef ((p ∩ q) ∪ (p ∩ r)) x → odef (p ∩ (q ∪ r)) x
|
|
|
96 lemma2 {x} (case1 p∩q) = ⟪ proj1 p∩q , case1 (proj2 p∩q ) ⟫
|
|
|
97 lemma2 {x} (case2 p∩r) = ⟪ proj1 p∩r , case2 (proj2 p∩r ) ⟫
|
|
|
98
|
|
|
99 dist-ord2 : {p q r : HOD } → p ∪ ( q ∩ r ) ≡ ( p ∪ q ) ∩ ( p ∪ r )
|
|
|
100 dist-ord2 {p} {q} {r} = ==→o≡ ( record { eq→ = lemma1 ; eq← = lemma2 } ) where
|
|
|
101 lemma1 : {x : Ordinal} → odef (p ∪ (q ∩ r)) x → odef ((p ∪ q) ∩ (p ∪ r)) x
|
|
|
102 lemma1 {x} (case1 cp) = ⟪ case1 cp , case1 cp ⟫
|
|
|
103 lemma1 {x} (case2 cqr) = ⟪ case2 (proj1 cqr) , case2 (proj2 cqr) ⟫
|
|
|
104 lemma2 : {x : Ordinal} → odef ((p ∪ q) ∩ (p ∪ r)) x → odef (p ∪ (q ∩ r)) x
|
|
|
105 lemma2 {x} lt with proj1 lt | proj2 lt
|
|
|
106 lemma2 {x} lt | case1 cp | _ = case1 cp
|
|
|
107 lemma2 {x} lt | _ | case1 cp = case1 cp
|
|
|
108 lemma2 {x} lt | case2 cq | case2 cr = case2 ⟪ cq , cr ⟫
|
|
|
109
|
|
|
110 record IsBooleanAlgebra ( L : Set n)
|
|
|
111 ( b1 : L )
|
|
|
112 ( b0 : L )
|
|
|
113 ( -_ : L → L )
|
|
|
114 ( _+_ : L → L → L )
|
|
|
115 ( _x_ : L → L → L ) : Set (suc n) where
|
|
|
116 field
|
|
|
117 +-assoc : {a b c : L } → a + ( b + c ) ≡ (a + b) + c
|
|
|
118 x-assoc : {a b c : L } → a x ( b x c ) ≡ (a x b) x c
|
|
|
119 +-sym : {a b : L } → a + b ≡ b + a
|
|
|
120 -sym : {a b : L } → a x b ≡ b x a
|
|
|
121 +-aab : {a b : L } → a + ( a x b ) ≡ a
|
|
|
122 x-aab : {a b : L } → a x ( a + b ) ≡ a
|
|
|
123 +-dist : {a b c : L } → a + ( b x c ) ≡ ( a x b ) + ( a x c )
|
|
|
124 x-dist : {a b c : L } → a x ( b + c ) ≡ ( a + b ) x ( a + c )
|
|
|
125 a+0 : {a : L } → a + b0 ≡ a
|
|
|
126 ax1 : {a : L } → a x b1 ≡ a
|
|
|
127 a+-a1 : {a : L } → a + ( - a ) ≡ b1
|
|
|
128 ax-a0 : {a : L } → a x ( - a ) ≡ b0
|
|
|
129
|
|
|
130 record BooleanAlgebra ( L : Set n) : Set (suc n) where
|
|
|
131 field
|
|
|
132 b1 : L
|
|
|
133 b0 : L
|
|
|
134 -_ : L → L
|
|
|
135 _+_ : L → L → L
|
|
|
136 _x_ : L → L → L
|
|
|
137 isBooleanAlgebra : IsBooleanAlgebra L b1 b0 -_ _+_ _x_
|
|
|
138
|
