Was genau ist der semantische Unterschied zwischen Menge und Typ?

33

EDIT: Ich habe jetzt eine ähnliche Frage zum Unterschied zwischen Kategorien und Mengen gestellt.

Jedes Mal, wenn ich über Typentheorie lese (die zugegebenermaßen eher informell ist), kann ich nicht wirklich verstehen, wie sie sich konkret von der Mengenlehre unterscheidet .

Ich verstehe, dass es einen konzeptionellen Unterschied zwischen dem Sprichwort "x gehört zu einer Menge X" und "x ist vom Typ X" gibt, da eine Menge intuitiv nur eine Sammlung von Objekten ist, während ein Typ bestimmte "Eigenschaften" hat. Trotzdem werden Mengen oft auch nach Eigenschaften definiert, und wenn ja, habe ich Probleme zu verstehen, wie diese Unterscheidung in irgendeiner Weise von Bedeutung ist.

So in der die meisten konkreten Art und Weise möglich, was genau bedeutet es bedeutet , etwax zu sagen , dass es vom Typ , im Vergleich zu sagen , dass es ein Element in dem Satz S ?STS

(Sie können jeden Typ und Satz auswählen, der den Vergleich am klarsten macht.)

user56834
quelle
In welchem ​​Kontext verwenden Sie / hören Sie das Wort "Typ"? Ist es, wie Ihr Name schon sagt, Programmiersprachen? Weil ich denke, dass die Antworten unten etwas anderes annehmen.
einpoklum - Monica wieder einsetzen
@einpoklum, ich bin mir nicht zu 100% sicher, wie ich den "Kontext" beschreiben soll, aber im Grunde ist es so: Ich versuche die Rolle von Typen in der Mathematik zu verstehen. Im Wesentlichen haben Mengen (wie ich es sehe) zwei Kontexte: Erstens werden sie als Sammlungen von Objekten verwendet, um die alltägliche Mathematik zu betreiben. Zweitens sind sie Objekte in der axiomatischen Mengenlehre, wo sie meistens als sehr seltsames, aber hilfreiches Werkzeug verwendet werden Sprechen Sie über Mathematik in der Logik erster Ordnung, indem Sie Mengen mit Funktionen und Zahlen korrespondieren lassen und so weiter. Mich interessiert vor allem die Beziehung zwischen "Menge" im ersten Sinne und "Typ".
user56834
Welche Art von Rolle? Welche Arten sehen Sie in Mathepapieren / Lehrbüchern oder welche Arten von Variablen in Computerprogrammen?
einpoklum - Monica 30.04.18 um 12:43 wieder
1
@einpoklum, diese Frage bezieht sich auf diejenigen in Mathepapieren. (Obwohl ich eigentlich auch daran interessiert bin, den fundamentalen Unterschied zwischen Typen in Mathematik und Typen in Programmiersprachen zu kennen, falls vorhanden. Aber darum geht es in dieser Frage nicht).
user56834

Antworten:

29

Um die Differenz zwischen den Sätzen und Arten zu verstehen, muss diejenigen , gehen Sie zurück zu Pre -mathematical Ideen von „Sammlung“ und „Bau“, und sehen , wie Sätze und Typen mathematisieren diese.

Es gibt ein Spektrum von Möglichkeiten, worum es in der Mathematik geht. Zwei davon sind:

  1. Wir verstehen Mathematik als eine Aktivität, in der mathematische Objekte nach bestimmten Regeln konstruiert werden (stellen Sie sich Geometrie als die Aktivität vor, Punkte, Linien und Kreise mit einem Lineal und einem Kompass zu konstruieren). So mathematische Objekte werden nach organisiert , wie sie gebaut , und es gibt verschiedene Arten von Bau. Ein mathematisches Objekt wird immer auf eine eindeutige Weise konstruiert, die seinen eindeutigen Typ bestimmt.

  2. Wir denken an Mathematik als ein riesiges Universum voller vorbestehender mathematischer Objekte (denken Sie an die geometrische Ebene als gegeben). Wir entdecken, analysieren und denken über diese Objekte nach (wir stellen fest, dass es Punkte, Linien und Kreise in der Ebene gibt). Wir sammeln sie im Set . Normalerweise sammeln wir Elemente, die etwas gemeinsam haben (zum Beispiel alle Linien, die durch einen bestimmten Punkt verlaufen), aber im Prinzip kann eine Menge eine beliebige Auswahl von Objekten zusammenhalten. Eine Menge wird durch ihre Elemente und nur durch ihre Elemente spezifiziert. Ein mathematisches Objekt kann zu vielen Mengen gehören.

