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.7 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-pf1-x437.google.com (mail-pf1-x437.google.com [IPv6:2607:f8b0:4864:20::437]) by inbox.vuxu.org (OpenSMTPD) with ESMTP id fb86ea3b for ; Sun, 11 Aug 2019 10:46:59 +0000 (UTC) Received: by mail-pf1-x437.google.com with SMTP id w16sf377053pfn.12 for ; Sun, 11 Aug 2019 03:46:59 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1565520417; cv=pass; d=google.com; s=arc-20160816; b=UUB7Fks558Y/hl64ClZoqWzj6JTcZvDbe9Ip3ObxtQ8rJDvph9FcK1Qmww+WsereMn L0l5bMsk882uC+rIy1EQvWg1LT4h7qiafcb8bqGmskQ11D10U6uBRMWWNElZpSleuL5d FlsdrTajuwiHKQ5KHaIWoEF7yWIilDQ9tfUMOzZyBvi3Ta8VzYGheaeWEWUa8UXD2A1d f4+1Patyx3Dh1v1jWVYXoiEkgoCJ+7P5+JUsdrFqdHT4xWLk9Ghh066k086tT9AbAQqi vJJOIPGfiLwzKHvVESBUE8mLy9sgGONjlc9tk+IStT1odD6sfm1e+qm0xAIuSm6W8vBq 7rTg== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-unsubscribe:list-archive:list-help:list-post:list-id :mailing-list:precedence:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:sender:dkim-signature :dkim-signature; bh=20tLLwGJ+Gb4BO9KkZR//C04ZtoukoiQlr5DozWM4SI=; b=XdTeSOAy5u/0sOKAeAYbGWlTpIZ4sk2XSiWr8JwRvyRw0Tg1Kl3LCPiJ60vz30huAM NNkrthGrUNA5LSCN+oBAAbtx4RhuQ1zl4IZU94vxus3WwkEenktwFisxhJ0U78l/eFmn pKddb0XxrqZzfjNJ3n9TXsO2Dfh2Jqym1QMuHYFu3IgVSLyFc12O+IGQiq+J7ELJqu5o gzTPLGXiEgouFL8sPhmFSAp+BwZSw/Dqc2q7qkn4eBfE/tKq5EWMwfKyyQo0aISWgZNI g3aIqm9YytBG2PR2QHQlJl/6Hr+w3tl9fubbueipzGqdDWQSujrNaCRFWm7JmK27nQ7L tBmA== ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=maUEx3Tn; spf=pass (google.com: domain of valery.isaev@gmail.com designates 2607:f8b0:4864:20::333 as permitted sender) smtp.mailfrom=valery.isaev@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20161025; h=sender:mime-version:references:in-reply-to:from:date:message-id :subject:to:cc:x-original-sender:x-original-authentication-results :precedence:mailing-list:list-id:list-post:list-help:list-archive :list-unsubscribe; bh=20tLLwGJ+Gb4BO9KkZR//C04ZtoukoiQlr5DozWM4SI=; b=QfyuuEotKaxGymPSxaLIyoDAPkksSQSW8n39411glgQGfqUgnS34ZBlZGqGN0/cNYF VKxyt2B5ph0Kbm/f7C/ettHrRWRcnimqMjJyZ0bxN9peS3HLrWI1YMannhvVwHIQGKsd Skg+XhHcHj2h+OXLigN+yeoqrGwnadKynkSAbG7aMS9476czUXMe9imp0Ln/uCoE6uVF meEx5kBlQqLaaSJdOb2Xu7Xs0XGm6ZVQ09zuSdLL2NdhfOmnSWIX8m8J11V0MBlbCHEZ ohO7DES0559b5UjejTEz5HxWHR3HyQLqghJz+UXRdAsxPku+u9is4tZfXfS+1AolMIZt +5Xw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:x-original-sender:x-original-authentication-results:precedence :mailing-list:list-id:list-post:list-help:list-archive :list-unsubscribe; bh=20tLLwGJ+Gb4BO9KkZR//C04ZtoukoiQlr5DozWM4SI=; b=IgPeRVCy4ABhAoi3bATLBnp1IWzq5JsyNO7oF+s8F+0v3uAsOw6Za6ewmsywZ8T0Rg SQ4m5XvntMihY03Yyh1dje8dkWsuyuYAnQSnpQUjb/UUOC3vHw0ETtoBmCr9e5OlZxHs uaKdfGFwswmqk86HhqniI4c/TlAryATdS58unx2bdM4vBGAqutrY2ZjYIV0Ds+2vD9un nuDeLAwktjqwFLchf4waf3kBa24w+4SIaao/XCJXM5pxhr619WTogvB+IBBdTiRYkFpR BDM02yB3HU8BKwLXl5DCWnbByyFX9/X0pBolsxt4wsf+SsBscz60KhmGT/u38SszM95s hRlQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=sender:x-gm-message-state:mime-version:references:in-reply-to:from :date:message-id:subject:to:cc:x-original-sender :x-original-authentication-results:precedence:mailing-list:list-id :x-spam-checked-in-group:list-post:list-help:list-archive :list-unsubscribe; bh=20tLLwGJ+Gb4BO9KkZR//C04ZtoukoiQlr5DozWM4SI=; b=CAEHOK0q7C+qcc8/fENYBMpNYsXrWAINWYxQCmcRcY1Q7JeU0S3WZh6YSEHHkLJnep rqKZc5QBsRnRQVs8p0kGWaNXeeEVRFZlLqG6nnGH8yUwHMoCAaiFGtnWTMcGPzgtW6nT HpoiZXR98tHaV5BmVheWcYoie2+x8P+V2bV2qVgM11gaE342SKKeMO59Vwiy69TLmaAN AyUexMmU4a36cWjISwuxWSW2p6Uz29c5fO+9LpApHb88MqnN6GBlZgVkLd6xuwv1KwE3 QQA/rRLiusTk8RQeoHscjie+/Vq4vQmzckpyt3YTclZql3BmQw9JZbrkRusS5cza2vJ5 //ww== Sender: homotopytypetheory@googlegroups.com X-Gm-Message-State: APjAAAUzbf9CZ8zWZwCj5GNNvao2c6pI2vruoZ/cRNZ9KwhovMlS0/NL 3TW++VU8WKyqJ7ByizTPsd0= X-Google-Smtp-Source: APXvYqx89xnPfOvM4UmnbOpOft9QfIhN5kDJItpG4wBOMH4ELwD7lE89Sno9tV2xVVWVuU7sDdJGlw== X-Received: by 2002:a62:1941:: with SMTP id 62mr14268135pfz.188.1565520417383; Sun, 11 Aug 2019 03:46:57 -0700 (PDT) X-BeenThere: homotopytypetheory@googlegroups.com Received: by 2002:a17:902:8346:: with SMTP id z6ls3194287pln.8.gmail; Sun, 11 Aug 2019 03:46:57 -0700 (PDT) X-Received: by 2002:a17:902:f082:: with SMTP id go2mr29378667plb.25.1565520416976; Sun, 11 Aug 2019 03:46:56 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1565520416; cv=none; d=google.com; s=arc-20160816; b=Mh9flw6GXb8AcqIom0NSp6hHXLb06xj1YrabKzBfepYLuae6FDrSKdMLUVo4FEEgoU FPVIvo4DZQqxwmshEgchUFBiXHzbpFoq7OoJgUnI/0ZI7BvbvOEmXO2ZtbkUTjd1+BmF Av5p+IlJgD6XzmZcqDeu/7OjUW6zzXQ+hTYmQkVP/tddjH7X3K3Ese1MNDTT6mrRVB4k JuDtNz96dUzsE6ylKsL5HYOwvzdMRyIHHSGnxrpdCxhoNiJV8Y9NFUXzF9b3Vn39LJQW W4Izdras37CS0qnJ703WpM+5jqYLLTDumSRYd+CzHew7xO/jTLtpFKkGR76ZDRvgPIti GBhw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:dkim-signature; bh=9oH0OltGnxAd4XceZfJqH/0apmpjA13A7XQJ+zqvkSY=; b=xBsa1thfj+b83fJf6aj9NTYdb5PztIXViNqWLpBtr0vUoFLk8N2b6ejAtqtzdQVxZs 5fhOaKC/hNmJJvkEpdvkHiL72W5GFcR8cD2nnLB34qxAA68B0an/abLYbuUkt1e9Y26O IF8XwP3l0TN4hrOkLLyFIusXWBXH87q8YwgLjnkTYmEs4L3TPUrjVLAcMovDzd0d4yqj enzOwxGpRKJZUfGD79UK1ApXmLVPWhqlnx3yoDY2PxSNGvSFuaamjfSbNefJGWwYkGTp QZr0RbqQnF0xEb+lOJMYu3Dx2zA8QAVixUX0Bc5inoM6q3EwwH8St+izaMoD/W0b/OZR xS9g== ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=maUEx3Tn; spf=pass (google.com: domain of valery.isaev@gmail.com designates 2607:f8b0:4864:20::333 as permitted sender) smtp.mailfrom=valery.isaev@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Received: from mail-ot1-x333.google.com (mail-ot1-x333.google.com. [2607:f8b0:4864:20::333]) by gmr-mx.google.com with ESMTPS id l72si4408244pge.0.2019.08.11.03.46.56 for (version=TLS1_3 cipher=AEAD-AES128-GCM-SHA256 bits=128/128); Sun, 11 Aug 2019 03:46:56 -0700 (PDT) Received-SPF: pass (google.com: domain of valery.isaev@gmail.com designates 2607:f8b0:4864:20::333 as permitted sender) client-ip=2607:f8b0:4864:20::333; Received: by mail-ot1-x333.google.com with SMTP id b7so98908165otl.11 for ; Sun, 11 Aug 2019 03:46:56 -0700 (PDT) X-Received: by 2002:a5d:8b8a:: with SMTP id p10mr7626727iol.218.1565520416138; Sun, 11 Aug 2019 03:46:56 -0700 (PDT) MIME-Version: 1.0 References: <9d23061c-4b7a-4d69-9c22-f28261ad3b33@googlegroups.com> <06e24c98-7409-4e75-88ee-a6e1bb891e1e@www.fastmail.com> In-Reply-To: From: Valery Isaev Date: Sun, 11 Aug 2019 13:46:19 +0300 Message-ID: Subject: Re: [HoTT] New theorem prover Arend is released To: Michael Shulman Cc: Jon Sterling , "HomotopyTypeTheory@googlegroups.com" Content-Type: multipart/alternative; boundary="0000000000004ae948058fd52077" X-Original-Sender: valery.isaev@gmail.com X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=maUEx3Tn; spf=pass (google.com: domain of valery.isaev@gmail.com designates 2607:f8b0:4864:20::333 as permitted sender) smtp.mailfrom=valery.isaev@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=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: , --0000000000004ae948058fd52077 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable =D0=B2=D1=81, 11 =D0=B0=D0=B2=D0=B3. 2019 =D0=B3. =D0=B2 02:37, Michael Shu= lman : > On Sat, Aug 10, 2019 at 5:25 AM Valery Isaev > wrote: > > The document is slightly outdated. We do not have the rule iso A B (=CE= =BBx =E2=87=92 > x) (=CE=BBx =E2=87=92 x) idp idp i =E2=87=92=CE=B2 A in the actual implem= entation since univalence is > true even without it. This rule has another problem. It seems that the > theory as presented in the document introduces a quasi-equivalence betwee= n > A =3D B and Equiv A B, which means that there are some true statements wh= ich > are not provable in it. > > I don't understand. By "quasi-equivalence" do you mean an incoherent > equivalence (what the book calls a map with a quasi-inverse)? If so, > then every quasi-equivalence can of course be promoted to a strong > equivalence. > Yes, a quasi-equivalence is a function together with its quasi-inverse. The problem is that we've got some terms in the theory of which we know nothing about. It's the same as if I just add a new type *Magic *without any additional rules. Then we cannot prove anything about it and the resulting theory won't be equivalent to the original one. > > However, as I said, I'm more worried about the fourth rule coe_{=CE=BB k = =E2=87=92 > iso A B f g p q k} a right =E2=87=92=CE=B2 f a. That's the one that I ha= ve trouble > seeing how to interpret in a model category. Can you say anything > about that? > I don't remember well, but I think the idea is that you need to prove that there is a trivial cofibration Eq(A,B) -> F(U^I,A,B), where the first object is the object of equivalences between A and B and the second object is the fiber of U^I over A and B. The fact that this map is a weak equivalence is just the univalence axiom. The problem is to show that it is a cofibration and whether this is true or not depends on the definition of Eq(A,B). I don't actually remember whether I finished this proof. > > > If you can prove that some \data or \record satisfies isSet (or, more > generally, that it is an n-type), then you can put this proof in \use > \level function corresponding to this definition and it will be put in th= e > corresponding universe. > > What does it mean for it to be "put in" the corresponding universe? > I mean F(A,p) will have type \Set0 instead of \Type0 that it would have without the \use \level annotation. > The documentation for \use \level makes it sound as though the > definition *itself*, rather than something equivalent to it, ends up > in the corresponding universe. Yes, F(A,p) *itself* has type \Set0, but A still has type \Type0. > How is the equivalence between A and > F(A,p) accessed inside the proof assistant? > Since F(A,p) is the usual (inductive) data type, you can do everything you can do with other data types. In particular, since it has only one constructor with one parameter A, it is easy to proof that it is equivalent to A. --=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. To view this discussion on the web visit https://groups.google.com/d/msgid/= HomotopyTypeTheory/CAA520ftYLYwiZs0B3fmuYb%3D%3D8mWiOpVD0yVbV8otfTEfgWV8UQ%= 40mail.gmail.com. --0000000000004ae948058fd52077 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable


