Heyting Algebra - Heyting algebra

In der Mathematik ist eine Heyting-Algebra (auch als pseudo-Boolesche Algebra bekannt ) ein beschränktes Gitter (mit Join- und Meet-Operationen geschrieben ∨ und ∧ und mit kleinstem Element 0 und größtem Element 1) ausgestattet mit einer binären Operation a → b der Implikation wie dass ( c ∧ a ) ≤ b äquivalent zu c ≤ ( a → b ) ist. Vom logischen Standpunkt aus ist A → B nach dieser Definition der schwächste Satz, für den modus ponens , die Inferenzregel A → B , A ⊢ B , richtig ist. Wie Boolesche Algebren bilden Heyting-Algebren eine Varietät, die mit endlich vielen Gleichungen axiomatisierbar ist. Heyting-Algebren wurden von Arend Heyting  ( 1930 ) eingeführt, um die intuitionistische Logik zu formalisieren .

Als Gitter sind Heyting-Algebren distributiv . Jede Boolesche Algebra ist eine Heyting-Algebra, wenn a → b wie üblich als ¬ a ∨ b definiert ist , ebenso wie jedes vollständige Verteilungsgitter , das ein einseitiges unendliches Verteilungsgesetz erfüllt, wenn a → b als Supremum der Menge aller c für die c ∧ a ≤ b . Im endlichen Fall ist jedes nichtleere Verteilungsgitter, insbesondere jede nichtleere endliche Kette , automatisch vollständig und vollständig distributiv, also eine Heyting-Algebra.

Aus der Definition folgt, dass 1 ≤ 0 → a , entsprechend der Intuition, dass jeder Satz a durch einen Widerspruch 0 impliziert wird. Obwohl die Negationsoperation ¬ a nicht Teil der Definition ist, ist sie als a → 0 definierbar Inhalt von ¬ a ist der Satz, dass die Annahme von a zu einem Widerspruch führen würde. Die Definition impliziert , dass a ∧ ¬ a = 0. Es kann weiter gezeigt werden , dass a ≤ ¬¬ ein , obwohl das Gegenteil, ¬¬ a ≤ a , ist im allgemeinen nicht wahr ist , das heißt, doppelte Negation Eliminierung nicht gilt generell in einer Heyting-Algebra.

Heyting-Algebren verallgemeinern Boolesche Algebren in dem Sinne, dass eine Heyting-Algebra, die a ¬ a = 1 ( außer Mitte ) erfüllt, äquivalent ¬¬ a = a ( doppelte Negationseliminierung ), eine Boolesche Algebra ist. Die Elemente einer Heyting-Algebra H der Form ¬ a umfassen ein Boolesches Gitter, aber im Allgemeinen ist dies keine Subalgebra von H (siehe unten ).

Heyting-Algebren dienen als algebraische Modelle der propositionalen intuitionistischen Logik in der gleichen Weise, wie Boolesche Algebren die propositionale klassische Logik modellieren . Die interne Logik eines elementaren Topos basiert auf der Heyting-Algebra der nach Inklusion geordneten Unterobjekte des Terminalobjekts 1, äquivalent den Morphismen von 1 zum Unterobjekt-Klassifikator Ω.

Die offenen Mengen eines beliebigen topologischen Raums bilden eine vollständige Heyting-Algebra . Vollständige Heyting-Algebren werden damit zu einem zentralen Untersuchungsgegenstand in der sinnlosen Topologie .

Jede Heyting-Algebra, deren Menge der nicht-größten Elemente ein größtes Element hat (und eine andere Heyting-Algebra bildet) ist subdirekt irreduzibel , daher kann jede Heyting-Algebra subdirekt irreduzibel gemacht werden, indem ein neues größtes Element angefügt wird. Daraus folgt, dass es sogar unter den endlichen Heyting-Algebren unendlich viele subdirekt irreduzibel gibt, von denen keine zwei dieselbe Gleichungstheorie haben. Daher kann keine endliche Menge endlicher Heyting-Algebren alle Gegenbeispiele zu Nichtgesetzen der Heyting-Algebra liefern. Dies steht in scharfem Gegensatz zu Booleschen Algebren, deren einzige subdirekt irreduzible die Zwei-Elemente-Algebren ist, die also allein für alle Gegenbeispiele zu Nichtgesetzen der Booleschen Algebra, der Basis für die einfache Wahrheitstabellen- Entscheidungsmethode, ausreicht . Dennoch ist es entscheidbar, ob eine Gleichung von allen Heyting-Algebren gilt.

Heyting-Algebren werden seltener als pseudo-boolesche Algebren oder sogar als Brouwer-Gitter bezeichnet , obwohl der letztere Begriff die duale Definition bezeichnen oder eine etwas allgemeinere Bedeutung haben kann.

Formale Definition

Eine Heyting-Algebra H ist ein beschränktes Gitter, so dass es für alle a und b in H ein größtes Element x von H gibt, so dass

${\displaystyle a\wedge x\leq b.}$

Dieses Element ist das relative Pseudokomplement von a bezüglich b und wird als a → b bezeichnet . Wir schreiben 1 und 0 für das größte bzw. das kleinste Element von H .

In jeder Heyting-Algebra definiert man das Pseudokomplement ¬ a eines beliebigen Elements a durch Setzen von ¬ a = ( a →0). Per Definition ist , und ¬ a das größte Element mit dieser Eigenschaft. Es ist jedoch nicht allgemein wahr, dass , also ¬ nur ein Pseudo-Komplement ist, kein echtes Komplement , wie es in einer Booleschen Algebra der Fall wäre. ${\displaystyle a\wedge \lnot a=0}$${\displaystyle a\vee \lnot a=1}$

