Können Sie eine Intuition hinter Coherent Spaces erklären?

13

Die lineare Logik wird mit kohärenten Räumen interpretiert und ist in Girards Arbeiten ein wichtiger Bestandteil. Ich kenne alle drei Hauptmethoden, um sie formal zu definieren, und sie stellen kein Problem dar, Dinge zu verwenden und zu beweisen, aber ich kann einfach nicht verstehen, was sie bedeuten .

Es fühlt sich wirklich so an, als gäbe es eine Möglichkeit, sie zu verstehen . Zuallererst gibt es einige Beispiele, die Funktionen auf Booleanern verwenden (wie in einem Wiki irgendwo ). Und es deutet auf etwas Interessantes und Bedeutendes hinter der formalen Definition hin. Es boolist jedoch ein sehr einfacher zusammenhängender Raum ohne Größenklassen > 1. Kann das jemand ausarbeiten?

Eine andere Sache, die Girard irgendwo sagt, dass jeder Punkt eines kohärenten Raums eine bestimmte "Folge von Fragen / Antworten" darstellt, wobei zwei Punkte kohärent sind, wenn sie sich "negativ aufteilen (dh auf verschiedene Fragen)" und inkohärent, wenn sie sich auf verschiedene Antworten aufteilen [1] Es scheint eine einfach zu verstehende Idee zu sein, aber ich kann kein Beispiel erfinden, was bedeutet, dass ich es nicht wirklich verstehe ...

Könnte mir bitte jemand dabei helfen?

[1] JY Girard, Das Phantom der Transparenz . URL: http://iml.univ-mrs.fr/~girard/longo1.pdf

valya
quelle
Haben Sie Girards Linear Logic -Originalpapier überprüft ?
Kaveh
@Kaveh Ich habe es (schnell) durchgesehen, aber es scheint nichts zu bieten, was "The Blind Spot" nicht hat (was ich gelesen habe) ... Es hat eine Definition, aber keine Metapher / Interpretation / Erklärung.
Valya
2
Es ist lange her, dass ich mich mit diesen beschäftigt habe, aber ich denke, wenn Sie wirklich verstehen wollen, woher diese kommen, müssen Sie zurückgehen, um die Heyting-Algebra- und Scott-Domain-Semantik der intuitionistischen Logik zu vervollständigen. Domänen (dcpo) werden im Allgemeinen zum Ausdrücken von Teilinformationen verwendet. Zwei Elemente x und y sind kompatibel, wenn ihre Informationen kombiniert werden können, dh {x, y} hat ein sup. Kohärenz ist genau diese Kompatibilität von Informationen. (Ich denke, das Linear Logic-Papier ist lesenswert, um zu verstehen, woher Girards Ideen stammen.)
Kaveh,
Das Geräusch darüber, was ich mit Domains machen soll, ja ... Danke! Ich werde in diese Richtung wandern und dann, wenn niemand antwortet, vielleicht eines Tages die Antwort selbst schreiben.
Valya
(Und ich werde auch einen guten Blick auf die Zeitung werfen, danke - es stellt sich heraus, dass ich die falsche
überflogen habe

Antworten:

10

Die Intuition hinter Kohärenzräumen besteht darin, dass die Elemente eines Kohärenzraums Beobachtungen einiger zugrunde liegender Daten darstellen. Die Kohärenzbeziehung gibt Aufschluss darüber, ob zwei Beobachtungen von derselben Dateneinheit stammen könnten.

Nehmen wir konkret an, wir haben eine Reihe von Tieren

Animals = {cat, duck, fish}

Nun können wir eine Reihe von Beobachtungen machen:

Observations = {warm-blooded, swims, water-breathing, furry}

Nehmen wir an, dass zwei Beobachtungen kompatibel sind , wenn beide vom gleichen Tier stammen könnten. Jede Beobachtung ist mit sich selbst vereinbar und zusätzlich:

Wir wissen, dass Warmblütigkeit mit Schwimmen vereinbar ist, da Enten sowohl warmblütig als auch schwimmend sind. Warmblütig zu sein und Wasser zu atmen ist nicht kompatibel, da wir keine Tiere haben, die sowohl warmblütig als auch Wasser atmen.

ObservationsObservations

Neel Krishnaswami
quelle
aber so wie ich es verstehe, wäre der Wert von Typ Observationseine Clique - also keine Beobachtung, sondern eine Menge von ihnen. es ist also eher so [Observation], oder? das gleiche mit Animals(die Cliquen wären Singletones, aber immer noch) ...
Valya
Natürlich nicht einmal genau [Observation], aber trotzdem ... Ich habe Probleme, ein Beispiel zu finden, bei dem eine Clique ohne Singleton einen sinnvollen Wert hätte
valya
6

Es fiel mir immer schwer, eine Intuition für Kohärenzräume zu entwickeln, bis ich mich mit der Domänentheorie vertraut machte und Girards "Das System F variabler Typen, fünfzehn Jahre später" las. Kohärenzräume sind nur eine besondere Art von Domäne, und ich fand es viel einfacher zu verstehen, was Kohärenz bedeutet, wenn man von dort ausgeht. Ich werde versuchen, eine Erklärung zu geben, die für mich mehr oder weniger sinnvoll war.

Stellen Sie sich vor, Sie möchten Programme untersuchen, die Integer-Eingaben in Integer-Ausgaben umwandeln. Im Allgemeinen können diese Programme eine Endlosschleife bilden. Daher ist es sinnvoll, sie mathematisch als Teilfunktionen von Ganzzahl zu Ganzzahl zu modellieren. Wenn das Programm eine Endlosschleife ausführt, ist die entsprechende Teilfunktion für diese Eingabe undefiniert. Wir können eine solche Teilfunktion fals Graph betrachten : eine Menge von Paaren von ganzen Zahlen (n, m), fdie auf nund gleich definiert sind m. Dies ermöglicht uns, diese Funktionen als Kohärenzraum darzustellen:

  • Das Netz des Kohärenzraums ist die Menge von Paaren von ganzen Zahlen (n, m).
  • Zwei Paare (n, m)und (n', m')sind genau dann kohärent, wenn nund n'sich unterscheiden, oder mundm' gleich sind.

Durch das Auspacken von Definitionen sehen wir, dass jede Clique dieses Kohärenzraums der Graph einer Teilfunktion ist und umgekehrt. Wir können die Kohärenzbeziehung so interpretieren, dass eine Teilfunktion für eine Eingabe definiert ist und nur ein Ergebnis für diese Eingabe erzeugt. Wenn Sie an andere Arten domänentheoretischer Semantik gewöhnt sind, entspricht die Einbeziehung von Cliquen der üblichen Scott-Reihenfolge für Teilfunktionen an ganzen Zahlen.

Arthur Azevedo De Amorim
quelle