Logik Und Spiele

Eintragsnavigation

• Eintragsinhalt
• Literaturverzeichnis
• Akademische Werkzeuge
• Freunde PDF Vorschau
• Autor und Zitierinfo
• Zurück nach oben

Logik und Spiele

Erstveröffentlichung am 27. Juli 2001; inhaltliche Überarbeitung Fr 16. August 2019

Spiele zwischen zwei Spielern, bei denen ein Spieler gewinnt und einer verliert, wurden in der zweiten Hälfte des 20. Jahrhunderts in vielen Bereichen der Logik zu einem vertrauten Werkzeug. Wichtige Beispiele sind semantische Spiele, die zur Definition der Wahrheit verwendet werden, Hin- und Her-Spiele zum Vergleichen von Strukturen und Dialogspiele zum Ausdrücken (und möglicherweise Erklären) formaler Beweise.

• 1. Spiele in der Geschichte der Logik
• 2. Logische Spiele
• 3. Semantische Spiele für die klassische Logik
• 4. Semantische Spiele mit unvollständigen Informationen
• 5. Semantische Spiele für andere Logiken
• 6. Hin- und Her-Spiele

• 7. Andere modelltheoretische Spiele

  • 7.1 Spiele erzwingen
  • 7.2 Cut-and-Choose-Spiele
  • 7.3 Spiele im Baum zweier Nachfolgerfunktionen
• 8. Spiele des Dialogs, der Kommunikation und des Beweises

• Literaturverzeichnis

  • Spiele in der Geschichte der Logik
  • Spiele zum Unterrichten von Logik
  • Logische Spiele
  • Semantische Spiele für die klassische Logik
  • Semantische Spiele mit unvollständigen Informationen
  • Semantische Spiele für andere Logiken
  • Hin- und Her-Spiele
  • Andere modelltheoretische Spiele
  • Spiele des Dialogs, der Kommunikation und des Beweises
• Akademische Werkzeuge
• Andere Internetquellen
• Verwandte Einträge

1. Spiele in der Geschichte der Logik

Die Verbindungen zwischen Logik und Spielen reichen weit zurück. Wenn man eine Debatte als eine Art Spiel betrachtet, dann hat Aristoteles bereits die Verbindung hergestellt; Seine Schriften über den Syllogismus sind eng mit seinem Studium der Ziele und Regeln der Debatte verbunden. Aristoteles 'Standpunkt blieb bis zum mittelalterlichen Namen für Logik erhalten: Dialektik. Mitte des 20. Jahrhunderts belebte Charles Hamblin die Verbindung zwischen Dialog und den Regeln des vernünftigen Denkens, kurz nachdem Paul Lorenzen den Dialog mit konstruktiven Grundlagen der Logik verbunden hatte.

Es gibt enge Verbindungen zwischen Spielen und Unterricht. Während des gesamten Mittelalters sprechen Schriftsteller von Dialogen, um die Verwendung von fundiertem Denken zu „lehren“oder zu „testen“. Wir haben mindestens zwei Lehrbücher der Logik aus dem frühen 16. Jahrhundert, die es als Spiel für einen einzelnen Schüler darstellen, und Lewis Carrolls The Game of Logic (1887) ist ein weiteres Beispiel im selben Genre. Es gibt auch viele moderne Beispiele, obwohl es wahrscheinlich nicht genug Kontinuität gegeben hat, um die Rede von einer Tradition des Lehrens von Logik durch Spiele zu rechtfertigen.

Die mathematische Spieltheorie wurde im frühen zwanzigsten Jahrhundert gegründet. Obwohl bis in die 1950er Jahre keine mathematischen Verbindungen zur Logik entstanden sind, fällt auf, wie viele der frühen Pioniere der Spieltheorie auch für ihre Beiträge zur Logik bekannt sind: John Kemeny, JCC McKinsey, John von Neumann, Willard Quine, Julia Robinson, Ernst Zermelo und andere. 1953 stellten David Gale und Frank Stewart fruchtbare Verbindungen zwischen Mengenlehre und Spielen her. Kurz darauf schlug Leon Henkin vor, Spiele zu verwenden, um Semantik für unendliche Sprachen zu geben.

Die erste Hälfte des 20. Jahrhunderts war eine Zeit zunehmender Strenge und Professionalität in der Logik, und für die meisten Logiker dieser Zeit wäre die Verwendung von Spielen in der Logik wahrscheinlich leichtfertig gewesen. Der Intuitionist LEJ Brouwer drückte diese Haltung aus, als er seine Gegner beschuldigte, die Mathematik "zu einem Spiel ausarten zu lassen" (wie David Hilbert ihn 1927 zitierte, zitiert in van Heijenoort 1967). Hermann Weyl (zitiert in Mancosu 1998) benutzte den Begriff der Spiele, um Hilberts Metamathematik zu erklären: Mathematische Beweise verlaufen wie Spiele eines bedeutungslosen Spiels, aber wir können außerhalb des Spiels stehen und bedeutungsvolle Fragen dazu stellen. Wittgensteins Sprachspiele stießen bei den Logikern auf wenig Resonanz. In der zweiten Hälfte des Jahrhunderts verlagerte sich der Schwerpunkt der logischen Forschung von den Grundlagen auf die Techniken.und ab etwa 1960 wurden Spiele immer häufiger in logischen Papieren verwendet.

Zu Beginn des 21. Jahrhunderts war allgemein anerkannt worden, dass Spiele und Logik zusammenpassen. Das Ergebnis war eine enorme Verbreitung neuer Kombinationen von Logik und Spielen, insbesondere in Bereichen, in denen Logik angewendet wird. Viele dieser neuen Entwicklungen entsprangen ursprünglich der Arbeit in reiner Logik, obwohl sie heute ihren eigenen Vorstellungen folgen. Ein solcher Bereich ist die Argumentationstheorie, in der Spiele ein Werkzeug zur Analyse der Struktur von Debatten bilden.

Im Folgenden konzentrieren wir uns auf die Spiele, die am engsten mit der reinen Logik verbunden sind.

2. Logische Spiele

Aus Sicht der Spieltheorie sind die Hauptspiele, die Logiker studieren, überhaupt nicht typisch. Normalerweise sind nur zwei Spieler beteiligt, sie haben oft eine unendliche Länge, die einzigen Ergebnisse sind Gewinnen und Verlieren, und mit Aktionen oder Ergebnissen sind keine Wahrscheinlichkeiten verbunden. Die wichtigsten Aspekte eines logischen Spiels sind folgende.

Es gibt zwei Spieler. Im Allgemeinen können wir sie (forall) und (existiert) nennen. Die Aussprachen "Abaelard" und "Eloise" gehen auf die Mitte der 1980er Jahre zurück und fixieren die Spieler sinnvollerweise als Männer und Frauen, um die Bezugnahme zu erleichtern: ihren Zug, seinen Zug. Andere Namen werden für die Spieler in bestimmten Arten von logischen Spielen gebräuchlich.

Die Spieler spielen, indem sie Elemente eines Satzes (Omega) auswählen, der als Domäne des Spiels bezeichnet wird. Während sie wählen, bauen sie eine Sequenz auf

[a_0, a_1, a_2, \ ldots)

von Elementen von (Omega). Unendliche Folgen von Elementen von (Omega) werden Spiele genannt. Endliche Folgen von Elementen von (Omega) werden Positionen genannt; Sie zeichnen auf, wo ein Stück zu einem bestimmten Zeitpunkt angekommen sein könnte. Eine Funktion (tau) (die Turn-Funktion oder die Player-Funktion) bringt jede Position (mathbf {a}) entweder zu (existiert) oder (forall); Wenn (tau (mathbf {a}) = \ existiert), bedeutet dies, dass Spieler (existiert) die nächste Wahl trifft (und ebenso), wenn das Spiel (mathbf {a}) erreicht hat mit (forall)). Die Spielregeln definieren zwei Sätze (W _ { forall}) und (W _ { existiert}), die aus Positionen und Spielen bestehen, mit den folgenden Eigenschaften: wenn eine Position (mathbf {a}) befindet sich in (W _ { forall}), ebenso wie jedes Spiel oder jede längere Position, die mit (mathbf {a}) beginnt (und ebenfalls mit (W _ { existiert}));und kein Spiel ist sowohl in (W _ { forall}) als auch in (W _ { existiert}). Wir sagen, dass Spieler (forall) ein Spiel gewinnt (mathbf {b}) und dass (mathbf {b}) ein Gewinn für (forall) ist, wenn (mathbf {b}) ist in (W _ { forall}); Wenn sich eine Position (mathbf {a}), die ein Anfangssegment von (mathbf {b}) ist, in (W _ { forall}) befindet, dann sagen wir, dass Spieler (forall) gewinnt bereits bei (mathbf {a}). (Und ebenso mit (existiert) und (W _ { existiert}).) Zusammenfassend ist ein logisches Spiel ein 4-Tupel ((Omega, \ tau), (W_) { forall}), (W _ { existiert})) mit den gerade beschriebenen Eigenschaften.dann sagen wir, dass Spieler (forall) bereits bei (mathbf {a}) gewinnt. (Und ebenso mit (existiert) und (W _ { existiert}).) Zusammenfassend ist ein logisches Spiel ein 4-Tupel ((Omega, \ tau), (W_) { forall}), (W _ { existiert})) mit den gerade beschriebenen Eigenschaften.dann sagen wir, dass Spieler (forall) bereits bei (mathbf {a}) gewinnt. (Und ebenso mit (existiert) und (W _ { existiert}).) Zusammenfassend ist ein logisches Spiel ein 4-Tupel ((Omega, \ tau), (W_) { forall}), (W _ { existiert})) mit den gerade beschriebenen Eigenschaften.

Wir sagen, dass ein logisches Spiel total ist, wenn jedes Spiel entweder (W _ { forall}) oder (W _ { existiert}) ist, so dass es keine Unentschieden gibt. Sofern keine explizite Ausnahme gemacht wird, wird davon ausgegangen, dass logische Spiele immer vollständig sind. (Verwechseln Sie das Totale nicht mit der viel stärkeren Eigenschaft, bestimmt zu sein - siehe unten.)

Nur aus mathematischen Gründen erwartet die obige Definition, dass das Spiel auch dann unendlich bleibt, wenn ein Spieler an einer endlichen Position gewonnen hat. Es besteht kein Interesse an irgendetwas, das passiert, nachdem ein Spieler gewonnen hat. Viele logische Spiele haben die Eigenschaft, dass in jedem Spiel einer der Spieler bereits an einer endlichen Position gewonnen hat. Spiele dieser Art sollen begründet sein. Eine noch stärkere Bedingung ist, dass es eine endliche Zahl (n) gibt, so dass in jedem Spiel einer der Spieler bereits um die (n) -te Position gewonnen hat; In diesem Fall sagen wir, dass das Spiel eine endliche Länge hat.

Eine Strategie für einen Spieler besteht aus einer Reihe von Regeln, die genau beschreiben, wie dieser Spieler wählen soll, je nachdem, wie die beiden Spieler bei früheren Zügen gewählt haben. Mathematisch gesehen besteht eine Strategie für (forall) aus einer Funktion, die jede Position (mathbf {a}) mit (tau (mathbf {a}) = \ forall) zu einem Element (nimmt. b) von (Omega); Wir betrachten es als eine Anweisung an (forall), (b) zu wählen, wenn das Spiel die Position (mathbf {a}) erreicht hat. (Ebenso mit einer Strategie für (existiert).) Eine Strategie für einen Spieler gilt als Gewinn, wenn dieser Spieler jedes Spiel gewinnt, in dem er die Strategie anwendet, unabhängig davon, was der andere Spieler tut. Höchstens einer der Spieler hat eine Gewinnstrategie (da sonst die Spieler ihre Gewinnstrategien gegeneinander spielen könnten und beide gewinnen würden,im Widerspruch dazu, dass (W _ { forall}) und (W _ { existiert}) keine gemeinsamen Spiele haben). Gelegentlich trifft man auf Situationen, in denen es den Anschein hat, dass zwei Spieler Gewinnstrategien haben (zum Beispiel in den folgenden Forcierungsspielen), aber eine genauere Betrachtung zeigt, dass die beiden Spieler tatsächlich unterschiedliche Spiele spielen.