Eine vollständige Heyting-Algebra ist eine Heyting-Algebra, die ein vollständiges Gitter ist .

A Subalgebra eine Heyting Algebra H ist eine Teilmenge H ₁ von H enthält , 0 und 1 und geschlossen unter den Operationen ∧, ∨ und →. Daraus folgt, dass es auch unter ¬ geschlossen ist. Aus einer Subalgebra wird durch die induzierten Operationen eine Heyting-Algebra.

Alternative Definitionen

Kategorietheoretische Definition

Eine Heyting-Algebra ist ein beschränktes Gitter, das alle exponentiellen Objekte enthält . ${\displaystyle H}$

Das Gitter wird als eine Kategorie angesehen, in der treffen, , das Produkt ist . Die Exponentialbedingung bedeutet, dass für beliebige Objekte und in einer Exponentialfunktion eindeutig als Objekt in existiert . ${\displaystyle H}$${\displaystyle\keil}$${\displaystyle Y}$${\displaystyle Z}$${\displaystyle H}$${\displaystyle Z^{Y}}$${\displaystyle H}$

Eine Heyting-Implikation (oft geschrieben mit oder um Verwechslungen zu vermeiden, wie die Verwendung von , um einen Funktor anzugeben ) ist nur eine Exponentialfunktion: ist eine alternative Notation für . Aus der Definition von Exponentialfunktionen ergibt sich, dass die Implikation ( ) rechtsadjungiert zu ( ) ist. Dieser Zusatz kann geschrieben werden als oder vollständiger als: ${\displaystyle \Rightarrow}$${\displaystyle \multimap}$${\displaystyle \to}$${\displaystyle Y\Rightarrow Z}$${\displaystyle Z^{Y}}$${\displaystyle \Rightarrow :H\times H\to H}$${\displaystyle \wedge :H\times H\to H}$${\displaystyle (-\wedge Y)\dashv (Y\Rightarrow -)}$

Gittertheoretische Definitionen

Eine äquivalente Definition von Heyting-Algebren kann durch Betrachtung der Abbildungen gegeben werden:

${\displaystyle {\begin{cases}f_{a}\colon H\to H\\f_{a}(x)=a\wedge x\end{cases}}}$

für einige feste a in H . Ein beschränktes Gitter H ist genau dann eine Heyting-Algebra, wenn jede Abbildung f _a die untere Adjungierte einer monotonen Galois-Verbindung ist . In diesem Fall ist die jeweilige obere Adjungierte g _a gegeben durch g _a ( x ) = a → x , wobei → wie oben definiert ist.

Noch eine andere Definition ist ein Gitter mit Resten, dessen monoide Operation ∧ ist. Die Monoideinheit muss dann das oberste Element 1 sein. Die Kommutativität dieses Monoids impliziert, dass die beiden Residuen als a → b zusammenfallen .

Begrenztes Gitter mit einer Implikationsoperation

Gegeben ein beschränktes Gitter A mit größtem und kleinstem Element 1 und 0 und einer binären Operation → bilden diese zusammen genau dann eine Heyting-Algebra, wenn gilt:

1. ${\displaystyle a\to a=1}$
2. ${\displaystyle a\keil (a\to b)=a\keil b}$
3. ${\displaystyle b\keil (a\to b)=b}$
4. ${\displaystyle a\to (b\wedge c)=(a\to b)\wedge (a\to c)}$

wobei 4 das Verteilungsgesetz für → ist.

Charakterisierung mit den Axiomen der intuitionistischen Logik

Diese Charakterisierung der Heyting-Algebren macht den Beweis der grundlegenden Tatsachen bezüglich der Beziehung zwischen der intuitionistischen Aussagenkalküle und den Heyting-Algebren unmittelbar. (Zu diesen Tatsachen siehe die Abschnitte „ Beweisbare Identitäten “ und „ Universelle Konstruktionen “.) Man sollte sich das Element intuitiv als „beweisbar wahr“ vorstellen. Vergleiche mit den Axiomen der Intuitionistischen Logik#Axiomatization ). ${\displaystyle \top }$

Gegeben eine Menge A mit drei binären Operationen →, ∧ und ∨ und zwei ausgezeichneten Elementen und , dann ist A eine Heyting-Algebra für diese Operationen (und die Beziehung ≤ definiert durch die Bedingung, dass wenn a → b = ) genau dann, wenn die folgende Bedingungen gelten für alle Elemente x , y und z von A : ${\displaystyle \bot}$${\displaystyle \top }$${\displaystyle a\leq b}$${\displaystyle \top }$

1. ${\displaystyle {\mbox{Wenn }}x\leq y{\mbox{ und }}y\leq x{\mbox{ dann }}x=y,}$
2. ${\displaystyle {\mbox{Wenn }}\top \leq y,{\mbox{ then }}y=\top ,}$
3. ${\displaystyle x\leq y\to x,}$
4. ${\displaystyle x\to (y\to z)\leq (x\to y)\to (x\to z),}$
5. ${\displaystyle x\land y\leq x,}$
6. ${\displaystyle x\land y\leq y,}$
7. ${\displaystyle x\leq y\to (x\land y),}$
8. ${\displaystyle x\leq x\lor y,}$
9. ${\displaystyle y\leq x\lor y,}$
10. ${\displaystyle x\to z\leq (y\to z)\to (x\lor y\to z),}$
11. ${\displaystyle \bot \leq x.}$

Schließlich definieren wir ¬ x als x → . ${\displaystyle \bot}$

Bedingung 1 besagt, dass äquivalente Formeln identifiziert werden sollen. Bedingung 2 besagt, dass beweisbar wahre Formeln im Modus Ponens abgeschlossen sind . Bedingungen 3 und 4 sind dann Bedingungen. Bedingungen 5, 6 und 7 sind und Bedingungen. Bedingungen 8, 9 und 10 sind oder Bedingungen. Bedingung 11 ist eine falsche Bedingung.

