view cardinal.agda @ 234:e06b76e5b682

ac from LEM in abstract ordinal
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Tue, 13 Aug 2019 22:21:10 +0900
parents af60c40298a4
children 846e0926bb89
line wrap: on
line source

open import Level
open import Ordinals
module cardinal {n : Level } (O : Ordinals {n}) where

open import zf
open import logic
import OD 
open import Data.Nat renaming ( zero to Zero ; suc to Suc ;  ℕ to Nat ; _⊔_ to _n⊔_ ) 
open import Relation.Binary.PropositionalEquality
open import Data.Nat.Properties 
open import Data.Empty
open import Relation.Nullary
open import Relation.Binary
open import Relation.Binary.Core

open inOrdinal O
open OD O
open OD.OD

open _∧_
open _∨_
open Bool

-- we have to work on Ordinal to keep OD Level n
-- since we use p∨¬p which works only on Level n

<_,_> : (x y : OD) → OD
< x , y > = (x , x ) , (x , y )

record SetProduct ( A B : OD ) (x : Ordinal ) : Set n where
   field
      π1 : Ordinal
      π2 : Ordinal
      A∋π1 : def A π1
      B∋π2 : def B π2
      -- opair :  x ≡ od→ord (Ord ( omax (omax π1 π1)  (omax π1 π2) )) -- < π1 , π2 >

open SetProduct

∋-p : (A x : OD ) → Dec ( A ∋ x ) 
∋-p A x with p∨¬p ( A ∋ x )
∋-p A x | case1 t = yes t
∋-p A x | case2 t = no t

_⊗_  : (A B : OD) → OD
A ⊗ B  = record { def = λ x → SetProduct A B x }
-- A ⊗ B  = record { def = λ x → (y z : Ordinal) → def A y ∧ def B z ∧ ( x ≡ od→ord (< ord→od y , ord→od z >) ) }

--  Power (Power ( A ∪ B )) ∋ ( A ⊗ B )

Func :  ( A B : OD ) → OD
Func A B = record { def = λ x → def (Power (A ⊗ B)) x } 

-- power→ :  ( A t : OD) → Power A ∋ t → {x : OD} → t ∋ x → ¬ ¬ (A ∋ x)

func←od : { dom cod : OD } → {f : Ordinal }  → def (Func dom cod ) f → (Ordinal → Ordinal )
func←od {dom} {cod} {f} lt x = sup-o ( λ y → lemma  y ) where
   lemma1 = subst (λ k → def (Power (dom ⊗ cod)) k ) (sym {!!}) lt
   lemma : Ordinal → Ordinal
   lemma y with IsZF.power→ isZF (dom ⊗ cod) (ord→od f) (subst (λ k → def (Power (dom ⊗ cod)) k ) {!!} lt ) | ∋-p (ord→od f) (ord→od y)
   lemma y | p | no n  = o∅
   lemma y | p | yes f∋y with double-neg-eilm ( p {ord→od y} f∋y ) -- p : {x : OD} → f ∋ x → ¬ ¬ (dom ⊗ cod ∋ x)
   ... | t with decp ( x  ≡ π1 t )
   ... | yes _ = π2 t
   ... | no _ = o∅

func→od : (f : Ordinal → Ordinal ) → ( dom : OD ) → OD 
func→od f dom = Replace dom ( λ x →  < x , ord→od (f (od→ord x)) > )


-- contra position of sup-o<
--

postulate
  -- contra-position of mimimulity of supermum required in Cardinal
  sup-x  : ( Ordinal  → Ordinal ) →  Ordinal 
  sup-lb : { ψ : Ordinal  →  Ordinal } → {z : Ordinal }  →  z o< sup-o ψ → z o< osuc (ψ (sup-x ψ))

------------
--
-- Onto map
--          def X x ->  xmap
--     X ---------------------------> Y
--          ymap   <-  def Y y
--
record Onto  (X Y : OD )  : Set n where
   field
       xmap : Ordinal 
       ymap : Ordinal 
       xfunc : def (Func X Y) xmap 
       yfunc : def (Func Y X) ymap 
       onto-iso   : {y :  Ordinal  } → (lty : def Y y ) →
          func←od {X} {Y} {xmap} xfunc ( func←od  yfunc y )  ≡ y

