Gibt es so etwas wie einen schwachen Homomorphismus der Kohlegebra?

12

Wenn ein Endofunktor F:SetSet , können wir Beobachtungsfunktionen als Funktionen definieren, die für jede Kohlegebra polymorph sind, dh für jede Kohlegebra definiert ist . Eine andere Art, Beobachtungsfunktionen zu betrachten, sind die Funktionen der endgültigen Kohle, falls vorhanden . Wir erhalten den Polymorphismus automatisch, indem wir die Beobachtungsfunktion mit dem einzigartigen Homomorphismus zum endgültigenFobsFA,c:AFA

obs:A,c.AB
FF-Kohlegebra. Dies funktioniert aber nur, wenn die endgültige Coalgebra existiert.F

Eines der bestimmenden Merkmale einer Beobachtungsfunktion besteht darin, dass sie jeden rechts zusammengesetzten Homomorphismus der Kohlegebra aufgrund seines Polymorphismus aufhebt. Wenn ein Coalgebra-Homomorphismus ist, dann: Während meiner Recherche kam mir die Idee eines schwachen Coalgebra-Homomorphismus. Die Idee ist, dass wir einen Kohlegebra-Homomorphismus "vortäuschen" können, wenn wir die Beobachtungsfunktion im Voraus kennen. Wir könnten also befriedigen, aber nur für ein bestimmtes .homF

obs=obshom
obs=obshom
obs

Beispielsweise sei und sei definiert als Das heißt, nimmt die ersten beiden Elemente von ein Strom.FX={0,1}×Xobs

obs:A,c.A{0,1}2
obs=(π1c),(π1cπ2c)
obs

Dann müsste ein F-Kohlegebra-Homomorphismus sicherstellen, dass alle Elemente des Stroms erhalten bleiben, wohingegen ein schwacher Homomorphismus für nur die ersten beiden Elemente des Stroms erhalten muss.obs

In meiner Forschung wäre dieser Begriff nützlich, um zu zeigen, dass eine Kohlebra mit einer anderen beobachtungskonform ist, indem gezeigt wird, dass jede endliche lineare Beobachtungsfunktion einen schwachen Homomorphismus von der ersten zur zweiten Kohlebra aufweist. Mit anderen Worten kann jede endliche lineare Beobachtung in der ersten Kohlegebra in der zweiten Kohlegebra reproduziert werden.

(Was ich unter linearer Beobachtungsfunktion verstehe, ist größtenteils irrelevant, aber zum Teilen ... Eine lineare Beobachtungsfunktion ist mehr oder weniger eine, die jeden Zustand des Trägersatzes nur einmal verwendet. Ich versuche, ein Orakel zu modellieren. und der Benutzer darf nicht zurückgehen und so tun, als hätte er nie eine Frage gestellt.)

Meine Fragen sind also:

  1. Wurde dies untersucht? Gibt es schon "schwache Homomorphismen der Kohlegebra", vielleicht unter einem anderen Namen?

  2. Gibt es eine "Kategorietheorie", um dies zu präsentieren?

Bearbeiten : Zwei Fragen wurden entfernt, die nicht so wichtig sind.

Francisco Mota
quelle
4
Gibt es einen Grund zu der Annahme, dass eine Frage- und Antwortseite für Informatik der richtige Ort für diese Frage ist?
Sasho Nikolov
5
Ja. Kohlengebren haben Anwendungen in der Informatik, und diese Frage tauchte auf, als sie in der Informatik forschten. Außerdem gibt es auf cstheory.stackexchange noch weitere Fragen zu F- Kohlegebren. FF
Francisco Mota
1
Als Beispiel für Anwendungen in der Informatik können Begriffe der Ununterscheidbarkeit (die manchmal in der Kryptographie verwendet werden) in Form von schwachen Homomorphismen definiert werden.
Francisco Mota
1
Ich wäre gespannt auf eine Referenz, in der dies getan und verwendet wurde, um etwas zu beweisen.
Sasho Nikolov
1
Dieser Artikel: citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.7571 Scheint eine sehr ähnliche Vorstellung von "schwachem Homomorphismus" zu haben wie oben. Aber die Definition ist etwas anders und ich weiß nicht, ob sie tatsächlich übereinstimmt. Es definiert einen Beobachter , die ich noch nicht verstehen, und sie definiert einen schwachen Homomorphismus für O zwischen A , & agr; und B , β als Funktion f : A B , so dass β Of = O ( f ) αOOA,αB,βf:AB Aber ich weiß noch nicht, was das O bedeutet.
βOf=O(f)αO
O
Francisco Mota

