Boolesches Modell - Boolean-valued model

In der mathematischen Logik , ein Boolean-Wert - Modell ist eine Verallgemeinerung des gewöhnlichen Tarskischen Begriffs der Struktur von Modelltheorie . In einem booleschen Modell sind die Wahrheitswerte von Aussagen nicht auf „wahr“ und „falsch“ beschränkt, sondern nehmen stattdessen Werte in einer festen vollständigen booleschen Algebra an .

Boolesche Modelle wurden in den 1960er Jahren von Dana Scott , Robert M. Solovay und Petr Vopěnka eingeführt, um Paul Cohens Methode des Forcens zu verstehen . Sie sind auch mit der Heyting-Algebra- Semantik in der intuitionistischen Logik verwandt .

Definition

Fixiere eine vollständige Boolesche Algebra B und eine Sprache erster Ordnung L ; die Signatur von L besteht aus einer Sammlung von konstanten Symbolen, Funktionssymbolen und Beziehungssymbolen.

Ein boolesches Modell für die Sprache L besteht aus einem Universum M , das eine Menge von Elementen (oder Namen ) ist, zusammen mit Interpretationen für die Symbole. Insbesondere muss das Modell jedem konstanten Symbol von L ein Element von M zuweisen und jedem n- ären Funktionssymbol f von L und jedem n- Tupel <a ₀ ,...,a _{n -1} > von Elementen von M , muss das Modell dem Term f ein Element von M zuordnen (a ₀ ,...,a _{n -1} ).

Die Interpretation der Atomformeln von L ist komplizierter. Jedem Paar a und b von Elementen von M muss das Modell einen Wahrheitswert || a  =  b || zum Ausdruck a  =  b ; dieser Wahrheitswert wird der Booleschen Algebra B entnommen . In ähnlicher Weise muss das Modell für jedes n- äre Beziehungssymbol R von L und jedes n- Tupel <a ₀ ,...,a _{n -1} > von Elementen von M ein Element von B als Wahrheitswert || . zuweisen R (a ₀ ,...,a _{n -1} )||.

Interpretation anderer Formeln und Sätze

Die Wahrheitswerte der atomaren Formeln können verwendet werden, um die Wahrheitswerte komplizierterer Formeln unter Verwendung der Struktur der Booleschen Algebra zu rekonstruieren. Für propositionale Konnektoren ist dies einfach; man wendet einfach die entsprechenden Booleschen Operatoren auf die Wahrheitswerte der Teilformeln an. Wenn beispielsweise φ( x ) und ψ( y , z ) Formeln mit einer bzw. zwei freien Variablen sind und wenn a , b , c Elemente des Modelluniversums sind, die für x , y und z zu ersetzen sind , dann der Wahrheitswert von

${\displaystyle \phi (a)\land \psi (b,c)}$

ist einfach

${\displaystyle \|\phi (a)\land \psi (b,c)\|=\|\phi (a)\|\ \land \ \|\psi (b,c)\|}$

Die Vollständigkeit der Booleschen Algebra ist erforderlich, um Wahrheitswerte für quantifizierte Formeln zu definieren. Wenn φ( x ) eine Formel mit freier Variable x ist (und möglicherweise anderen freien Variablen, die unterdrückt werden), dann

${\displaystyle \|\exists x\phi (x)\|=\bigvee_{a\in M}\|\phi (a)\|,}$

wobei die rechte Seite als Infimum in B der Menge aller Wahrheitswerte ||φ( a )|| . zu verstehen ist als ein Bereich über M .

Der Wahrheitswert einer Formel wird manchmal als ihre Wahrscheinlichkeit bezeichnet . Dies sind jedoch keine Wahrscheinlichkeiten im gewöhnlichen Sinne, da es sich nicht um reelle Zahlen , sondern um Elemente der vollständigen Booleschen Algebra B handelt .

Boolesch bewertete Modelle der Mengenlehre

Bei einer vollständigen Booleschen Algebra B gibt es ein Boolesch-wertiges Modell, das mit V ^{B bezeichnet wird} , welches das Boolesche Analogon des von-Neumann-Universums V ist . (Streng genommen ist V ^B eine richtige Klasse , daher müssen wir entsprechend neu interpretieren, was es bedeutet, ein Modell zu sein .) Informell sind die Elemente von V ^B "Boolesche Mengen". Gegeben eine gewöhnliche Menge A ist jede Menge entweder ein Mitglied oder nicht; aber bei einer gegebenen booleschen Menge hat jede Menge eine bestimmte, feste "Wahrscheinlichkeit", ein Mitglied von A zu sein . Auch hier ist die "Wahrscheinlichkeit" ein Element von B , keine reelle Zahl. Das Konzept der booleschen Mengen ähnelt dem Begriff einer Fuzzy-Menge , ist aber nicht dasselbe .

