123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602 |
- module SET where
- ----------------------------------------------------------------------------
- -- Auxiliary.
- ----------------------------------------------------------------------------
- data Fun (X Y : Set) : Set where
- fun : (X -> Y) -> Fun X Y
- {-
- Unop : Set -> Set
- Unop X = Fun X X
- Binop : Set -> Set
- Binop X = Fun X (Fun X X)
- -}
- -- We need to replace Pred X by its RHS (less readable!)
- -- Pred : Set -> Set1
- -- Pred X = X -> Set
- -- Pow = Pred
- -- Rel : Set -> Set1
- -- Rel X = X -> X -> Set
- data Reflexive {X : Set} (R : X -> X -> Set) : Set where
- reflexive : ((x : X) -> R x x) -> Reflexive R
- data Symmetrical {X : Set} (R : X -> X -> Set) : Set where
- symmetrical : ( {x1 x2 : X} -> R x1 x2 -> R x2 x1) -> Symmetrical R
- {-
- Transitive {X : Set}(R : X -> X -> Set) : Set
- = (x1 x2 x3 : X) |-> R x1 x2 -> R x2 x3 -> R x1 x3
- Compositional {X : Set}(R : X -> X -> Set) : Set
- = (x1 : X) |-> (x2 : X) |-> (x3 : X) |-> R x2 x3 -> R x1 x2 -> R x1 x3
- -}
- data Substitutive {X : Set} (R : X -> X -> Set) : Set1 where
- substitutive : ( (P : X -> Set) -> {x1 x2 : X} -> R x1 x2 -> P x1 -> P x2)
- -> Substitutive R
- {-
- Collapsed (X : Set) : Set1
- = (P : X -> Set) -> (x1 x2 : X) |-> P x1 -> P x2
- id {X : Set} : X -> X
- = \x -> x
- cmp (|X |Y |Z : Set) : (Y -> Z) -> (X -> Y) -> X -> Z
- = \f -> \g -> \x -> f (g x)
- seq (|X |Y |Z : Set)(f : X -> Y)(g : Y -> Z) : X -> Z
- = cmp g f
- const (|X |Y : Set)(x : X)(y : Y) : X
- = x
- proj {X : Set}(Y : X -> Set)(x : X)(f : (x : X) -> Y x) : Y x
- = f x
- flip {X : Set}{Y : Set}{Z : Set}(f : X -> Y -> Z)(y : Y)(x : X) : Z
- = f x y
- FlipRel {X : Set}(R : X -> X -> Set)(x1 : X)(x2 : X) : Set
- = R x2 x1
- ----------------------------------------------------------------------------
- -- Product sets.
- ----------------------------------------------------------------------------
- Prod (X : Set)(Y : X -> Set) : Set
- = (x : X) -> Y x
- mapProd {X : Set}
- {Y1 : X -> Set}
- {Y2 : X -> Set}
- (f : (x : X) -> Y1 x -> Y2 x)
- : Prod X Y1 -> Prod X Y2
- = \g -> \x -> f x (g x)
- -- Fun(X : Set)(Y : Set) = X -> Y
- mapFun (|X1 |X2 |Y1 |Y2 : Set)
- : (X2 -> X1) -> (Y1 -> Y2) -> (X1 -> Y1) -> X2 -> Y2
- = \f -> \g -> \h -> \x ->
- g (h (f x))
- ----------------------------------------------------------------------------
- -- Identity proof sets.
- ----------------------------------------------------------------------------
- Id {X : Set} : X -> X -> Set
- = idata ref (x : X) : _ x x
- refId {X : Set} : Reflexive Id
- = \(x : X) -> ref@_ x
- elimId (|X : Set)
- (C : (x1 x2 : X) |-> Id x1 x2 -> Set)
- (refC : (x : X) -> C (refId x))
- (|x1 |x2 : X)
- (u : Id x1 x2) :
- C u
- = case u of { (ref x) -> refC x;}
- abstract whenId {X : Set}(C : X -> X -> Set)(c : (x : X) -> C x x)
- : (x1 x2 : X) |-> Id x1 x2 -> C x1 x2
- = elimId (\x1 x2 |-> \(u : Id x1 x2) -> C x1 x2) c
- abstract substId {X : Set} : Substitutive Id
- = \(C : X -> Set) ->
- whenId (\x1 x2 -> C x1 -> C x2) (\x -> id)
- abstract mapId {X : Set}{Y : Set}(f : X -> Y)
- : (x1 x2 : X) |-> Id x1 x2 -> Id (f x1) (f x2)
- = whenId (\x1 x2 -> Id (f x1) (f x2)) (\(x : X) -> refId (f x))
- abstract symId {X : Set} : Symmetrical Id
- = whenId (\(x1 x2 : X) -> Id x2 x1) refId
- abstract cmpId {X : Set} : Compositional Id
- = let lem : (x y : X) |-> Id x y -> (z : X) |-> Id z x -> Id z y
- = whenId ( \(x y : _) -> (z : X) |-> Id z x -> Id z y)
- ( \x -> \z |-> id)
- in \(x1 x2 x3 : _) |->
- \(u : Id x2 x3) ->
- \(v : Id x1 x2) ->
- lem u v
- abstract tranId {X : Set} : Transitive Id
- = \(x1 x2 x3 : X) |->
- \(u : Id x1 x2) ->
- \(v : Id x2 x3) ->
- cmpId v u
- ----------------------------------------------------------------------------
- -- The empty set.
- ----------------------------------------------------------------------------
- -}
- data Zero : Set where
- {-
- abstract whenZero (X : Set)(z : Zero) : X
- = case z of { }
- elimZero (C : Zero -> Set)(z : Zero) : C z
- = case z of { }
- abstract collZero : Collapsed Zero
- = \(C : Zero -> Set) ->
- \(z1 z2 : Zero) |->
- \(c : C z1) ->
- case z1 of { }
- ----------------------------------------------------------------------------
- -- The singleton set.
- ----------------------------------------------------------------------------
- -}
- data Unit : Set where
- unit : Unit
- {-
- elUnit = tt
- elimUnit (C : Unit -> Set)(c_tt : C tt@_)(u : Unit) : C u
- = case u of { (tt) -> c_tt;}
- abstract collUnit : Collapsed Unit
- = \(C : Unit -> Set) ->
- \(u1 u2 : Unit) |->
- \(c : C u1) ->
- case u1 of { (tt) -> case u2 of { (tt) -> c;};}
- ----------------------------------------------------------------------------
- -- The successor set adds a new element.
- ----------------------------------------------------------------------------
- Succ (X : Set) : Set
- = data zer | suc (x : X)
- zerSucc {X : Set} : Succ X
- = zer@_
- sucSucc {X : Set}(x : X) : Succ X
- = suc@_ x
- elimSucc {X : Set}
- (C : Succ X -> Set)
- (c_z : C zer@_)
- (c_s : (x : X) -> C (suc@_ x))
- (x' : Succ X)
- : C x'
- = case x' of {
- (zer) -> c_z;
- (suc x) -> c_s x;}
- whenSucc (|X |Y : Set)(y_z : Y)(y_s : X -> Y)(x' : Succ X) : Y
- = case x' of {
- (zer) -> y_z;
- (suc x) -> y_s x;}
- mapSucc (|X |Y : Set)(f : X -> Y) : Succ X -> Succ Y
- = whenSucc zer@(Succ Y) (\(x : X) -> suc@_ (f x)) -- (Succ Y)
- ----------------------------------------------------------------------------
- -- The (binary) disjoint union.
- ----------------------------------------------------------------------------
- data Plus (X Y : Set) = inl (x : X) | inr (y : Y)
- elimPlus (|X |Y : Set)
- (C : Plus X Y -> Set)
- (c_lft : (x : X) -> C (inl@_ x))
- (c_rgt : (y : Y) -> C (inr@_ y))
- (xy : Plus X Y)
- : C xy
- = case xy of {
- (inl x) -> c_lft x;
- (inr y) -> c_rgt y;}
- when (|X |Y |Z : Set)(f : X -> Z)(g : Y -> Z) : Plus X Y -> Z
- = \xy -> case xy of {
- (inl x) -> f x;
- (inr y) -> g y;}
- whenPlus = when
- mapPlus (|X1 |X2 |Y1 |Y2 : Set)(f : X1 -> X2)(g : Y1 -> Y2)
- : Plus X1 Y1 -> Plus X2 Y2
- = when (\x1 -> inl (f x1)) (\y1 -> inr (g y1))
- swapPlus (|X |Y : Set) : Plus X Y -> Plus Y X
- = when inr inl
- ----------------------------------------------------------------------------
- -- Dependent pairs.
- ----------------------------------------------------------------------------
- Sum (X : Set)(Y : X -> Set) : Set
- = sig{fst : X;
- snd : Y fst;}
- dep_pair {X : Set}{Y : X -> Set}(x : X)(y : Y x) : Sum X Y
- = struct {fst = x; snd = y;}
- dep_fst {X : Set}{Y : X -> Set}(xy : Sum X Y) : X
- = xy.fst
- dep_snd {X : Set}{Y : X -> Set}(xy : Sum X Y) : Y (dep_fst xy)
- = xy.snd
- dep_cur {X : Set}{Y : X -> Set}{Z : Set}(f : Sum X Y -> Z)
- : (x : X) |-> Y x -> Z
- = \x |-> \y -> f (dep_pair x y)
- dep_uncur {X : Set}{Y : X -> Set}{Z : Set}
- : ((x : X) -> Y x -> Z) -> Sum X Y -> Z
- = \(f : (x : X) -> (x' : Y x) -> Z) -> \(xy : Sum X Y) -> f xy.fst xy.snd
- dep_curry {X : Set}
- {Y : X -> Set}
- (Z : Sum X Y -> Set)
- (f : (xy : Sum X Y) -> Z xy)
- : (x : X) -> (y : Y x) -> Z (dep_pair x y)
- = \(x : X) -> \(y : Y x) -> f (dep_pair x y)
- dep_uncurry {X : Set}
- {Y : X -> Set}
- (Z : Sum X Y -> Set)
- (f : (x : X) ->
- (y : Y x) ->
- Z (dep_pair x y))
- (xy : Sum X Y)
- : Z xy
- = f xy.fst xy.snd
- mapSum {X : Set}{Y1 : X -> Set}{Y2 : X -> Set}(f : (x : X) -> Y1 x -> Y2 x)
- : Sum X Y1 -> Sum X Y2
- = \(p : Sum X Y1) -> dep_pair p.fst (f p.fst p.snd)
- elimSum = dep_uncurry
- ----------------------------------------------------------------------------
- -- Nondependent pairs (binary) cartesian product.
- ----------------------------------------------------------------------------
- Times (X : Set)(Y : Set) : Set
- = Sum X (\(x : X) -> Y)
- pair {X : Set}{Y : Set} : X -> Y -> Times X Y
- = \(x : X) ->
- \(y : Y) ->
- struct {
- fst = x;
- snd = y;}
- fst {X : Set}{Y : Set} : Times X Y -> X
- = \(xy : Times X Y) -> xy.fst
- snd {X : Set}{Y : Set} : Times X Y -> Y
- = \(xy : Times X Y) -> xy.snd
- pairfun {X : Set}{Y : Set}{Z : Set}(f : X -> Y)(g : X -> Z)(x : X)
- : Times Y Z
- = pair (f x) (g x)
- mapTimes {X1 : Set}{X2 : Set}{Y1 : Set}{Y2 : Set}
- : (f : X1 -> X2) -> (g : Y1 -> Y2) -> Times X1 Y1 -> Times X2 Y2
- = \(f : (x : X1) -> X2) ->
- \(g : (x : Y1) -> Y2) ->
- \(xy : Times X1 Y1) ->
- pair (f xy.fst) (g xy.snd)
- swapTimes {X : Set}{Y : Set} : Times X Y -> Times Y X
- = pairfun snd fst
- cur {X : Set}{Y : Set}{Z : Set}(f : Times X Y -> Z) : X -> Y -> Z
- = \(x : X) -> \(y : Y) -> f (pair |_ |_ x y)
- uncur {X : Set}{Y : Set}{Z : Set}(f : X -> Y -> Z) : Times X Y -> Z
- = \(xy : Times X Y) -> f xy.fst xy.snd
- curry {X : Set}
- {Y : Set}
- {Z : Times X Y -> Set}
- (f : (xy : Times X Y) -> Z xy)
- : (x : X) ->
- (y : Y) ->
- Z (pair |_ |_ x y)
- = \(x : X) ->
- \(y : Y) ->
- f (pair |_ |_ x y)
- uncurry {X : Set}
- {Y : Set}
- {Z : Times X Y -> Set}
- (f : (x : X) ->
- (y : Y) ->
- Z (pair |_ |_ x y))
- : (xy : Times X Y) -> Z xy
- = \(xy : Times X Y) -> f xy.fst xy.snd
- elimTimes = uncurry
- ----------------------------------------------------------------------------
- -- Natural numbers.
- ----------------------------------------------------------------------------
- Nat : Set
- = data zer | suc (m : Nat)
- zero : Nat
- = zer@_
- succ (x : Nat) : Nat
- = suc@_ x
- elimNat (C : Nat -> Set)
- : (c_z : C zer@_) ->
- (c_s : (x : Nat) -> C x -> C (suc@_ x)) ->
- (m : Nat) ->
- C m
- = \(c_z : C zer@_) ->
- \(c_s : (x : Nat) -> (x' : C x) -> C (suc@_ x)) ->
- \(m : Nat) ->
- case m of {
- (zer) -> c_z;
- (suc m') -> c_s m' (elimNat C c_z c_s m');}
- ----------------------------------------------------------------------------
- -- Linear universe of finite sets.
- ----------------------------------------------------------------------------
- Fin (m : Nat) : Set
- = case m of {
- (zer) -> Zero;
- (suc m') -> Succ (Fin m');}
- valFin (m : Nat) : Fin m -> Nat
- = \(n : Fin m) ->
- case m of {
- (zer) -> case n of { };
- (suc m') ->
- case n of {
- (zer) -> zer@_;
- (suc n') -> suc@_ (valFin m' n');};}
- zeroFin (m : Nat) : Fin (succ m)
- = zer@_
- succFin (m : Nat)(n : Fin m) : Fin (succ m)
- = suc@_ n
- ----------------------------------------------------------------------------
- -- Do these really belong here?
- ----------------------------------------------------------------------------
- HEAD (X : Set1)(m : Nat)(f : Fin (succ m) -> X) : X
- = f (zeroFin m)
- TAIL (X : Set1)(m : Nat)(f : Fin (succ m) -> X) : Fin m -> X
- = \(n : Fin m) -> f (succFin m n)
- ----------------------------------------------------------------------------
- -- Lists.
- ----------------------------------------------------------------------------
- List (X : Set) : Set
- = data nil | con (x : X) (xs : List X)
- nil {X : Set} : List X
- = nil@_
- con {X : Set}(x : X)(xs : List X) : List X
- = con@_ x xs
- elimList {X : Set}
- (C : List X -> Set)
- (c_nil : C (nil |_))
- (c_con : (x : X) -> (xs : List X) -> C xs -> C (con@_ x xs))
- (xs : List X)
- : C xs
- = case xs of {
- (nil) -> c_nil;
- (con x xs') -> c_con x xs' (elimList |_ C c_nil c_con xs');}
- ----------------------------------------------------------------------------
- -- Tuples are "dependently typed vectors".
- ----------------------------------------------------------------------------
- Nil : Set
- = data nil
- Con (X0 : Set)(X' : Set) : Set
- = data con (x : X0) (xs : X')
- Tuple (m : Nat)(X : Fin m -> Set) : Set
- = case m of {
- (zer) -> Nil;
- (suc m') -> Con (X zer@_) (Tuple m' (\(n : Fin m') -> X (suc@_ n)));}
- ----------------------------------------------------------------------------
- -- Vectors homogeneously typed tuples.
- ----------------------------------------------------------------------------
- Vec (X : Set)(m : Nat) : Set
- = Tuple m (\(n : Fin m) -> X)
- ----------------------------------------------------------------------------
- -- Monoidal expressions.
- ----------------------------------------------------------------------------
- Mon (X : Set) : Set
- = data unit | at (x : X) | mul (xs1 : Mon X) (xs2 : Mon X)
- ----------------------------------------------------------------------------
- -- Propositions.
- ----------------------------------------------------------------------------
- Imply (X : Set)(Y : Set) : Set
- = X -> Y
- -}
- Absurd : Set
- Absurd = Zero
- Taut : Set
- Taut = Unit
- {-
- Not (X : Set) : Set
- = X -> Absurd
- Exist {X : Set}(P : X -> Set) : Set
- = Sum X P
- Forall (X : Set)(P : X -> Set) : Set
- = (x : X) -> P x
- And (X : Set)(Y : Set) : Set
- = Times X Y
- Iff (X : Set)(Y : Set) : Set
- = And (Imply X Y) (Imply Y X)
- Or (X : Set)(Y : Set) : Set
- = Plus X Y
- Decidable (X : Set) : Set
- = Or X (Imply X Absurd)
- DecidablePred {X : Set}(P : X -> Set) : Set
- = (x : X) -> Decidable (P x)
- DecidableRel {X : Set}(R : X -> X -> Set) : Set
- = (x1 : X) -> (x2 : X) -> Decidable (R x1 x2)
- Least {X : Set}((<=) : X -> X -> Set)(P : X -> Set) : X -> Set
- = \(x : X) -> And (P x) ((x' : X) -> P x' -> (x <= x'))
- Greatest {X : Set}((<=) : X -> X -> Set)(P : X -> Set) : X -> Set
- = \(x : X) -> And (P x) ((x' : X) -> P x' -> (x' <= x))
- ----------------------------------------------------------------------------
- -- Booleans.
- ----------------------------------------------------------------------------
- -}
- data Bool : Set where
- true : Bool
- false : Bool
- {-
- elimBool (C : Bool -> Set)(c_t : C true@_)(c_f : C false@_)(p : Bool)
- : C p
- = case p of {
- (true) -> c_t;
- (false) -> c_f;}
- whenBool (C : Set)(c_t : C)(c_f : C) : Bool -> C
- = elimBool (\(x : Bool) -> C) c_t c_f
- pred (X : Set) : Set
- = X -> Bool
- -}
- -- rel (X : Set) : Set
- -- = X -> X -> Bool
- True : Bool -> Set
- True (true) = Taut
- True (false) = Absurd
- {-
- bool2set = True
- pred2Pred {X : Set} : pred X -> X -> Set
- = \(p : pred X) -> \(x : X) -> True (p x)
- rel2Rel {X : Set} : (X -> X -> Bool) -> X -> X -> Set
- = \(r : (X -> X -> Bool)) -> \(x : X) -> \(y : X) -> True (r x y)
- decTrue (p : Bool) : Decidable (True p)
- = case p of {
- (true) -> inl@_ tt;
- (false) -> inr@_ (id |_);}
- abstract dec_lem {P : Set}(decP : Decidable P)
- : Exist |_ (\(b : Bool) -> Iff (True b) P)
- = case decP of {
- (inl trueP) ->
- struct {
- fst = true@_;
- snd =
- struct {
- fst = const |_ |_ trueP; -- (True true@_)
- snd = const |_ |_ tt;};};
- (inr notP) ->
- struct {
- fst = false@_;
- snd =
- struct {
- fst = whenZero P;
- snd = notP;};};}
- dec2bool : (P : Set) |-> (decP : Decidable P) -> Bool
- = \(P : Set) |-> \(decP : Decidable P) -> (dec_lem |_ decP).fst
- dec2bool_spec {P : Set}(decP : Decidable P)
- : Iff (True (dec2bool |_ decP)) P
- = (dec_lem |_ decP).snd
- abstract collTrue : (b : Bool) -> Collapsed (True b)
- = let aux (X : Set)(C : X -> Set)
- : (b : Bool) ->
- (f : True b -> X) ->
- (t1 : True b) |->
- (t2 : True b) |->
- C (f t1) -> C (f t2)
- = \(b : Bool) ->
- case b of {
- (true) ->
- \(f : (x : True true@_) -> X) ->
- \(t1 t2 : True true@_) |->
- \(c : C (f t1)) ->
- case t1 of { (tt) -> case t2 of { (tt) -> c;};};
- (false) ->
- \(f : (x : True false@_) -> X) ->
- \(t1 t2 : True false@_) |->
- \(c : C (f t1)) ->
- case t1 of { };}
- in \(b : Bool) -> \(P : True b -> Set) -> aux (True b) P b id
- bool2nat (p : Bool) : Nat
- = case p of {
- (true) -> succ zero;
- (false) -> zero;}
- ----------------------------------------------------------------------------
- -- Decidable subsets.
- ----------------------------------------------------------------------------
- Filter {X : Set}(p : pred X) : Set
- = Sum X (pred2Pred |_ p)
- ----------------------------------------------------------------------------
- -- Equality.
- ----------------------------------------------------------------------------
- -- "Deq" stands for "datoid equality" and represents exactly the data
- -- that has to be added to turn a set into a datoid.
- Deq (X : Set) : Set1
- = sig{eq : X -> X -> Bool;
- ref : (x : X) -> True (eq x x);
- subst :
- (C : X -> Set) -> (x1 x2 : X)|-> True (eq x1 x2) -> C x1 -> C x2;}
- -- The "Equality" type represents the data that has to be added to turna
- -- set into a setoid.
- Equality (X : Set) : Set1
- = sig{Equal : X -> X -> Set;
- ref : Reflexive |_ Equal;
- sym : Symmetrical |_ Equal;
- tran : Transitive |_ Equal;}
- -}
- data Datoid : Set1 where
- datoid : (Elem : Set) ->
- (eq : Elem -> Elem -> Bool) ->
- (ref : (x : Elem) -> True (eq x x)) ->
- (subst : Substitutive (\x1 -> \x2 -> True (eq x1 x2))) ->
- Datoid
- pElem : Datoid -> Set
- pElem (datoid Elem _ _ _) = Elem
- {-
- ElD (X : Datoid) : Set
- = X.Elem
- eqD {X : Datoid} : ElD X -> ElD X -> Bool
- = X.eq
- EqD {X : Datoid}(x1 x2 : ElD X) : Set
- = True (X.eq x1 x2)
- Setoid : Set1
- = sig{Elem : Set;
- Equal : Elem -> Elem -> Set;
- ref : (x : Elem) -> Equal x x;
- sym : (x1 : Elem) |-> (x2 : Elem) |-> Equal x1 x2 -> Equal x2 x1;
- tran :
- (x1 : Elem) |->
- (x2 : Elem) |->
- (x3 : Elem) |->
- Equal x1 x2 -> Equal x2 x3 -> Equal x1 x3;}
- El (X : Setoid) : Set
- = X.Elem
- Eq {X : Setoid} : Rel (El X)
- = X.Equal
- NotEq {X : Setoid} : Rel (El X)
- = \x1-> \x2-> Not (Eq |X x1 x2)
- Respectable {X : Setoid}(P : El X -> Set) : Set
- = (x1 x2 : El X) |-> Eq |X x1 x2 -> P x1 -> P x2
- RspEq {X Y : Setoid}(f : El X -> El Y) : Set
- = (x1 x2 : El X) |-> Eq |X x1 x2 -> Eq |Y (f x1) (f x2)
- RspEq2 (|X |Y |Z : Setoid)(f : El X -> El Y -> El Z)
- : Set
- = (x1 x2 : X.Elem) |-> (y1 y2 : Y.Elem) ->
- Eq |X x1 x2 ->
- Eq |Y y1 y2 ->
- Eq |Z (f x1 y1) (f x2 y2)
- D2S (Y : Datoid) : Setoid
- = struct {
- Elem = Y.Elem;
- Equal = \(x1 x2 : Elem) -> True (Y.eq x1 x2);
- ref = Y.ref;
- sym =
- \(x1 x2 : Elem) |->
- \(u : Equal x1 x2) ->
- Y.subst (\(x : Y.Elem) -> Equal x x1) |_ |_ u (ref x1);
- tran =
- \(x1 x2 x3 : Elem) |->
- \(u : Equal x1 x2) ->
- \(v : Equal x2 x3) ->
- Y.subst (Equal x1) |_ |_ v u;}
- {-# Alfa unfoldgoals off
- brief on
- hidetypeannots off
- wide
- nd
- hiding on
- con "nil" as "[]" with symbolfont
- con "con" infix as " : " with symbolfont
- var "Forall" as "\"" with symbolfont
- var "Exist" as "$" with symbolfont
- var "And" infix as "&" with symbolfont
- var "Or" infix as "Ú" with symbolfont
- var "Iff" infix as "«" with symbolfont
- var "Not" as "Ø" with symbolfont
- var "Imply" infix as "É" with symbolfont
- var "Taut" as "T" with symbolfont
- var "Absurd" as "^" with symbolfont
- var "El" mixfix as "|_|" with symbolfont
- var "Eq" distfix3 as "==" with symbolfont
- var "NotEq" distfix3 as "=|=" with symbolfont
- var "True" mixfix as "|_|" with symbolfont
- var "ElD" mixfix as "|_|" with symbolfont
- var "EqD" distfix3 as "==" with symbolfont
- var "Id" distfix3 as "=" with symbolfont
- #-}
- -}
|