Wenn für die Logik ein anderer Satz von Axiomen gewählt würde, könnten wir natürlich unseren entsprechend modifizieren.

Beispiele

• Jede Boolesche Algebra ist eine Heyting-Algebra mit p → q gegeben durch ¬ p ∨ q .
• Jede total geordnete Menge mit einem kleinsten Element 0 und einem größten Element 1 ist eine Heyting-Algebra (wenn man sie als Gitter betrachtet). In diesem Fall ist p → q gleich 1, wenn p q und ansonsten q .
• Die einfachste Heyting-Algebra, die noch keine Boolesche Algebra ist, ist die total geordnete Menge {0, 1/2, 1} (als Gitter betrachtet), was die Operationen ergibt:

  ${\displaystyle a\land b}$ B ein 0 1/2 1 0 0 0 0 1/2 0 1/2 1/2 1 0 1/2 1

  ${\displaystyle a\lor b}$ B ein 0 1/2 1 0 0 1/2 1 1/2 1/2 1/2 1 1 1 1 1

  a → b B ein 0 1/2 1 0 1 1 1 1/2 0 1 1 1 0 1/2 1

  ein ¬ a 0 1 1/2 0 1 0

  In diesem Beispiel ist das 1/2¬1/2 = 1/2∨(1/2 → 0) = 1/2∨0 = 1/2 verfälscht das Gesetz der ausgeschlossenen Mitte.

• Jede Topologie liefert eine vollständige Heyting-Algebra in Form ihres offenen Mengengitters. In diesem Fall ist das Element A → B das Innere der Vereinigung von A ^c und B , wobei A ^c das Komplement der offenen Menge A bezeichnet . Nicht alle vollständigen Heyting-Algebren haben diese Form. Diese Fragen werden in sinnloser Topologie untersucht , wobei vollständige Heyting-Algebren auch Frames oder Locales genannt werden .
• Jede innere Algebra liefert eine Heyting-Algebra in Form ihres Gitters aus offenen Elementen. Jede Heyting-Algebra hat diese Form, da eine Heyting-Algebra zu einer Booleschen Algebra vervollständigt werden kann, indem man ihre freie Boolesche Erweiterung als beschränktes Verteilungsgitter nimmt und sie dann als verallgemeinerte Topologie in dieser Booleschen Algebra behandelt.
• Die Lindenbaum-Algebra der propositionalen intuitionistischen Logik ist eine Heyting-Algebra.
• Die globalen Elemente des Unterobjekt-Klassifikators Ω eines elementaren Topos bilden eine Heyting-Algebra; es ist die Heyting-Algebra der Wahrheitswerte der durch den Topos induzierten intuitiven Logik höherer Ordnung.
• ukasiewicz-Moisil-Algebren (LM _n ) sind auch Heyting-Algebren für beliebige n (aber keine MV-Algebren für n ≥ 5).

Eigenschaften

Allgemeine Eigenschaften

Die Ordnung auf einer Heyting-Algebra H kann aus der Operation → wie folgt gewonnen werden: für alle Elemente a , b von H , genau dann, wenn a → b = 1. ${\displaystyle \leq}$${\displaystyle a\leq b}$

Im Gegensatz zu einigen mehrwertigen Logiken teilen Heyting-Algebren die folgende Eigenschaft mit Booleschen Algebren: Wenn die Negation einen Fixpunkt hat (dh ¬ a = a für einige a ), dann ist die Heyting-Algebra die triviale einelementige Heyting-Algebra.

Nachweisbare Identitäten

Gegeben eine Formel der Aussagenrechnung (die zusätzlich zu den Variablen die Konnektoren und die Konstanten 0 und 1 verwendet), ist es eine Tatsache, die schon früh in jedem Studium der Heyting-Algebren bewiesen wurde, dass die folgenden beiden Bedingungen äquivalent sind: ${\displaystyle F(A_{1},A_{2},\ldots,A_{n})}$${\displaystyle \land,\lor,\lnot,\to}$

1. Die Formel F ist im intuitionistischen Aussagenkalkül nachweislich wahr.
2. Die Identität gilt für jede Heyting-Algebra H und alle Elemente .${\displaystyle F(a_{1},a_{2},\ldots,a_{n})=1}$${\displaystyle a_{1},a_{2},\ldots ,a_{n}\in H}$

Die Metaimplikation 1 ⇒ 2 ist äußerst nützlich und die wichtigste praktische Methode zum Beweisen von Identitäten in Heyting-Algebren. In der Praxis verwendet man in solchen Beweisen häufig den Deduktionssatz .

Da für jeden a und b in einer Heyting Algebra H haben wir , wenn und nur wenn a → b = 1 ist , folgt aus 1 ⇒ 2 , daß , wenn eine Formel F → G beweisbar wahr ist, haben wir für jeden Heyting Algebra H , und jeden Elemente . (Es folgt aus dem Deduktionstheorem dass F → G beweisbar [aus dem Nichts] ist , wenn und nur wenn G beweisbar ist aus F , das heißt, wenn G eine beweisbar Folge ist F .) Insbesondere wenn F und G beweisbar äquivalent ist , dann , da ≤ eine Ordnungsrelation ist. ${\displaystyle a\leq b}$${\displaystyle F(a_{1},a_{2},\ldots,a_{n})\leq G(a_{1},a_{2},\ldots,a_{n})}$${\displaystyle a_{1},a_{2},\ldots ,a_{n}\in H}$${\displaystyle F(a_{1},a_{2},\ldots,a_{n})=G(a_{1},a_{2},\ldots,a_{n})}$