Ein Spiel soll bestimmt werden, ob der eine oder andere Spieler eine Gewinnstrategie hat. Es gibt viele Beispiele für Spiele, die nicht bestimmt sind, wie Gale und Stewart 1953 anhand des Axioms der Wahl zeigten. Diese Entdeckung führte zu wichtigen Anwendungen des Begriffs der Bestimmtheit in den Grundlagen der Mengenlehre (siehe Eintrag zu großen Kardinälen und Bestimmtheit). Gale und Stewart haben auch einen wichtigen Satz bewiesen, der ihren Namen trägt: Jedes fundierte Spiel ist bestimmt. Daraus folgt, dass jedes Spiel endlicher Länge bestimmt wird - eine Tatsache, die Zermelo bereits 1913 bekannt war. (Eine genauere Aussage des Gale-Stewart-Theorems lautet: Ein Spiel (G) gilt als geschlossen, wenn (existiert) gewinnt jedes Spiel von (G), in dem sie noch nicht an einer endlichen Position verloren hat. Der Satz besagt, dass jedes geschlossene Spiel bestimmt ist. Der Beweis des Satzes ist grundsätzlich einfach: Nennen wir eine Gewinnposition für (forall), wenn er von dieser Position aus eine Gewinnstrategie hat. Angenommen, (forall) hat keine Gewinnstrategie im Spiel, dh am Anfang gewinnt die Position nicht für (forall). Wenn der erste Zug ein Zug von (forall) ist, gewinnt die Position nach seinem Zug immer noch nicht für ihn. Wenn der erste Zug ein Zug von (existiert) ist, muss sie einen Zug haben, nach dem die Position immer noch nicht für (forall) gewinnt, da sonst die vorherige Position für (forall gewonnen hätte)). Das Spiel geht auf diese Weise unendlich viele Züge durch Positionen, die nicht für (forall) gewinnen. Da das Spiel geschlossen ist, gewinnt (existiert).)Angenommen, (forall) hat keine Gewinnstrategie im Spiel, dh am Anfang gewinnt die Position nicht für (forall). Wenn der erste Zug ein Zug von (forall) ist, gewinnt die Position nach seinem Zug immer noch nicht für ihn. Wenn der erste Zug ein Zug von (existiert) ist, muss sie einen Zug haben, nach dem die Position immer noch nicht für (forall) gewinnt, da sonst die vorherige Position für (forall gewonnen hätte)). Das Spiel geht auf diese Weise unendlich viele Züge durch Positionen, die nicht für (forall) gewinnen. Da das Spiel geschlossen ist, gewinnt (existiert).)Angenommen, (forall) hat keine Gewinnstrategie im Spiel, dh am Anfang gewinnt die Position nicht für (forall). Wenn der erste Zug ein Zug von (forall) ist, gewinnt die Position nach seinem Zug immer noch nicht für ihn. Wenn der erste Zug ein Zug von (existiert) ist, muss sie einen Zug haben, nach dem die Position immer noch nicht für (forall) gewinnt, da sonst die vorherige Position für (forall gewonnen hätte)). Das Spiel geht auf diese Weise unendlich viele Züge durch Positionen, die nicht für (forall) gewinnen. Da das Spiel geschlossen ist, gewinnt (existiert).)Wenn der erste Zug ein Zug von (existiert) ist, muss sie einen Zug haben, nach dem die Position immer noch nicht für (forall) gewinnt, da sonst die vorherige Position für (forall gewonnen hätte)). Das Spiel geht auf diese Weise unendlich viele Züge durch Positionen, die nicht für (forall) gewinnen. Da das Spiel geschlossen ist, gewinnt (existiert).)Wenn der erste Zug ein Zug von (existiert) ist, muss sie einen Zug haben, nach dem die Position immer noch nicht für (forall) gewinnt, da sonst die vorherige Position für (forall gewonnen hätte)). Das Spiel geht auf diese Weise unendlich viele Züge durch Positionen, die nicht für (forall) gewinnen. Da das Spiel geschlossen ist, gewinnt (existiert).)

Genau wie in der klassischen Spieltheorie dient die obige Definition von logischen Spielen als Wäscheständer, an dem wir andere Konzepte festhalten können. Zum Beispiel ist es üblich, einige Gesetze zu haben, die beschreiben, welche Elemente von (Omega) einem Spieler bei einem bestimmten Zug zur Auswahl stehen. Streng genommen ist diese Verfeinerung unnötig, da die Gewinnstrategien nicht beeinflusst werden, wenn wir stattdessen festlegen, dass ein Spieler, der gegen das Gesetz verstößt, sofort verliert. Für viele Spiele erscheint diese Sichtweise jedoch unnatürlich. Im Folgenden sehen wir einige weitere zusätzliche Funktionen, die Spielen hinzugefügt werden können.

Die obigen Definitionen von Spiel und Strategie waren rein mathematisch. Also haben sie ausgelassen, was wahrscheinlich das wichtigste Merkmal von Spielen ist, nämlich dass die Leute sie spielen (zumindest metaphorisch). Die Spieler wollen gewinnen, und indem wir die Strategien untersuchen, die ihnen offen stehen, untersuchen wir, welches Verhalten für eine Person mit einem bestimmten Ziel rational ist. In den meisten Spielen gibt es mehrere Spieler, sodass wir untersuchen können, was eine rationale Reaktion auf das Verhalten eines anderen ist. Indem wir die Bewegungen der Spieler und mögliche Strategien einschränken, können wir die begrenzte Rationalität untersuchen, bei der ein Agent rationale Entscheidungen unter Bedingungen begrenzter Informationen, begrenzten Gedächtnisses oder begrenzter Zeit treffen muss.

Kurz gesagt, Spiele werden zur Modellierung von Rationalität und begrenzter Rationalität verwendet. Dies ist unabhängig von jeglicher Verbindung mit der Logik. Einige Logiken wurden jedoch entwickelt, um Aspekte rationalen Verhaltens zu untersuchen, und in den letzten Jahren ist es immer häufiger geworden, diese Logiken mit geeigneten Spielen zu verknüpfen. Siehe Abschnitt 5 ('Semantische Spiele für andere Logiken') und seine Bibliographie.

Aber bis vor kurzem waren logische Spiele auf ganz andere Weise mit rationalem Verhalten verbunden. An der Oberfläche hatte die fragliche Logik keinen direkten Zusammenhang mit dem Verhalten. Logiker und Mathematiker stellten jedoch fest, dass einige Ideen intuitiver gestaltet werden könnten, wenn sie mit möglichen Zielen verknüpft würden. Beispielsweise ist in vielen Anwendungen logischer Spiele der zentrale Begriff die einer Gewinnstrategie für den Spieler (existiert). Oft erweisen sich diese Strategien (oder ihre Existenz) als äquivalent zu etwas von logischer Bedeutung, das ohne Verwendung von Spielen hätte definiert werden können - zum Beispiel als Beweis. Es wird jedoch angenommen, dass Spiele eine bessere Definition geben, da sie buchstäblich eine gewisse Motivation liefern: (existiert) versucht zu gewinnen.

Dies wirft eine Frage auf, die mathematisch nicht von großem Interesse ist, aber Philosophen betreffen sollte, die logische Spiele verwenden. Wenn wir wollen, dass die Motivation von (existiert) in einem Spiel (G) einen erklärenden Wert hat, müssen wir verstehen, was erreicht wird, wenn (existiert) gewinnt. Insbesondere sollten wir in der Lage sein, eine realistische Geschichte einer Situation zu erzählen, in der ein Agent namens (existiert) versucht, etwas Verständliches zu tun, und dies ist dasselbe wie das Gewinnen im Spiel. Wie Richard Dawkins sagte und die entsprechende Frage für die Evolutionsspiele von Maynard Smith aufwirft,

Der ganze Zweck unserer Suche… ist es, einen geeigneten Schauspieler zu finden, der die Hauptrolle in unseren Metaphern des Zwecks spielt. Wir … wollen sagen: "Es ist zum Wohle von …". Unsere Suche in diesem Kapitel ist nach dem richtigen Weg, um diesen Satz zu vervollständigen. (Der erweiterte Phänotyp, Oxford University Press, Oxford 1982, Seite 91.)

Nennen wir dies zum späteren Nachschlagen die Dawkins-Frage. In vielen Arten von logischen Spielen ist es deutlich schwieriger zu beantworten als die Pioniere dieser Spiele. (Marion 2009 diskutiert die Dawkins-Frage weiter.)

3. Semantische Spiele für die klassische Logik

In den frühen 1930er Jahren schlug Alfred Tarski eine Definition der Wahrheit vor. Seine Definition bestand aus einer notwendigen und ausreichenden Bedingung, damit ein Satz in der Sprache einer typischen formalen Theorie wahr ist; seine notwendige und ausreichende Bedingung verwendete nur Begriffe aus der Syntax und der Mengenlehre zusammen mit den primitiven Begriffen der fraglichen formalen Theorie. Tatsächlich definierte Tarski die allgemeinere Beziehung 'Formel (phi (x_1, \ ldots, x_n)) gilt für die Elemente (a_1, \ ldots, a_n)' Die Wahrheit eines Satzes ist der Sonderfall, in dem (n = 0). Zum Beispiel die Frage, ob

'Für alle (x) gibt es (y), so dass R ((x, y))' wahr ist

reduziert sich auf die Frage, ob folgendes gilt:

Für jedes Objekt (a) ist der Satz 'Es gibt (y), so dass R ((a, y))' wahr ist.

Dies reduziert sich wiederum auf:

Für jedes Objekt (a) gibt es ein Objekt (b), so dass der Satz 'R ((a, b))' wahr ist.

In diesem Beispiel geht uns Tarskis Wahrheitsdefinition so weit.

In den späten 1950er Jahren bemerkte Leon Henkin, dass wir einige Sätze intuitiv verstehen können, die mit Tarskis Definition nicht behandelt werden können. Nehmen Sie zum Beispiel den unendlich langen Satz

Für alle (x_0) gibt es (y_0), so dass für alle (x_1) (y_1), so dass… R ((x_0, y_0, x_1, y_1, \ ldots)).

Tarskis Ansatz schlägt fehl, weil die Anzahl der Quantifizierer am Anfang unendlich ist und wir niemals ein Ende erreichen würden, wenn wir sie abstreifen würden. Stattdessen, schlug Henkin vor, sollten wir das Spiel betrachten, bei dem eine Person (forall) ein Objekt (a_0) für (x_0) auswählt, dann wählt eine zweite Person (existiert) ein Objekt (b_0)) für (y_0), dann wählt (für alle) (a_1) für (x_1, \ existiert) wählt (b_1) für (y_1) und so weiter. Ein Spiel dieses Spiels ist ein Gewinn für (existiert) genau dann, wenn der unendliche Atomsatz

) R (a_0, b_0, a_1, b_1, \ ldots))

ist wahr. Der ursprüngliche Satz ist genau dann wahr, wenn Spieler (existiert) eine Gewinnstrategie für dieses Spiel hat. Streng genommen benutzte Henkin das Spiel nur als Metapher, und die von ihm vorgeschlagene Wahrheitsbedingung war, dass die skolemisierte Version des Satzes wahr ist, dh dass es Funktionen (f_0, f_1, \ ldots) gibt, so dass für jede Wahl von (a_0, a_1, a_2) usw. haben wir

) R (a_0, f_0 (a_0), a_1, f_1 (a_0, a_1), a_2, f_2 (a_0, a_1, a_2), \ ldots).)

