[Agda] Equivalence axiom => extensionality
Dan Licata
drl at cs.cmu.edu
Wed Jun 23 17:54:44 CEST 2010
Agda agrees, in the sense that the following bit of code shows that
weakly equivalent sets are isomorphic (append it to
http://www.cs.cmu.edu/~drl/tmp/equivax.tgz). Note that this result does
not use the equivalence axiom.
module Iso where
record Iso (A B : Set) : Set where
field
l : A -> B
r : B -> A
lr : (x : _) -> Id (l (r x)) x
rl : (x : _) -> Id (r (l x)) x
back : ∀ {A B : Set} -> WEq A B -> (B -> A)
back (f , by) b = fst (fst (by b))
iso : ∀ {A B : Set} -> WEq A B -> Iso A B
iso {A} {B} w = record {l = fst w; r = back w; lr = lr w; rl = rl w}
where lr : (w : WEq A B) (x : B) -> Id (fst w (back w x)) x
lr (f , by) x with (by x)
... | ((a , b) , c) = b
rl : (w : WEq A B) (x : A) -> Id (back w (fst w x)) x
rl (f , by) x with by (f x)
... | ((a , b) , c) = IdM.sym (IdM.substeq fst (c (x , Refl)))
-Dan
On Jun23, Thorsten Altenkirch wrote:
> >
> > Clearly, isomorphic implies bijective but the other way around seems
> > not provable constructively, afaik. From surjective you get an iverse
> > g' : B → A such that g ∘ g' = id but not the other way
> > around. Injectivity doesn't give you a function, but even if you
> > assume that it is split (or what is the word) you just get another
> > function g'' : B → A, such that g'' ∘ g = id but I don't see why g'' =
> > g' or how you could in general construct one function which is both
> > left and right inverse to f. Or am I overlooking something obvious?
>
> As Thierry just pointed out to me, I am. If g ∘ g' = id
> then g ∘ g' ∘ g = g and because g is monic g' ∘ g = id.
>
>
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda
More information about the Agda
mailing list