=
=D0=B2=D1=81, 11 =D0=B0=D0=B2=D0=B3. = 2019 =D0=B3. =D0=B2 02:37, Michael Shulman <shulman@sandiego.edu>:
On Sat, Aug 10, 2019 at 5:25 AM Valery Isaev <= valery.isaev@gm= ail.com> wrote:
> The document is slightly outdated. We do not have the rule iso A B (= =CE=BBx =E2=87=92 x) (=CE=BBx =E2=87=92 x) idp idp i =E2=87=92=CE=B2 A in t= he actual implementation since univalence is true even without it. This rul= e has another problem. It seems that the theory as presented in the documen= t introduces a quasi-equivalence between A =3D B and Equiv A B, which means= that there are some true statements which are not provable in it.

I don't understand.=C2=A0 By "quasi-equivalence" do you mean = an incoherent
equivalence (what the book calls a map with a quasi-inverse)?=C2=A0 If so,<= br> then every quasi-equivalence can of course be promoted to a strong
equivalence.

Yes, a quasi-equivalence i= s a function together with its quasi-inverse. The problem is that we've= got some terms in the theory of which we know nothing=C2=A0about. It's= the same as if I just add a new type=C2=A0Magic without any additio= nal rules. Then we cannot prove anything about it and the resulting theory = won't be equivalent to the original one.
=C2=A0

