Re: [HoTT] Re: Proof that something is an embedding without assuming excluded middle?

["Martín Hötzel Escardó" <escardo.martin@gmail.com>]

[-- Attachment #1.1: Type: text/plain, Size: 5040 bytes --]

Here is my take on the independent proofs by Mike and Paolo. My aim in
this version is to avoid calculations as much as possible.

We want to show that the following map s is an embedding:

 s : (P → 𝓤) → 𝓤
 s = Π

Our strategy will be to exhibit s as a composition of an equivalence
followed by something that is clearly an embedding:

  (P → 𝓤) ≃  M ↪ 𝓤

We take M := Σ (X : 𝓤), is-equiv (κ X),
where the function κ X : X → (P → X) is defined by κ x p = x.

The map M ↪ 𝓤 is simply the first projection. It is an embedding
because "being an equivalence" is a proposition.

The equivalence (P → 𝓤) ≃ M is easy. Given A : P → 𝓤 we take X to be
the type s A, with a short argument to show that the map κ(s A) is an
equivalence. Conversely, given X : 𝓤 such that κ X is an equivalence,
we take A to be the constant family (p ↦ X). It is direct and short to
check that this does give an inverse (using function extensionality and 
univalence).

By construction, the map s is the composition of the equivalence
followed by the projection.

Because equivalences are embeddings, and compositions of embeddings
are embeddings, it follows that s is an embedding.

I coded this in Agda here:
http://www.cs.bham.ac.uk/~mhe/agda-new/UF-InjectiveTypes.html#17057

Thanks for your input!

Martin


On Wednesday, 14 November 2018 15:52:45 UTC, Michael Shulman wrote:
>
> Here's a sketch of a more conceptual argument.  Both 𝓤 and P → 𝓤 are 
> the object-types of (oo-)categories, and Π is the object-map of a 
> right adjoint functor whose counit is an equivalence.  Thus, by a 
> standard argument, it is fully faithful, and hence also fully faithful 
> on equivalences (which, by univalence, are the equalities).  Of course 
> we can't define the whole oo-categories in Book HoTT, but I think this 
> is one of those arguments that only needs the 1- or 2-dimensional 
> structure. 
> On Wed, Nov 14, 2018 at 3:07 AM Paolo Capriotti <p.cap...@gmail.com 
> <javascript:>> wrote: 
> > 
> > On Tue, 13 Nov 2018, at 8:32 PM, Martín Hötzel Escardó wrote: 
> > > Let P be a subsingleton and 𝓤 be a universe, and consider the 
> > > product map 
> > > 
> > >   Π : (P → 𝓤) → 𝓤 
> > >          A     ↦ Π (p:P), A(p). 
> > > 
> > > Is this an embedding? (In the sense of having subsingleton 
> > > fibers.) 
> > > 
> > > It is easy to see that this is the case if P=𝟘 or P=𝟙 (empty or 
> > > singleton type). 
> > > 
> > > But the reasons are fundamentally different: 
> > > 
> > > (0) If P=𝟘, the domain of Π is equivalent to 𝟙, and Π amounts to 
> > >     the map 𝟙 → 𝓤 with constant value 𝟙. 
> > > 
> > >     In general, a function 𝟙 → X into a type X is *not* an 
> > >     embedding. Such a function is an embedding iff it maps the 
> > >     point of 𝟙 to a point x:X such that the type x=x is a 
> > >     singleton. 
> > > 
> > >     And indeed for X:=𝓤 we have that the type 𝟙=𝟙 is a singleton. 
> > > 
> > > (1) If P=𝟙, the domain of Π is equivalent to 𝓤, and Π amounts to 
> > >     the identity map 𝓤 → 𝓤, which, being an equivalence, is an 
> > >     embedding. 
> > > 
> > > Question. Is there a uniform proof that Π as above for P a 
> > > subsingleton is an embedding, without considering the case 
> > > distinction (P=𝟘)+(P=𝟙)? 
> > 
> > I think one can show that ap Π is an equivalence by giving an inverse. 
> Given X, Y : P → 𝓤, first note that the equality type X = Y is equivalent 
> by function extensionality to (u : P) → X u = Y u. Since one can prove 
> easily that (u : P) → X u = Π X, it follows that X = Y is equivalent to P → 
> Π X = Π Y. Hence we get a map ω : Π X = Π Y → X = Y. To show that it is 
> indeed an inverse of ap Π, start with some α : Π X = Π Y. By following the 
> construction above, we get that ap Π (ω α) maps a function h : Π X to λ u . 
> α (λ v . tr^X [u,v] (h u)) u, where [u,v] : u = v is given by the fact that 
> P is a proposition. Now, within the assumption u : P, the λ expression in 
> brackets is equal to h itself, hence ap Π (ω α) = α. The other composition 
> is easier, since it can just be checked on reflexivity. 
> > 
> > Best, 
> > Paolo 
> > 
> > -- 
> > You received this message because you are subscribed to the Google 
> Groups "Homotopy Type Theory" group. 
> > To unsubscribe from this group and stop receiving emails from it, send 
> an email to HomotopyTypeTheory+unsubscribe@googlegroups.com <javascript:>. 
>
> > For more options, visit https://groups.google.com/d/optout. 
>

-- 
You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[-- Attachment #1.2: Type: text/html, Size: 6676 bytes --]