Die ("probabilistischen") Elemente der booleschen Menge sind wiederum auch boolesche Mengen, deren Elemente ebenfalls boolesche Mengen sind und so weiter. Um eine nicht-zirkuläre Definition einer booleschen Menge zu erhalten, werden sie induktiv in einer Hierarchie ähnlich der kumulativen Hierarchie definiert . Für jede Ordinalzahl α von V ist die Menge V ^B _α wie folgt definiert.

• V ^B ₀ ist die leere Menge.
• V ^B _α+1 ist die Menge aller Funktionen von V ^B _α bis B . ( Eine derartige Funktion stellt einen „Wahrscheinlichkeits“ Teilmenge von V ^B _α , wenn f eine solche Funktion ist, dann ist für jedes x  ∈  V ^B _α , der Wert f ( x ) die Wahrscheinlichkeit ist, dass x in der Menge ist.)
• Wenn α eine Grenzordinal ist, ist V ^B _α die Vereinigung von V ^B _β für β < α.

Die Klasse V ^B ist definiert als Vereinigung aller Mengen V ^B _α .

Es ist auch möglich, diese gesamte Konstruktion auf ein transitives Modell M von ZF (oder manchmal ein Fragment davon) zu relativieren . Die Boolesche Wertmodell M ^B wird durch die Anwendung der obigen Konstruktion erhalten innen M . Die Beschränkung auf transitive Modelle ist nicht gravierend, da der Kollapssatz von Mostowski impliziert, dass jedes "vernünftige" (begründete, extensionale) Modell zu einem transitiven isomorph ist. (Wenn das Modell M nicht transitiv ist, werden die Dinge unübersichtlicher, da Ms Interpretation dessen, was es bedeutet, eine "Funktion" oder eine "Ordinalzahl" zu sein, von der "externen" Interpretation abweichen kann.)

Nachdem die Elemente von V ^B wie oben definiert wurden, ist es notwendig, B- wertige Gleichheits- und Zugehörigkeitsbeziehungen auf V ^{B zu definieren} . Hier ist eine B- wertige Beziehung auf V ^B eine Funktion von V ^B  ×  V ^B zu B . Um Verwechslungen mit der üblichen Gleichheit und Zugehörigkeit zu vermeiden, werden diese mit || . bezeichnet x  =  y || und || x  ∈  y || für x und y in V ^B . Sie sind wie folgt definiert:

|| x  ∈  y || ist definiert als Σ _{t ∈Dom( y )} || x  =  t || ∧ y ( t ) (" x ist in y wenn es gleich etwas in y ist ").

|| x  =  y || ist definiert als || x  ⊆  y || || y⊆  x || (" x ist gleich y, wenn x und y beide Teilmengen voneinander sind"), wobei

|| x  ⊆  y || ist definiert als Π _{t ∈Dom( x )} x ( t ) ⇒ || t  ∈  j || (" x ist eine Teilmenge von y, wenn alle Elemente von x in y sind ")

Die Symbole Σ und Π bezeichnen die Operationen der kleinsten Obergrenze bzw. der größten Untergrenze in der vollständigen Booleschen Algebra B . Auf den ersten Blick erscheinen die obigen Definitionen zirkulär: || || hängt von || . ab = ||, die von || . abhängt ⊆ ||, das von || . abhängt ||. Eine genaue Untersuchung zeigt jedoch, dass die Definition von || || hängt nur von || . ab || für Elemente kleineren Ranges, also || || und || = || sind wohldefinierte Funktionen von V ^B × V ^B bis B .

Es kann gezeigt werden, dass die B -wertigen Beziehungen || || und || = || auf V ^B machen V ^B zu einem booleschen Modell der Mengenlehre. Jeder Satz der Mengenlehre erster Ordnung ohne freie Variablen hat einen Wahrheitswert in B ; es muss gezeigt werden, dass die Gleichheitsaxiome und alle Axiome der ZF-Mengentheorie (ohne freie Variablen geschrieben) den Wahrheitswert 1 (das größte Element von B ) haben. Dieser Beweis ist einfach, aber er ist lang, weil es viele verschiedene Axiome gibt, die überprüft werden müssen.

Verhältnis zum Erzwingen

Mengentheoretiker verwenden eine Technik namens Erzwingen , um Unabhängigkeitsergebnisse zu erhalten und Modelle der Mengentheorie für andere Zwecke zu konstruieren. Die Methode wurde ursprünglich von Paul Cohen entwickelt, aber seitdem stark erweitert. In einer Form wird durch das Erzwingen "dem Universum" eine generische Untermenge eines Poset hinzugefügt , wobei das Poset entworfen ist, um dem neu hinzugefügten Objekt interessante Eigenschaften aufzuerlegen. Die Falte ist , dass (für interessante posets) nachgewiesen werden kann , dass es einfach ist keine solche generischen Teilmengen des Poset. Es gibt drei übliche Möglichkeiten, damit umzugehen:

• syntaktisches erzwingen Eine erzwingende Beziehung wird zwischen Elementen p des Poset und Formeln φ der erzwingenden Sprache definiert . Diese Relation ist syntaktisch definiert und hat keine Semantik; das heißt, es wird nie ein Modell hergestellt. Ausgehend von der Annahme, dass ZFC (oder eine andere Axiomatisierung der Mengenlehre) die unabhängige Aussage beweist, zeigt man vielmehr, dass ZFC auch einen Widerspruch beweisen können muss. Das Forcieren ist jedoch "über V "; das heißt, es ist nicht notwendig, mit einem abzählbaren transitiven Modell zu beginnen. Siehe Kunen (1980) für eine Darstellung dieser Methode.${\displaystyle p\Vdash \phi}$
• abzählbare transitive Modelle Man beginnt mit einem abzählbaren transitiven Modell M von so viel Mengenlehre, wie für den gewünschten Zweck benötigt wird, und das das Poset enthält. Dann gibt do exist Filter auf der poset , die generisch sind über M ; das heißt, die alle dichten offenen Teilmengen des Poset erfüllen, die zufällig auch Elemente von M sind .
• fiktive generische Objekte Im Allgemeinen werden Mengentheoretiker einfach so tun , als ob das Poset eine Untermenge hätte, die über ganz V generisch ist . Dieses generische Objekt kann in nichttrivialen Fällen kein Element von V sein und ist daher "nicht wirklich vorhanden". (Natürlich ist es ein philosophischer Streitpunkt, ob irgendwelche Mengen "wirklich existieren", aber das liegt außerhalb des Rahmens der aktuellen Diskussion.) Vielleicht überraschend, mit ein wenig Übung ist diese Methode nützlich und zuverlässig, aber sie kann philosophisch sein unbefriedigend.

Boolesche Modelle und syntaktisches Forcing

Boolesche Modelle können verwendet werden, um dem syntaktischen Forcing Semantik zu verleihen; der bezahlte Preis ist, dass die Semantik nicht zweiwertig ist ("wahr oder falsch"), sondern Wahrheitswerte aus einer vollständigen Booleschen Algebra zuweist. Bei einem erzwungenen Poset P gibt es eine entsprechende vollständige Boolesche Algebra B , die oft als Sammlung regulärer offener Teilmengen von P erhalten wird , wobei die Topologie auf P definiert wird, indem alle unteren Mengen offen (und alle oberen Mengen geschlossen) deklariert werden . (Andere Ansätze zur Konstruktion von B werden unten diskutiert.)

Nun kann die Ordnung auf B (nach dem Entfernen des Null-Elements) P zu erzwingenden Zwecken ersetzen , und die erzwingende Beziehung kann semantisch interpretiert werden, indem man sagt, dass für p ein Element von B und φ eine Formel der erzwingenden Sprache ist,

${\displaystyle p\Vdash\phi\iff p\leq ||\phi ||}$

wobei ||φ|| ist der Wahrheitswert von φ in V ^B .

Mit diesem Ansatz gelingt es, dem Erzwingen von V eine Semantik zuzuweisen, ohne auf fiktive generische Objekte zurückzugreifen. Die Nachteile sind, dass die Semantik nicht 2-wertig ist und dass die Kombinatorik von B oft komplizierter ist als die des zugrunde liegenden Poset P .

Boolesch bewertete Modelle und generische Objekte über zählbare transitive Modelle

Eine Interpretation des Forcings beginnt mit einem abzählbaren transitiven Modell M der ZF-Mengentheorie, einer partiell geordneten Menge P und einer "generischen" Teilmenge G von P und konstruiert aus diesen Objekten ein neues Modell der ZF-Mengentheorie. (Die Bedingungen, dass das Modell abzählbar und transitiv ist, vereinfachen einige technische Probleme, sind aber nicht wesentlich.) Die Konstruktion von Cohen kann wie folgt unter Verwendung von booleschen Modellen ausgeführt werden.

• Konstruieren Sie eine vollständige Boolesche Algebra B als die vollständige Boolesche Algebra, die vom Poset P "erzeugt" wurde .
• Konstruieren Sie einen Ultrafilter U auf B (oder äquivalent einen Homomorphismus von B zur Booleschen Algebra {wahr, falsch}) aus der generischen Teilmenge G von P .
• Verwenden Sie den Homomorphismus von B zu {true, false}, um das boolesche Modell M ^B des obigen Abschnitts in ein gewöhnliches Modell von ZF zu verwandeln .

Diese Schritte erklären wir Ihnen nun genauer.

