Reasoning about dependence and independence : teams and multiteams

Wilke, Richard Marlon; Grädel, Erich (Thesis advisor); Lakemeyer, Gerhard (Thesis advisor); Väänänen, Jouko (Thesis advisor)

Aachen : RWTH Aachen University (2021, 2022)
Doktorarbeit

Dissertation, RWTH Aachen University, 2021

Kurzfassung

Team-Semantik ist die mathematische Grundlage moderner Logiken für Abhängigkeit und Unabhängigkeit. Ihr Kernmerkmal ist, dass Formeln über einer Menge von Zuweisungen ausgewertet werden, die als Team bezeichnet wird. Dieser Ansatz geht auf Hodges (1997) zurück, der ihn verwendet hat, um eine kompositionelle Semantik der Independence Friendly Logic anzugeben. Aufbauend auf dieser Idee schlug Väänänen (2007) vor, dass Abhängigkeiten zwischen Variablen als atomare Aussagen anstelle von Annotationen von Quantoren behandelt werden sollen. Da die Team-Semantik auf Mengen basiert, kann sie ausschließlich über das Vorhandensein oder Fehlen von Daten sprechen. Multiteam-Semantik berücksichtigt die Multiplizitäten der Daten und basiert auf Multimengen von Zuweisungen, genannt Multiteams. In dieser Dissertation entwickeln und untersuchen wir systematisch Logiken mit Multiteam-Semantik. Die Definition der Multiteam-Semantik wird durch bestimmte Postulate begründet, die natürliche Eigenschaften widerspiegeln, die eine Logik mit Multiteam-Semantik erfüllen sollte. Des Weiteren entspricht die natürliche Erweiterung der spieltheoretischen Semantik (GTS) von Logiken mit Team-Semantik um Multiplizitäten der GTS unserer Semantik. Wir erforschen ein breites Spektrum von Logiken mit Multiteam-Semantik hinsichtlich ihrer Eigenschaften und Ausdrucksstärke. Ein paar der erzielten Ergebnisse ähneln dem, was aus der Team-Semantik bekannt ist, erfordern aber neue Techniken. Die Formalismen weisen auch interessante Unterschiede auf. Beispielsweise ist die Inklusions-Exklusions Logik in der Team-Semantik äquivalent zur Unabhängigkeitslogik und hat damit die volle Ausdrucksstärke der existentiellen Logik zweiter Stufe. In der Multiteam-Semantik hingegen kann Unabhängigkeit nicht durch eine beliebige Kombination von nach unten abgeschlossenen und unter Vereinigung abgeschlossenen Atomen ausgedrückt werden. Darüber hinaus vergleichen wir die Multiteam-Semantik mit der Team-Semantik und einer Variante der existentiellen Logik zweiter Stufe. Ferner werden Modellprüfungsspiele für Logiken mit Multiteam-Semantik entwickelt. Ein weiterer Beitrag dieser Dissertation betrifft die Charakterisierung der unter Vereinigung abgeschlossenen Fragmente von Logiken mit Team-Semantik und existentieller Logik zweiter Stufe. Dies beantwortet offene Fragen von Galliani und Hella (2013). Insbesondere entwickeln wir neuartige Modellprüfungsspiele für die Team-Semantik, genannt inclusion-exclusion games, und verwenden diese, um ein Atom zu definieren, dessen Abschluss unter den logischen Junktoren und Quantoren erster Stufe alle unter Vereinigung abgeschlossenen Eigenschaften von Teams, die in der existentiellen Logik zweiter Stufe definierbar sind, erfasst. Der letzte Beitrag dieser Dissertation behandelt Logiken mit inquisitiver Semantik, welche, wie von Ciardelli (2016) beobachtet wurde, auffallende Parallelen zu Logiken mit Team-Semantik haben. Wir führen eine inquisitive monadische Logik zweiter Stufe (InqMSO) ein und geben eine präzise Charakterisierung von Ciardellis inquisitiver Logik erster Stufe (InqBQ) als ein Fragment von InqMSO an.

Einrichtungen

• Graduiertenkolleg UnRAVeL [080060]
• Fachgruppe Mathematik [110000]
• Lehr- und Forschungsgebiet Mathematische Grundlagen der Informatik (Logik und Komplexität) [117220]