Wir sagen nicht, dass die obigen Möglichkeiten die einzigen sind oder dass eine von ihnen vollständig beschreibt, was Mathematik ist. Nichtsdestotrotz kann jede Ansicht als nützlicher Ausgangspunkt für eine allgemeine mathematische Theorie dienen, die eine breite Palette mathematischer Aktivitäten sinnvoll beschreibt.

Es ist natürlich, einen Typ zu nehmen und sich die Sammlung aller Dinge vorzustellen, die wir nach den Regeln von konstruieren können . Dies ist die Erweiterung von , und es ist nicht selbst. Hier sind zum Beispiel zwei Typen mit unterschiedlichen Konstruktionsregeln, die jedoch dieselbe Erweiterung haben:T T TTTT T

  1. Die Art der Paare denen als natürliche Zahl und als Beweis dafür konstruiert sind, dass eine gerade Primzahl größer als .n p n 3(n,p)npn3

  2. Die Art der Paare denen als natürliche Zahl und als Beweis dafür konstruiert sind, dass eine ungerade Primzahl kleiner als .m q m 2(m,q)mqm2

Ja, das sind dumme, triviale Beispiele, aber der springende Punkt ist: Beide Typen haben nichts in ihrer Erweiterung, aber sie haben unterschiedliche Konstruktionsregeln. Im Gegensatz dazu sind die Mengen und sind gleich, weil sie dieselben Elemente haben.{ m Nm  ist eine ungerade Primzahl kleiner als  2 }

{nNn is an even prime larger than 3}
{mNm is an odd prime smaller than 2}

Beachten Sie, dass es bei der Typentheorie nicht um Syntax geht. Es ist eine mathematische Theorie der Konstruktionen, genau wie die Mengenlehre eine mathematische Theorie der Sammlungen ist. Es kommt einfach so vor, dass die üblichen Darstellungen der Typentheorie die Syntax betonen und folglich die Leute am Ende denken, Typentheorie sei Syntax. Das ist nicht der Fall. Ein mathematisches Objekt (Konstruktion) mit einem syntaktischen Ausdruck zu verwechseln, der es darstellt (ein früherer Begriff), ist ein grundlegender Kategoriefehler, der die Logik seit langem verwirrt hat, aber nicht mehr.