Diese Bedingung wird jedoch sofort in die Sprache der Spiele übersetzt. Die Skolem-Funktionen (f_0) usw. definieren eine Gewinnstrategie für (existiert) und erklären ihr, wie sie im Lichte früherer Entscheidungen von (forall) wählen soll. (Einige Zeit später stellte sich heraus, dass CS Peirce bereits vorgeschlagen hatte, den Unterschied zwischen "jedem" und "einigen" in Bezug darauf zu erklären, wer das Objekt auswählt; zum Beispiel in seinem zweiten Vortrag auf der Cambridge-Konferenz von 1898.)

Kurz nach Henkins Arbeit fügte Jaakko Hintikka hinzu, dass die gleiche Idee für Konjunktionen und Disjunktionen gilt. Wir können eine Konjunktion '(phi \ wedge \ psi)' als eine universell quantifizierte Aussage betrachten, die 'Jeder der Sätze (phi, \ psi) gilt' ausdrückt, also sollte es für den Spieler sein (forall), um einen der Sätze auszuwählen. Wie Hintikka es ausdrückte, wählt \ forall), um das Spiel (G (phi \ wedge \ psi) zu spielen, ob das Spiel als (G (phi)) oder als (G (psi) fortgesetzt werden soll.). Ebenso werden Disjunktionen zu existenziell quantifizierten Aussagen über Sätze, und sie markieren Züge, bei denen der Spieler wählt, wie das Spiel ablaufen soll. Um Quantifizierer in den gleichen Stil zu bringen, schlug er vor, dass das Spiel (G (forall x \ phi (x))) folgendermaßen abläuft: Spieler (forall) wählt ein Objekt aus und gibt einen Namen (a) dafür,und das Spiel geht weiter als (G (phi (a))). (Und ebenso mit existenziellen Quantifizierern, außer dass (existiert) wählt.) Hintikka machte auch einen genialen Vorschlag für die Einführung der Negation. Jedes Spiel G hat ein Doppelspiel, das mit G identisch ist, außer dass die Spieler (forall) und (existent) sowohl in den Spielregeln als auch in den Gewinnregeln umgesetzt sind. Das Spiel (G (neg \ phi)) ist das Dual von (G (phi)).

Man kann beweisen, dass für jeden Satz erster Ordnung (phi), interpretiert in einer festen Struktur (A), Spieler (existiert) eine Gewinnstrategie für Hintikkas Spiel (G (phi) hat) genau dann, wenn (phi) in (A) im Sinne von Tarski wahr ist. Zwei Merkmale dieses Beweises sind interessant. Erstens, wenn (phi) ein Satz erster Ordnung ist, dann hat das Spiel (G (phi)) eine endliche Länge, und so sagt uns das Gale-Stewart-Theorem, dass es bestimmt ist. Wir schließen daraus, dass (existiert) eine Gewinnstrategie in genau einer von (G (phi)) und seinem Dual hat; Sie hat also genau dann eine Gewinnstrategie in (G (neg \ phi)), wenn sie keine in (G (phi)) hat. Dies kümmert sich um die Verneinung. Und zweitens, wenn (existiert) eine Gewinnstrategie für jedes Spiel hat (G (phi (a))), dann nach Auswahl einer solchen Strategie (f_a) für jedes (a),Sie kann sie zu einer einzigen Gewinnstrategie für (G (forall x \ phi (x))) zusammenfassen (nämlich 'Warten Sie ab, welches Element (a \ forall) auswählt, und spielen Sie dann (f_a)))) '). Dies kümmert sich um die Klausel für universelle Quantifizierer; Das Argument verwendet jedoch das Axiom der Wahl, und tatsächlich ist es nicht schwer zu erkennen, dass die Aussage, dass Hintikkas und Tarskis Definitionen der Wahrheit äquivalent sind, selbst dem Axiom der Wahl entspricht (angesichts der anderen Axiome der Zermelo-Fraenkel-Mengenlehre)..und tatsächlich ist es nicht schwer zu erkennen, dass die Aussage, dass Hintikkas und Tarskis Definitionen der Wahrheit äquivalent sind, selbst dem Axiom der Wahl entspricht (angesichts der anderen Axiome der Zermelo-Fraenkel-Mengenlehre).und tatsächlich ist es nicht schwer zu erkennen, dass die Aussage, dass Hintikkas und Tarskis Definitionen der Wahrheit äquivalent sind, selbst dem Axiom der Wahl entspricht (angesichts der anderen Axiome der Zermelo-Fraenkel-Mengenlehre).

Es ist rätselhaft, dass wir hier zwei Theorien haben, wann ein Satz wahr ist, und die Theorien sind nicht gleichwertig, wenn das Axiom der Wahl versagt. In der Tat ist der Grund nicht sehr tief. Das Axiom der Wahl wird nicht benötigt, weil die Hintikka-Definition Spiele verwendet, sondern weil davon ausgegangen wird, dass Strategien deterministisch sind, dh dass es sich um einwertige Funktionen handelt, die dem Benutzer keine Wahl der Optionen geben. Eine natürlichere Art, die Tarski-Definition in Spielbegriffe zu übersetzen, ist die Verwendung nichtdeterministischer Strategien, die manchmal als Quasistrategien bezeichnet werden (Einzelheiten siehe Kolaitis 1985). (Hintikka 1996 besteht jedoch darauf, dass die korrekte Erklärung von 'wahr' diejenige ist, die deterministische Strategien verwendet, und dass diese Tatsache das Axiom der Wahl bestätigt.)

Computerimplementierungen dieser Spiele von Hintikka erwiesen sich als sehr effektive Methode, um die Bedeutung von Sätzen erster Ordnung zu lehren. Ein solches Paket wurde von Jon Barwise und John Etchemendy in Stanford entworfen und heißt "Tarski's World". Unabhängig davon konstruierte ein anderes Team der Universität Omsk eine russische Version für Schulen für begabte Kinder.

In der veröffentlichten Version seiner John Locke-Vorlesungen in Oxford warf Hintikka 1973 die Dawkins-Frage (siehe oben) für diese Spiele auf. Seine Antwort war, dass man sich Wittgensteins Sprachspiele ansehen sollte, und die Sprachspiele zum Verständnis von Quantifizierern sind diejenigen, die sich um das Suchen und Finden drehen. In den entsprechenden logischen Spielen sollte man sich (existiert) als mich selbst und (forall) als eine feindliche Natur vorstellen, auf die man sich niemals verlassen kann, um das gewünschte Objekt zu präsentieren. Um sicher zu sein, dass ich es finde, brauche ich eine Gewinnstrategie. Diese Geschichte war nie sehr überzeugend; Die Motivation der Natur ist irrelevant und nichts im logischen Spiel entspricht dem Suchen. Rückblickend ist es ein wenig enttäuschend, dass sich niemand die Mühe gemacht hat, nach einer besseren Geschichte zu suchen. Es kann hilfreicher sein, sich eine Gewinnstrategie für (existiert) in (G (phi)) als eine Art Beweis (in einem geeigneten unendlichen System) vorzustellen, dass (phi) wahr ist.

Später erweiterte Jaakko Hintikka die Ideen dieses Abschnitts in zwei Richtungen, nämlich auf die Semantik der natürlichen Sprache und auf Spiele mit unvollständigen Informationen (siehe nächster Abschnitt). Der Name Game-Theoretic Semantics, kurz GTS, wurde verwendet, um diese beiden Erweiterungen abzudecken.

Die in diesem Abschnitt beschriebenen Spiele passen sich fast trivial der vielfach sortierten Logik an: zum Beispiel dem Quantifizierer (forall x _ { sigma}), wobei (x _ { sigma}) eine Variable der Sortierung (sigma) ist) ist eine Anweisung für den Spieler (forall), ein Sortierelement (sigma) auszuwählen. Dies gibt uns sofort die entsprechenden Spiele für die Logik zweiter Ordnung, wenn wir die Elemente einer Struktur als eine Art, die Mengen von Elementen als eine zweite Art, die binären Beziehungen als eine dritte und so weiter betrachten. Daraus folgt, dass wir ziemlich routinemäßig auch Spielregeln für die meisten verallgemeinerten Quantifizierer haben; Wir können sie finden, indem wir zuerst die verallgemeinerten Quantifizierer in Logik zweiter Ordnung übersetzen.

4. Semantische Spiele mit unvollständigen Informationen

In diesem und im nächsten Abschnitt betrachten wir einige Anpassungen der semantischen Spiele des vorherigen Abschnitts an andere Logiken. In unserem ersten Beispiel wurde die Logik (die unabhängigheitsfreundliche Logik von Hintikka und Sandu 1997 oder kurz IF-Logik) erstellt, um dem Spiel zu entsprechen. Weitere Informationen zu dieser Logik finden Sie im Eintrag zur unabhängigkeitsfreundlichen Logik sowie in Mann, Sandu und Sevenster 2011.

Die Spiele hier sind die gleichen wie im vorherigen Abschnitt, außer dass wir die Annahme fallen lassen, dass jeder Spieler die vorherige Geschichte des Spiels kennt. Zum Beispiel können wir von einem Spieler verlangen, eine Wahl zu treffen, ohne zu wissen, welche Entscheidungen der andere Spieler bei bestimmten früheren Zügen getroffen hat. Der klassische Weg, dies innerhalb der Spieltheorie zu handhaben, besteht darin, die Strategien der Spieler einzuschränken. Zum Beispiel können wir verlangen, dass die Strategiefunktion, die (existiert) sagt, was in einem bestimmten Schritt zu tun ist, eine Funktion ist, deren Domäne die Familie der möglichen Auswahlmöglichkeiten von (forall) nur in seinem ersten und zweiten Zug ist; Dies ist eine Art auszudrücken, dass (existiert) nicht weiß, wie (forall) bei seinem dritten und späteren Zug gewählt hat. Spiele mit solchen Einschränkungen der Strategiefunktionen sollen unvollständige Informationen enthalten.im Gegensatz zu den Spielen der perfekten Information im vorherigen Abschnitt.

Um eine Logik zu erstellen, die zu diesen Spielen passt, verwenden wir dieselbe Sprache erster Ordnung wie im vorherigen Abschnitt, außer dass einigen Quantifizierern (und möglicherweise auch einigen Konnektiven) eine Notation hinzugefügt wird, um zu zeigen, dass Skolem für diese Quantifizierer funktioniert (oder Konnektiva) sind unabhängig von bestimmten Variablen. Zum Beispiel der Satz

[(forall x) (existiert y / \ forall x) R (x, y))

wird gelesen als: "Für jedes (x) gibt es (y), nicht abhängig von (x), so dass (R (x, y))".

Es gibt drei wichtige Anmerkungen zur Unterscheidung zwischen perfekter und unvollständiger Information. Das erste ist, dass das Gale-Stewart-Theorem nur für Spiele mit perfekter Information gilt. Angenommen, (forall) und (existiert) spielen das folgende Spiel. Zuerst wählt (forall) eine der Zahlen 0 und 1. Dann wählt (existiert) eine dieser beiden Zahlen. Spieler (existiert) gewinnt, wenn die beiden gewählten Zahlen gleich sind, und ansonsten gewinnt Spieler (forall). Wir fordern, dass (existiert), wenn sie ihre Wahl trifft, nicht weiß, was (forall) gewählt hat; Eine Skolem-Funktion für sie wird also eine Konstante sein. (Dieses Spiel entspricht dem obigen IF-Satz mit (R) als Gleichheit in einer Struktur mit einer Domäne bestehend aus 0 und 1.) Es ist klar, dass Spieler (existiert) keine konstante Gewinnstrategie hat,und auch dieser Spieler (forall) hat überhaupt keine Gewinnstrategie. Dieses Spiel ist also unbestimmt, obwohl seine Länge nur 2 beträgt.

Eine Konsequenz ist, dass Hintikkas Rechtfertigung, Negation als Dualisierung zu lesen („Spieler tauschen Plätze“), in seinen Spielen für Logik erster Ordnung nicht auf IF-Logik übertragen wird. Hintikkas Antwort war, dass Dualisierung selbst im Fall erster Ordnung die richtige intuitive Bedeutung von Negation war, so dass keine Begründung erforderlich ist.

