From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.9 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,HTML_MESSAGE,MAILING_LIST_MULTI, RCVD_IN_DNSWL_NONE autolearn=ham autolearn_force=no version=3.4.2 Received: from mail-ot1-x339.google.com (mail-ot1-x339.google.com [IPv6:2607:f8b0:4864:20::339]) by inbox.vuxu.org (OpenSMTPD) with ESMTP id 42330393 for ; Wed, 14 Nov 2018 10:23:40 +0000 (UTC) Received: by mail-ot1-x339.google.com with SMTP id t50sf3199617otf.2 for ; Wed, 14 Nov 2018 02:23:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20161025; h=sender:date:from:to:message-id:in-reply-to:references:subject :mime-version:x-original-sender:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-unsubscribe; bh=Xi/lEvmHyxSfHVRe5fzPKjQ7XTxkcXGasmEa1aQZ9cU=; b=CndnuL7fvBjaQj5y81DXdfQorji03vBU5t1pAMHcSRyq5QRLuk8I+lauCUn3+hjdr3 MBmyQyyk63GYrvfZiXg4ZzBimLtbjdJrcYFKhVNGgXRkFJVX9GkCZTteNL/pUdYNGItw +Q0hvDhCV7GlohIOh9Zmhs0dmbR4y+jsuPZEfO+G19E7yo1Fv+0oEmLQcNdm+VKk7xAP OCMvMeLSAqn8jYxKK3f/u24zgsxpMW72diUkEqMJwl0Ifz0FCctDQktXYEQttcuCtpvL w+q7jTh2v0lsLoafV1akBS/NaNUpB+kG9LT1AlPHpdKpXfsnWC5tImdMZzHhSShi/Alj GiKQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:message-id:in-reply-to:references:subject:mime-version :x-original-sender:precedence:mailing-list:list-id:list-post :list-help:list-archive:list-unsubscribe; bh=Xi/lEvmHyxSfHVRe5fzPKjQ7XTxkcXGasmEa1aQZ9cU=; b=sMiJfhQ07chNrDYJc3xODmh9vrn+BOhzuOsPtM2EjdeqzVhkdohY+KwtNjbkRDNimM rJaQaRsWn0MF48UMmsL0W6IF/BZDixlGb93qctgRFpou+llrRS490ZwtGShCxA9SHjhe GMuvhlBhT6StmrSxvcycSg9pVBZmlTPf95Esmw2gA9QJ2eHdhRmqyIKOR/1rnAg9zkn7 h0YdoYLpXudyIt8KNZ5MdwGIp0iwMikiGqAHU8pHcihJEW1U4896UtAuSeegMBoYV1G0 kty7gCOMyKh2aRbbfjtEysNrgWQh9Bw868a9egtK/ezODC+ZRoODt3bNCfOxeDpYsNQ9 fwYw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=sender:x-gm-message-state:date:from:to:message-id:in-reply-to :references:subject:mime-version:x-original-sender:precedence :mailing-list:list-id:x-spam-checked-in-group:list-post:list-help :list-archive:list-unsubscribe; bh=Xi/lEvmHyxSfHVRe5fzPKjQ7XTxkcXGasmEa1aQZ9cU=; b=Z4KTYQ+NL/ci7hAK96wZPZmdAza0aspoYIXY5S1SWeKkuYe7zQv4tzCYQNKk5WHkLX tWXoNbrs+t2wZRi978CpBSqtlrCzuTDzWQn3UbCxTg6nmvxNF+QdyYJPRXOPVtZ6621H ZTHIe+ep9ibrD+cwhjZzrwPm5tlhfgcp5iHxtuqPmqCs5yGrhSJmfPDONXoFHuFm1Wzr /r3txN/nN2DHVh2H11QsjAhWcIL9VZvt/DzXCoCdzuPSo61IhGmDUnjOcvGCG5+GinjB qSiT8EPbEcLoqwodK7coSmsBA3iLWVRhwG7dh/L+MXDkNdxnhGNdrBuElhOcSkayIN3B vYCw== Sender: homotopytypetheory@googlegroups.com X-Gm-Message-State: AGRZ1gLaM4pju3kyKQ1vNznSbxehMvJ3lt2tHzoprkCSCYM97NYxcHa2 Ta1LE+o6AwXWu+FyLsLS+2g= X-Google-Smtp-Source: AJdET5c6MoKYZQ4EvxSOnhdZJGCoYvkllHLXcuObTzCpVAK6r9X9QvN/1ThOu/jyaDgmLU+do72Rlw== X-Received: by 2002:aca:c703:: with SMTP id x3mr41132oif.5.1542191018990; Wed, 14 Nov 2018 02:23:38 -0800 (PST) X-BeenThere: homotopytypetheory@googlegroups.com Received: by 2002:a9d:2c62:: with SMTP id f89ls4559464otb.2.gmail; Wed, 14 Nov 2018 02:23:38 -0800 (PST) X-Received: by 2002:a9d:2c22:: with SMTP id f31mr43900otb.4.1542191017332; Wed, 14 Nov 2018 02:23:37 -0800 (PST) Date: Wed, 14 Nov 2018 02:23:36 -0800 (PST) From: =?UTF-8?Q?Mart=C3=ADn_H=C3=B6tzel_Escard=C3=B3?= To: Homotopy Type Theory Message-Id: In-Reply-To: <0472bc2b-0212-48b9-bfe7-fb98c7916763@googlegroups.com> References: <0090c5e9-8e11-484c-953c-bf2958d03b72@googlegroups.com> <0472bc2b-0212-48b9-bfe7-fb98c7916763@googlegroups.com> Subject: [HoTT] Re: Proof that something is an embedding without assuming excluded middle? MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_1282_1012810287.1542191016640" X-Original-Sender: escardo.martin@gmail.com Precedence: list Mailing-list: list HomotopyTypeTheory@googlegroups.com; contact HomotopyTypeTheory+owners@googlegroups.com List-ID: X-Google-Group-Id: 1041266174716 List-Post: , List-Help: , List-Archive: , ------=_Part_1282_1012810287.1542191016640 Content-Type: multipart/alternative; boundary="----=_Part_1283_379933819.1542191016641" ------=_Part_1283_379933819.1542191016641 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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 =E2=86=A6 =CE=BBp.X: =CE=A0 : (P =E2=86=92 =F0=9D=93=A4) =E2=86=92 =F0=9D=93=A4 A =E2=86=A6 =CE=A0(p:P), A(p) (section) =CE=BB(p:P).X =E2=86=A4 X (retraction) because if p:P is given then A is constant with value (equivalent to) =CE=A0A. 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= .=20 > For any proposition Q, let P =3D {0 : Z | Q}. Let A be defined as for all= p :=20 > P, A(p) =3D 0 : P, and let B be defined as for all p : P, B(p) =3D not no= t (0 :=20 > P). To show that Pi (p : P), A(p) =3D Pi (p : P), B(p), you can define th= e=20 > following isomorphism (?): for any f : Pi (p : P), A(p), define g : Pi (p= :=20 > P), B(p) by picking p : P, then f(p) : A(p), so Q is true. Hence, not not= Q=20 > is true, meaning it has an element, so g(p) is that element. We then can= =20 > conclude A =3D B. By function extensionality, that's equivalent to for al= l p=20 > : P, A (p) =3D B (p), which gives Q =3D not not Q.=20 > > Jean > > On Tuesday, November 13, 2018 at 3:32:22 PM UTC-5, Mart=C3=ADn H=C3=B6tze= l Escard=C3=B3=20 > wrote: >> >> Let P be a subsingleton and =F0=9D=93=A4 be a universe, and consider the >> product map >> >> =CE=A0 : (P =E2=86=92 =F0=9D=93=A4) =E2=86=92 =F0=9D=93=A4 >> A =E2=86=A6 =CE=A0 (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=3D=F0=9D=9F=98 or P=3D=F0= =9D=9F=99 (empty or >> singleton type). >> >> But the reasons are fundamentally different: >> >> (0) If P=3D=F0=9D=9F=98, the domain of =CE=A0 is equivalent to =F0=9D=9F= =99, and =CE=A0 amounts to >> the map =F0=9D=9F=99 =E2=86=92 =F0=9D=93=A4 with constant value =F0= =9D=9F=99. >> >> In general, a function =F0=9D=9F=99 =E2=86=92 X into a type X is *no= t* an >> embedding. Such a function is an embedding iff it maps the >> point of =F0=9D=9F=99 to a point x:X such that the type x=3Dx is a >> singleton. >> >> And indeed for X:=3D=F0=9D=93=A4 we have that the type =F0=9D=9F=99= =3D=F0=9D=9F=99 is a singleton. >> >> (1) If P=3D=F0=9D=9F=99, the domain of =CE=A0 is equivalent to =F0=9D=93= =A4, and =CE=A0 amounts to >> the identity map =F0=9D=93=A4 =E2=86=92 =F0=9D=93=A4, which, being a= n equivalence, is an >> embedding. >> >> Question. Is there a uniform proof that =CE=A0 as above for P a >> subsingleton is an embedding, without considering the case >> distinction (P=3D=F0=9D=9F=98)+(P=3D=F0=9D=9F=99)? >> >> Martin >> >> --=20 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 e= mail to HomotopyTypeTheory+unsubscribe@googlegroups.com. For more options, visit https://groups.google.com/d/optout. ------=_Part_1283_379933819.1542191016641 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
It seems to me that you are trying to show that if th= e map is
left-cancellable then excluded middle holds. However, as= I said, the
map is left-cancellable. Moreover, it is a section w= ith retraction
X =E2=86=A6 =CE=BBp.X:

= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =CE=A0 : (P =E2=86=92 =F0=9D=93=A4) =E2=86=92 = =F0=9D=93=A4
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0A=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =E2=86=A6 =CE=A0(p:P), A(p)=C2=A0 = =C2=A0 (section)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =CE=BB= (p:P).X=C2=A0 =E2=86=A4 X=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 (retraction)

because if p:P i= s given then A is constant with value (equivalent
to) =CE=A0A.

For sets, sections (and more generally left-cancella= ble maps) are
necessarily embeddings. However, for general types = this need not be
the case. See the paper https://arxiv.org/abs/15= 07.03634 by Mike
Shulman, and in particular Theorem 3.10, which g= ives 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 d= ouble negation. For any proposition Q, let P =3D {0 : Z | Q}. Let A be defi= ned as for all p : P, A(p) =3D 0 : P, and let B be defined as for all p : P= , B(p) =3D not not (0 : P). To show that Pi (p : P), A(p) =3D 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 th= at element. We then can conclude A =3D B. By function extensionality, that&= #39;s equivalent to for all p : P, A (p) =3D B (p), which gives Q =3D not n= ot Q.=C2=A0

Jean

On Tuesday, November 13,= 2018 at 3:32:22 PM UTC-5, Mart=C3=ADn H=C3=B6tzel Escard=C3=B3 wrote:
Let P be a subsing= leton and =F0=9D=93=A4 be a universe, and consider the
product ma= p