Andrej Bauer
quelle
1
Schön, danke! Könnten Sie ein Detail klarstellen? Wenn Sie die beiden Typen auflisten, deren Erweiterung beide leer sind, sagen Sie "den Typ, dessen Elemente ... sind". Ist das, nur aus Gründen der Klarheit, eine 100% korrekte Art, es auszudrücken? Sie haben im vorigen Satz gesagt, dass ein Typ keine Sammlung ist. Es scheint also, dass er keine "Elemente" haben kann (die ich mit Mengen assoziiere). So wie Sie es jetzt geschrieben haben, ist es im Grunde so, als würden Sie den Typ gemäß der Menge definieren, die seine Erweiterung darstellt. Wenn Sie dies nicht beabsichtigt hätten, könnten Sie sie genauer umformulieren, um ihre Idee als Typen zu erfassen?
user56834
Die Erweiterung eines Typs ist ein sehr nützliches Konzept, und da es sich um eine Art Sammlung handelt, können wir "Element der Erweiterung eines Typs" sagen. Dies ist umständlich und wird oft nur als "Element eines Typs" abgekürzt. Ich habe die Formulierung entfernt, um die Möglichkeit von Verwirrung zu verringern, aber hüte dich, es ist übliche Terminologie.
Andrej Bauer
Danke, das klärt. Ist es also richtig, folgendes zu sagen? Zu sagen, dass ein Objekt "vom Typ T" ist, bedeutet dasselbe wie, dass das Objekt "ein Element der Erweiterung von T" ist, so dass es einen natürlichen Gegensatz von Typen zu Mengen gibt. Das Gegenteil ist jedoch nicht der Fall, da jede Menge auf verschiedene Arten konstruiert werden kann. Im Wesentlichen ist der Unterschied zwischen Menge und Typ aus der Perspektive eines bestimmten Objekts nicht wichtig , da und (wobei die Erweiterung von ) genau die gleiche Information über liefern . Allerdingsx : T x X T X T T xxx:TxXTXTTx
user56834
Der Unterschied ist relevant, wenn wir über Typen und Mengen sowie deren Eigenschaften und Beziehungen sprechen möchten . Mit anderen Worten, die Informationen, die wir verlieren, wenn wir anstelle von sagen, sagen uns nichts Relevantes über , aber das gleiche gilt möglicherweise nicht, wenn wir z. Subtyp-Beziehungen? Ist das korrekt? x : T xxXTx:Tx
user56834
4
Ja, man fragt sich, wo diese Bücher sind. Jemand sollte sie schreiben.
Andrej Bauer
11

Zu Beginn befinden sich Sets und Typen nicht einmal in derselben Arena. Mengen sind die Objekte einer Theorie erster Ordnung, wie beispielsweise der ZFC-Mengen-Theorie. Während Typen wie überwucherte Sorten sind. Anders ausgedrückt ist eine Mengenlehre eine Theorie erster Ordnung innerhalb der Logik erster Ordnung. Eine Typentheorie ist eine Erweiterung der Logik. Beispielsweise wird die Martin-Löf-Typentheorie nicht als Theorie erster Ordnung in der Logik erster Ordnung dargestellt. Es ist nicht üblich, gleichzeitig über Mengen und Typen zu sprechen.

SVscale:S×VVscale(scale(s,v),v)f(x)fXYXYff(x)(x:X)y=3x:X

xyf(x)=y(x,y)fp.pfp=(x,y)