However, as I said, I'm more worried about the fourth rule coe_{=CE=BB = k =E2=87=92
iso A B f g p q k} a right =E2=87=92=CE=B2 f a.=C2=A0 That's the one th= at I have trouble
seeing how to interpret in a model category.=C2=A0 Can you say anything
about that?

I don't remember well, = but I think the idea is that you need to prove that there is a trivial cofi= bration Eq(A,B) -> F(U^I,A,B), where the first object is the object of e= quivalences between A and B and the second object is the fiber of U^I over = A and B. The fact that this map is a weak equivalence is just the univalenc= e axiom. The problem is to show that it is a cofibration and whether this i= s true or not depends on the definition of Eq(A,B). I don't actually re= member whether I finished this proof.
=C2=A0

> If you can prove that some \data or \record satisfies isSet (or, more = generally, that it is an n-type), then you can put this proof in \use \leve= l function corresponding to this definition and it will be put in the corre= sponding universe.

What does it mean for it to be "put in" the corresponding univers= e?

I mean F(A,p) will have type \Set0 i= nstead of \Type0 that it would have without the \use \level annotation.
=C2=A0
The documentation for \use \level makes it sound as though the
definition *itself*, rather than something equivalent to it, ends up
in the corresponding universe.

Yes, F(A,p)= itself=C2=A0has type \Set0, but A still has type \Type0.
= =C2=A0
How is the eq= uivalence between A and
F(A,p) accessed inside the proof assistant?

=
Since F(A,p) is the usual (inductive) data type, you can do everything= you can do with other data types. In particular, since it has only one con= structor with one parameter A, it is easy to proof that it is equivalent to= A.=C2=A0

--
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.
To view this discussion on the web visit https:/= /groups.google.com/d/msgid/HomotopyTypeTheory/CAA520ftYLYwiZs0B3fmuYb%3D%3D= 8mWiOpVD0yVbV8otfTEfgWV8UQ%40mail.gmail.com.
--0000000000004ae948058fd52077--