Der zweite Kommentar ist, dass es bereits in Spielen mit perfekten Informationen vorkommen kann, dass Gewinnstrategien nicht alle verfügbaren Informationen verwenden. Wenn zum Beispiel in einem Spiel mit perfekten Informationen die Spielerin (existiert) eine Gewinnstrategie hat, hat sie auch eine Gewinnstrategie, bei der die Strategiefunktionen nur von den vorherigen Entscheidungen von (forall) abhängen. Dies liegt daran, dass sie ihre eigenen vorherigen Züge mithilfe ihrer früheren Strategiefunktionen rekonstruieren kann.

Als Hintikka Skolem-Funktionen als Strategien in seinen Spielen für Logik erster Ordnung verwendete, ließ er die Strategien für einen Spieler nur von den vorherigen Zügen des anderen Spielers abhängen. (Eine Skolem-Funktion für (existiert) hängt nur von universell quantifizierten Variablen ab.) Da es sich bei den Spielen um Spiele mit perfekter Information handelte, gab es durch den zweiten Kommentar oben keinen Verlust. Aber als er zur IF-Logik überging, machte die Anforderung, dass Strategien nur von den Zügen des anderen Spielers abhängen, wirklich einen Unterschied. Hodges 1997 zeigte dies, indem er die Notation überarbeitete, so dass zum Beispiel ((existiert y / x)) bedeutet: „Es gibt (y) unabhängig von (x), unabhängig davon, welcher Spieler (x gewählt hat)”.

Betrachten Sie jetzt den Satz

[(für alle x) (existiert z) (existiert y / x) (x = y),)

erneut auf einer Struktur mit zwei Elementen 0 und 1 gespielt. Spieler (existiert) kann wie folgt gewinnen. Für (z) wählt sie dasselbe wie Spieler (forall) für (x); dann wählt sie für (y) dasselbe, das sie für (z) gewählt hat. Diese Gewinnstrategie funktioniert nur, weil (existiert) in diesem Spiel auf ihre eigenen vorherigen Entscheidungen zurückgreifen kann. Sie hätte keine Gewinnstrategie, wenn der dritte Quantifizierer ((existiert y / xz)) wäre, wieder, weil jede Skolem-Funktion für diesen Quantifizierer konstant sein müsste. Die Art und Weise, wie (existiert) Informationen unter Bezugnahme auf ihre vorherige Wahl an sich selbst weitergibt, ist ein Beispiel für das Phänomen der Signalisierung. John von Neumann und Oskar Morgenstern veranschaulichten dies am Beispiel von Bridge, wo ein einzelner Spieler aus zwei Partnern besteht, die Informationen austauschen müssen, indem sie ihre öffentlichen Bewegungen nutzen, um sich gegenseitig zu signalisieren.

Der dritte Kommentar ist, dass es eine Versetzung zwischen der intuitiven Idee unvollständiger Informationen und der spieltheoretischen Definition derselben in Bezug auf Strategien gibt. Intuitive Informationen sind intuitiv eine Tatsache über die Umstände, unter denen das Spiel gespielt wird, nicht über die Strategien. Dies ist eine sehr knifflige Angelegenheit, die weiterhin zu Missverständnissen über IF und ähnliche Logiken führt. Nehmen Sie zum Beispiel den Satz

[(existiert x) (existiert y / x) (x = y),)

wieder auf einer Struktur mit den Elementen 0 und 1 gespielt. Intuitiv könnte man denken, wenn (existiert) sich beim zweiten Quantifizierer nicht erinnern darf, was sie beim ersten gewählt hat, dann kann sie kaum eine Gewinnstrategie haben. Tatsächlich hat sie aber eine sehr einfache: 'Wähle immer 0'!

Im Vergleich zur Logik erster Ordnung fehlt der IF-Logik eine Komponente, die die Spielesemantik nicht liefert. Die Spielsemantik sagt uns, wann ein Satz in einer Struktur wahr ist. Aber wenn wir eine Formel mit (n) freien Variablen nehmen, was drückt die Formel über die geordneten (n) - Tupel von Elementen der Struktur aus? In der Logik erster Ordnung würde es eine Menge von ihnen definieren, dh eine (n) - Beziehung auf der Struktur; Die Tarski-Wahrheitsdefinition erklärt, wie. Gibt es eine ähnliche Definition für beliebige Formeln der IF-Logik? Es stellt sich heraus, dass es eine für die etwas andere Logik gibt, die von Hodges 1997 eingeführt wurde, und dies führt zu einer Wahrheitsdefinition im Tarski-Stil für die Sprache dieser Logik. Mit ein wenig Anpassung kann diese Wahrheitsdefinition auch an die IF-Logik angepasst werden. Aber für diese beiden neuen Logiken gibt es einen Haken:Anstatt zu sagen, wann eine Zuweisung von Elementen zu freien Variablen eine Formel wahr macht, sagen wir, wann eine Reihe von Zuweisungen von Elementen zu freien Variablen die Formel wahr macht. Väänänen 2007 machte diese Idee zur Grundlage für eine Reihe neuer Logiken zur Untersuchung des Begriffs der Abhängigkeit (siehe Eintrag zur Abhängigkeitslogik). In dieser Logik wird die Semantik ohne Spiele definiert, obwohl die ursprüngliche Inspiration aus der Arbeit von Hintikka und Sandu stammt.

In Väänänens Logik ist leicht zu erkennen, warum man Sätze von Aufgaben benötigt. Er hat eine Atomformel, die '(x) ist abhängig von (y)' ausdrückt. Wie können wir dies in einer Struktur interpretieren, zum Beispiel der Struktur natürlicher Zahlen? Es macht überhaupt keinen Sinn, zum Beispiel zu fragen, ob 8 von 37 abhängig ist. Wenn wir jedoch eine Menge X geordneter Paare natürlicher Zahlen haben, ist es sinnvoll zu fragen, ob in X das erste Mitglied jedes Paares von der abhängig ist zweite; Die Antwort Ja würde bedeuten, dass es eine Funktion (f) gibt, so dass jedes Paar ((a, b)) in X die Form ((f (b), b)) hat.

5. Semantische Spiele für andere Logiken

Strukturen der folgenden Art führen zu interessanten Spielen. Die Struktur (A) besteht aus einer Menge (S) von Elementen (die wir Zustände nennen werden und hinzufügen, dass sie oft Welten genannt werden), einer binären Beziehung (R) auf (S) (wir) soll (R) als Pfeil) und eine Familie (P_1, \ ldots, P_n) von Teilmengen von (S) lesen. Die beiden Spieler (forall) und (existiert) spielen ein Spiel G auf (A), beginnend mit einem Zustand (s), der ihnen gegeben wurde, indem sie eine geeignete logische Formel (lesen) phi) als eine Anleitung zum Spielen und zum Gewinnen.

Wenn also (phi) (P_i) ist, gewinnt Spieler (existiert) sofort, wenn (s) in (P_i) ist, und ansonsten gewinnt Spieler (forall) auf einmal. Die Formeln (psi \ wedge \ theta, \ psi \ vee \ theta) und (neg \ psi) verhalten sich wie in den obigen Spielen von Hintikka. Zum Beispiel weist (psi \ wedge \ theta) den Spieler (forall) an, zu entscheiden, ob das Spiel wie für (psi) oder für (theta) fortgesetzt werden soll. Wenn die Formel (phi) (Box \ psi) lautet, wählt der Spieler (forall) einen Pfeil von (s) zu einem Zustand (t) (dh einem Zustand (). t) so, dass sich das Paar ((s, t)) in der Beziehung (R)) befindet und das Spiel dann gemäß den Anweisungen (psi) aus dem Zustand (t) ausgeht.. Die Regel für (Diamond \ psi) ist dieselbe, außer dass der Spieler (existiert) die Wahl trifft. Schließlich sagen wir, dass die Formel (phi) bei s in A wahr ist, wenn Spieler (existiert) eine Gewinnstrategie für dieses Spiel hat, die auf (phi) basiert und bei (s) beginnt.

Diese Spiele stehen für Modallogik ähnlich wie Hintikkas Spiele für Logik erster Ordnung. Insbesondere sind sie eine Möglichkeit, eine Semantik für die Modallogik zu geben, und sie stimmen mit der üblichen Kripke-Semantik überein. Natürlich gibt es viele Arten und Verallgemeinerungen der Modallogik (einschließlich eng verwandter Logiken wie zeitlicher, epistemischer und dynamischer Logik), und daher gibt es die entsprechenden Spiele in vielen verschiedenen Formen. Ein interessantes Beispiel ist die computer-theoretische Logik von Matthew Hennessy und Robin Milner, die zur Beschreibung des Verhaltens von Systemen verwendet wird. Hier sind die Pfeile in mehr als einer Farbe erhältlich. Wenn Sie sich entlang eines Pfeils einer bestimmten Farbe bewegen, wird eine bestimmte Aktion ausgeführt, um den Status zu ändern. Ein anderes Beispiel ist der leistungsfähigere Modal (mu) - Kalkül von Dexter Kozen, der Festpunktoperatoren hat;siehe Kapitel 5 von Stirling 2001.

Ein interessantes Merkmal dieser Spiele ist, dass, wenn ein Spieler ab einer bestimmten Position eine Gewinnstrategie hat, diese Strategie sich niemals auf etwas beziehen muss, das früher im Spiel passiert ist. Es ist unerheblich, welche Entscheidungen früher getroffen wurden oder wie viele Schritte gespielt wurden. Wir haben also das, was die Informatiker manchmal als "memoryless" Gewinnstrategie bezeichnen.

In der von Rohit Parikh vorgeschlagenen verwandten "Logik der Spiele" sind Spiele, die uns zwischen den Staaten bewegen, eher Gegenstand als eine Möglichkeit, eine Wahrheitsdefinition zu geben. Diese Spiele haben viele interessante Aspekte. 2003 veröffentlichte die Zeitschrift Studia Logica eine ihnen gewidmete Ausgabe, herausgegeben von Marc Pauly und Parikh.

Einflüsse aus Wirtschaft und Informatik haben eine Reihe von Logikern dazu veranlasst, Logik zur Analyse der Entscheidungsfindung unter Bedingungen teilweiser Ignoranz zu verwenden. (Siehe zum Beispiel den Artikel über epistemische Logik.) Es gibt verschiedene Möglichkeiten, Wissenszustände darzustellen. Eine besteht darin, sie als Zustände oder Welten in der Art von Modalstruktur zu betrachten, die wir am Anfang dieses Abschnitts erwähnt haben. Eine andere Möglichkeit besteht darin, die IF-Logik oder eine Variante davon zu verwenden. Wie hängen diese Ansätze zusammen? Johan van Benthem 2006 präsentiert einige Gedanken und Ergebnisse zu dieser sehr natürlichen Frage. Siehe auch die Artikel von Johan van Benthem, Krister Segerberg, Eric Pacuit und K. Venkatesh und ihre Referenzen in Teil IV 'Logik, Agentur und Spiele' von Van Benthem, Gupta und Parikh 2011 und den Eintrag über Logik zur Analyse von Spielen für a Beispiel der jüngsten Arbeiten in diesem Bereich.

6. Hin- und Her-Spiele

1930 formulierte Alfred Tarski die Vorstellung, dass zwei Strukturen (A) und (B) elementar äquivalent sind, dh dass in (A) genau dieselben Sätze erster Ordnung wahr sind wie in (B.). Auf einer Konferenz in Princeton im Jahr 1946 beschrieb er diesen Begriff und äußerte die Hoffnung, dass es möglich sein würde, eine Theorie davon zu entwickeln, die "so tief ist wie die Begriffe des Isomorphismus usw., die jetzt verwendet werden" (Tarski 1946).

