Discussion of Homotopy Type Theory and Univalent Foundations
 help / color / mirror / Atom feed
From: "Martín Hötzel Escardó" <escardo.martin@gmail.com>
To: Homotopy Type Theory <HomotopyTypeTheory@googlegroups.com>
Subject: [HoTT] Re: Proof that something is an embedding without assuming excluded middle?
Date: Wed, 14 Nov 2018 02:23:36 -0800 (PST)	[thread overview]
Message-ID: <e0110ae3-8cfc-4c4b-a424-f2c185a4e4b6@googlegroups.com> (raw)
In-Reply-To: <0472bc2b-0212-48b9-bfe7-fb98c7916763@googlegroups.com>


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

It seems to me that you are trying to show that if the map is
left-cancellable then excluded middle holds. However, as I said, the
map is left-cancellable. Moreover, it is a section with retraction
X ↦ λp.X:

        Π : (P → 𝓤) → 𝓤
               A          ↦ Π(p:P), A(p)    (section)
            λ(p:P).X  ↤ X                    (retraction)

because if p:P is given then A is constant with value (equivalent
to) ΠA.

For sets, sections (and more generally left-cancellable maps) are
necessarily embeddings. However, for general types this need not be
the case. See the paper https://arxiv.org/abs/1507.03634 by Mike
Shulman, and in particular Theorem 3.10, which gives a criterion for a
section being an embedding.

(I think the problem with your proof attempt is that you forgot to
give the other direction of the "isomorphism", which would require
double negation elimination.)

Best,
Martin

On Tuesday, 13 November 2018 23:47:40 UTC, Jean Joseph wrote:
>
> I think to show this is an embedding may imply the law of double negation. 
> For any proposition Q, let P = {0 : Z | Q}. Let A be defined as for all p : 
> P, A(p) = 0 : P, and let B be defined as for all p : P, B(p) = not not (0 : 
> P). To show that Pi (p : P), A(p) = Pi (p : P), B(p), you can define the 
> following isomorphism (?): for any f : Pi (p : P), A(p), define g : Pi (p : 
> P), B(p) by picking p : P, then f(p) : A(p), so Q is true. Hence, not not Q 
> is true, meaning it has an element, so g(p) is that element. We then can 
> conclude A = B. By function extensionality, that's equivalent to for all p 
> : P, A (p) = B (p), which gives Q = not not Q. 
>
> Jean
>
> On Tuesday, November 13, 2018 at 3:32:22 PM UTC-5, 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=𝟙)?
>>
>> Martin
>>
>>

-- 
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: 4337 bytes --]

  reply	other threads:[~2018-11-14 10:23 UTC|newest]

Thread overview: 12+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-11-13 20:32 [HoTT] " Martín Hötzel Escardó
2018-11-13 20:36 ` [HoTT] " Martín Hötzel Escardó
2018-11-13 23:47 ` Jean Joseph
2018-11-14 10:23   ` Martín Hötzel Escardó [this message]
2018-11-14 11:07     ` Paolo Capriotti
2018-11-14 15:52       ` Michael Shulman
2018-11-15 11:05         ` Martín Hötzel Escardó
2018-11-15 19:23           ` Martín Hötzel Escardó
2018-11-15 19:29             ` Michael Shulman
2018-11-15 22:26               ` Martín Hötzel Escardó
2018-11-15 23:38                 ` Michael Shulman
2018-11-14 19:00       ` Martín Hötzel Escardó

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=e0110ae3-8cfc-4c4b-a424-f2c185a4e4b6@googlegroups.com \
    --to=escardo.martin@gmail.com \
    --cc=HomotopyTypeTheory@googlegroups.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).