1 ⇒ 2 kann bewiesen werden, indem man die logischen Axiome des Beweissystems untersucht und verifiziert, dass ihr Wert 1 in einer Heyting-Algebra ist, und dann verifiziert, dass die Anwendung der Inferenzregeln auf Ausdrücke mit dem Wert 1 in einer Heyting-Algebra ergibt: Ausdrücke mit dem Wert 1. Lassen Sie uns zum Beispiel das Beweissystem wählen, das Modus Ponens als einzige Folgerungsregel hat und dessen Axiome die in der Intuitionistischen Logik#Axiomatization angegebenen Axiome im Hilbert-Stil sind . Dann folgen die zu verifizierenden Tatsachen unmittelbar aus der oben gegebenen axiomartigen Definition der Heyting-Algebren.

1 ⇒ 2 bietet auch eine Methode zum Beweisen, dass bestimmte Aussagenformeln, obwohl sie in der klassischen Logik Tautologien sind , in der intuitionistischen Aussagenlogik nicht bewiesen werden können. Um zu beweisen, dass eine Formel nicht beweisbar ist, reicht es aus, eine Heyting-Algebra H und Elemente wie zu zeigen . ${\displaystyle F(A_{1},A_{2},\ldots,A_{n})}$${\displaystyle a_{1},a_{2},\ldots ,a_{n}\in H}$${\displaystyle F(a_{1},a_{2},\ldots ,a_{n})\neq 1}$

Will man die Erwähnung von Logik vermeiden, so ist es in der Praxis notwendig, als Lemma eine für Heyting-Algebren gültige Version des Deduktionssatzes zu beweisen: für alle Elemente a , b und c einer Heyting-Algebra H gilt . ${\displaystyle (a\land b)\to c=a\to (b\to c)}$

Für mehr zur Metaimplikation 2 ⇒ 1 siehe den Abschnitt „ Universelle Konstruktionen “ weiter unten.

Verteilung

Heyting-Algebren sind immer distributiv . Konkret haben wir immer die Identitäten

1. ${\displaystyle a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)}$
2. ${\displaystyle a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)}$

Das Distributivgesetz wird manchmal als Axiom angegeben, aber tatsächlich folgt es aus der Existenz relativer Pseudokomplemente. Der Grund dafür ist , dass, wobei die untere adjoint eines Galoisverbindung , bewahrt alle vorhandenen suprema . Distributivität wiederum ist nur die Erhaltung der binären Suprema durch . ${\displaystyle\keil}$ ${\displaystyle\keil}$

Nach einem ähnlichen Argument gilt das folgende unendliche Verteilungsgesetz in jeder vollständigen Heyting-Algebra:

${\displaystyle x\wedge\bigvee Y=\bigvee\{x\wedge y\mid y\in Y\}}$

für jedes Element x in H und jede Teilmenge Y von H . Umgekehrt ist jedes vollständige Gitter, das das obige unendliche Verteilungsgesetz erfüllt, eine vollständige Heyting-Algebra mit

${\displaystyle a\to b=\bigvee \{c\mid a\land c\leq b\}}$

seine relative Pseudokomplement-Operation ist.

Regelmäßige und ergänzte Elemente

Ein Element x einer Heyting-Algebra H heißt regulär, wenn eine der folgenden äquivalenten Bedingungen erfüllt ist:

1. x = ¬¬ x .
2. x = ¬ y für ein y in H .

Die Äquivalenz dieser Bedingungen kann einfach als die Identität ¬¬¬ x = ¬ x , gültig für alle x in H, ausgedrückt werden .

Die Elemente x und y einer Heyting-Algebra H heißen Komplemente zueinander, wenn x ∧ y = 0 und x ∨ y = 1. Wenn es existiert, ist jedes solche y eindeutig und muss tatsächlich gleich ¬ x sein . Wir nennen ein Element x komplementär, wenn es ein Komplement zulässt. Es ist wahr, dass wenn x komplementiert ist, dann auch ¬ x , und dann sind x und ¬ x zueinander komplementär. Verwirrenderweise kann ¬ x dennoch ein Komplement (ungleich x ) haben , selbst wenn x nicht komplementiert ist . In jeder Heyting-Algebra sind die Elemente 0 und 1 einander komplementär. Zum Beispiel ist es möglich, dass ¬ x für jedes x ungleich 0 0 ist, und 1 wenn x = 0, in diesem Fall sind 0 und 1 die einzigen regulären Elemente.

Jedes komplementierte Element einer Heyting-Algebra ist regelmäßig, obwohl das Umgekehrte im Allgemeinen nicht gilt. Insbesondere sind 0 und 1 immer regulär.

Für jede Heyting-Algebra H sind die folgenden Bedingungen äquivalent:

1. H ist eine Boolesche Algebra ;
2. jedes x in H ist regulär;
3. jedes x in H wird ergänzt.

In diesem Fall ist das Element a → b gleich ¬ a ∨ b .

Die regulären (bzw. komplementierten) Elemente jeder Heyting-Algebra H bilden eine Boolesche Algebra H _reg (bzw. H _comp ), in der die Operationen ∧, ¬ und → sowie die Konstanten 0 und 1 mit denen von H . übereinstimmen . Im Fall von H _comp ist auch die Operation ∨ dieselbe, also ist H _comp eine Teilalgebra von H . Im Allgemeinen ist H _reg jedoch keine Subalgebra von H , da ihre Join-Operation ∨ _reg von ∨ abweichen kann. Für x , y ∈ H _reg , haben wir x ∨ _reg y = ¬ (¬ x ∧ ¬ y ). Siehe unten für notwendige und ausreichende Bedingungen, damit ∨ _reg mit ∨ übereinstimmt.

