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

changeset 667:c6cd972b468c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
...
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Mon, 04 Jul 2022 21:58:07 +0900
parents 431d074311f5
children f40388701930
files src/zorn.agda
diffstat 1 files changed, 45 insertions(+), 54 deletions(-) [+]
line wrap: on
line diff
--- a/src/zorn.agda	Mon Jul 04 21:25:38 2022 +0900
+++ b/src/zorn.agda	Mon Jul 04 21:58:07 2022 +0900
@@ -284,14 +284,10 @@
 ChainF : (A : HOD) →  ( f : Ordinal → Ordinal )  (mf : ≤-monotonic-f A f) {y : Ordinal} (ay : odef A y) → (chain : HOD ) → Chain A f mf ay (& A) chain → (x : Ordinal) → x o< & A →  HOD
 ChainF A f mf {y} ay chain Ch x x<a = {!!}
 
-record ZChain1 ( A : HOD )    ( f : Ordinal → Ordinal )  (mf : ≤-monotonic-f A f) {y : Ordinal } (ay : odef A y ) ( z : Ordinal ) : Set (Level.suc n) where
+record ZChain ( A : HOD )    ( f : Ordinal → Ordinal )  (mf : ≤-monotonic-f A f) {init : Ordinal} (ay : odef A init) ( z : Ordinal )  : Set (Level.suc n) where
    field
       chain : HOD
       chain-uniq : Chain A f mf ay z chain 
-
-record ZChain ( A : HOD )    ( f : Ordinal → Ordinal )  (mf : ≤-monotonic-f A f) {init : Ordinal} (ay : odef A init) ( z : Ordinal )   : Set (Level.suc n) where
-   field
-      chain : HOD
       chain⊆A : chain ⊆' A
       chain∋init : odef chain init
       initial : {y : Ordinal } → odef chain y → * init ≤ * y
@@ -364,21 +360,21 @@
      cf-is-≤-monotonic : (nmx : ¬ Maximal A ) →  ≤-monotonic-f A ( cf nmx )
      cf-is-≤-monotonic nmx x ax = ⟪ case2 (proj1 ( cf-is-<-monotonic nmx x ax  ))  , proj2 ( cf-is-<-monotonic nmx x ax  ) ⟫
 
-     sp0 : ( f : Ordinal → Ordinal ) → (mf : ≤-monotonic-f A f ) (zc0 : ZChain1 A f mf as0 (& A) ) (zc : ZChain A f mf as0 (& A) ) 
+     sp0 : ( f : Ordinal → Ordinal ) → (mf : ≤-monotonic-f A f ) (zc : ZChain A f mf as0  (& A) ) 
         (total : IsTotalOrderSet (ZChain.chain zc) )  → SUP A (ZChain.chain zc)
-     sp0 f mf zc0 zc total = supP (ZChain.chain zc) (ZChain.chain⊆A zc) total 
+     sp0 f mf zc total = supP (ZChain.chain zc) (ZChain.chain⊆A zc) total 
      zc< : {x y z : Ordinal} → {P : Set n} → (x o< y → P) → x o< z → z o< y → P
      zc< {x} {y} {z} {P} prev x<z z<y = prev (ordtrans x<z z<y)
 
      ---
      --- the maximum chain  has fix point of any ≤-monotonic function
      ---
-     fixpoint :  ( f : Ordinal → Ordinal ) → (mf : ≤-monotonic-f A f ) (zc0 : ZChain1 A f mf as0 (& A)) (zc : ZChain A f mf as0 (& A) )
+     fixpoint :  ( f : Ordinal → Ordinal ) → (mf : ≤-monotonic-f A f )  (zc : ZChain A f mf as0 (& A)   )
             → (total : IsTotalOrderSet (ZChain.chain zc) )
-            → f (& (SUP.sup (sp0 f mf zc0 zc total ))) ≡ & (SUP.sup (sp0 f mf zc0 zc  total))
-     fixpoint f mf zc0 zc total = z14 where
+            → f (& (SUP.sup (sp0 f mf zc total ))) ≡ & (SUP.sup (sp0 f mf zc  total))
+     fixpoint f mf zc total = z14 where
            chain = ZChain.chain zc
-           sp1 = sp0 f mf zc0 zc total
+           sp1 = sp0 f mf zc total
            z10 :  {a b : Ordinal } → (ca : odef chain a ) → b o< osuc (& A) → (ab : odef A b ) 
               →  HasPrev A chain ab f ∨  IsSup A chain {b} ab -- (supO  chain  (ZChain.chain⊆A zc) (ZChain.f-total zc) ≡ b )
               → * a < * b  → odef chain b
