Was sind die Gleichungsgesetze für Nulltypen?

13

Haftungsausschluss : Während ich mich für Typentheorie interessiere, betrachte ich mich selbst nicht als Experten für Typentheorie.

Im einfach getippten Lambda-Kalkül hat der Null-Typ keine Konstruktoren und einen eindeutigen Eliminator:

ΓM:0Γinitial(M):A

Aus denotational Sicht der Gleichung initial(M1)=initial(M2) ist offensichtlich , (wenn die Typen sinnvoll).

Aus dieser Perspektive kann ich jedoch auch ableiten, dass, wenn M,M:0 , dann: M=M . Dieser Abzug scheint stärker zu sein, obwohl mir ein bestimmtes Modell, das dies zeigt, entgeht.

(Ich habe allerdings einige Beweistheoretische Anschauungen: Es spielt keine Rolle, welchen Widerspruch Sie verwenden, um einen Einwohner zu erhalten, aber es kann verschiedene Widerspruchsbeweise geben.)

Meine Fragen sind also:

  1. Was sind die Standardgleichungsgesetze für Nulltypen?
  2. Sind einige von ihnen als η oder β Gesetze klassifiziert ?
Ohad Kammar
quelle

Antworten:

12
  1. Die Standardgleichungsregeln für den leeren Typ lauten , wie Sie vermuten, . Denken Sie an das standardmäßige satztheoretische Modell, bei dem Mengen nach Typen interpretiert werden: Summentypen sind disjunkte Vereinigungen, und der leere Typ ist die leere Menge. Also müssen auch zwei beliebige Funktionen e , e ' : Γ 0 gleich sein, da sie einen gemeinsamen Graphen haben (nämlich den leeren Graphen). .Γe=e:0e,e:Γ0

  2. Der leere Typ hat keine Regeln, da es keine Einführungsformulare dafür gibt. Seine einzige Gleichungsregel ist ein ηβη Regel. Abhängig davon, wie streng Sie interpretieren möchten, was eine eta-Regel ist, möchten Sie diese möglicherweise in ein plus eine Pendelumwandlung aufteilen. Die strenge η- Regel lautet:ηη

    e=initial(e)

    Die Pendlerversicherung lautet:

    C[initial(e)]=initial(e)

BEARBEITEN:

Deshalb impliziert die Verteilung beim Null-Typ die Gleichheit aller Abbildungen .A0

Um die Notation zu korrigieren, schreiben wir , um die eindeutige Zuordnung von 0 zu A zu sein , und schreiben wir e : A 0 , um eine Zuordnung von A zu 0 zu sein .!A:0A0Ae:A0A0

Nun sagt die Verteilbarkeit Bedingung , dass es ein Isomorphismus . Da ursprüngliche Objekte bis zum Isomorphismus eindeutig sind, bedeutet dies, dass A ×i:0A×0 selbst ein initiales Objekt ist. Damit können wir nun zeigen, dass A selbst ein Ausgangsobjekt ist.A×0A

Da ein Ausgangsobjekt ist, kennen wir die Abbildungen π 1 : A × 0 A und ! EINA×0π1:A×0A sind gleich.!Aπ2

Um zu zeigen, dass ein Ausgangsobjekt ist, müssen wir einen Isomorphismus zwischen A und 0 zeigen . Wählen wir e : A 0 und ! A : 0 A als Komponenten des Isomorphismus. Wir wollen zeigen, dass e ! A = i d 0 und ! Ae = i d A .A0e:A0!A:0Ae!A=id0!Ae=idA

Zeigen, dass e!A=id0 ist unmittelbar, da es nur eine Karte vom Typ gibt und wir wissen, dass es immer eine Identitätskarte gibt.00

Um die andere Richtung zu zeigen, notiere

idA=π1(idA,e)Product equations=!Aπ2(idA,e)Since A×0 is initial=!AeProduct equations

Wir haben also einen Isomorphismus , und so ist A ein Ausgangsobjekt. Daher sind die Abbildungen A 0 eindeutig. Wenn Sie also e , e 'haben : A 0 , dann ist e = e ' .A0AA0e,e:A0e=e

EDIT 2: Es stellt sich heraus, dass die Situation schöner ist als ich ursprünglich dachte. Ich habe von Ulrich Bucholz gelernt, dass es offensichtlich ist (im mathematischen Sinne von "retrospektiv offensichtlich"), dass jedes biCCC distributiv ist. Hier ist ein süßer kleiner Beweis:

Hom((A+B)×C,(A+B)×C)Hom((A+B)×C,(A+B)×C)Hom((A+B),C(A+B)×C)Hom(A,C(A+B)×C)×Hom(B,C(A+B)×C)Hom(A×C,(A+B)×C)×Hom(B×C,(A+B)×C)Hom((A×C)+(B×C),(A+B)×C)
Neel Krishnaswami
quelle
1
Zu 1: Ich stelle mir einen Null-Typ als Ausgangsobjekt vor. Anfängliche Objekte können mehrere Pfeile in sie, aber kann man nur Pfeil haben aus von ihnen. Mit anderen Worten, ich sehe nicht sofort einen Grund, warum das Bi-CCC bedeutet, dass 0 unterirdisch ist. Ist dort eines?
Ohad Kammar
Ja: Die Tatsache , dass der STLC mit Summen einen muss distributive bi-CCC ( ) zu interpretieren, und die Einzigartigkeit für den 0 - Typen kommt , wie die nullary Version davon. (Versuchen Sie, die Interpretation der Eliminierungsregel für Summen aufzuschreiben, und Sie werden es sehen.)(X×A)+(X×B)X×(A+B)
Neel Krishnaswami
Ich folge nicht Die Verteilungsfähigkeit beträgt mit einer Inversen. Warum impliziert das, dass 0 unterirdisch ist? initial:0A×00
Ohad Kammar
Aha! Danke für diesen Beweis! Und für die Geduld auch!
Ohad Kammar
bezüglich edit 2: Linke Adjoints behalten Colimits bei. Wenn die Kategorie ist Kartesischen geschlossen, dann ist links adjungierten zu ( - ) C so ( A + B ) × C ist die Summe A × C + B × C . ()×C()C(A+B)×C A×C+B×C
Ohad Kammar
8

Die Gleichung fängt nur die Tatsache ein, dass 0 höchstens ein Element hat, also glaube ich nicht, dass Neel die ganze Geschichte einfängt . Ich würde den leeren Typ axiomatisierene=e:00 folgendermaßen.0

Es gibt keine Einführungsregeln. Die Eliminierungsregel ist Die Gleichung lautetmagicτ(e)=e':τwobeie:0unde':τ. Inτist jeder Typ. Die Gleichung ist wie folgt motiviert: Wenn Sie es geschafft haben, den Termmagicτ(e) zu bilden,dann ist

e:0magicτ(e):τ.
magicτ(e)=e:τ
e:0e:ττmagicτ(e) ist bewohnt von0e, aber das ist absurd, damit alle Gleichungen gelten. Eine andere Möglichkeit, den gleichen Effekt zu erzielen, besteht darin, die Gleichung aufzustellen, die vielleicht nicht so schön ist, weil sie mit dem Kontext spielt. Andererseits zeigt es deutlicher, dass wir die Tatsache angeben, dass zwei beliebige Morphismen von 0 bis τ gleich sind (das Γ ist eine Ablenkung in einem CCC).
x:0,Γe1=e2:τ
0τΓ
Andrej Bauer
quelle
1
Hallo Andrej, die Gleichung, die du vorschlägst, lässt sich aus der von mir angegebenen Pendelumwandlung ableiten. ist ableitbar von C [ m a g i c ( e ) ] = m a g i c ( e ) , da m a g i c ( e ) eigentlich nicht vorkommen muss auf der linken Seite. Die Analogie ist zu C [ c amagic(e)=eC[magic(e)]=magic(e)magic(e) , wenn es in beiden Zweigen in Ordnung ist, das Ergebnis einer Fallanalyse nicht zu verwenden. C[case(e,x.e,y.e)]=case(e,x.C[e],y.C[e])
Neel Krishnaswami
Ich sollte jedoch hinzufügen, dass mir die Darstellung mit Kontexten besser gefällt - in der Tat denke ich, dass es im Allgemeinen am saubersten ist, wenn Sie im Kontext tatsächlich Gleichungen für Summenwerte zulassen! Das ist viel schöner für echte Beweise als Spiele mit Pendelumwandlungen, IMO. (IIRC, dies entspricht dem Hinzufügen der zusätzlichen Annahme von stabilen Nebenprodukten, aber für alle Modelle kann ich vernünftigerweise sehen, dass dies wichtig ist.)
Neel Krishnaswami,
Ah ja, ausgezeichnet. Es war zu spät für mich, über Umbauten nachzudenken, also tat ich so, als hättest du diesen Teil nicht geschrieben. Jetzt kann Ohad seine Wahl treffen.
Andrej Bauer
1
Ich habe einige Strukturregeln ( , β usw.) in einer Klasse von Modellen validiert . Obwohl ich weiß, dass der Satz von Gleichungen, den ich gegeben habe, nicht vollständig ist (Sie benötigen dafür CBPV mit komplexen Werten und Stapeln), wollte ich zumindest die Standardgleichungen erfassen, die verwendet werden, um die Vollständigkeit zu beweisen, wenn ich genügend Gleichungen habe. Mit anderen Worten, ich wollte die Standardgleichungsgesetze für Nulltypen. ηβ
Ohad Kammar
1
Es gibt keine Standardgleichungsgesetze für Nulltypen. Logiker hatten schon immer Angst vor dem leeren Universum des Diskurses, und Informatiker hatten schon immer Angst vor dem leeren Typ. Sie nannten sogar einen nicht leeren Typ "void", um den leeren Typ abzulehnen.
Andrej Bauer