Heyting-Algebra

In d​er Mathematik s​ind Heyting-Algebren spezielle partielle Ordnungen; gleichzeitig i​st der Begriff d​er Heyting-Algebra e​ine Verallgemeinerung d​es Begriffs d​er Booleschen Algebra. Heyting-Algebren entstehen a​ls Modelle intuitionistischer Logik, e​iner Logik, i​n der d​er Satz v​om ausgeschlossenen Dritten i​m Allgemeinen n​icht gilt. Vollständige Heyting-Algebren s​ind ein zentraler Gegenstand d​er punktfreien Topologie.

Die Heyting-Algebra i​st nach Arend Heyting benannt.

Formale Definition

Eine Heyting-Algebra ${\displaystyle H}$ ist ein beschränkter Verband mit der Eigenschaft, dass es für alle ${\displaystyle a}$ und ${\displaystyle b}$ in ${\displaystyle H}$ ein größtes Element ${\displaystyle x}$ in ${\displaystyle H}$ gibt mit

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

Dieses Element wird das relative Pseudokomplement von ${\displaystyle a}$ bezüglich ${\displaystyle b}$ genannt und ${\displaystyle a\rightarrow b}$ geschrieben.

Eine äquivalente Definition k​ann mittels folgender Abbildungen gegeben werden:

${\displaystyle f_{a}\colon H\rightarrow H}$ definiert als ${\displaystyle f_{a}(x)=a\wedge x,}$

für festes ${\displaystyle a}$ in ${\displaystyle H}$. Ein beschränkter Verband ${\displaystyle H}$ ist eine Heyting-Algebra genau dann, wenn alle Abbildungen ${\displaystyle f_{a}}$ Linksadjungierte einer Galoisverbindung sind. In diesem Fall ist der jeweilige Rechtsadjungierte ${\displaystyle g_{a}}$ gegeben durch ${\displaystyle g_{a}(x)=(a\rightarrow x)}$, wobei ${\displaystyle \rightarrow }$ wie oben definiert wird.

Eine vollständige Heyting-Algebra i​st eine Heyting-Algebra, d​ie ein vollständiger Verband ist.

In jeder Heyting-Algebra kann man das Pseudokomplement ${\displaystyle \lnot x}$ eines Elements ${\displaystyle x}$ definieren durch ${\displaystyle \lnot x=(x\rightarrow 0)}$, wobei 0 das kleinste Element der Heyting-Algebra ist. Es gilt ${\displaystyle a\wedge \lnot a=0}$, und zudem ist ${\displaystyle \lnot a}$ das größte Element mit dieser Eigenschaft. Jedoch gilt im Allgemeinen nicht ${\displaystyle a\vee \lnot a=1}$, so dass ${\displaystyle \lnot }$ nur ein Pseudokomplement und kein echtes Komplement ist.

Beispiele

Die freie Heyting-Algebra über einem Erzeuger (Rieger–Nishimura-Verband)

• Jede totale Ordnung, die ein beschränkter Verband ist, ist auch eine Heyting-Algebra mit ${\displaystyle (a\to b)={\begin{cases}1&a\leq b\\b&{\text{sonst.}}\end{cases}}}$

• Jede Boolesche Algebra ist eine Heyting-Algebra, mit ${\displaystyle a\to b}$ definiert als ${\displaystyle \lnot a\lor b}$.

• Die einfachste Heyting-Algebra, die nicht schon eine Boolesche Algebra ist, ist die linear geordnete Menge { 0, ½, 1 } mit folgenden Operationen:

${\displaystyle a\land b}$ ${\displaystyle b}$ ${\displaystyle a}$ 0 ½ 1 0 0 0 0 ½ 0 ½ ½ 1 0 ½ 1

${\displaystyle a\lor b}$ ${\displaystyle b}$ ${\displaystyle a}$ 0 ½ 1 0 0 ½ 1 ½ ½ ½ 1 1 1 1 1

${\displaystyle a\rightarrow b}$ ${\displaystyle b}$ ${\displaystyle a}$ 0 ½ 1 0 1 1 1 ½ 0 1 1 1 0 ½ 1

${\displaystyle a}$ ${\displaystyle \neg a}$ 0 1 ½ 0 1 0

Man sieht, dass ${\displaystyle {\tfrac {1}{2}}\lor \neg {\tfrac {1}{2}}={\tfrac {1}{2}}\lor 0={\tfrac {1}{2}}}$ den Satz vom ausgeschlossenen Dritten verletzt.

• Der Verband der offenen Mengen eines topologischen Raums ist eine vollständige Heyting-Algebra. In diesem Fall ist ${\displaystyle A\rightarrow B}$ das Innere der Vereinigung von ${\displaystyle A_{c}}$ und ${\displaystyle B}$, wobei ${\displaystyle A_{c}}$ das Komplement der offenen Menge ${\displaystyle A}$ bezeichnet. Nicht alle vollständigen Heyting-Algebren sind auf diese Weise erzeugbar. Damit zusammenhängende Fragen werden in der punktfreien Topologie untersucht, in der vollständige Heyting-Algebren auch Frames oder Locales genannt werden.