@@ -401,7 +397,7 @@
                    ... | case1 y=p = case1 (subst (λ k → k ≡ _ ) &iso ( cong (&) y=p ))
                    ... | case2 y<p = case2 (subst (λ k → * y < k ) (sym *iso) y<p )
                    -- λ {y} zy → subst (λ k → (y ≡ & k ) ∨ (y << & k)) ?  (SUP.x<sup sp1 ? ) }
-           z14 :  f (& (SUP.sup (sp0 f mf zc0 zc total ))) ≡ & (SUP.sup (sp0 f mf zc0 zc total ))
+           z14 :  f (& (SUP.sup (sp0 f mf zc total ))) ≡ & (SUP.sup (sp0 f mf zc total ))
            z14 with total (subst (λ k → odef chain k) (sym &iso)  (ZChain.f-next zc z12 )) z12 
            ... | tri< a ¬b ¬c = ⊥-elim z16 where
                z16 : ⊥
@@ -422,14 +418,14 @@
      -- ZChain forces fix point on any ≤-monotonic function (fixpoint)
      -- ¬ Maximal create cf which is a <-monotonic function by axiom of choice. This contradicts fix point of ZChain
      --
-     z04 :  (nmx : ¬ Maximal A ) → (zc0 : ZChain1 A (cf nmx) (cf-is-≤-monotonic nmx)  as0 (& A)) (zc : ZChain A (cf nmx) (cf-is-≤-monotonic nmx) as0 (& A) ) 
+     z04 :  (nmx : ¬ Maximal A ) →  (zc : ZChain A (cf nmx) (cf-is-≤-monotonic nmx) as0 (& A)  ) 
            → IsTotalOrderSet (ZChain.chain zc) → ⊥
-     z04 nmx zc0 zc total = <-irr0  {* (cf nmx c)} {* c} (subst (λ k → odef A k ) (sym &iso) (proj1 (is-cf nmx (SUP.A∋maximal  sp1 ))))
+     z04 nmx zc total = <-irr0  {* (cf nmx c)} {* c} (subst (λ k → odef A k ) (sym &iso) (proj1 (is-cf nmx (SUP.A∋maximal  sp1 ))))
                                                (subst (λ k → odef A (& k)) (sym *iso) (SUP.A∋maximal sp1) )
-           (case1 ( cong (*)( fixpoint (cf nmx) (cf-is-≤-monotonic nmx ) zc0 zc total ))) -- x ≡ f x ̄
+           (case1 ( cong (*)( fixpoint (cf nmx) (cf-is-≤-monotonic nmx ) zc total ))) -- x ≡ f x ̄
            (proj1 (cf-is-<-monotonic nmx c (SUP.A∋maximal sp1 ))) where          -- x < f x
           sp1 : SUP A (ZChain.chain zc)
-          sp1 = sp0 (cf nmx) (cf-is-≤-monotonic nmx) zc0 zc total
+          sp1 = sp0 (cf nmx) (cf-is-≤-monotonic nmx) zc total
           c = & (SUP.sup sp1)
 
      --
@@ -437,62 +433,62 @@
      --
 
      sind : ( f : Ordinal → Ordinal ) → (mf : ≤-monotonic-f A f ) {y : Ordinal} (ay : odef A y) → (x : Ordinal)
-         → ((z : Ordinal) → z o< x → ZChain1 A f mf ay z ∧ ZChain A f mf ay z ) → ZChain1 A f mf ay x  ∧ ZChain A f mf ay x
+         → ((z : Ordinal) → z o< x → ZChain A f mf ay z ) → ZChain A f mf ay x
      sind f mf {y} ay x prev  with Oprev-p x
      ... | yes op = sc4 where
-          open ZChain1
+          open ZChain
           px = Oprev.oprev op
           px<x : px o< x
           px<x = subst (λ k → px o< k) (Oprev.oprev=x op) <-osuc 
-          sc : ZChain1 A f mf ay px 
-          sc = proj1 (prev px px<x)
-          sc4 : ZChain1 A f mf ay x ∧ ZChain A f mf ay x
+          sc : ZChain A f mf ay px 
+          sc = prev px px<x
+          sc4 : ZChain A f mf ay x 
           sc4 with ODC.∋-p O A (* x)