Ein natürlicher Teil einer solchen Theorie wäre eine rein strukturell notwendige und ausreichende Bedingung, damit zwei Strukturen elementar äquivalent sind. Roland Fraïssé, ein Französisch-Algerier, war der erste, der eine brauchbare notwendige und ausreichende Bedingung fand. Es wurde einige Jahre später vom kasachischen Logiker AD Taimanov wiederentdeckt und vom polnischen Logiker Andrzej Ehrenfeucht spielerisch umformuliert. Die Spiele werden heute als Ehrenfeucht-Fraïssé-Spiele oder manchmal als Hin- und Her-Spiele bezeichnet. Sie haben sich als eine der vielseitigsten Ideen in der Logik des 20. Jahrhunderts herausgestellt. Sie passen sich fruchtbar an eine Vielzahl von Logiken und Strukturen an.

In einem Hin- und Her-Spiel gibt es zwei Strukturen (A) und (B) sowie zwei Spieler, die üblicherweise als Spoiler und Duplicator bezeichnet werden. (Die Namen stammen von Joel Spencer in den frühen 1990er Jahren. In jüngerer Zeit schlug Neil Immerman Samson und Delilah mit denselben Initialen vor. Dadurch werden Spoiler als männlicher Spieler (forall) und Duplicator als weiblicher (existent) platziert).) Jeder Schritt im Spiel besteht aus einem Zug von Spoiler, gefolgt von einem Zug von Duplicator. Spoiler wählt ein Element einer der beiden Strukturen aus, und Duplicator muss dann ein Element der anderen Struktur auswählen. Nach (n) Schritten wurden zwei Sequenzen ausgewählt, eine aus (A) und eine aus (B):

[(a_0, \ ldots, a_ {n-1}; b_0, \ ldots, b_ {n-1}).)

Diese Position ist genau dann ein Gewinn für Spoiler, wenn eine Atomformel (einer der Formen '(R (v_0, \ ldots, v_ {k-1}))' oder '(mathrm {F}) vorliegt. (v_0, \ ldots, v_ {k-1}) = v_k) 'oder' (v_0 = v_1) 'oder eine davon mit unterschiedlichen Variablen) wird durch ((a_0, \ ldots, a_ {) erfüllt n-1})) in (A), aber nicht durch ((b_0, \ ldots, b_ {n-1})) in (B) oder umgekehrt. Die Bedingung, dass Duplicator gewinnt, ist in verschiedenen Spielformen unterschiedlich. In der einfachsten Form, (EF (A, B)), ist ein Spiel genau dann ein Gewinn für Duplicator, wenn kein erster Teil davon ein Gewinn für Spoiler ist (dh sie gewinnt, wenn sie durch keinen verloren hat endliche Stufe). Für jede natürliche Zahl (m) gibt es ein Spiel (EF_m (A, B)); In diesem Spiel gewinnt Duplicator nach (m) Schritten, sofern sie noch nicht verloren hat. Alle diese Spiele werden nach dem Gale-Stewart-Theorem bestimmt. Die beiden Strukturen (A) und (B) werden als Hin- und Her-Äquivalent bezeichnet, wenn Duplicator eine Gewinnstrategie für (EF (A, B)) hat, und als m-Äquivalent, wenn sie eine hat eine Gewinnstrategie für (EF_m (A, B)).

Man kann beweisen, dass wenn (A) und (B) (m) - Äquivalent für jede natürliche Zahl (m) sind, sie elementar äquivalent sind. In der Tat, wenn Eloise eine Gewinnstrategie (tau) im Hintikka-Spiel G ((phi)) auf (A) hat, wo die Verschachtelung der Quantifiziererbereiche von (phi) bei hat Die meisten m Levels und Duplicator haben eine Gewinnstrategie (varrho) im Spiel (EF_m (A, B)), aus der die beiden Strategien (tau) und (varrho) zusammengesetzt werden können eine Gewinnstrategie von Eloise in G ((phi)) auf (B). Andererseits kann eine Gewinnstrategie für Spoiler in (EF_m (A, B)) in einen Satz erster Ordnung umgewandelt werden, der in genau einem von (A) und (B) und wahr ist in dem die Verschachtelung von Quantifiziererbereichen höchstens (m) Ebenen hat. Wir haben also unsere notwendige und ausreichende Bedingung für die elementare Äquivalenz und noch ein bisschen mehr.

Wenn (A) und (B) hin und her äquivalent sind, dann sind sie sicherlich elementar äquivalent; Tatsächlich stellt sich jedoch heraus, dass die Hin- und Her-Äquivalenz dieselbe ist wie die elementare Äquivalenz in einer unendlichen Logik, die viel ausdrucksvoller ist als die Logik erster Ordnung. Es gibt viele Anpassungen des Spiels, die andere Arten von Äquivalenz ergeben. Zum Beispiel haben Barwise, Immerman und Bruno Poizat unabhängig voneinander ein Spiel beschrieben, bei dem die beiden Spieler jeweils genau (p) nummerierte Kieselsteine haben. Jeder Spieler muss seine Auswahl mit einem Kieselstein kennzeichnen, und die beiden Auswahlmöglichkeiten im selben Schritt müssen mit Kieselsteinen gekennzeichnet sein, die dieselbe Nummer tragen. Im Verlauf des Spiels gehen den Spielern die Kieselsteine aus und sie müssen bereits verwendete Kieselsteine wiederverwenden. Die Bedingung, dass Spoiler an einer Position (und allen nachfolgenden Positionen) gewinnt, ist dieselbe wie zuvor, außer dass nur die Elemente zählen, die an dieser Position Etiketten tragen. Die Existenz einer Gewinnstrategie für Duplicator in diesem Spiel bedeutet, dass die beiden Strukturen für Sätze übereinstimmen, die höchstens (p) Variablen verwenden (so dass diese Variablen beliebig oft vorkommen können).

Die Theorie hinter Hin- und Her-Spielen verwendet nur sehr wenige Annahmen über die fragliche Logik. Infolgedessen sind diese Spiele eine der wenigen modelltheoretischen Techniken, die sowohl für endliche als auch für unendliche Strukturen gelten, und dies macht sie zu einem der Eckpfeiler der theoretischen Informatik. Man kann sie verwenden, um die Ausdrucksstärke formaler Sprachen zu messen, beispielsweise Datenbankabfragesprachen. Ein typisches Ergebnis könnte beispielsweise sein, dass eine bestimmte Sprache nicht zwischen "gerade" und "ungerade" unterscheiden kann. Wir würden dies beweisen, indem wir für jede Ebene (n) der Komplexität von Formeln der Sprache ein Paar endlicher Strukturen finden, für die Duplicator eine Gewinnstrategie im Hin- und Her-Spiel der Ebene (n) hat., aber eine der Strukturen hat eine gerade Anzahl von Elementen und die andere hat eine ungerade Anzahl. Semantiker natürlicher Sprachen haben Hin- und Her-Spiele nützlich gefunden, um die Ausdruckskraft verallgemeinerter Quantifizierer zu vergleichen. (Siehe zum Beispiel Peters und Westerståhl 2006, Abschnitt IV.)

Es gibt auch eine Art Hin- und Her-Spiel, das unserer obigen Modalsemantik entspricht, genauso wie Ehrenfeucht-Fraïssé-Spiele Hintikkas Spielsemantik für Logik erster Ordnung entsprechen. Die Spieler beginnen mit einem Zustand (s) in der Struktur (A) und einem Zustand (t) in der Struktur (B). Spoiler und Duplikator bewegen sich wie zuvor abwechselnd. Jedes Mal, wenn er sich bewegt, wählt Spoiler, ob er sich in (A) oder in (B) bewegt, und dann muss sich Duplicator in der anderen Struktur bewegen. Eine Bewegung wird immer ausgeführt, indem Sie entlang eines Pfeils aus dem aktuellen Status vorwärts gehen. Wenn zwischen ihnen die beiden Spieler gerade in einen Zustand (s) ´ in (A) und einen Zustand (t) ´ in (B) gewechselt sind und ein Prädikat (P_i) bei hält nur eines von (s) ´ und (t) ´, dann verliert Duplicator sofort. Außerdem verliert sie, wenn keine Pfeile für sie verfügbar sind. Wenn Spoiler jedoch feststellt, dass für beide Strukturen keine Pfeile verfügbar sind, gewinnt Duplicator. Wenn die beiden Spieler dieses Spiel mit den angegebenen Startzuständen (s) in (A) und (t) in (B) spielen und beide Strukturen nur endlich viele Zustände haben, kann man diesen Duplikator zeigen hat eine Gewinnstrategie, wenn und nur wenn die gleichen Modalsätze bei (s) in (A) wahr sind wie bei (t) in (B).

Es gibt viele Verallgemeinerungen dieses Ergebnisses, von denen einige den folgenden Begriff beinhalten. Sei (Z) eine binäre Beziehung, die Zustände von (A) mit Zuständen von (B) in Beziehung setzt. Dann nennen wir (Z) eine Bisimulation zwischen (A) und (B), wenn Duplicator (Z) als nicht deterministische Gewinnstrategie im Hin- und Her-Spiel zwischen (A) verwenden kann. und (B) wobei das erste Zugpaar der beiden Spieler darin besteht, ihre Startzustände zu wählen. In der Informatik ist der Begriff der Bisimulation entscheidend für das Verständnis von (A) und (B) als Systemen; es drückt aus, dass die beiden Systeme Schritt für Schritt auf die gleiche Weise mit ihrer Umgebung interagieren. Kurz bevor die Informatiker den Begriff einführten, erschien im Wesentlichen das gleiche Konzept in Johan van Benthems Doktorarbeit über die Semantik der Modallogik (1976).

7. Andere modelltheoretische Spiele

Die logischen Spiele in diesem Abschnitt sind Werkzeuge für Mathematiker, haben jedoch einige konzeptionell interessante Funktionen.

7.1 Spiele erzwingen

Forcing-Spiele sind auch beschreibenden Mengen-Theoretikern als Banach-Mazur-Spiele bekannt. Weitere Einzelheiten zum mathematischen Hintergrund finden Sie in den Referenzen von Kechris oder Oxtoby. Modelltheoretiker verwenden sie, um unendliche Strukturen mit kontrollierten Eigenschaften aufzubauen. Im einfachsten Fall spielen (forall) und (existiert) ein sogenanntes Model Existence Game, bei dem (existiert) behauptet, dass ein fester Satz (phi) ein Modell hat, während (forall) behauptet, er könne aus (phi) einen Widerspruch ableiten. Am Anfang ist eine zählbar unendliche Menge (C) neuer konstanter Symbole (a_0, a_1, a_2) usw. festgelegt. (existiert) verteidigt eine Disjunktion durch Auswahl einer Disjunktion und eine existenzielle Aussage durch Auswahl einer Konstante aus (C) als Zeuge. (forall) kann eine Konjunktion herausfordern, indem Sie eine der Konjunktionen auswählen.und eine universelle Aussage durch Auswahl eines beliebigen Zeugen aus (C). (existiert) gewinnt, wenn keine widersprüchlichen Atomsätze gespielt werden. (existiert) hat eine Gewinnstrategie (eine Konsistenz-Eigenschaft ist eine Möglichkeit, eine Gewinnstrategie zu beschreiben), wenn und nur wenn (phi) ein Modell hat. Wenn andererseits (forall) eine Gewinnstrategie hat, bezieht sich der Baum (der endlich gemacht werden kann) aller Spiele gegen seine Gewinnstrategie auf einen Gentzen-Stil-Beweis für die Negation von (phi).. Diese Methode zur Analyse von Sätzen ist eng mit Beths Methode der semantischen Tableaus und dem Dialogspiel verwandt (siehe Abschnitt 8). Wenn (forall) eine Gewinnstrategie hat, bezieht sich der Baum (der endlich gemacht werden kann) aller Spiele gegen seine Gewinnstrategie auf einen Gentzen-Stil-Beweis für die Negation von (phi). Diese Methode zur Analyse von Sätzen ist eng mit Beths Methode der semantischen Tableaus und dem Dialogspiel verwandt (siehe Abschnitt 8). Wenn (forall) eine Gewinnstrategie hat, bezieht sich der Baum (der endlich gemacht werden kann) aller Spiele gegen seine Gewinnstrategie auf einen Gentzen-Stil-Beweis für die Negation von (phi). Diese Methode zur Analyse von Sätzen ist eng mit Beths Methode der semantischen Tableaus und dem Dialogspiel verwandt (siehe Abschnitt 8).

