Mercurial > hg > Members > kono > Proof > ZF-in-agda

changeset 497:2a8629b5cff9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
other strategy
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Mon, 11 Apr 2022 15:14:53 +0900
parents c03d80290855
children 8ec0b88b022f
files src/zorn.agda
diffstat 1 files changed, 96 insertions(+), 83 deletions(-) [+]
line wrap: on
line diff
--- a/src/zorn.agda	Sat Apr 09 13:56:49 2022 +0900
+++ b/src/zorn.agda	Mon Apr 11 15:14:53 2022 +0900
@@ -1,12 +1,12 @@
 {-# OPTIONS --allow-unsolved-metas #-}
 open import Level
 open import Ordinals
-module zorn {n : Level } (O : Ordinals {n})   where
+import OD 
+module zorn {n : Level } (O : Ordinals {n}) (_<_ : (x y : OD.HOD O ) → Set n ) where
 
 open import zf
 open import logic
 -- open import partfunc {n} O
-import OD 
 
 open import Relation.Nullary 
 open import Relation.Binary 
@@ -47,8 +47,8 @@
 
 open Element
 
-IsPartialOrderSet : ( A : HOD ) →  (_<_ : (x y : HOD) → Set n )  → Set (suc n)
-IsPartialOrderSet A _<_ = IsStrictPartialOrder _≡A_ _<A_  where
+IsPartialOrderSet : ( A : HOD ) → Set (suc n)
+IsPartialOrderSet A = IsStrictPartialOrder _≡A_ _<A_  where
    _<A_ : (x y : Element A ) → Set n
    x <A y = elm x < elm y
    _≡A_ : (x y : Element A ) → Set (suc n)
@@ -60,9 +60,9 @@
 isA : { A B  : HOD } → B ⊆ A → (x : Element B) → Element A
 isA B⊆A x = record { elm = elm x ; is-elm = incl B⊆A (is-elm x) }
 
-⊆-IsPartialOrderSet : { A B  : HOD } → B ⊆ A →  {_<_ : (x y : HOD) → Set n }  → IsPartialOrderSet A _<_ → IsPartialOrderSet B _<_
-⊆-IsPartialOrderSet {A} {B} B⊆A {_<_} PA = record {
-       isEquivalence = record { refl = refl ; sym = sym ; trans = trans } ; reflexive = λ eq → case1 eq ; trans = λ {x} {y} {z} → trans1 {x} {y} {z} 
+⊆-IsPartialOrderSet : { A B  : HOD } → B ⊆ A → IsPartialOrderSet A → IsPartialOrderSet B 
+⊆-IsPartialOrderSet {A} {B} B⊆A  PA = record {
+       isEquivalence = record { refl = refl ; sym = sym ; trans = trans } ;  trans = λ {x} {y} {z} → trans1 {x} {y} {z} 
      ; irrefl = λ {x} {y} → irrefl1 {x} {y} ; trans = trans1 ; <-resp-≈ = resp0 
    } where
    _<B_ : (x y : Element B ) → Set n
@@ -76,10 +76,10 @@
    resp0 = Data.Product._,_  (λ {x} {y} {z} → proj₁ (IsStrictPartialOrder.<-resp-≈ PA) {isA B⊆A x } {isA B⊆A y }{isA B⊆A z }) 
                              (λ {x} {y} {z} → proj₂ (IsStrictPartialOrder.<-resp-≈ PA) {isA B⊆A x } {isA B⊆A y }{isA B⊆A z })
 
-open import Relation.Binary.Properties.Poset as Poset
+-- open import Relation.Binary.Properties.Poset as Poset
 
-IsTotalOrderSet : ( A : HOD ) →  (_<_ : (x y : HOD) → Set n )  → Set (suc n)
-IsTotalOrderSet A _<_ = IsStrictTotalOrder  _≡A_ _<A_ where
+IsTotalOrderSet : ( A : HOD ) →  Set (suc n)
+IsTotalOrderSet A = IsStrictTotalOrder  _≡A_ _<A_ where
    _<A_ : (x y : Element A ) → Set n
    x <A y = elm x < elm y
    _≡A_ : (x y : Element A ) → Set (suc n)
@@ -88,32 +88,35 @@
 me : { A a : HOD } → A ∋ a → Element A
 me {A} {a} lt = record { elm = a ; is-elm = lt }
 
-record SUP ( A B : HOD ) (_<_ : (x y : HOD) → Set n ) : Set (suc n) where
+record SUP ( A B : HOD )  : Set (suc n) where
    field
       sup : HOD
       A∋maximal : A ∋ sup
       x<sup : {x : HOD} → B ∋ x → (x ≡ sup ) ∨ (x < sup )   -- B is Total, use positive
 
-record Maximal ( A : HOD ) (_<_ : (x y : HOD) → Set n ) : Set (suc n) where
+record Maximal ( A : HOD )  : Set (suc n) where
    field
       maximal : HOD
       A∋maximal : A ∋ maximal
       ¬maximal<x : {x : HOD} → A ∋ x  → ¬ maximal < x       -- A is Partial, use negative
 
 
-record ZChain ( A : HOD ) (y : Ordinal)  (_<_ : (x y : HOD) → Set n ) : Set (suc n) where
+record ZChain ( A : HOD ) (y : Ordinal)   : Set (suc n) where
    field
-      fb : (x : Ordinal ) → HOD
-      A∋fb : (ox : Ordinal ) → ox o< y → A ∋ fb ox 
-      total : {ox oz : Ordinal } → (x<y : ox o< y ) → (z<y : oz o< y ) → ( ox ≡ oz ) ∨ ( fb ox < fb oz ) ∨ ( fb oz < fb ox  )
-      monotonic : {ox oz : Ordinal } → (x<y : ox o< y ) → (z<y : oz o< y ) → ox o< oz → fb ox < fb oz 
-
-Zorn-lemma : { A : HOD } → { _<_ : (x y : HOD) → Set n }
+      max : HOD
+      A∋max : A ∋ max
+      y<max : y o< & max
+      chain : HOD
+      chain⊆A : chain ⊆ A  
+      total : IsTotalOrderSet chain 
+      chain-max : (x : HOD) → chain ∋ x → (x ≡ max ) ∨ ( x < max )
+      
+Zorn-lemma : { A : HOD } 
     → o∅ o< & A 
-    → IsPartialOrderSet A _<_
-    → ( ( B : HOD) → (B⊆A : B ⊆ A) → IsTotalOrderSet B _<_ → SUP A B  _<_  ) -- SUP condition
-    → Maximal A _<_ 
-Zorn-lemma {A} {_<_} 0<A PO supP = zorn00 where
+    → IsPartialOrderSet A 
+    → ( ( B : HOD) → (B⊆A : B ⊆ A) → IsTotalOrderSet B → SUP A B   ) -- SUP condition
+    → Maximal A 
+Zorn-lemma {A}  0<A PO supP = zorn00 where
      someA : HOD
      someA = ODC.minimal O A (λ eq → ¬x<0 ( subst (λ k → o∅ o< k ) (=od∅→≡o∅ eq) 0<A )) 
      isSomeA : A ∋ someA
@@ -137,25 +140,25 @@
             bx : Ordinal
             bx<y : bx o< y
             is-fb : x ≡ & (fb bx )
-     bx<A : (z : ZChain A (& A) _<_ ) → {x : Ordinal } → (bx : BX x (& A) ( ZChain.fb z ))  → BX.bx bx o< & A
+     bx<A : (z : ZChain A (& A) ) → {x : Ordinal } → (bx : BX x (& A) {!!})  → BX.bx bx o< & A
      bx<A z {x} bx = BX.bx<y bx
-     z12 : (z : ZChain A (& A) _<_ ) →  {y : Ordinal} → BX y (& A) (ZChain.fb z) → y o< & A
-     z12 z {y} bx = subst (λ k → k o< & A) (sym (BX.is-fb bx)) (c<→o< (ZChain.A∋fb z (BX.bx bx)  (BX.bx<y bx)))  
-     B :  (z : ZChain A (& A) _<_ ) → HOD
-     B z = record { od = record { def = λ x → BX x (& A) ( ZChain.fb z )  } ; odmax = & A ; <odmax = z12 z } 
-     z11 :  (z : ZChain A (& A) _<_ ) → (x : Element (B z)) → elm x ≡  ZChain.fb z (BX.bx (is-elm x)) 
+     z12 : (z : ZChain A (& A) ) →  {y : Ordinal} → BX y (& A) {!!} → y o< & A
+     z12 z {y} bx = subst (λ k → k o< & A) (sym (BX.is-fb bx)) (c<→o< {!!})  
+     B :  (z : ZChain A (& A) ) → HOD
+     B z = {!!}
+     z11 :  (z : ZChain A (& A) ) → (x : Element (B z)) → elm x ≡  {!!} 
      z11 z x = subst₂ (λ j k → j ≡ k ) *iso *iso ( cong (*) (BX.is-fb (is-elm x)) )
-     obx : (z : ZChain A (& A) _<_ ) → {x : HOD} → B z ∋ x → Ordinal
+     obx : (z : ZChain A (& A) ) → {x : HOD} → B z ∋ x → Ordinal
      obx z {x} bx = BX.bx bx
-     obx=fb : (z : ZChain A (& A) _<_ ) → {x : HOD} → (bx : B z ∋ x ) → x ≡ ZChain.fb z (BX.bx bx) 
+     obx=fb : (z : ZChain A (& A) ) → {x : HOD} → (bx : B z ∋ x ) → x ≡ {!!}
      obx=fb z {x} bx = subst₂ (λ j k → j ≡ k ) *iso *iso (cong (*) (BX.is-fb bx)) 
-     B⊆A : (z : ZChain A (& A) _<_ ) → B z ⊆ A
-     B⊆A z = record { incl = λ {x} bx → subst (λ k → odef A k ) (sym (BX.is-fb bx)) (ZChain.A∋fb z (BX.bx bx) (BX.bx<y bx) ) }
-     PO-B : (z : ZChain A (& A) _<_ ) → IsPartialOrderSet (B z) _<_
-     PO-B z = ⊆-IsPartialOrderSet (B⊆A z) PO
-     bx-monotonic : (z : ZChain A (& A) _<_ ) → {x y : Element (B z)} → obx z (is-elm x) o< obx z (is-elm y) → elm x < elm y 
-     bx-monotonic z {x} {y} a = subst₂ (λ j k → j < k ) (sym (z11 z x)) (sym (z11 z y)) (ZChain.monotonic z (bx<A z (is-elm x)) (bx<A z (is-elm y)) a ) 
-     bcmp : (z : ZChain A (& A) _<_ ) → Trichotomous (λ (x : Element (B z)) y → elm x ≡ elm y ) (λ x y → elm x < elm y )
+     B⊆A : (z : ZChain A (& A) ) → B z ⊆ A
+     B⊆A z = record { incl = λ {x} bx → subst (λ k → odef A k ) (sym (BX.is-fb bx)) {!!}  }
+     -- PO-B : (z : ZChain A (& A) ) → IsPartialOrderSet (B z) _<_
+     -- PO-B z = ⊆-IsPartialOrderSet (B⊆A z) PO
+     bx-monotonic : (z : ZChain A (& A) ) → {x y : Element (B z)} → obx z (is-elm x) o< obx z (is-elm y) → elm x < elm y 
+     bx-monotonic z {x} {y} a = subst₂ (λ j k → j < k ) (sym (z11 z x)) (sym (z11 z y)) {!!}  
+     bcmp : (z : ZChain A (& A) ) → Trichotomous (λ (x : Element (B z)) y → elm x ≡ elm y ) (λ x y → elm x < elm y )
      bcmp z x y with trio< (obx z (is-elm x)) (obx z (is-elm y))
      ... | tri< a ¬b ¬c = tri< z15 (λ eq → z01 (incl (B⊆A z) (is-elm y)) (incl (B⊆A z) (is-elm x))(case1 (sym eq)) z15 ) z17 where
           z15 :  elm x < elm y
@@ -164,37 +167,45 @@
           z17 lt =  z01 (incl (B⊆A z) (is-elm y)) (incl (B⊆A z) (is-elm x))(case2 lt) z15 
      ... | tri≈ ¬a b ¬c = tri≈ (IsStrictPartialOrder.irrefl PO {isA (B⊆A z) x} {isA (B⊆A z) y} z14) z14 z16 where
           z14 :  elm x ≡ elm y
-          z14 = begin
-                elm x ≡⟨ obx=fb z (is-elm x) ⟩
-                ZChain.fb z (BX.bx (is-elm x)) ≡⟨ cong (ZChain.fb z) b ⟩
-                ZChain.fb z (BX.bx (is-elm y)) ≡⟨ sym ( obx=fb z (is-elm y)) ⟩
-                elm y ∎ where open ≡-Reasoning 
+          z14 = {!!}
           z16 = IsStrictPartialOrder.irrefl PO {isA (B⊆A z) y} {isA (B⊆A z) x} (sym z14)
      ... | tri> ¬a ¬b c = tri> z17 (λ eq → z01 (incl (B⊆A z) (is-elm x)) (incl (B⊆A z) (is-elm y))(case1 eq) z15 ) z15 where
           z15 :  elm y < elm x
           z15 =  bx-monotonic z {y} {x} c
           z17 : elm x < elm y → ⊥
           z17 lt =  z01 (incl (B⊆A z) (is-elm x)) (incl (B⊆A z) (is-elm y))(case2 lt) z15 
-     B-is-total :  (z : ZChain A (& A) _<_ ) → IsTotalOrderSet (B z) _<_ 
+     B-is-total :  (z : ZChain A (& A) ) → IsTotalOrderSet (B z) 
      B-is-total zc = record { isEquivalence = record { refl = refl ; sym = sym ; trans = trans }
          ; trans = λ {x} {y} {z} x<y y<z → IsStrictPartialOrder.trans PO {isA (B⊆A zc) x} {isA (B⊆A zc) y} {isA (B⊆A zc) z} x<y y<z
          ; compare = bcmp zc }
-     ZChain→¬SUP :  (z : ZChain A (& A) _<_ ) →  ¬ (SUP A (B z) _<_ )
-     ZChain→¬SUP z sp = ⊥-elim {!!} where
-         z03 : & (SUP.sup sp) o< osuc (& A)
-         z03 = ordtrans (c<→o< (SUP.A∋maximal sp)) <-osuc
-         z02 :  (x : HOD) → B z ∋ x → SUP.sup sp < x → ⊥
-         z02 x xe s<x = z01 (incl (B⊆A z) xe) (SUP.A∋maximal sp) (SUP.x<sup sp xe) s<x 
-     ind :  HasMaximal =h= od∅
-         → (x : Ordinal) → ((y : Ordinal) → y o< x →  ZChain A y _<_ )
-         →  ZChain A x _<_
-     ind nomx x prev with Oprev-p x
+     ind : (x : Ordinal) → ((y : Ordinal) → y o< x →  ZChain A y ∨ Maximal A )
+         →  ZChain A x ∨ Maximal A 
+     --     has previous ordinal
+     --        has maximal          use this
+     --        else has chain
+     --        & A < y              A is a counter example of assumption
+     --          chack y is maximal 
+     --          y < max              use previous chain
+     --          y = max  (  y > max  cannot happen )
+     --              ¬ A ∋ y           use previous chain
+     --              A ∋ y is use oridinaly min of y or previous
+     --     y is limit ordinal    
+     --        has maximal in some lower   use this
+     --        no maximal in all lower
+     --          & A < y              A is a counter example of assumption
+     --          A ∋ y is maximal      use this            
+     --          ¬ A ∋ y           use previous chain
+     --          check some y ≤ max 
+     --              if none A < y is the counter example
+     --              else use the ordinaly smallest max as next chain
+     ind x prev with Oprev-p x
      ... | yes op with ODC.∋-p O A (* x)
      ... | no ¬Ax = {!!} where
           -- we have previous ordinal and ¬ A ∋ x, use previous Zchain
           px = Oprev.oprev op
-          zc1 : ZChain A px _<_
-          zc1 = prev px (subst (λ k → px o< k) (Oprev.oprev=x op) <-osuc) 
+          zc1 : ZChain A px 
+          zc1 with prev px (subst (λ k → px o< k) (Oprev.oprev=x op) <-osuc) 
+          ... | t = {!!}
           z04 :  {!!} -- (sup : HOD) (as : A ∋ sup) → & sup o< osuc x → sup < ZChain.fb zc1 as
           z04 sup as s<x with trio< (& sup) x
           ... | tri≈ ¬a b ¬c = ⊥-elim (¬Ax (subst (λ k → odef A k) (trans b (sym &iso)) as) )  
@@ -202,33 +213,34 @@
           ... | tri> ¬a ¬b c with  osuc-≡< s<x
           ... | case1 eq = ⊥-elim (¬Ax (subst (λ k → odef A k) (trans eq (sym &iso)) as) )  
           ... | case2 lt = ⊥-elim (¬a lt )
-     ... | yes ax = z06 where -- we have previous ordinal and A ∋ x
+     ... | yes ax = {!!} where -- we have previous ordinal and A ∋ x
           px = Oprev.oprev op
-          zc1 : ZChain A px _<_
-          zc1 = prev px (subst (λ k → px o< k) (Oprev.oprev=x op) <-osuc) 
-          z06 : ZChain A x _<_
-          z06 with is-o∅ (& (Gtx ax))
-          ... | yes nogt = ⊥-elim (no-maximal nomx x ⟪ subst (λ k → odef A k) &iso ax , x-is-maximal ⟫ ) where -- no larger element, so it is maximal
-              x-is-maximal :  (m : Ordinal) → odef A m → ¬ (* x < * m)
-              x-is-maximal m am  =  ¬x<m   where
-                 ¬x<m :  ¬ (* x < * m)
-                 ¬x<m x<m = ∅< {Gtx ax} {* m} ⟪ subst (λ k → odef A k) (sym &iso) am , subst (λ k → * x < k ) (cong (*) (sym &iso)) x<m ⟫  (≡o∅→=od∅ nogt) 
-          ... | no not = {!!} where
-     ind nomx x prev | no ¬ox with trio< (& A) x   --- limit ordinal case
+          zc1 : ZChain A px 
+          zc1 with  prev px (subst (λ k → px o< k) (Oprev.oprev=x op) <-osuc) 
+          ... | t = {!!}
+     ind x prev | no ¬ox with trio< (& A) x   --- limit ordinal case
      ... | tri< a ¬b ¬c = {!!} where
-          zc1 : ZChain A (& A) _<_
-          zc1 = prev (& A) a 
+          zc1 : ZChain A (& A) 
+          zc1 with prev (& A) a 
+          ... | t = {!!}
      ... | tri≈ ¬a b ¬c = {!!} where
      ... | tri> ¬a ¬b c with ODC.∋-p O A (* x)
      ... | no ¬Ax = {!!} where
      ... | yes ax with is-o∅ (& (Gtx ax))
-     ... | yes nogt = ⊥-elim (no-maximal nomx x ⟪ subst (λ k → odef A k) &iso ax , x-is-maximal ⟫ ) where -- no larger element, so it is maximal
+     ... | yes nogt = ⊥-elim {!!} where -- no larger element, so it is maximal
               x-is-maximal :  (m : Ordinal) → odef A m → ¬ (* x < * m)
               x-is-maximal m am  =  ¬x<m   where
                  ¬x<m :  ¬ (* x < * m)
                  ¬x<m x<m = ∅< {Gtx ax} {* m} ⟪ subst (λ k → odef A k) (sym &iso) am , subst (λ k → * x < k ) (cong (*) (sym &iso)) x<m ⟫  (≡o∅→=od∅ nogt) 
      ... | no not = {!!} where
-     zorn00 : Maximal A _<_
+     zorn03 : (x : Ordinal) → ZChain A x  ∨ Maximal A 
+     zorn03 x with TransFinite ind  x
+     ... | t = {!!}
+     zorn04 : Maximal A 
+     zorn04 with zorn03 (& A)
+     ... | case1 chain = {!!}
+     ... | case2 m = m
+     zorn00 : Maximal A 
      zorn00 with is-o∅ ( & HasMaximal )
      ... | no not = record { maximal = ODC.minimal O HasMaximal  (λ eq → not (=od∅→≡o∅ eq)) ; A∋maximal = zorn01 ; ¬maximal<x  = zorn02 } where
          -- yes we have the maximal
@@ -238,17 +250,18 @@
          zorn01 =  proj1 hasm
          zorn02 : {x : HOD} → A ∋ x → ¬ (ODC.minimal O HasMaximal (λ eq → not (=od∅→≡o∅ eq)) < x)
          zorn02 {x} ax m<x = ((proj2 hasm) (& x) ax) (subst₂ (λ j k → j < k) (sym *iso) (sym *iso) m<x )
-     ... | yes ¬Maximal = ⊥-elim {!!} where
+     ... | yes ¬Maximal = {!!} where
          -- if we have no maximal, make ZChain, which contradict SUP condition
-         z : (x : Ordinal) → HasMaximal =h= od∅  → ZChain A x _<_ 
-         z x nomx = TransFinite (ind nomx) x
+         z : (x : Ordinal) → HasMaximal =h= od∅  → ZChain A x  ∨ Maximal A 
+         z x nomx with TransFinite {!!} x
+         ... | t = {!!}
 
-_⊆'_ : ( A B : HOD ) → Set n
-_⊆'_ A B = (x : Ordinal ) → odef A x → odef B x
+-- _⊆'_ : ( A B : HOD ) → Set n
+-- _⊆'_ A B = (x : Ordinal ) → odef A x → odef B x
 
-MaximumSubset : {L P : HOD} 
-       → o∅ o< & L →  o∅ o< & P → P ⊆ L
-       → IsPartialOrderSet P _⊆'_
-       → ( (B : HOD) → B ⊆ P → IsTotalOrderSet B _⊆'_ → SUP P B _⊆'_ )
-       → Maximal P (_⊆'_)
-MaximumSubset {L} {P} 0<L 0<P P⊆L PO SP  = Zorn-lemma {P} {_⊆'_} 0<P PO SP
+-- MaximumSubset : {L P : HOD} 
+--        → o∅ o< & L →  o∅ o< & P → P ⊆ L
+--        → IsPartialOrderSet P _⊆'_
+--        → ( (B : HOD) → B ⊆ P → IsTotalOrderSet B _⊆'_ → SUP P B _⊆'_ )
+--        → Maximal P (_⊆'_)
+-- MaximumSubset {L} {P} 0<L 0<P P⊆L PO SP  = Zorn-lemma {P} {_⊆'_} 0<P PO SP