Die De Morgan-Gesetze in einer Heyting-Algebra

Eines der beiden De-Morgan-Gesetze ist in jeder Heyting-Algebra erfüllt, nämlich

${\displaystyle \forall x,y\in H:\qquad \lnot (x\vee y)=\lnot x\wedge \lnot y.}$

Das andere De-Morgan-Gesetz gilt jedoch nicht immer. Wir haben stattdessen ein schwaches de Morgan-Gesetz:

${\displaystyle \forall x,y\in H:\qquad \lnot (x\wedge y)=\lnot \lnot (\lnot x\vee \lnot y).}$

Die folgenden Aussagen sind für alle Heyting-Algebren H äquivalent :

1. H erfüllt beide De Morgan-Gesetze,
2. ${\displaystyle \lnot (x\wedge y)=\lnot x\vee \lnot y{\mbox{ für alle }}x,y\in H,}$
3. ${\displaystyle \lnot (x\wedge y)=\lnot x\vee \lnot y{\mbox{ für alle regulären }}x,y\in H,}$
4. ${\displaystyle \lnot \lnot (x\vee y)=\lnot \lnot x\vee \lnot \lnot y{\mbox{ für alle }}x,y\in H,}$
5. ${\displaystyle \lnot \lnot (x\vee y)=x\vee y{\mbox{ für alle regulären }}x,y\in H,}$
6. ${\displaystyle \lnot (\lnot x\wedge \lnot y)=x\vee y{\mbox{ für alle regulären }}x,y\in H,}$
7. ${\displaystyle \lnot x\vee \lnot \lnot x=1{\mbox{ für alle }}x\in H.}$

Bedingung 2 ist das andere Gesetz von De Morgan. Bedingung 6 besagt, dass die Join-Operation ∨ _reg auf der Booleschen Algebra H _reg von regulären Elementen von H mit der Operation ∨ von H zusammenfällt . Bedingung 7 besagt, dass jedes reguläre Element komplementär ist, dh H _reg = H _comp .

Wir beweisen die Äquivalenz. Offensichtlich sind die Metaimplikationen 1 ⇒ 2, 2 3 und 4 ⇒ 5 trivial. Außerdem ergeben sich 3 ⇔ 4 und 5 ⇔ 6 einfach aus dem ersten De-Morgan-Gesetz und der Definition regulärer Elemente. Wir zeigen, dass 6 7 ist, indem wir ¬ x und ¬¬ x anstelle von x und y in 6 nehmen und die Identität a ∧ ¬ a = 0 verwenden. Beachten Sie, dass 2 ⇒ 1 aus dem ersten De-Morgan-Gesetz folgt und 7 ⇒ 6 ergibt sich aus der Tatsache, dass die Join-Operation ∨ auf der Subalgebra H _comp nur die Beschränkung von ∨ auf H _{comp ist} , unter Berücksichtigung der von uns gegebenen Charakterisierungen der Bedingungen 6 und 7. Die Metaimplikation 5 ⇒ 2 ist eine triviale Folge der schwachen De-Morgan-Gesetz, wobei ¬ x und ¬ y anstelle von x und y in 5 genommen werden.

Heyting-Algebren, die die obigen Eigenschaften erfüllen, sind mit der De-Morgan-Logik in der gleichen Weise verwandt, wie Heyting-Algebren im Allgemeinen mit der intuitionistischen Logik verwandt sind.

Heyting Algebra Morphismen

Definition

Gegeben zwei Heyting-Algebren H ₁ und H ₂ und eine Abbildung f  : H ₁ → H ₂ , sagen wir, dass ƒ ein Morphismus der Heyting-Algebren ist, wenn für beliebige Elemente x und y in H ₁ gilt:

1. ${\displaystyle f(0)=0,}$
2. ${\displaystyle f(x\land y)=f(x)\land f(y),}$
3. ${\displaystyle f(x\lor y)=f(x)\lor f(y),}$
4. ${\displaystyle f(x\to y)=f(x)\to f(y),}$

Daraus folgt , aus einem der letzten drei Bedingungen (2, 3 oder 4) , dass f eine zunehmende Funktion ist, das heißt, dass f ( x ) ≤ f ( y ) , wenn x ≤ y .

Angenommen, H ₁ und H ₂ sind Strukturen mit den Operationen →, ∧, ∨ (und möglicherweise ¬) und den Konstanten 0 und 1, und f ist eine surjektive Abbildung von H ₁ auf H ₂ mit den obigen Eigenschaften 1 bis 4. Wenn H ₁ eine Heyting-Algebra ist, ist es auch H ₂ . Dies folgt aus der Charakterisierung von Heyting-Algebren als beschränkte Gitter (als algebraische Strukturen und nicht als teilweise geordnete Mengen gedacht) mit einer Operation → bestimmte Identitäten erfüllend.

Eigenschaften

Die Identitätsabbildung f ( x ) = x einer beliebigen Heyting-Algebra auf sich selbst ist ein Morphismus, und die zusammengesetzte g ∘ f aus zwei beliebigen Morphismen f und g ist ein Morphismus. Daher bilden Heyting-Algebren eine Kategorie .

Beispiele

Gegeben eine Heyting-Algebra H und eine beliebige Subalgebra H ₁ , ist die Inklusionsabbildung i  : H ₁ → H ein Morphismus.

Für jeden Heyting Algebra H , die Karte x ↦ ¬¬ x definiert eine morphism von H auf die Booleschen Algebra seines regulären Elemente H _reg . Dies ist nicht im allgemeinen ein morphism von H auf sich selbst, da der Betrieb von Join H _reg sich von der verschieden sein können H .

Quotienten