• Die Lindenbaum-Algebra der intuitionistischen Aussagenlogik ist eine Heyting-Algebra. Sie ist definiert als die Menge aller aussagenlogischen Formeln, geordnet durch die logische Folgerungsrelation: für zwei Formeln ${\displaystyle F}$ und ${\displaystyle G}$ sei ${\displaystyle F\leq G}$ genau dann, wenn ${\displaystyle F\models G}$. Dabei ist ${\displaystyle \leq }$ allerdings nur eine Quasiordnung, die eine partielle Ordnung induziert, welche dann die gewünschte Heyting-Algebra ist.

• Die globalen Elemente des Unterobjekt-Klassifikators ${\displaystyle \Omega }$ eines Elementartopos bilden eine Heyting-Algebra; es ist die Heyting-Algebra der Wahrheitswerte der von dem Topos induzierten intuitionistischen Logik höherer Stufe.

• Die Heytingalgebra mit dem Hassediagramm

      1
      |
      M
     / \
    L   R
     \ /
      0

  ist ein minimales Beispiel mit Elementen ${\displaystyle x}$, für die ${\displaystyle \lnot \lnot x\leq x}$ gilt, aber nicht ${\displaystyle 1\leq x\lor \lnot x}$ (nämlich: L und R).

Eigenschaften

Heyting-Algebren s​ind stets distributiv, d. h.

1. ${\displaystyle x\land (y\lor z)=(x\land y)\lor (x\land z)}$ und
2. ${\displaystyle x\lor (y\land z)=(x\lor y)\land (x\lor z)}$.

Die Distributivität wird manchmal als Axiom postuliert, aber sie folgt schon aus der Existenz relativer Pseudokomplemente. Der Grund für das Gelten von 1) ist, dass ${\displaystyle x\wedge -}$ als unterer Adjungierter einer Galois-Verbindung alle existierenden Suprema bewahrt. 1) ist aber nichts anderes als die Bewahrung binärer Suprema durch ${\displaystyle x\wedge -}$.

Mit e​inem ähnlichen Argument lässt s​ich folgendes infinitäres Distributivgesetz i​n vollständigen Heyting-Algebren zeigen:

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

für alle ${\displaystyle x}$ aus ${\displaystyle H}$ und Teilmengen ${\displaystyle Y}$ von ${\displaystyle H}$.

Ein Verband ${\displaystyle A}$ mit einer binären Operation ${\displaystyle \rightarrow }$ ist eine Heyting-Algebra genau dann, wenn:

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

Nicht jede Heyting-Algebra erfüllt die beiden De Morganschen Gesetze. Allerdings sind folgende Aussagen über eine beliebige Heyting-Algebra ${\displaystyle H}$ äquivalent:

1. ${\displaystyle H}$ erfüllt beide De Morganschen Gesetze.
2. ${\displaystyle \lnot (x\wedge y)=\lnot x\vee \lnot y}$, für alle ${\displaystyle x,y\in H}$.
3. ${\displaystyle \lnot x\vee \lnot \lnot x=1}$, für alle ${\displaystyle x\in H}$.
4. ${\displaystyle \lnot \lnot (x\vee y)=\lnot \lnot x\vee \lnot \lnot y}$, für alle ${\displaystyle x,y\in H}$.

Das Pseudokomplement eines Elements ${\displaystyle x}$ aus ${\displaystyle H}$ ist das Supremum der Menge ${\displaystyle \{\,y\mid y\wedge x=0\,\}}$, und es gehört zu dieser Menge (d. h. es gilt ${\displaystyle x\wedge \lnot x=0}$).

Ein Element ${\displaystyle x}$ einer Heyting-Algebra ${\displaystyle H}$ heißt regulär, wenn eine der folgenden äquivalenten Bedingungen gilt:

1. ${\displaystyle x=\lnot \lnot x}$.
2. ${\displaystyle x=\lnot y}$ für ein ${\displaystyle y}$ aus ${\displaystyle H}$.

Eine Heyting-Algebra ${\displaystyle H}$ ist eine Boolesche Algebra genau dann, wenn eine der folgenden äquivalenten Bedingungen gilt:

1. Jedes ${\displaystyle x}$ aus ${\displaystyle H}$ ist regulär.[1]
2. ${\displaystyle x\vee \lnot x=1}$ für alle ${\displaystyle x}$ aus ${\displaystyle H}$.[1]

In diesem Fall ist das Element ${\displaystyle a\rightarrow b}$ gleich ${\displaystyle \lnot a\vee b}$.

In j​eder Heyting-Algebra s​ind das kleinste u​nd das größte Element, 0 u​nd 1, regulär.

Die regulären Elemente einer Heyting-Algebra bilden eine Boolesche Algebra. Wenn nicht alle Elemente der Heyting-Algebra regulär sind, ist diese Boolesche Algebra kein Unterverband der Heyting-Algebra, weil die Supremums-Operationen verschieden sind.