-          ... | no noax = ⟪ record { chain = chain sc ; chain-uniq = ch-noax op (subst (λ k → ¬ odef A k) &iso noax) ( chain-uniq sc )  }  , ? ⟫
-          ... | yes ax with ODC.p∨¬p O ( HasPrev A (ZChain1.chain sc ) ax f )   
-          ... | case1 pr = ⟪ record { chain = chain sc ; chain-uniq = ch-hasprev op (subst (λ k → odef A k) &iso ax) ( chain-uniq sc ) 
-                                       record { y = HasPrev.y pr  ; ay = HasPrev.ay pr  ; x=fy = sc6 } } , ? ⟫ where
+          ... | no noax =  record { chain = ? ; chain-uniq = ch-noax op (subst (λ k → ¬ odef A k) &iso noax) ( chain-uniq sc )  }  
+          ... | yes ax with ODC.p∨¬p O ( HasPrev A (ZChain.chain sc ) ax f )   
+          ... | case1 pr = record { chain = chain sc ; chain-uniq = ch-hasprev op (subst (λ k → odef A k) &iso ax) ( chain-uniq sc ) 
+                                       record { y = HasPrev.y pr  ; ay = HasPrev.ay pr  ; x=fy = sc6 } }  where
                 sc6 : x ≡ f (HasPrev.y pr)
                 sc6 = subst (λ k → k ≡ f (HasPrev.y pr) ) &iso  ( HasPrev.x=fy pr  )
-          ... | case2 ¬fy<x with ODC.p∨¬p O (IsSup A (ZChain1.chain sc ) ax )
-          ... | case1 is-sup = ⟪ record { chain = schain ; chain-uniq = sc9 } , ? ⟫ where
+          ... | case2 ¬fy<x with ODC.p∨¬p O (IsSup A (ZChain.chain sc ) ax )
+          ... | case1 is-sup =  record { chain = schain ; chain-uniq = sc9 }  where
                 schain : HOD