p.pf(z.zp[z=x(w.wzw=y)])
fπ(7)=3π
f(x)={N,if x=17,if x=QxRR,if x=(Z,N)
ist eine völlig legitime Funktion in der Mengenlehre. In der Typentheorie gibt es dazu auch nur annähernd Entsprechendes. Am nächsten wäre es, Codes für ein Tarskian-Universum zu verwenden. Mengen sind die Objekte der Mengenlehre; Typen sind nicht Gegenstand der Typentheorie.

Ein Typ ist keine Sammlung von Dingen (und auch keine Menge ...) und wird nicht durch eine Eigenschaft definiert. Ein Typ ist eine syntaktische Kategorie, mit der Sie wissen, welche Operationen auf Begriffe dieses Typs anwendbar sind und welche Ausdrücke gut geformt sind. Aus der Sicht der Sätze als Typen sind die zu klassifizierenden Typen die gültigen Beweise für den Satz, dem der Typ entspricht. Das heißt, die wohlgeformten (dh gut typisierten) Begriffe eines gegebenen Typs entsprechen den gültigen Beweisen (die auch syntaktische Objekte sind) des entsprechenden Satzes. In der Mengenlehre passiert so etwas nicht.

Mengen- und Typentheorie sind sich eigentlich gar nicht ähnlich.

Derek Elkins
quelle
1
Es ist falsch, dass Typen nur syntaktische Entitäten sind.
Andrej Bauer
1
Dies ist sehr hilfreich, aber ein Hauptpunkt in Ihrer Antwort nervt mich. Es scheint mir, dass es ein Fehler ist (den viele Leute machen, oder alternativ ist es kein Fehler und ich liege falsch), zu sagen, dass "ein Set keine Ansammlung von Dingen ist". Ich würde sagen, dass ein Set eine Sammlung von Dingen ist. Das ist die grundlegendste Eigenschaft einer Menge. Woher wissen wir überhaupt, dass z. B. ZFC die richtigen Axiome für die Auswahl sind (und nicht völlig willkürliche Formeln), ohne zu sagen, dass sie wahr sind, vorausgesetzt, dass Mengen Sammlungen von Objekten sind? Natürlich verstehe ich das ...
user56834
1
@ Programmer2134 Um das zu beantworten, müssten wir uns mit der semantischen Bedeutung des Wortes "Sammlung" befassen. Wir können nicht sicher sein, ob sie "richtig" sind, es sei denn, Sie nehmen sich die Zeit, um genau zu definieren, was "richtig" bedeutet. Was wir jedoch sagen können, ist, dass "Menge" das Ergebnis von über hundert Jahren von Mathematikern ist, die sich mit dem Konzept einer Sammlung befassen und ein konsistentes System suchen, das dem intuitiven Konzept einer Sammlung entspricht. Um diese Konsistenz zu erreichen, mussten sie Entscheidungen treffen. Zum Beispiel sind Mengen nicht die einzige Sammlung in der Mathematik. Eine "Klasse" beschreibt auch eine Sammlung.
Cort Ammon
1
xTxT
9

xT xS

Ein Beispiel

Um diese Unterscheidung zu verdeutlichen, verwende ich das Beispiel in den Vorlesungsskripten von Herman Geuvers . Als erstes betrachten wir ein Beispiel für das Bewohnen eines Typs:

3+(78)5:Nat,
3{nNx,y,zN+(xn+ynzn)}

Der Hauptunterschied besteht darin, dass wir, um zu testen, ob der erste Ausdruck eine natürliche Zahl ist, keine semantische Bedeutung berechnen müssen, sondern lediglich die Tatsache ablesen müssen, dass alle Literale vom Typ Nat sind und alle Operatoren geschlossen am Typ Nat.

33

Algorithmen gegen Beweise

Zusammenfassend gesagt, werden Typen häufig für 'einfache' Behauptungen zur Syntax eines Ausdrucks verwendet, so dass die Zugehörigkeit eines Typs von einem Algorithmus überprüft werden kann , während zum Testen der Zugehörigkeit zu einer Menge in der Regel ein Beweis erforderlich ist .

Um zu sehen, warum diese Unterscheidung nützlich ist, betrachten Sie einen Compiler einer typisierten Programmiersprache. Wenn dieser Compiler einen formalen Beweis für die Überprüfung von Typen erstellen muss, wird der Compiler aufgefordert, eine fast unmögliche Aufgabe zu erledigen (die automatische Beweisführung ist im Allgemeinen schwierig). Wenn der Compiler dagegen einfach einen (effizienten) Algorithmus ausführen kann, um die Typen zu überprüfen, kann er die Aufgabe realistisch ausführen.

Eine Motivation für eine strikte (er) Interpretation

Es gibt mehrere Interpretationen der semantischen Bedeutung von Mengen und Typen. Während unter der hier vorgenommenen Unterscheidung Erweiterungstypen und Typen mit unentscheidbarer Typprüfung (wie die in NuPRL verwendeten, wie in den Kommentaren erwähnt) keine "Typen" wären, können andere diese natürlich als solche bezeichnen (ebenso kostenlos) wie sie sind, um sie etwas anderes zu nennen, solange ihre Definitionen passen).

Wir (Herman Geuvers und ich) ziehen es jedoch vor, diese Interpretation nicht aus dem Fenster zu werfen, wofür ich (nicht Herman, obwohl er vielleicht zustimmt) die folgende Motivation habe:

Erstens ist die Absicht dieser Interpretation nicht so weit von der von Andrej Bauer entfernt. Die Absicht einer Syntax besteht normalerweise darin, zu beschreiben, wie etwas konstruiert werden soll, und einen Algorithmus zu haben, um es tatsächlich zu konstruieren, ist im Allgemeinen nützlich. Darüber hinaus werden die Merkmale einer Menge normalerweise nur benötigt, wenn wir eine semantische Beschreibung wünschen, für die Unentscheidbarkeit zulässig ist.