=C2=A0 =CE=A0 : (P =E2=86=92 =F0=9D=93=A4) =E2= =86=92 =F0=9D=93=A4
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0A=C2=A0 =C2= =A0 =C2=A0=E2=86=A6 =CE=A0 (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=3D=F0=9D=9F= =98 or P=3D=F0=9D=9F=99 (empty or
singleton type).

=
But the reasons are fundamentally different:

(0) If P=3D=F0=9D=9F=98, the domain of =CE=A0 is equivalent to =F0=9D= =9F=99, and =CE=A0 amounts to
=C2=A0 =C2=A0 the map =F0=9D=9F=99 = =E2=86=92 =F0=9D=93=A4 with constant value =F0=9D=9F=99.

=C2=A0 =C2=A0 In general, a function =F0=9D=9F=99 =E2=86=92 X into a= type X is *not* an
=C2=A0 =C2=A0 embedding. Such a function is a= n embedding iff it maps the
=C2=A0 =C2=A0 point of =F0=9D=9F=99 t= o a point x:X such that the type x=3Dx is a
=C2=A0 =C2=A0 singlet= on.

=C2=A0 =C2=A0 And indeed for X:=3D=F0=9D=93=A4= we have that the type =F0=9D=9F=99=3D=F0=9D=9F=99 is a singleton.

(1) If P=3D=F0=9D=9F=99, the domain of =CE=A0 is equivalen= t to =F0=9D=93=A4, and =CE=A0 amounts to
=C2=A0 =C2=A0 the identi= ty map =F0=9D=93=A4 =E2=86=92 =F0=9D=93=A4, which, being an equivalence, is= an
=C2=A0 =C2=A0 embedding.

Question. I= s there a uniform proof that =CE=A0 as above for P a
subsingleton= is an embedding, without considering the case
distinction (P=3D= =F0=9D=9F=98)+(P=3D=F0=9D=9F=99)?

Martin

--
You received this message because you are subscribed to the Google Groups &= quot;Homotopy Type Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to = HomotopyTypeTheory+unsubscribe@googlegroups.com.
For more options, visit http= s://groups.google.com/d/optout.
------=_Part_1283_379933819.1542191016641-- ------=_Part_1282_1012810287.1542191016640--