open Onto

onto-restrict : {X Y Z : OD} → Onto X Y → ({x : OD} → _⊆_ Z Y {x}) → Onto X Z
onto-restrict {X} {Y} {Z} onto  Z⊆Y = record {
     xmap = xmap1
   ; ymap = zmap
   ; xfunc = xfunc1
   ; yfunc = zfunc
   ; onto-iso = onto-iso1
  } where
       xmap1 : Ordinal 
       xmap1 = od→ord (Select (ord→od (xmap onto)) {!!} ) 
       zmap : Ordinal 
       zmap = {!!}
       xfunc1 : def (Func X Z) xmap1
       xfunc1 = {!!}
       zfunc : def (Func Z X) zmap 
       zfunc = {!!}
       onto-iso1   : {z :  Ordinal  } → (ltz : def Z z ) → func←od  xfunc1 ( func←od  zfunc z )  ≡ z
       onto-iso1   = {!!}


record Cardinal  (X  : OD ) : Set n where
   field
       cardinal : Ordinal 
       conto : Onto X (Ord cardinal)  
       cmax : ( y : Ordinal  ) → cardinal o< y → ¬ Onto X (Ord y)  

cardinal :  (X  : OD ) → Cardinal X
cardinal  X = record {
       cardinal = sup-o ( λ x → proj1 ( cardinal-p x) )
     ; conto = onto
     ; cmax = cmax
   } where
    cardinal-p : (x  : Ordinal ) →  ( Ordinal  ∧ Dec (Onto X (Ord x) ) )
    cardinal-p x with p∨¬p ( Onto X (Ord x)  ) 
    cardinal-p x | case1 True  = record { proj1 = x  ; proj2 = yes True }
    cardinal-p x | case2 False = record { proj1 = o∅ ; proj2 = no False }
    S = sup-o (λ x → proj1 (cardinal-p x))
    lemma1 :  (x : Ordinal) → ((y : Ordinal) → y o< x → Lift (suc n) (y o< (osuc S) → Onto X (Ord y))) →
                    Lift (suc n) (x o< (osuc S) → Onto X (Ord x) )
    lemma1 x prev with trio< x (osuc S)
    lemma1 x prev | tri< a ¬b ¬c with osuc-≡< a
    lemma1 x prev | tri< a ¬b ¬c | case1 x=S = lift ( λ lt → {!!} )
    lemma1 x prev | tri< a ¬b ¬c | case2 x<S = lift ( λ lt → lemma2 ) where
         lemma2 : Onto X (Ord x) 
         lemma2 with prev {!!} {!!}
         ... | lift t = t {!!}
    lemma1 x prev | tri≈ ¬a b ¬c = lift ( λ lt → ⊥-elim ( o<¬≡ b lt ))
    lemma1 x prev | tri> ¬a ¬b c = lift ( λ lt → ⊥-elim ( o<> c lt ))
    onto : Onto X (Ord S) 
    onto with TransFinite {λ x → Lift (suc n) ( x o< osuc S → Onto X (Ord x) ) } lemma1 S 
    ... | lift t = t <-osuc  
    cmax : (y : Ordinal) → S o< y → ¬ Onto X (Ord y) 
    cmax y lt ontoy = o<> lt (o<-subst  {_} {_} {y} {S}
       (sup-o<  {λ x → proj1 ( cardinal-p x)}{y}  ) lemma refl ) where
          lemma : proj1 (cardinal-p y) ≡ y
          lemma with  p∨¬p ( Onto X (Ord y) )
          lemma | case1 x = refl
          lemma | case2 not = ⊥-elim ( not ontoy )


-----
--  All cardinal is ℵ0,  since we are working on Countable Ordinal, 
--  Power ω is larger than ℵ0, so it has no cardinal.