Um die Idee des allgemeinen Forcing-Spiels zu skizzieren, stellen Sie sich vor, dass ein unzählig unendliches Team von Bauherren ein Haus (A) baut. Jeder Bauherr hat seine eigene Aufgabe zu erfüllen: zum Beispiel ein Bad zu installieren oder die Eingangshalle zu tapezieren. Jeder Bauherr hat unendlich viele Chancen, das Grundstück zu betreten und dem Haus eine begrenzte Menge an Material hinzuzufügen. Diese Slots für die Builder sind so verschachtelt, dass der gesamte Prozess in einer Folge von Schritten abläuft, die durch die natürlichen Zahlen gezählt werden.

Um zu zeigen, dass das Haus auf Bestellung gebaut werden kann, müssen wir zeigen, dass jeder Bauherr seine festgelegte Aufgabe separat ausführen kann, unabhängig davon, was die anderen Bauherren tun. Wir stellen uns also jeden Builder als Spieler (existiert) in einem Spiel vor, in dem alle anderen Spieler als (forall) zusammengefasst sind, und wir wollen beweisen, dass (existiert) eine Gewinnstrategie dafür hat Spiel. Wenn wir dies für jeden Bauunternehmer separat bewiesen haben, können wir uns vorstellen, dass er mit seiner eigenen Gewinnstrategie arbeiten wird. Sie alle gewinnen ihre jeweiligen Spiele und das Ergebnis ist ein schönes Haus.

Technisch gesehen werden die Elemente der Struktur (A) im Voraus festgelegt, beispielsweise als (a_0, a_1, a_2) usw., aber die Eigenschaften dieser Elemente müssen durch das Spiel festgelegt werden. Jeder Spieler bewegt sich, indem er eine Reihe von atomaren oder negierten atomaren Aussagen über die Elemente einwirft, unter der Bedingung, dass die Menge, die aus allen bisher eingeworfenen Aussagen besteht, mit einer festen Reihe von Axiomen übereinstimmt, die vor dem Spiel niedergeschrieben wurden. (Wenn Sie also einen negierten Atomsatz (neg \ phi) einwerfen, wird verhindert, dass ein Spieler zu einem späteren Zeitpunkt (phi) hinzufügt.) Am Ende des gemeinsamen Spiels die Menge der Atomsätze eingeworfen hat ein kanonisches Modell, und dies ist die Struktur (A); Es gibt Möglichkeiten, um sicherzustellen, dass es sich um ein Modell des festen Satzes von Axiomen handelt. Eine mögliche Eigenschaft P von (A) gilt als durchsetzbar, wenn ein Builder, der die Aufgabe hat, P für (A) wahr zu machen, eine Gewinnstrategie hat. Ein zentraler Punkt (im Wesentlichen aufgrund der Ehrenfeucht) ist, dass die Verbindung einer zählbar unendlichen Menge durchsetzbarer Eigenschaften wieder durchsetzbar ist.

Verschiedene Löwenheim-Skolem-Theoreme der Modelltheorie können mit Varianten des Forcing Game bewiesen werden. In diesen Varianten konstruieren wir kein Modell, sondern ein Untermodell eines bestimmten Modells. Wir beginnen mit einem großen Modell (M) für einen Satz (oder eine abzählbare Menge von Sätzen) (phi). Dann listen wir die Unterformeln von (phi) auf und jeder Spieler hat eine Unterformel mit einer freien Variablen, um die er sich kümmern muss. Die Aufgabe des Spielers besteht darin, sicherzustellen, dass ein solcher Zeuge gespielt wird, sobald die Parameter der Unterformel im Spiel auftreten und es einen Zeugen für die Wahrheit der Formel im großen Modell gibt. Wenn das Spiel vorbei ist, wurde ein zählbares Untermodell von (M) so erstellt, dass es (phi) erfüllt.

Der Name "Forcen" stammt aus einer Anwendung verwandter Ideen von Paul Cohen, um Modelle der Mengenlehre in den frühen 1960er Jahren zu konstruieren. Abraham Robinson passte es an, um eine allgemeine Methode zum Aufbau zählbarer Strukturen zu entwickeln, und Martin Ziegler stellte die Spielumgebung vor. Später verwendeten Robin Hirsch und Ian Hodkinson verwandte Spiele, um einige alte Fragen zu Beziehungsalgebren zu klären.

Forcing-Spiele sind ein gesundes Beispiel, wenn Sie über die Dawkins-Frage nachdenken. Sie erinnern uns daran, dass es in logischen Spielen nicht hilfreich sein muss, sich die Spieler als Gegner vorzustellen.

7.2 Cut-and-Choose-Spiele

Im traditionellen Cut-and-Choose-Spiel nehmen Sie ein Stück Kuchen und schneiden es in zwei kleinere Stücke. dann wähle ich eines der Stücke aus und esse es, wobei ich das andere für dich lasse. Dieses Verfahren soll Druck auf Sie ausüben, um den Kuchen fair zu schneiden. Mathematiker, die den Zweck der Übung nicht ganz verstehen, bestehen darauf, sie zu wiederholen. So lasse ich dich das Stück, das ich ausgewählt habe, in zwei Teile schneiden, dann wähle ich eines dieser beiden; dann schneidest du dieses Stück wieder und so weiter auf unbestimmte Zeit. Einige noch weltfremdere Mathematiker lassen Sie den Kuchen in zählbar viele statt in zwei Stücke schneiden.

Diese Spiele sind wichtig in der Definitionstheorie. Angenommen, wir haben eine Sammlung (A) von Objekten und eine Familie (S) von Eigenschaften; Jede Eigenschaft schneidet (A) in die Menge der Objekte, die die Eigenschaft haben, und in die Menge derjenigen, die dies nicht tun. Lassen Sie (existiert) schneiden, beginnend mit der gesamten Menge (A) und unter Verwendung einer Eigenschaft in (S) als Messer; Lassen Sie (forall) eines der Teile (die Teilmengen von (A) sind) auswählen und geben Sie es an (existent) zurück, um es erneut zu schneiden, indem Sie erneut eine Eigenschaft in (S) verwenden. und so weiter. Lassen Sie (existiert) verlieren, sobald (forall) ein leeres Stück auswählt. Wir sagen, dass ((A, S)) höchstens Rang (m) hat, wenn (forall) eine Strategie hat, die sicherstellt, dass (existiert) vor ihrem (m) verliert - th bewegen. Der Rang von ((A, S)) gibt wertvolle Informationen über die Familie von Teilmengen von (A), die durch Eigenschaften in (S) definiert werden können.

Variationen dieses Spiels, die es ermöglichen, ein Stück in unendlich viele kleinere Stücke zu schneiden, sind im Zweig der Modelltheorie, der Stabilitätstheorie, von grundlegender Bedeutung. Im Großen und Ganzen ist eine Theorie im Sinne der Stabilitätstheorie 'gut', wenn wir immer dann, wenn wir ein Modell (A) der Theorie und (S) die Menge von Formeln erster Ordnung in einer freien Variablen mit Parametern von nehmen (A), die Struktur ((A, S)) hat 'kleinen' Rang. Eine andere Variante besteht darin, dass (existiert) bei jedem Schritt in zwei Teile unterteilt wird, die von früheren Schritten erhalten geblieben sind, und sie verliert erneut, sobald eines der geschnittenen Fragmente leer ist. (In dieser Version ist (forall) redundant.) Bei dieser Variante wird der Rang von ((A), S) als Vapnik-Chervonenkis-Dimension bezeichnet. Dieser Begriff wird in der Theorie des rechnergestützten Lernens verwendet.

7.3 Spiele im Baum zweier Nachfolgerfunktionen

Stellen Sie sich einen Baum vor, der in Ebenen aufgebaut wurde. Auf der untersten Ebene befindet sich ein einzelner Wurzelknoten, von dem jedoch ein linker und ein rechter Zweig ausgehen. Auf der nächsten Ebene gibt es zwei Knoten, einen auf jedem Zweig, und von jedem dieser Knoten wachsen ein linker Zweig und ein rechter Zweig auf. Auf der nächsten Ebene gibt es also vier Knoten, und wieder verzweigt sich der Baum an jedem dieser Knoten nach links und rechts. Dieser Baum wird bis ins Unendliche als Baum zweier Nachfolgerfunktionen bezeichnet (linker Nachfolger und rechter Nachfolger). Wenn wir die Knoten als Elemente nehmen und zwei Funktionssymbole für den linken und rechten Nachfolger einführen, haben wir eine Struktur. Ein mächtiger Satz von Michael Rabin besagt, dass es einen Algorithmus gibt, der uns für jeden monadischen Satz zweiter Ordnung (phi) in der für diese Struktur geeigneten Sprache sagt:ob (phi) in der Struktur wahr ist oder nicht. ('Monadische zweite Ordnung' bedeutet, dass die Logik der ersten Ordnung entspricht, außer dass wir auch über Mengen von Elementen quantifizieren können - aber nicht über binäre Beziehungen auf Elementen zum Beispiel.)

Rabins Theorem hat eine Reihe nützlicher Konsequenzen. Zum Beispiel hat Dov Gabbay damit die Entscheidbarkeit einiger modaler Logiken bewiesen. Aber Rabins Beweis mit Automaten war notorisch schwer zu verfolgen. Yuri Gurevich und Leo Harrington sowie unabhängig Andrei Muchnik fanden viel einfachere Beweise, bei denen der Automat ein Spieler in einem Spiel ist.

Dieses Ergebnis von Rabin ist eines von mehreren einflussreichen Ergebnissen, die Spiele mit Automaten verbinden. Ein weiteres Beispiel sind die Paritätsspiele, mit denen die Eigenschaften modaler Systeme überprüft werden. Siehe zum Beispiel Stirling (2001), Kapitel 6; Bradfield und Stirling (2006) diskutieren Paritätsspiele für den Modal (mu) - Kalkül.

8. Spiele des Dialogs, der Kommunikation und des Beweises

Mehrere mittelalterliche Texte beschreiben eine Form der Debatte, die als Verpflichtungen bezeichnet wird. Es gab zwei Disputanten, Opponens und Respondens. Zu Beginn einer Sitzung einigten sich die Disputanten auf ein „Positum“, typischerweise eine falsche Aussage. Die Aufgabe von Respondens war es, rationale Antworten auf Fragen von Opponens zu geben, wobei die Wahrheit des Positivs angenommen wurde; vor allem musste er vermeiden, sich unnötig zu widersprechen. Die Aufgabe von Opponens war es, Respondens zu Widersprüchen zu zwingen. Wir kennen also die Antwort auf die Dawkins-Frage im Großen und Ganzen, aber wir kennen die Spielregeln nicht! Die mittelalterlichen Lehrbücher beschreiben verschiedene Regeln, denen die Disputanten folgen sollten. Diese Regeln sind jedoch keine festgelegten Spielregeln. Es handelt sich um Richtlinien, die die Lehrbücher anhand von Beispielen aus Prinzipien des vernünftigen Denkens ableiten.(Paulus von Venedig rechtfertigt eine Regel durch die Praxis von „großen Logikern, Philosophen, Geometern und Theologen“.) Insbesondere stand sie einem Lehrer offen, der verpflichtet war, neue Regeln zu entdecken. Diese Offenheit impliziert, dass Verpflichtungen in unserem Sinne keine logischen Spiele sind.

Nicht jeder stimmt dem vorherigen Satz zu. Zum Beispiel verteidigt Catarina Dutilh Novaes (2007, 6) ausführlich die Ansicht, dass Verpflichtungen „einen bemerkenswerten Fall konzeptioneller Ähnlichkeit zwischen einem mittelalterlichen und einem modernen theoretischen Rahmen“darstellen. Unabhängig von unserer Ansicht zu dieser Frage haben diese Debatten eine wichtige Linie der modernen Forschung in logischen Spielen inspiriert.