Lassen Sie H eine Heyting Algebra, und sei F ⊆ H . Wir nennen F einen Filter auf H, wenn es die folgenden Eigenschaften erfüllt:

1. ${\displaystyle 1\in F,}$
2. ${\displaystyle {\mbox{If }}x,y\in F{\mbox{ then }}x\land y\in F,}$
3. ${\displaystyle {\mbox{Wenn }}x\in F,\ y\in H,\ {\mbox{und }}x\leq y{\mbox{ dann }}y\in F.}$

Der Schnittpunkt einer beliebigen Menge von Filtern auf H ist wieder ein Filter. Daher gibt es für jede Teilmenge S von H einen kleinsten Filter, der S enthält . Wir nennen es den von S erzeugten Filter . Wenn S leer ist, ist F = {1}. Andernfalls F ist mit dem Satz von gleich x in H , so daß es existiert y ₁ , y ₂ , ..., y _n ∈ S mit Y ₁ ∧ y ₂ ∧ ... ∧ y _n ≤ x .

Wenn H eine Heyting-Algebra und F ein Filter auf H ist , definieren wir eine Beziehung ∼ auf H wie folgt: Wir schreiben x ∼ y immer dann, wenn x → y und y → x beide zu F gehören . Dann ist ∼ eine Äquivalenzrelation ; wir schreiben H / F für die Quotientenmenge . Es gibt eine eindeutige Heyting-Algebra-Struktur auf H / F, so dass die kanonische Surjektion p _F  : H → H / F zu einem Heyting-Algebra-Morphismus wird. Wir nennen die Heyting-Algebra H / F den Quotienten von H durch F .

Sei S eine Teilmenge einer Heyting-Algebra H und sei F der von S erzeugte Filter . Dann erfüllt H / F die folgende universelle Eigenschaft:

Gegeben jede morphism von Heyting algebras f  : H → H ' erfüllen , f ( y ) = 1 für jeden y ∈ S , f Faktoren eindeutig durch das kanonischen Surjektion p _F  : H → H / F . Das heißt, es gibt einen eindeutigen Morphismus f′  : H / F → H′ , der f′p _F = f erfüllt . Der Morphismus f′ wird durch f induziert .

Sei f  : H ₁ → H ₂ ein Morphismus von Heyting-Algebren. Der Kern von f , geschrieben ker f , ist die Menge f ⁻¹ [{1}]. Es ist ein Filter auf H ₁ . (Es ist Vorsicht geboten, da diese Definition, wenn sie auf einen Morphismus von Booleschen Algebren angewendet wird, dual zu dem ist, was man den Kern des Morphismus nennen würde, der als Morphismus von Ringen betrachtet wird.) Nach dem Vorhergehenden induziert f einen Morphismus f′  : H ₁ / (Ker f ) → H ₂ . Es ist ein Isomorphismus von H ₁ /(ker f ) auf die Subalgebra f [ H ₁ ] von H ₂ .

Universelle Konstruktionen

Heyting Algebra von Aussagenformeln in n Variablen bis zur intuitionistischen Äquivalenz

Die Metaimplikation 2 ⇒ 1 im Abschnitt „ Beweisbare Identitäten “ wird bewiesen, indem gezeigt wird, dass das Ergebnis der folgenden Konstruktion selbst eine Heyting-Algebra ist:

1. Betrachten Sie die Menge L der Aussagenformeln in den Variablen A ₁ , A ₂ ,..., A _n .
2. Ausstatten L mit einem preorder ≼ durch Definieren F ≼ G , falls G eine (intuitionist) ist logische Folge von F , das heißt, wenn G belegbar ist aus F . Es ist sofort ersichtlich, dass ≼ eine Vorbestellung ist.
3. Betrachten Sie die durch die Vorordnung F≼G induzierte Äquivalenzrelation F ∼ G. (Es wird definiert durch F ~ G , wenn und nur wenn F ≼ G und G ≼ F . Tatsächlich ~ ist die Beziehung von (intuitionist) logische Äquivalenz.)
4. Sei H ₀ die Quotientenmenge L /∼. Dies wird die gewünschte Heyting-Algebra sein.
5. Wir schreiben [ F ] für die Äquivalenzklasse einer Formel F . Die Operationen →, ∧, ∨ und ¬ sind auf L offensichtlich definiert . Verifizieren Sie, dass die Äquivalenzklassen [ F → G ], [ F ∧ G ], [ F ∨ G ] und [¬ F ] für die gegebenen Formeln F und G nur von [ F ] und [ G ] abhängen . Dies definiert Operationen →, ∧, ∨ und ¬ auf der Quotientenmenge H ₀ = L /∼. Definiere weiter 1 als die Klasse der beweisbar wahren Aussagen und setze 0=[⊥].
6. Verifizieren Sie, dass H ₀ zusammen mit diesen Operationen eine Heyting-Algebra ist. Wir tun dies mit der axiomähnlichen Definition von Heyting-Algebren. H ₀ erfüllt die Bedingungen THEN-1 bis FALSE, weil alle Formeln der gegebenen Formen Axiome der intuitionistischen Logik sind. MODUS-PONENS folgt aus der Tatsache, dass wenn eine Formel ⊤→ F beweisbar wahr ist, wobei ⊤ beweisbar wahr ist, dann F beweisbar wahr ist (durch Anwendung der Inferenzregel modus ponens). Schließlich ergibt sich EQUIV aus der Tatsache, dass wenn F → G und G → F beide beweisbar wahr sind, dann F und G voneinander beweisbar sind (durch Anwendung der Inferenzregel modus ponens), also [ F ]=[ G ] .