Der Vorteil unserer strengeren Beschreibung besteht also darin, die Trennung einfacher zu halten und eine Unterscheidung zu erhalten, die direkter mit der üblichen praktischen Verwendung zusammenhängt. Dies funktioniert gut, solange Sie Ihre Nutzung nicht wie bei NuPRL benötigen oder lockern möchten.

Diskrete Eidechse
quelle
3
Die Typprüfung muss nicht entscheidend sein (obwohl dies sicherlich wünschenswert ist). Beispielsweise verlangt NuPRL vom Benutzer, einen Beweis dafür zu erbringen, dass ein Begriff in einem Typ vorkommt.
Derek Elkins
3
3...
1
@DerekElkins Ich bin nicht mit NuPRL vertraut, aber zB der Proof-Assistent Coq führt mit Sicherheit eine Typprüfung durch (dh es handelt sich um den angegebenen Begriff für den Typ meines Theorems). Wie überprüft NuPRL den Beweis, wenn der Benutzer die Tatsache „beweisen“ muss, dass ein Begriff eines bestimmten Typs vorliegt? (Mit anderen Worten, dies klingt so, als würde NuPRL die Curry-Howard-Korrespondenz nicht verwenden. Was wird also verwendet?)
Diskrete Eidechse
1
@ Discretelizard Ich sage nicht, dass NuPRL typisch ist. Es ist definitiv der übliche Fall, dass die Typprüfung entscheidbar ist. Ich empfehle dringend, sich damit vertraut zu machen, nur weil es einen ganz anderen Weg geht. NuPRL ist eher ein Curry-Stil als ein kirchlicher Kalkül, was es eher zu einem Typverfeinerungssystem macht. Anstatt nur Terme zu schreiben (oder Taktiken, die Terme erzeugen), haben Sie auf jeden Fall ein Proof-System im LCF-Stil, mit dem Sie Ableitungen selbst eingeben können. Wahrscheinlich sind die Ableitungen wichtig, und es ist ein bisschen ein "Zufall", dass wir sie aus Begriffen ableiten können.
Derek Elkins
3
4

Ich glaube, einer der konkretesten Unterschiede in Bezug auf Mengen und Typen ist der Unterschied in der Art und Weise, wie die "Dinge" in Ihrem Geist in die formale Sprache kodiert werden.

Mit Sets und Typen können Sie über Dinge und Sammlungen von Dingen sprechen. Der Hauptunterschied besteht darin, dass Sie bei Sets jede Frage stellen können, die Sie über die Dinge haben möchten, und dies wird vielleicht wahr sein, vielleicht auch nicht. bei typen muss man erst beweisen, dass die frage sinnvoll ist.

B={true,false}N={0,1,}true=1

0[0]={}n+1[n+1]={[n]}[n]truefalsetrue=1true1

a=babtrue=1SBNιB:BSιN:NSιB(true)=ιN(1)

(ifvery_hard_questionthen1elsetrue)=1

Zusammenfassend lässt sich sagen, dass Sie mit Sets jede gewünschte Frage stellen können. Mit Typen werden Sie jedoch gezwungen, Codierungen explizit anzugeben, wenn die Antwort davon abhängen kann.

xavierm02
quelle
Rsin(2)
@AndrejBauer Richtig. Würden Sie zustimmen, dass diese Antwort einen Unterschied zwischen einfach sortierten Theorien (einschließlich der meisten Mengen-Theorien oder zumindest der häufigsten Theorien) und mehrfach sortierten Theorien (einschließlich aller (?) Typ-Theorien) gibt?
Xavierm02
Auch in einer einsortierten Theorie muss man Begriffe von Formeln unterscheiden ...
Andrej Bauer
@AndrejBauer Ich verstehe deinen zweiten Kommentar nicht.
Xavierm02
Eine einsortierte Theorie erster Ordnung hat zwei syntaktische Kategorien: logische Formeln und Terme . Man muss sicherstellen, dass sie nicht verwechselt werden, sonst könnte man am Ende " " schreiben(xX.ϕ(x))N