Stellen Sie sich vor, Sie machen eine mündliche Prüfung in der Beweistheorie. Der Prüfer gibt ihr einen Satz und lädt sie ein, ihn zu beweisen. Wenn der Satz die Form hat

) phi \ vee \ psi)

dann ist sie berechtigt, einen der Sätze zu wählen und zu sagen 'OK, ich werde diesen beweisen'. (Wenn der Prüfer ein Intuitionist ist, kann er darauf bestehen, dass sie einen der zu beweisenden Sätze wählt.) Andererseits, wenn der Satz ist

) phi \ wedge \ psi)

dann könnte der Prüfer als Prüfer selbst eine der Verbindungen auswählen und sie einladen, diese zu beweisen. Wenn sie weiß, wie man die Konjunktion beweist, dann weiß sie sicher, wie man die Konjunktion beweist.

Der Fall von (phi \ rightarrow \ psi) ist etwas subtiler. Sie wird wahrscheinlich zunächst (phi) annehmen wollen, um (psi) abzuleiten; Es besteht jedoch die Gefahr von Verwirrung, da die Sätze, die sie bisher niedergeschrieben hat, allesamt zu beweisende Dinge sind und (phi) nicht bewiesen werden muss. Der Prüfer kann ihr helfen, indem er sagt: "Ich gehe von (phi) aus, und wir werden sehen, ob Sie von dort aus zu (psi) gelangen können." An diesem Punkt besteht die Möglichkeit, dass sie einen Weg sieht, um zu (psi) zu gelangen, indem sie einen Widerspruch aus (phi) ableitet. so kann sie dem Prüfer den Spieß umdrehen und ihn einladen, zu zeigen, dass seine Annahme konsistent ist, um zu beweisen, dass dies nicht der Fall ist. Die Symmetrie ist nicht perfekt: Er bat sie zu zeigen, dass ein Satz überall wahr ist, während sie ihn einlädt, zu zeigen, dass ein Satz irgendwo wahr ist. Trotzdem können wir eine Art Dualität sehen.

Ideen dieser Art stecken hinter den dialektischen Spielen von Paul Lorenzen. Er zeigte, dass man mit einer gewissen Menge an Schieben und Schieben Regeln für das Spiel schreiben kann, die die Eigenschaft haben, dass (existiert) eine Gewinnstrategie hat, wenn und nur wenn der Satz, mit dem sie am Anfang präsentiert wird, a ist Satz der intuitionistischen Logik. In einer Geste in Richtung mittelalterlicher Debatten nannte er (existiert) den Befürworter und den anderen Spieler den Gegner. Fast wie in den mittelalterlichen Verpflichtungen gewinnt die Gegnerin, indem sie die Befürworterin zu einem Punkt treibt, an dem ihr nur noch offensichtliche Selbstwidersprüche zur Verfügung stehen.

Lorenzen behauptete, dass seine Spiele sowohl für die intuitionistische als auch für die klassische Logik Rechtfertigungen darstellten (oder sie in seinen Worten zu "zufälligen" machten, Lorenzen (1961, 196)). Leider beinhaltet jede "Rechtfertigung" eine überzeugende Antwort auf die Dawkins-Frage, und diese hat Lorenzen nie geliefert. Zum Beispiel sprach er von Bewegungen als "Angriffen", selbst wenn sie (wie die Wahl des Prüfers unter (phi \ wedge \ psi) oben) eher nach Hilfe als nach Feindseligkeit aussehen.

Die dialogische Logik des Eintrags bietet einen umfassenderen Überblick über Lorenzens Spiele und eine Reihe neuerer Varianten. In seiner jetzigen Form (Januar 2013) umgeht es Lorenzens Behauptungen, Logik zu rechtfertigen. Stattdessen werden die Spiele als Semantiken für die Logik beschrieben (ein Punkt, dem Lorenzen sicherlich zugestimmt hätte), und es kann hilfreich sein, ihre Semantik zu vergleichen, um die Unterschiede zwischen den Logiken zu verstehen.

Unter diesem Gesichtspunkt sind Lorenzens Spiele ein wichtiges Paradigma für das, was neuere Beweistheoretiker als Semantik von Beweisen bezeichnet haben. Eine Semantik von Beweisen gibt nicht nur dem Begriff der Beweisbarkeit eine "Bedeutung", sondern jedem einzelnen Schritt eines Beweises. Es beantwortet die Frage: "Was erreichen wir, wenn wir diesen besonderen Schritt im Beweis machen?" In den neunziger Jahren suchten einige Arbeiter am logischen Ende der Informatik nach Spielen, die für lineare Logik und einige andere Beweissysteme stehen würden, genauso wie Lorenzens Spiele für intuitionistische Logik. Andreas Blass und später Samson Abramsky und Kollegen gaben Spiele, die Teilen der linearen Logik entsprachen, aber zum Zeitpunkt des Schreibens haben wir noch keine perfekte Entsprechung zwischen Spiel und Logik. Dieses Beispiel ist besonders interessant, weil die Antwort auf die Dawkins-Frage eine intuitive Interpretation der Gesetze der linearen Logik geben sollte, was diese Logik dringend benötigt hat. Die Spiele von Abramsky et al. Erzählen Sie eine Geschichte über zwei interagierende Systeme. Aber während er mit Spielen begann, in denen sich die Spieler höflich abwechseln, erlaubte Abramsky den Spielern später, "verteilt, asynchron" zu handeln und sich nur dann gegenseitig zu beachten, wenn sie dies wünschen. Diese Spiele haben nicht mehr das normale Format logischer Spiele und ihre reale Interpretation wirft eine Reihe neuer Fragen auf. Aber während er mit Spielen begann, in denen sich die Spieler höflich abwechseln, erlaubte Abramsky den Spielern später, "verteilt, asynchron" zu handeln und sich nur dann gegenseitig zu beachten, wenn sie dies wünschen. Diese Spiele haben nicht mehr das normale Format logischer Spiele und ihre reale Interpretation wirft eine Reihe neuer Fragen auf. Aber während er mit Spielen begann, in denen sich die Spieler höflich abwechseln, erlaubte Abramsky den Spielern später, "verteilt, asynchron" zu handeln und sich nur dann gegenseitig zu beachten, wenn sie dies wünschen. Diese Spiele haben nicht mehr das normale Format logischer Spiele und ihre reale Interpretation wirft eine Reihe neuer Fragen auf.

Giorgi Japaridze hat eine 'Berechenbarkeitslogik' für das Studium der Berechnung vorgeschlagen. Die Syntax ist Logik erster Ordnung mit einigen zusätzlichen Elementen, die an lineare Logik erinnern. Seine Semantik bezieht sich auf semantische Spiele mit einigen ungewöhnlichen Merkmalen. Zum Beispiel wird nicht immer bestimmt, welcher Spieler den nächsten Zug macht. Der Begriff der Strategiefunktionen reicht nicht mehr aus, um die Spieler zu beschreiben. Stattdessen beschreibt Japaridze Möglichkeiten, den zweiten Spieler (Spieler (existiert) in unserer Notation) als eine Art Rechenmaschine zu lesen. Weitere Informationen finden Sie auf seiner Website.

Eine andere Gruppe von Spielen derselben allgemeinen Familie wie Lorenzens sind die Beweisspiele von Pavel Pudlak 2000. Hier ist der Gegner (genannt Prover) in der Rolle eines Anwalts vor einem Gericht, der weiß, dass der Proponent (genannt Gegner) ist eines Vergehens schuldig. Der Befürworter wird darauf bestehen, dass er unschuldig ist und bereit ist, Lügen zu erzählen, um sich zu verteidigen. Das Ziel des Gegners ist es, den Befürworter zu zwingen, etwas zu widersprechen, von dem der Antragsteller berichtet, dass es zuvor gesagt wurde. Der Gegner behält jedoch die Aufzeichnung und muss (wie in den obigen Kieselspielen) manchmal Gegenstände aus Platz- oder Speichergründen aus der Aufzeichnung entfernen. Die wichtige Frage ist nicht, ob der Gegner eine Gewinnstrategie hat (von Anfang an wird davon ausgegangen, dass er eine hat), sondern wie viel Speicher er für seine Aufzeichnung benötigt. Diese Spiele sind ein nützliches Gerät, um Ober- und Untergrenzen für die Länge von Proofs in verschiedenen Proofsystemen anzuzeigen.

Eine andere Art von logischem Spiel, das Lügen erlaubt, ist Ulams Spiel mit Lügen. Hier denkt ein Spieler an eine Zahl in einem bestimmten Bereich. Das Ziel des zweiten Spielers ist es, herauszufinden, was diese Zahl ist, indem er dem ersten Spieler Ja / Nein-Fragen stellt. Der erste Spieler darf jedoch eine feste Anzahl von Lügen in seinen Antworten erzählen. Wie in Pudlaks Spielen gibt es sicherlich eine Gewinnstrategie für den zweiten Spieler, aber die Frage ist, wie hart dieser Spieler arbeiten muss, um zu gewinnen. Das Maß dieser Zeit ist nicht Raum oder Erinnerung, sondern Zeit: Wie viele Fragen muss er stellen? Cignoli et al. 2000 Kapitel 5 bezieht dieses Spiel auf eine vielwertige Logik.

Um für einen Moment zu Lorenzen zurückzukehren: Er konnte nicht zwischen verschiedenen Standpunkten unterscheiden, die eine Person in einem Argument einnehmen könnte: angeben, annehmen, zugeben, abfragen, angreifen, sich verpflichten. Ob es wirklich möglich ist, all diese Begriffe zu definieren, ohne eine Logik vorauszusetzen, ist ein strittiger Punkt. Aber egal das; Eine Verfeinerung von Lorenzens Spielen in dieser Richtung könnte als Ansatz für die informelle Logik dienen, insbesondere für die Forschung, die darauf abzielt, die möglichen Strukturen einer fundierten informellen Argumentation zu systematisieren. Zu diesem Thema siehe Walton und Krabbe 1995. Die Arbeiten in Bench-Capon und Dunne 2007 sind ebenfalls relevant.

Literaturverzeichnis

Einige der wegweisenden Arbeiten von Henkin und Lorenzen sowie einige der unten zitierten Arbeiten erscheinen in der Sammlung Infinitistic Methods (Proceedings of the Symposium on Foundations of Mathematics, Warschau, 2.-9. September 1959), Oxford: Pergamon Press, 1961 Die Editoren sind unbenannt.

Spiele in der Geschichte der Logik

• Dutilh Novaes, Catarina, 2007, Formalisierung mittelalterlicher logischer Theorien: Suppositio, Consequentiae and Obligationes, New York: Springer-Verlag.
• Hamblin, Charles, 1970, Irrtümer, London: Methuen.
• Hilbert, David, 1967, „Die Grundlagen der Mathematik“, übersetzt als „Die Grundlagen der Mathematik“, in Jean van Heijenoort (Hrsg.), Von Frege bis Gödel, Cambridge Mass.: Harvard University Press, S. 464–479.
• Paul von Venedig, Logica Magna II (8), Tractatus de Obligationibus, E. Jennifer Ashworth (Hrsg.), New York: British Academy und Oxford University Press, 1988.
• Weyl, Hermann, 1925–1977, „Die Erkenntnis Erkenntnislage in der Mathematik“, übersetzt als „Die aktuelle erkenntnistheoretische Situation in der Mathematik“in Paolo Mancosu, Von Brouwer bis Hilbert: Die Debatte über die Grundlagen der Mathematik in den 1920er Jahren, New York: Oxford University Press, 1988, S. 123–142.
• Zermelo, Ernst, 1913, "Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels", in EW Hobson und AEH Love (Hrsg.), Proceedings of the Fifth International Congress of Mathematicians, Band II, Cambridge: Cambridge University Press.

Spiele zum Unterrichten von Logik