Wie immer unter der axiomartigen Definition der Heyting-Algebren definieren wir ≤ auf H ₀ durch die Bedingung, dass x ≤ y genau dann gilt, wenn x → y =1. Da nach dem Deduktionssatz eine Formel F → G genau dann beweisbar ist, wenn G aus F beweisbar ist , folgt [ F ]≤[ G ] genau dann, wenn F≼G ist. Mit anderen Worten, ist die Ordnungsrelation auf L /∼, die durch die Vorordnung ≼ auf L induziert wird .

Free Heyting Algebra auf einem beliebigen Satz von Generatoren

In der Tat kann die vorhergehende Konstruktion für jeden Satz von Variablen durchgeführt wird { A _i  : i ∈ I } (möglicherweise unendliche). Auf diese Weise erhält man die freie Heyting-Algebra über die Variablen { A _i }, die wir wiederum mit H _{0 bezeichnen} . Sie ist in dem Sinne frei, dass es für jede Heyting-Algebra H, die zusammen mit einer Familie ihrer Elemente 〈a _i : i ∈ I〉 gegeben ist, einen eindeutigen Morphismus f : H ₀ → H gibt , der f ([ A _i ])= a . erfüllt _ich . Die Eindeutigkeit von f ist nicht schwer zu erkennen, und ihre Existenz ergibt sich im Wesentlichen aus der Metaimplikation 1 ⇒ 2 des Abschnitts „ Beweisbare Identitäten “ oben in Form der Folgerung, dass immer dann, wenn F und G beweisbar äquivalente Formeln sind, F (〈a _i〉)= G (〈a _i〉) für eine beliebige Familie von Elementen 〈a _i〉in H .

Heyting-Algebra von Formeln äquivalent bezüglich einer Theorie T

Gegeben eine Menge von Formeln T in den Variablen { A _i }, betrachtet als Axiome, hätte man dieselbe Konstruktion bezüglich einer auf L definierten Relation F ≼ G so ausführen können , dass G eine beweisbare Folge von F ist und die Menge von Axiomen T . Bezeichnen wir mit H _T die so erhaltene Heyting-Algebra. Dann erfüllt H _T dieselbe universelle Eigenschaft wie H ₀ oben, aber bezüglich Heyting-Algebren H und Familien von Elementen 〈a _i〉 mit der Eigenschaft, dass J (〈a _i〉)=1 für jedes Axiom J (〈A _i〉 ) in T . (Beachten wir, dass H _T zusammen mit der Familie seiner Elemente 〈[ A _i ]〉 selbst diese Eigenschaft erfüllt.) Die Existenz und Eindeutigkeit des Morphismus wird auf die gleiche Weise wie für H ₀ bewiesen , nur muss modifiziert werden die Metaimplikation 1 ⇒ 2 in " Beweisbare Identitäten ", so dass 1 "beweisbar wahr von T " lautet, und 2 lautet "alle Elemente a ₁ , a ₂ ,..., a _n in H, die die Formeln von T erfüllen ."

Die soeben definierte Heyting-Algebra H _T kann als Quotient der freien Heyting-Algebra H ₀ auf derselben Variablenmenge betrachtet werden, indem man die universelle Eigenschaft von H ₀ bezüglich H _T und die Familie ihrer Elemente anwendet 〈[ A _i ]〉.

Jede Heyting-Algebra ist isomorph zu einer der Form H _T . Um dies zu sehen, sei H eine beliebige Heyting-Algebra und sei 〈a _i : i ∈I〉 eine Familie von Elementen, die H erzeugen (zB jede surjektive Familie). Betrachten Sie nun die Menge T der Formeln J (〈A _i〉) in den Variablen 〈A _i : i ∈I〉 mit J (〈a _i〉)=1. Dann erhalten wir einen Morphismus f : H _T → H durch die universelle Eigenschaft von H _T , die eindeutig surjektiv ist. Es ist nicht schwer zu zeigen, dass f injektiv ist.

Vergleich mit Lindenbaum-Algebren

Die eben gegebenen Konstruktionen spielen bezüglich der Heyting-Algebren eine ganz analoge Rolle wie die der Lindenbaum-Algebren bezüglich der Booleschen Algebren . Tatsächlich ist die Lindenbaum-Algebra B _T in den Variablen { A _i } bezüglich der Axiome T gerade unser H _{T ∪ T 1} , wobei T ₁ die Menge aller Formeln der Form ¬¬ F → F ist , da die zusätzliche Axiome von T ₁ sind die einzigen, die hinzugefügt werden müssen, um alle klassischen Tautologien beweisbar zu machen.

Heyting-Algebren in der Anwendung auf die intuitionistische Logik

Wenn man die Axiome der intuitionistischen Aussagenlogik als Terme einer Heyting-Algebra interpretiert, dann werden sie bei jeder Zuweisung von Werten an die Variablen der Formel zum größten Element, 1 in jeder Heyting-Algebra ausgewertet . Zum Beispiel ( P ∧ Q ) → P ist per definitionem der pseudo-Komplement, das größte Element x derart , daß . Diese Ungleichung ist für jedes x erfüllt , also ist das größte dieser x 1. ${\displaystyle P\land Q\land x\leq P}$

Außerdem erlaubt uns die Regel des Modus Ponens , die Formel Q aus den Formeln P und P → Q abzuleiten . Aber wenn in jeder Heyting-Algebra P den Wert 1 hat und P → Q den Wert 1 hat, dann bedeutet dies, dass , und so ; es kann nur sein, dass Q den Wert 1 hat. ${\displaystyle P\land 1\leq Q}$${\displaystyle 1\land 1\leq Q}$