Ist ${\displaystyle H}$ eine Heyting-Algebra, so kann es sein, dass der dazu duale Verband ${\displaystyle H^{\text{op}}}$ ebenfalls eine Heyting-Algebra ist. Falls das so ist, kann man zu einem Element ${\displaystyle a\in H}$ in ${\displaystyle H^{\text{op}}}$ das Pseudokomplement bilden und dieses als Element ${\displaystyle {\bar {a}}}$ von ${\displaystyle H}$ auffassen. Es gilt dann immer ${\displaystyle \lnot a\leq {\bar {a}}}$. In der anderen Richtung gilt die Ungleichung im Allgemeinen nicht: ${\displaystyle {\bar {a}}\leq \lnot a}$ ist äquivalent zu ${\displaystyle a\lor \lnot a=1}$ und zu ${\displaystyle a\land {\bar {a}}=0}$.

Im Unterschied zu manchen mehrwertigen Logiken teilen Heyting-Algebren mit Booleschen Algebren die folgende Eigenschaft: Wenn die Negation einen Fixpunkt hat (also ${\displaystyle \lnot a=a}$ für ein ${\displaystyle a}$), dann ist die Heyting-Algebra trivial: sie besteht nur aus einem Element.

Bedeutung für intuitionistische Logik

Arend Heytings Motivation, diesen Begriff einzuführen, war die Klärung der Bedeutung von intuitionistischer Logik für die Grundlagen der Mathematik. Das Peircesche Gesetz ${\displaystyle ((P\rightarrow Q)\rightarrow P)\rightarrow P}$ illustriert die Rolle, die Heyting-Algebren für die Semantik intuitionistischer Logik spielen. Das Peircesche Gesetz ist in klassischer Logik gültig, nicht aber in intuitionistischer Logik.

Eine Heyting-Algebra i​st vom logischen Standpunkt a​us gesehen e​ine Verallgemeinerung d​er üblichen Menge v​on Wahrheitswerten. Unter anderen entspricht d​em größten Element 1 e​iner Heyting-Algebra d​er Wahrheitswert wahr; d​as kleinste Element 0 entspricht falsch. Die übliche zweiwertige Logik i​st das einfachste Beispiel e​iner Heyting-Algebra – s​ie besteht n​ur aus diesen beiden Elementen. Abstrakt gesagt i​st die zwei-elementige Boolesche Algebra a​uch (wie j​ede Boolesche Algebra) e​ine Heyting-Algebra.

Klassisch gültige Formeln sind solche, die unter jeden möglichen Belegung der aussagenlogischen Variablen in der zweiwertigen Booleschen Algebra den Wert 1 (wahr) ergeben, d. h. die üblichen aussagenlogischen Tautologien. (Äquivalent dazu können auch alle Belegungen in allen Booleschen Algebren betrachtet werden.) Intuitionistisch gültige Formeln sind hingegen solche, die für alle Heyting-Algebren und alle Belegungen den Wert 1 ergeben. In der oben angegebenen dreielementigen Heyting-Algebra ist der Wert von Peirces Gesetz nicht immer 1: wenn man ${\displaystyle P}$ mit ½ und ${\displaystyle Q}$ mit 0 belegt, dann ist der Wert ${\displaystyle ((P\rightarrow Q)\rightarrow P)\rightarrow P}$ nicht 1, sondern nur ½. Nach oben Gesagtem bedeutet das, dass das Peircesche Gesetz intuitionistisch nicht gültig ist – klassisch ist es aber schon gültig.

Literatur

• Marcello Bonsangue, Bart Jacobs, Joost N. Kok: Duality Beyond Sober Spaces. Topological Spaces and Observation Frames (= Faculteit der Wiskunde en Informatica. Informatica Rapport. IR-350, ZDB-ID 777097-2). Vrije Universiteit – Faculteit der Wiskunde en Informatica, Amsterdam 1994.
• Francis Borceux: Handbook of Categorical Algebra. Band 3: Categories of Sheaves (= Encyclopedia of Mathematics and its Applications. 52). Cambridge University Press, Cambridge u. a. 1994, ISBN 0-521-44180-3.
• Gerhard Gierz, Karl H. Hofmann, Klaus Keimel, Jimmie D. Lawson, Michael W. Mislove, Dana S. Scott: Continuous Lattices and Domains (= Encyclopedia of Mathematics and its Applications. 93). Cambridge University Press, Cambridge u. a. 2003, ISBN 0-521-80338-1.
• Peter T. Johnstone: Stone Spaces. (= Cambridge Studies in Advanced Mathematics. 3). Cambridge University Press, Cambridge u. a. 1986, ISBN 0-521-33779-8.
• Daniel E. Rutherford: Introduction to Lattice Theory. Oliver and Boyd, Edinburgh u. a. 1965.

Einzelnachweise

1. Edward M. Patterson, Daniel E. Rutherford: Elementary Abstract Algebra. Oliver & Boyd, Edinburgh u. a. 1965, S. 78.