Antworten:

6

Die von Ihnen beschriebenen "schwachen Morphismen" haben einen leicht eingeschränkten Namen. Sie können auch ganz allgemein definiert werden, wie ich erklären werde.

In dem Fall, in dem schwache Pullbacks beibehält (viele natürliche Funktoren in S e t do), ist bekannt, dass die Verhaltensäquivalenz mit der kohlebraischen Bisimilarität zusammenfällt. Dann sind Ihre Morphismen als funktionelle α- Stufen-Bisimulationen bekannt, wobei α eine Ordnungszahl ist. Zugegeben, ich habe sie nur für Ordnungszahlen α ω definiert gesehenT:SetSetSetαααω. Vor der Kohlegebra hatten Modallogiker n-stufige Bisimulationen für Kripke-Frames untersucht, die für den Powerset-Funktor n-stufige Bisimulationen für Kohlegebras darstellen. Ihre Anforderung, dass sie Funktionen im Gegensatz zu Beziehungen sind, macht sie zu funktionalen n-Stufen-Bisimulationen.

Auf der anderen Seite können Sie das Konzept, von dem Sie sprechen, in einer viel allgemeineren Umgebung definieren, ohne auf kohlebraische Bisimulationen Bezug zu nehmen. Für jede Kategorie die Grenzen ordinaler Indexketten hat, und für jeden Funktor T : CC kann man die terminale Sequenz von T definieren . Die Bedingung Grenzen ist eigentlich , eher schwach wie viele Kategorien (einschließlich S e t ) abgeschlossen sind tatsächlich dh alle kleinen Grenzen. Die Terminalsequenz ist ein Diagramm in C und sieht wie folgt aus:CT:CCTSetC

1!T1T1T!T1T21T2!T1Tω1fωω+1T(Tω1)Tfωω+1

Hier ist das Terminalobjekt in C (Limit der leeren Kette). Zum Beispiel kann in S e t angenommen werden, dass dies die einzige Elementmenge 1 = { } ist . Die Karte ! T 1 : T 1 1 ist der eindeutige Morphismus in das Endobjekt, z. B. wird in S e t einfach jedes Element von T 1 auf ∗ abgebildet . Jedes T n 1 wird durch Iteration von T und T ω 1 berechnet1CSet1={}!T1:T11SetT1Tn1TTω1ist die Grenze der Kette davor. Gegebenenfalls kann man dann über hinaus fortfahren . Intuitiv ist T α 1 die Sammlung von α- Stufen-Verhaltensweisen.ωTα1α

Nun induziert jede Kohlegebra ( Z , γ ) einen Kegel über dieser Sequenz, dh eine Ansammlung von C- Morphismen b e h α γ : Z T α 1 für jede Ordnungszahl α . Ich werde sie nur für α < ω definieren :T(Z,γ)Cbehγα:ZTα1αα<ω

ist die eindeutige Abbildung in das Terminalobjekt.behγ0:Z1

behγn+1=Tbehγnγ:ZTn+11

Intuitiv senden diese Karten einen Zustand in zu seinem α- Schritt-Verhalten. Jetzt können wir beschreiben, wovon Sie sprechen. Angenommen, wir haben zwei T- Kohlegebren ( A , γ ) und ( B , δ ) . Dann behält ein C- Morphismus f : A B das α- Stufen-Verhalten bei, wenn:ZαT(A,γ)(B,δ)Cf:ABα

behδαf=behγα

Das heißt, das Stufen-Verhalten von f ( z ) in δ ist genau das α- Stufen-Verhalten von z in γ .αf(z)δαzγ