-                schain = record { od = record { def = λ z → odef A z ∧ ( odef (ZChain1.chain sc ) z ∨ (FClosure A f x z)) } 
+                schain = record { od = record { def = λ z → odef A z ∧ ( odef (ZChain.chain sc ) z ∨ (FClosure A f x z)) } 
                     ; odmax = & A ; <odmax = λ {y} sy → ∈∧P→o< sy }
                 sc7 : ¬ HasPrev A (chain sc) (subst (λ k → odef A k) &iso ax) f
                 sc7 not = ¬fy<x record { y = HasPrev.y not ; ay = HasPrev.ay not ; x=fy = subst (λ k → k ≡ _) (sym &iso) (HasPrev.x=fy not ) }
                 sc9 : Chain A f mf ay x schain
-                sc9 = ch-is-sup op (subst (λ k → odef A k) &iso ax) (ZChain1.chain-uniq sc) sc7
+                sc9 = ch-is-sup op (subst (λ k → odef A k) &iso ax) (ZChain.chain-uniq sc) sc7
                     record { x<sup = λ {z} lt → subst (λ k → (z ≡ k ) ∨ (z << k )) &iso (IsSup.x<sup is-sup lt) }
-          ... | case2 ¬x=sup = ⟪ record { chain = chain sc ; chain-uniq = ch-skip op (subst (λ k → odef A k) &iso ax) (ZChain1.chain-uniq sc) sc17 sc10 } , ? ⟫ where
+          ... | case2 ¬x=sup = record { chain = chain sc ; chain-uniq = ch-skip op (subst (λ k → odef A k) &iso ax) (ZChain.chain-uniq sc) sc17 sc10 }  where
                 sc17 : ¬ HasPrev A (chain sc) (subst (λ k → odef A k) &iso ax) f
                 sc17 not = ¬fy<x record { y = HasPrev.y not ; ay = HasPrev.ay not ; x=fy = subst (λ k → k ≡ _) (sym &iso) (HasPrev.x=fy not ) }
                 sc10 : ¬ IsSup A (chain sc) (subst (λ k → odef A k) &iso ax)
                 sc10 not = ¬x=sup ( record { x<sup  = λ {z} lt → subst (λ k → (z ≡ k ) ∨ (z << k ) ) (sym &iso) ( IsSup.x<sup not lt ) }  )
      ... | no ¬ox = sc4 where
           chainf : (z : Ordinal) → z o< x → HOD
-          chainf z z<x = ZChain1.chain ( proj1 (prev z z<x ) )
+          chainf z z<x = ZChain.chain ( prev z z<x  )
           chainq : ( z : Ordinal ) → (z<x : z o< x ) → Chain A f mf ay z ( chainf z z<x )
-          chainq z z<x = ZChain1.chain-uniq ( proj1 ( prev z z<x) )
-          sc4 : ZChain1 A f mf ay x ∧ ZChain A f mf ay x
+          chainq z z<x = ZChain.chain-uniq (  prev z z<x )
+          sc4 : ZChain A f mf ay x 
           sc4 with ODC.∋-p O A (* x)
-          ... | no noax = ⟪ record { chain = UnionCF A x chainf ; chain-uniq = ch-noax-union ¬ox (subst (λ k → ¬ odef A k) &iso noax) ? ? }  , ? ⟫
+          ... | no noax =  record { chain = UnionCF A x chainf ; chain-uniq = ch-noax-union ¬ox (subst (λ k → ¬ odef A k) &iso noax) ? ? }  
           ... | yes ax with ODC.p∨¬p O ( HasPrev A (UnionCF A x chainf) ax f )   
-          ... | case1 pr = ⟪ record { chain = UnionCF A x chainf  ; chain-uniq = ch-hasprev-union ¬ox (subst (λ k → odef A k) &iso ax) ? ? ? } , ? ⟫
+          ... | case1 pr = record { chain = UnionCF A x chainf  ; chain-uniq = ch-hasprev-union ¬ox (subst (λ k → odef A k) &iso ax) ? ? ? } 
           ... | case2 ¬fy<x with ODC.p∨¬p O (IsSup A (UnionCF A x chainf) ax )
           ... | case1 is-sup = ?
           ... | case2 ¬x=sup = ?
 
      ind : ( f : Ordinal → Ordinal ) → (mf : ≤-monotonic-f A f ) {y : Ordinal} (ay : odef A y) → (x : Ordinal) 
-         → ((z : Ordinal) → z o< x → (zc1 : ZChain1 A f mf ay z) → ZChain A f mf ay z ) → (zc0 :  ZChain1 A f mf ay x ) → ZChain A f mf ay x 
-     ind f mf {y} ay x prev zc0 with Oprev-p x
+         → ((z : Ordinal) → z o< x →  ZChain A f mf ay z ) → ZChain A f mf ay x 
+     ind f mf {y} ay x prev with Oprev-p x
      ... | yes op = zc4 where
           --
           -- we have previous ordinal to use induction
           --
           px = Oprev.oprev op
           supf : Ordinal → HOD
-          supf x = ZChain1.chain zc0 
+          supf x = ? -- ZChain.chain zc0 
           zc : ZChain A f mf ay (Oprev.oprev op) 
           zc = ? -- prev px (subst (λ k → px o< k) (Oprev.oprev=x op) <-osuc ) 
           zc-b<x : (b : Ordinal ) → b o< x → b o< osuc px
@@ -633,10 +629,10 @@
                 ... | case2 b=sup = ⊥-elim ( ¬x=sup record { 
                       x<sup = λ {y} zy → subst (λ k → (y ≡ k) ∨ (y << k)) (trans b=x (sym &iso)) (IsSup.x<sup b=sup zy)  } ) 
      ... | no ¬ox = zc5 where --- limit ordinal case
-          chainf : (zc : ZChain1 A f mf ay x ) → (z : Ordinal) → z o< x → HOD
-          chainf zc z z<x = ?
+          -- chainf : (zc : ZChain1 A f mf ay x ) → (z : Ordinal) → z o< x → HOD
+          -- chainf zc z z<x = ?
           uzc : HOD
-          uzc = UnionCF A x (chainf zc0)
+          uzc = UnionCF A x ? 
           zc5 : ZChain A f mf ay x 
           zc5 with ODC.∋-p O A (* x)
           ... | no noax = ? where -- ¬ A ∋ p, just skip
@@ -645,13 +641,13 @@
           ... | case2 ¬fy<x with ODC.p∨¬p O (IsSup A uzc ax )
           ... | case1 is-sup = ? -- x is a sup of zc 
           ... | case2 ¬x=sup = ? where -- x is not f y' nor sup of former ZChain from y -- no extention
-              chainf0 : (zc : ZChain1 A f mf ay x ) → (z : Ordinal) → z o< x → HOD
-              chainf0 zc z z<x with ZChain1.chain-uniq zc0
-              ... | t = ?
+              -- chainf0 : (zc : ZChain1 A f mf ay x ) → (z : Ordinal) → z o< x → HOD
+              -- chainf0 zc z z<x with ZChain1.chain-uniq zc0
+              -- ... | t = ?
               supf : Ordinal → HOD
-              supf x = ZChain1.chain zc0 
+              supf x = ? -- ZChain1.chain zc0 
               Uz : HOD
-              Uz = UnionCF A x ( chainf0 zc0 )
+              Uz = UnionCF A x ?
               u-next : {z : Ordinal} → odef Uz z → odef Uz (f z)
               u-next {z} = {!!}
               -- (case1 u) = case1 record { u = UChain.u u ; u<x = UChain.u<x u ; chain∋z = ZChain.f-next ( uzc u ) (UChain.chain∋z u)  }
@@ -664,7 +660,7 @@
               u-chain∋init = {!!} -- case2 ( init ay )
               supf0 : Ordinal → HOD
               supf0 z with trio< z x
-              ... | tri< a ¬b ¬c = ZChain1.chain zc0 
+              ... | tri< a ¬b ¬c = ? --  ZChain1.chain zc0 
               ... | tri≈ ¬a b ¬c = Uz 
               ... | tri> ¬a ¬b c = Uz
               u-mono :  {z : Ordinal} {w : Ordinal} → z o≤ w → w o≤ x → supf0 z ⊆' supf0 w
@@ -672,11 +668,8 @@
               ... | s | t = {!!}
 
          
-     SZ0 : ( f : Ordinal → Ordinal ) → (mf : ≤-monotonic-f A f ) → {y : Ordinal} (ay : odef A y) → (x : Ordinal) → ZChain1 A f mf ay x ∧ ZChain A f mf ay x
-     SZ0 f mf ay x = TransFinite {λ z → ZChain1 A f mf ay z ∧ ZChain A f mf ay z } (sind f mf ay ) x
-
      SZ : ( f : Ordinal → Ordinal ) → (mf : ≤-monotonic-f A f ) → {y : Ordinal} (ay : odef A y) → ZChain A f mf ay (& A) 
-     SZ f mf {y} ay = TransFinite {λ z → (zc1 : ZChain1 A f mf ay z ) → ZChain A f mf ay z } (λ x zc0 → ind f mf ay x zc0   ) (& A) ?
+     SZ f mf {y} ay = TransFinite {λ z → ZChain A f mf ay z } (λ x → ind f mf ay x ) (& A) 
 
      zorn00 : Maximal A 
      zorn00 with is-o∅ ( & HasMaximal )  -- we have no Level (suc n) LEM 
@@ -688,14 +681,12 @@
          zorn01  = proj1  zorn03  
          zorn02 : {x : HOD} → A ∋ x → ¬ (ODC.minimal O HasMaximal (λ eq → not (=od∅→≡o∅ eq)) < x)
          zorn02 {x} ax m<x = proj2 zorn03 (& x) ax (subst₂ (λ j k → j < k) (sym *iso) (sym *iso) m<x )
-     ... | yes ¬Maximal = ⊥-elim ( z04 nmx (zc0 (& A)) zorn04 total ) where
+     ... | yes ¬Maximal = ⊥-elim ( z04 nmx  zorn04 total ) where
          -- if we have no maximal, make ZChain, which contradict SUP condition
          nmx : ¬ Maximal A 
          nmx mx =  ∅< {HasMaximal} zc5 ( ≡o∅→=od∅  ¬Maximal ) where
               zc5 : odef A (& (Maximal.maximal mx)) ∧ (( y : Ordinal ) →  odef A y → ¬ (* (& (Maximal.maximal mx)) < * y)) 
               zc5 = ⟪  Maximal.A∋maximal mx , (λ y ay mx<y → Maximal.¬maximal<x mx (subst (λ k → odef A k ) (sym &iso) ay) (subst (λ k → k < * y) *iso mx<y) ) ⟫
-         zc0 : (x : Ordinal) → ZChain1 A  (cf nmx) (cf-is-≤-monotonic nmx) as0 x
-         zc0 x = proj1 ( TransFinite {λ z → ZChain1 A (cf nmx) (cf-is-≤-monotonic nmx)  as0 z ∧ _ } (sind (cf nmx) (cf-is-≤-monotonic nmx)  as0) x )
          zorn04 : ZChain A (cf nmx) (cf-is-≤-monotonic nmx) as0 (& A)  
          zorn04 = SZ (cf nmx) (cf-is-≤-monotonic nmx) (subst (λ k → odef A k ) &iso as ) 
          total : IsTotalOrderSet (ZChain.chain zorn04)