Für jedes Poset P gibt es eine vollständige Boolesche Algebra B und eine Abbildung e von P nach B ⁺ (die von Null verschiedenen Elemente von B ), so dass das Bild dicht ist, e ( p ) e ( q ), wenn p ≤ q , und e ( p ) e ( q ) = 0 immer dann, wenn p und q inkompatibel sind. Diese Boolesche Algebra ist bis auf Isomorphie eindeutig. Sie kann als Algebra regulärer offener Mengen im topologischen Raum von P konstruiert werden (mit zugrundeliegender Menge P und einer Basis gegeben durch die Mengen U _p der Elemente q mit q ≤ p ).

Die Abbildung vom Poset P zur vollständigen Booleschen Algebra B ist im Allgemeinen nicht injektiv. Die Abbildung ist genau dann injektiv, wenn P die folgende Eigenschaft hat: wenn jedes r ≤ p mit q kompatibel ist , dann ist p ≤ q .

Der Ultrafilter U auf B definiert ist , die Menge der Elemente zu sein , b von B , die größer als ein Element des (das Bild) G . Gegeben ein Ultrafilter U auf einer Booleschen Algebra, erhalten wir einen Homomorphismus zu {wahr, falsch}, indem wir U auf wahr und sein Komplement auf falsch abbilden . Umgekehrt ist bei einem solchen Homomorphismus das inverse Bild von wahr ein Ultrafilter, also sind Ultrafilter im Wesentlichen dieselben wie Homomorphismen zu {wahr, falsch}. (Algebraisten könnten es vorziehen, maximale Ideale anstelle von Ultrafiltern zu verwenden: Das Komplement eines Ultrafilters ist ein maximales Ideal, und umgekehrt ist das Komplement eines maximalen Ideals ein Ultrafilter.)

Wenn g ein Homomorphismus von einer Booleschen Algebra B zu einer Booleschen Algebra C ist und M ^B ein beliebiges B- wertiges Modell von ZF (oder einer anderen Theorie) ist, können wir M ^B in ein C- wertiges Modell umwandeln, indem wir Homomorphismus g zum Wert aller Formeln. Insbesondere wenn C {true, false} ist, erhalten wir ein {true, false}-wertiges Modell. Dies ist fast dasselbe wie ein gewöhnliches Modell: Tatsächlich erhalten wir ein gewöhnliches Modell auf der Menge der Äquivalenzklassen unter || = || eines {true, false}-wertigen Modells. Wir erhalten also ein gewöhnliches Modell der ZF-Mengentheorie, indem wir von M , einer Booleschen Algebra B und einem Ultrafilter U auf B ausgehen . (Das so konstruierte Modell von ZF ist nicht transitiv. In der Praxis wendet man den Kollapssatz von Mostowski an, um daraus ein transitives Modell zu machen.)

Wir haben gesehen, dass das Erzwingen mit booleschen Modellen erfolgen kann, indem eine Boolesche Algebra mit Ultrafilter aus einem Poset mit einer generischen Teilmenge konstruiert wird. Es ist auch möglich, in die andere Richtung zurückzugehen: Bei einer gegebenen Booleschen Algebra B können wir ein Poset P aus allen von Null verschiedenen Elementen von B bilden , und ein generischer Ultrafilter auf B beschränkt sich auf einen generischen Satz auf P . Die Techniken des Erzwingens und Boolesch-bewertete Modelle sind also im Wesentlichen äquivalent.

Anmerkungen

Verweise

• Bell, JL (1985) Boolean-Valued Models and Independence Proofs in Set Theory , Oxford. ISBN  0-19-853241-5
• Grishin, VN (2001) [1994], "Boolean-valueed model" , Encyclopedia of Mathematics , EMS Press
• Jech, Thomas (2002). Mengenlehre, dritte Jahrtausendausgabe (überarbeitet und erweitert) . Springer. ISBN 3-540-44085-2. OCLC-  174929965 .
• Kunen, Kenneth (1980). Mengentheorie: Eine Einführung in die Unabhängigkeitsbeweise . Nordholland. ISBN 0-444-85401-0. OCLC  12808956 .
• Kusraev, AG und SS Kutateladze (1999). Boolesch bewertete Analyse . Kluwer akademischer Verlag. ISBN 0-7923-5921-6. OCLC  41967176 . Enthält einen Bericht über boolesche Modelle und Anwendungen auf Riesz-Räume, Banach-Räume und Algebren.
• Mann, Yu. I. (1977). Ein Kurs in mathematischer Logik . Springer. ISBN 0-387-90243-0. OCLC  2797938 . Enthält einen Bericht über erzwingende und boolesche Modelle, die für Mathematiker geschrieben wurden, die keine Mengentheoretiker sind.
• Rosser, J. Barkley (1969). Vereinfachte Unabhängigkeitsbeweise, Boolesche Modelle der Mengenlehre . Akademische Presse.