Wie auch immer, ich hoffe das ist hilfreich. Sie können verschiedene Referenzen finden, indem Sie 'terminal sequence coalgebra' oder 'final sequence coalgebra' googeln.

rauben
quelle
Vielen Dank für diese informative und zugängliche Antwort! Ich habe eine Bemerkung und eine Frage. Anmerkung: Die Idee einer "Beobachtungsfunktion" und eines "schwachen Morphismus" wie in meinem Beitrag ist etwas allgemeiner - der schwache Morphismus muss nicht das gesamte Verhalten bis zur Ebene beibehalten (und dies ist für meine Anwendung entscheidend). Dies kann durch mit leicht werden 'fixiert' o b s : T & alpha; 1 B und O b sb e h & agr; & dgr;f = o b sb e h & agr; & ggr;αobs:Tα1Bobsbehδαf=obsbehγα. Frage: Was ist der Unterschied zwischen und b e h ω + 1 γ ? behγωbehγω+1
Francisco Mota
Ich bin nicht sicher, ob ich Ihre Bemerkung verstehe. Meinen Sie, dass die Tiefe des erhaltenen Verhaltens variiert, z. B. sind und f ( z ) 2-stufig äquivalent, aber z ' und f ( z ' ) sind 4-stufig äquivalent? Es ist zu beachten, dass die α- Stufen-Äquivalenz die β- Stufen-Äquivalenz für alle β α impliziert . zf(z)zf(z)αββα
Rob
Es ist nicht so einfach für mich den Unterschied zwischen zu erklären , und b e h ω + 1 γ in so wenig Platz. Kurz gesagt, das Verhalten vieler functors durch seine bestimmt ω -Schritt Verhalten zB für 2 × I d : S e tS e t jedes infinite Binärstrom durch seine Tiefe bestimmt wird n approximants. Es gibt jedoch Funktoren, deren Verhalten nicht auf diese Weise bestimmt wird, z. B. zählbarer Powerset oder voller Powerset-Funktor. In diesen Fällen b e h ωbehγωbehγω+1ω2×Id:SetSet liefert zusätzliche Informationen. behγω+1
Rob
Nein, Sie können konstant halten . Die Idee ist, dass wir nicht die volle Ähnlichkeit zeigen wollen, sondern nur einen Teil davon. Wenn mein Funktor beispielsweise eine Baumstruktur wie X ( 2 × X ) 2 erzeugt , könnte ich nur einen Zweig bis zur Tiefe α betrachten , anstatt alle Knoten bis zur Tiefe α zu betrachten . Danke für die Antwort. αX(2×X)2αα
Francisco Mota
5

In der Regel sollte man eine stark überlastete Terminologie wie schwach, regelmäßig, normal usw. vermeiden, es sei denn, der Begriff hat eine gewisse Universalität. Insbesondere scheint es, dass Ihr Begriff nicht dem üblichen Begriff des schwachen Homomorphismus nach dem Umblättern des Pfeils entspricht.

Es gibt immer aussagekräftigere Begriffe, wenn Sie etwas weniger Universelles tun, wie "beobachtungsbedingt geschwächter Homomorphismus", vielleicht abgekürzt als "OW-Homomorphismus".

Ihr Begriff der Beobachtungsfunktion liefert bereits eine kategorietheoretische Darstellung. Ich würde mir mehr Gedanken darüber machen, was es genau bedeutet und warum es interessant ist, anstatt die größtmögliche Allgemeinheit zu suchen. Insbesondere sollten Sie in der Regel ein informatives und ein nicht exemplarisches Beispiel angeben, wenn Sie ungewöhnliche Begriffe in den Druck einführen.

Jeff Burdges
quelle
Danke für die Antwort. Ich stimme Ihrer Empfehlung zu, einen genaueren Namen zu verwenden. Ich habe immer noch vor, in den Artikeln über schwache Bisimulationen von Jan Rothe ( citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.7571 ) nachzusehen , wie sie mit meiner obigen Definition zusammenhängen, aber ich bin ( vorzeitig) davon überzeugt, dass sie unterschiedlich sind. Nochmals vielen Dank.
Francisco Mota