Das heißt, wenn eine Formel aus den Gesetzen der intuitionistischen Logik ableitbar ist, indem sie nach der Regel des Modus Ponens aus ihren Axiomen abgeleitet wird, dann wird sie in allen Heyting-Algebren bei jeder Wertzuweisung zu den Variablen der Formel immer den Wert 1 haben . Man kann jedoch eine Heyting-Algebra konstruieren, in der der Wert des Peirceschen Gesetzes nicht immer 1 ist. Betrachten Sie die 3-Elemente-Algebra {0,1/2,1} wie oben angegeben. Wenn wir zuweisen1/2bis P und 0 bis Q , dann wird der Wert von Peirce Gesetz (( P → Q ) → P ) → P ist1/2. Daraus folgt, dass das Peircesche Gesetz nicht intuitiv abgeleitet werden kann. Siehe Curry-Howard-Isomorphismus für den allgemeinen Kontext dessen, was dies in der Typentheorie bedeutet .

Auch die Umkehrung lässt sich beweisen: Hat eine Formel immer den Wert 1, dann ist sie aus den Gesetzen der intuitionistischen Logik ableitbar, also sind die intuitionistisch gültigen Formeln genau diejenigen, die immer den Wert 1 haben dass klassisch gültige Formeln diejenigen Formeln sind, die in der zweielementigen Booleschen Algebra unter jeder möglichen Zuordnung von wahr und falsch zu den Variablen der Formel einen Wert von 1 haben – das heißt, es sind Formeln, die Tautologien im üblichen Wahrheitstabellensinn sind. Eine Heyting-Algebra ist dann vom logischen Standpunkt aus eine Verallgemeinerung des üblichen Systems von Wahrheitswerten, und ihr größtes Element 1 ist analog zu 'wahr'. Das übliche zweiwertige logische System ist ein Spezialfall einer Heyting-Algebra und des kleinsten nicht-trivialen, in dem die einzigen Elemente der Algebra 1 (wahr) und 0 (falsch) sind.

Entscheidungsprobleme

Das Problem, ob eine gegebene Gleichung in jeder Heyting-Algebra gilt, wurde 1965 von S. Kripke als entscheidbar gezeigt. Die genaue rechnerische Komplexität des Problems wurde 1979 von R. Statman festgestellt, der zeigte, dass es PSPACE-vollständig und damit at . ist mindestens so schwer wie das Entscheiden von Gleichungen der Booleschen Algebra (von S. Cook 1971 als conNP-vollständig gezeigt) und vermutlich erheblich schwieriger. Die elementare oder Theorie erster Ordnung der Heyting-Algebren ist unentscheidbar. Es bleibt offen, ob die universelle Horntheorie der Heyting-Algebren oder das Wortproblem entscheidbar ist. À propos des Wortproblems ist bekannt, dass Heyting-Algebren nicht lokal endlich sind (keine Heyting-Algebra, die von einer endlichen nichtleeren Menge erzeugt wird, ist endlich), im Gegensatz zu Booleschen Algebren, die lokal endlich sind und deren Wortproblem entscheidbar ist. Es ist nicht bekannt, ob freie vollständige Heyting-Algebren existieren, außer im Fall eines einzelnen Generators, bei dem die freie Heyting-Algebra auf einem Generator trivial durch Anfügen eines neuen Kreisels vervollständigt werden kann.

Topologische Darstellung und Dualitätstheorie

Jede Heyting-Algebra H ist natürlich isomorph zu einem beschränkten Untergitter L offener Mengen eines topologischen Raums X , wobei die Implikation von L durch das Innere von gegeben ist . Genauer gesagt ist X der Spektralraum der Primideale des beschränkten Gitters H und L ist das Gitter der offenen und quasikompakten Teilmengen von X . ${\displaystyle U\to V}$${\displaystyle (X\setminus U)\cup V}$

Allgemeiner gesagt ist die Kategorie der Heyting-Algebren doppelt äquivalent zur Kategorie der Heyting-Räume. Diese Dualität kann als Einschränkung der klassischen Stone-Dualität beschränkter Verteilungsgitter auf die (nicht vollständige) Unterkategorie der Heyting-Algebren angesehen werden.

Alternativ ist die Kategorie der Heyting-Algebren doppelt äquivalent zur Kategorie der Esakia-Räume . Dies wird Esakia-Dualität genannt .

Anmerkungen

Siehe auch

• Alexandrov-Topologie
• Superintuitionistische (auch bekannt als Zwischen-) Logiken
• Liste der Themen der Booleschen Algebra
• Ockham-Algebra

Verweise

• Rutherford, Daniel Edwin (1965). Einführung in die Gittertheorie . Oliver und Boyd. OCLC  224572 .
• F. Borceux, Handbook of Categorical Algebra 3 , In Encyclopedia of Mathematics and its Applications , Vol. 2 , No. 53, Cambridge University Press, 1994. ISBN  0-521-44180-3 OCLC  52238554
• G. Gierz, KH Hoffmann, K. Keimel, JD Lawson, M. Mislove und DS Scott, Continuous Lattices and Domains , In Encyclopedia of Mathematics and its Applications , Vol. 2 , No. 93, Cambridge University Press, 2003.
• S. Ghilardi. Heyting-Algebren als bi-Heyting-Algebren , Math. Repräsentant Akad. Wissenschaft Kanada XVI., 6:240–244, 1992.
• Heyting, A. (1930), "Die formalen Regeln der intuitionistischen Logik. I, II, III", Sitzungsberichte Akad. Berlin : 42–56, 57–71, 158–169, JFM  56.0823.01
• Dickmann, Max; Schwartz, Niels; Tressl, Marcus (2019). Spektrale Räume . Neue mathematische Monographien. 35 . Cambridge: Cambridge University Press . doi : 10.1017/9781316543870 . ISBN 9781107146723. S2CID  201542298 .

Externe Links

• Heyting Algebra bei PlanetMath .