• Barwise, Jon und John Etchemendy, 1995, Die Sprache der Logik erster Ordnung, einschließlich Tarskis World 3.0, Cambridge: Cambridge University Press.
• Carroll, Lewis, 1887, Das Spiel der Logik, London: Macmillan.
• Dienes, Zoltan P. und EW Golding, 1966, Learning Logic, Logical Games, Harlow: Educational Supply Association.
• Havas, Katalin, 1999, „Denken lernen: Logik für Kinder“, in Proceedings des 20. Weltkongresses für Philosophie (Band 3: Philosophie der Erziehung), David M. Steiner (Hrsg.), Bowling Green Ohio: Bowling Green State Universitätsphilosophie, S. 11–19.
• Nifo, Agostino, 1521, Dialectica Ludicra (Logik als Spiel), Florenz: Bindonis.
• Weng, Jui-Feng, mit Shian-Shyong Tseng und Tsung-Ju Lee, 2010, „Unterrichten von Boolescher Logik durch Optimierung von Spielregeln“, IEEE Transactions, Learning Technologies, 3 (4): 319–328. [Verwendet Pac-Man-Spiele, um Schülern der Mittelstufe Boolesche Logik beizubringen.]

Logische Spiele

• Gale, David und FM Stewart, 1953, "Unendliche Spiele mit perfekter Information", in Beiträge zur Theorie der Spiele II (Annals of Mathematics Studies 28), HW Kuhn und AW Tucker (Hrsg.), Princeton: Princeton University Press, pp 245–266.
• Kechris, Alexander S., 1995, Klassische deskriptive Mengenlehre, New York: Springer-Verlag.
• Marion, Mathieu, 2009, „Warum logische Spiele spielen?“In Ondrej Majer, Ahti-Veikko Pietarinen und Tero Tulenheimo, Hrsg., Games: Unifying Logic, Language and Philosophy, New York: Springer-Verlag, S. 3-25.
• Osbourne, Martin J. und Ariel Rubinstein, 1994, Ein Kurs in Spieltheorie, Cambridge: MIT Press.
• Väänänen, Jouko, 2011, Modelle und Spiele, Cambridge: Cambridge University Press.
• van Benthem, Johan, 2011, Logische Dynamik von Information und Interaktion, Cambridge: Cambridge University Press, 2011.
• –––, 2014, Logik in Spielen, Cambridge, MA: MIT Press.

Semantische Spiele für die klassische Logik

• Henkin, Leon, 1961, "Einige Bemerkungen zu unendlich langen Formeln", in Infinitistic Methods, op. cit. S. 167–183.
• Hintikka, Jaakko, 1973, Logik, Sprachspiele und Information: Kantianische Themen in der Philosophie der Logik, Oxford: Clarendon Press.
• Hintikka, Jaakko, 1996, The Principles of Mathematics Revisited, New York: Cambridge University Press. [Siehe zum Beispiel die Seiten 40, 82 zum Axiom der Wahl.]
• Hodges, Wilfrid, 2001, „Elementary Predicate Logic 25: Skolem Functions“, in Dov Gabbay, und Franz Guenthner (Hrsg.), Handbook of Philosophical Logic I, 2. Auflage, Dordrecht: Kluwer, S. 86–91. [Beweis der Äquivalenz von Spiel und Tarski-Semantik.]
• Kolaitis, Ph. G., 1985, "Game Quantification", in J. Barwise und S. Feferman (Hrsg.), Model-Theoretic Logics, New York: Springer-Verlag, S. 365-421.
• Peirce, Charles Sanders, 1898, Argumentation und die Logik der Dinge: Die Cambridge Conferences Lectures von 1898, hrsg. Kenneth Laine Ketner, Cambridge Mass., Harvard University Press, 1992.

Semantische Spiele mit unvollständigen Informationen

• Hintikka, Jaakko und Gabriel Sandu, 1997, „Spieltheoretische Semantik“, in Johan van Benthem und Alice ter Meulen (Hrsg.), Handbuch für Logik und Sprache, Amsterdam: Elsevier, S. 361–410.
• Hodges, Wilfrid, 1997, „Kompositionssemantik für eine Sprache unvollständiger Informationen“, Logic Journal of the IGPL, 5: 539–563.
• Janssen, Theo MV und Francien Dechesne, 2006, "Signaling: a kniffliges Geschäft", in J. van Benthem et al. (Hrsg.), Das Zeitalter der alternativen Logik: Bewertung der Philosophie von Logik und Mathematik heute, Dordrecht: Kluwer, S. 223–242.
• Mann, Allen L., Gabriel Sandu und Merlin Sevenster, 2011, Unabhängigkeitsfreundliche Logik: Ein spieltheoretischer Ansatz (Lecture Note Series 386 der London Mathematical Society), Cambridge: Cambridge University Press.
• von Neumann, John und Oskar Morgenstern, 1944, Theorie der Spiele und des wirtschaftlichen Verhaltens, Princeton: Princeton University Press.
• Väänänen, Jouko, 2007, Abhängigkeitslogik: Ein neuer Ansatz zur unabhängigkeitsfreundlichen Logik, Cambridge: Cambridge University Press.

Semantische Spiele für andere Logiken

• Bradfield, Julian und Colin Stirling, 2006, "Modal Mu-Calculi", in P. Blackburn et al. (Hrsg.), Handbook of Modal Logic, Amsterdam: Elsevier, S. 721–756.
• Dekker, Paul und Marc Pauly (Hrsg.), 2002, Journal of Logic, Language and Information, 11 (3): 287–387. [Sonderausgabe zu Logik und Spielen.]
• Hennessy, Matthew und Robin Milner, 1985, „Algebraische Gesetze für Indeterminismus und Parallelität“, Journal of the ACM, 32: 137–162.
• Parikh, Rohit, 1985, „Die Logik der Spiele und ihre Anwendungen“, in Marek Karpinski und Jan van Leeuwen (Hrsg.), „Topics in the Theory of Computation“, Annals of Discrete Mathematics, 24: 111–140.
• Pauly, Marc und Rohit Parikh (Hrsg.), 2003, Studia Logica, 72 (2): 163–256 [Sonderausgabe zur Spielelogik.]
• Stirling, Colin, 2001, Modale und zeitliche Eigenschaften von Prozessen, New York: Springer-Verlag.
• van Benthem, Johan, 2006, „Die epistemische Logik von IF-Spielen“, in Randall Auxier und Lewis Hahn (Hrsg.), The Philosophy of Jaakko Hintikka, Chicago: Open Court, S. 481–513.
• van Benthem, Johan mit Amitabha Gupta und Rohit Parikh, 2011, Beweis, Berechnung und Agentur, Dordrecht: Springer-Verlag.

Hin- und Her-Spiele

• Blackburn, Patrick mit Maarten de Rijke und Yde Venema, 2001, Modal Logic, Cambridge: Cambridge University Press.
• Doets, Kees, 1996, Basic Model Theory, Stanford: CSLI Publications und FoLLI.
• Ebbinghaus, Heinz-Dieter und Jörg Flum, 1999, Finite Model Theory, 2. Auflage, New York: Springer.
• Ehrenfeucht, Andrzej, 1961, „Eine Anwendung von Spielen auf das Vollständigkeitsproblem für formalisierte Theorien“, Fundamenta Mathematicae, 49: 129–141.
• Grädel, Erich mit Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema und Scott Weinstein, 2007, Finite Model Theory, Berlin: Springer-Verlag.
• Libkin, Leonid, 2004, Elemente der endlichen Modelltheorie, Berlin, Springer-Verlag.
• Otto, Martin, 1997, Bounded Variable Logics und Counting-A-Studie in endlichen Modellen (Lecture Notes in Logic, 9), Berlin: Springer-Verlag.
• Peters, Stanley und Dag Westerståhl, 2006, Quantifizierer in Sprache und Logik, Oxford: Clarendon Press.
• Tarski, Alfred, 1946, „Ansprache auf der Zweihundertjahrfeierkonferenz der Princeton University über Probleme der Mathematik (17. bis 19. Dezember 1946)“, Hourya Sinaceur (Hrsg.), Bulletin of Symbolic Logic, 6 (2000): 1–44.
• van Benthem, Johan, 2001, "Correspondence Theory", in Dov Gabbay und Franz Guenthner (Hrsg.), Handbuch der Philosophischen Logik III, 2. Auflage, Dordrecht: Kluwer.

Andere modelltheoretische Spiele

• Anthony, Martin und Norman Biggs, 1992, Computational Learning Theory, Cambridge: Cambridge University Press. [Für die Vapnik-Chervonenkis-Dimension.]
• Gurevich, Yuri und Leo Harrington, 1984, „Bäume, Automaten und Spiele“, in HR Lewis (Hrsg.), Proceedings of the ACM Symposium on the Theory of Computing, San Francisco: ACM, S. 171–182.
• Hirsch, Robin und Ian Hodkinson, 2002, Beziehungsalgebren von Games, New York: Nordholland.
• Hodges, Wilfrid, 1985, Building Models by Games, Cambridge: Cambridge University Press.
• Hodges, Wilfrid, 1993, Modelltheorie, Cambridge: Cambridge University Press.
• Oxtoby, JC, 1971, Maßnahme und Kategorie, New York: Springer-Verlag.
• Ziegler, Martin, 1980, "Algebraisch entferntee Gruppen", in SI Adian et al. (Hrsg.), Word Problems II: The Oxford Book, Amsterdam: Nordholland, S. 449–576.

Spiele des Dialogs, der Kommunikation und des Beweises

• Abramsky, Samson und Radha Jagadeesan, 1994, „Spiele und vollständige Vollständigkeit für multiplikative lineare Logik“, Journal of Symbolic Logic, 59: 543–574.
• Abramsky, Samson und Paul-André Melliès, 1999, „Gleichzeitige Spiele und vollständige Vollständigkeit“, in Proceedings des 14. Internationalen Symposiums für Logik in der Informatik, Computer Science Press des IEEE, S. 431–442.
• Bench-Capon, TJM und Paul E. Dunne, 2007, „Argumentation in künstlicher Intelligenz“, Artificial Intelligence, 171: 619–641. [Die Einführung in eine umfangreiche Sammlung von Artikeln zum gleichen Thema auf den Seiten 642–937.]
• Blass, Andreas, 1992, „Eine Spielsemantik für lineare Logik“, Annals of Pure and Applied Logic, 56: 183–220.
• Cignoli, Roberto LO, Itala ML D'Ottaviano und Daniele Mundici, 2000, Algebraische Grundlagen des vielwertigen Denkens, Dordrecht: Kluwer.
• Felscher, Walter, 2001, „Dialoge als Grundlage für intuitionistische Logik“, in Dov Gabbay und Franz Guenthner (Hrsg.), Handbuch der Philosophischen Logik V, 2. Auflage, Dordrecht: Kluwer.
• Hodges, Wilfrid und Erik CW Krabbe, 2001, „Dialoggrundlagen“, Proceedings of the Aristotelian Society (Supplementary Volume), 75: 17–49.
• Japaridze, Giorgi, 2003, „Einführung in die Berechenbarkeitslogik“, Annals of Pure and Applied Logic, 123: 1–99.
• Lorenzen, Paul, 1961 "Ein dialogisches Konstruktivitätskriterium" in Infinitistic Methods, op. cit. 1961, S. 193–200.
• Pudlak, Pavel, 2000, „Beweise als Spiele“, American Mathematical Monthly, 107 (6): 541–550.
• Walton, Douglas N. und Erik CW Krabbe, 1995, Engagement im Dialog: Grundlegende Konzepte des zwischenmenschlichen Denkens, Albany: State University of New York Press.

Akademische Werkzeuge

	Wie man diesen Eintrag zitiert.
	Vorschau der PDF-Version dieses Eintrags bei den Freunden der SEP-Gesellschaft.
	Schlagen Sie dieses Eintragsthema im Internet Philosophy Ontology Project (InPhO) nach.
	Erweiterte Bibliographie für diesen Eintrag bei PhilPapers mit Links zu seiner Datenbank.

Andere Internetquellen

Die Computability Logic-Seite von Giorgi Japaridze