# Heyting-Algebra

In der Mathematik sind Heyting-Algebren spezielle partielle Ordnungen; gleichzeitig ist der Begriff der Heyting-Algebra eine Verallgemeinerung des Begriffs der Booleschen Algebra. Heyting-Algebren entstehen als Modelle intuitionistischer Logik, einer Logik, in der der Satz vom ausgeschlossenen Dritten im Allgemeinen nicht gilt. Vollständige Heyting-Algebren sind ein zentraler Gegenstand der punktfreien Topologie.
Die Heyting-Algebra ist nach Arend Heyting benannt.

## Formale Definition

Eine Heyting-Algebra $H$ ist ein beschränkter Verband mit der Eigenschaft, dass es für alle $a$ und $b$ in $H$ ein größtes Element $x$ in $H$ gibt mit
    $a\wedge x\leq b.$
Dieses Element wird das relative Pseudokomplement von $a$ bezüglich $b$ genannt und $a\rightarrow b$ geschrieben.
Eine äquivalente Definition kann mittels folgender Abbildungen gegeben werden:
$f_{a}\colon H\rightarrow H$ definiert als $f_{a}(x)=a\wedge x,$
für festes $a$ in $H$. Ein beschränkter Verband $H$ ist eine Heyting-Algebra genau dann, wenn alle Abbildungen $f_{a}$ Linksadjungierte einer Galoisverbindung sind. In diesem Fall ist der jeweilige Rechtsadjungierte $g_{a}$ gegeben durch $g_{a}(x)=(a\rightarrow x)$, wobei $\rightarrow$ wie oben definiert wird.
Eine vollständige Heyting-Algebra ist eine Heyting-Algebra, die ein vollständiger Verband ist.
In jeder Heyting-Algebra kann man das Pseudokomplement $\lnot x$ eines Elements $x$ definieren durch $\lnot x=(x\rightarrow \bot )$, wobei $\bot$ das kleinste Element der Heyting-Algebra ist. Es gilt $a\wedge \lnot a=\bot$, und zudem ist $\lnot a$ das größte Element mit dieser Eigenschaft. Jedoch gilt im Allgemeinen nicht $a\vee \lnot a=\top$, so dass $\lnot$ nur ein Pseudokomplement und kein echtes Komplement ist.

## Beispiele

* Jede totale Ordnung, die ein beschränkter Verband ist, ist auch eine Heyting-Algebra mit $(a\to b)={\begin{cases}\top &a\leq b\\b&{\text{sonst.}}\end{cases}}$
* Jede Boolesche Algebra ist eine Heyting-Algebra, mit $a\to b$ definiert als $\lnot a\lor b$.
* Jeder vollständige Verband $A$, in dem für alle $x\in A,Y\subseteq A$ gilt $x\land \bigvee Y\leq \bigvee \{x\land y\mid y\in Y\}$ ist bereits eine vollständige Heyting-Algebra mit $(a\to b)=\bigvee \{x\in A\mid a\land x\leq b\}$. Endliche, beschränkte, distributive Verbände gehören in diese Klasse.
* Die einfachste Heyting-Algebra, die nicht schon eine Boolesche Algebra ist, ist die linear geordnete Menge mit dem Hassediagramm
    ${\begin{array}{ccccc}\top \\\mid \\M\\\mid \\\bot \end{array}}$
    Man sieht, dass $M\lor \neg M=M\lor \bot =M$ den Satz vom ausgeschlossenen Dritten verletzt.
* Der Verband der offenen Mengen eines topologischen Raums ist eine vollständige Heyting-Algebra. In diesem Fall ist $A\rightarrow B$ die Vereinigung aller offenen Mengen $F$, die $F\cap A\subseteq B$ erfüllen. Unter Verwendung klassischer Logik lässt sich zeigen, dass dies das Innere der Vereinigung von $A_{c}$ und $B$ ist, wobei $A_{c}$ das Komplement der offenen Menge $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 $F$ und $G$ sei $F\leq G$ genau dann, wenn $F\models G$. Dabei ist $\leq$ allerdings nur eine Quasiordnung, die eine partielle Ordnung induziert, welche dann die gewünschte Heyting-Algebra ist.
* Die globalen Elemente des Unterobjekt-Klassifikators $\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
    ${\begin{array}{ccccc}&&\top \\&&\mid \\&&M\\&\diagup &&\diagdown \\L&&&&R\\&\diagdown &&\diagup \\&&\bot \end{array}}$
    ist ein minimales Beispiel mit Elementen $x$, für die $\lnot \lnot x\leq x$ gilt, aber nicht $\top \leq x\lor \lnot x$ (nämlich: L und R), wie auch ein minimales Beispiel mit Elementen $p,q,r$, für die $p\to q\lor r\leq (p\to q)\lor (p\to r)$ nicht gilt (nämlich:$(p,q,r)=(M,L,R)$).
* Für eine natürlich Zahl $n\neq 0$ ist der Teilerverband von $n$ endlich, distributiv und beschränkt, und somit eine vollständige Heytingalgebra. Diese ist eine Boolesche Algebra gdw. $n$ quadratfrei ist.
* $\mathbb {N}$ mit Teilerrelation als Ordnungsrelation ist zwar ein vollständiger Verband (größtes Element ist 0, kleinstes Element ist 1, $\bigvee M=\mathrm {kgV} (M)$, bei unendlichen $M$ ist das 0), jedoch keine vollständige Heytingalgebra, und somit auch keine Heytingalgebra, da die Distributivität von $\land$ über $\bigvee$ nicht gilt: $2\land \bigvee \{3,5,7,9,\dots \}=2\land 0=2$, während $\bigvee \{2\land 3,2\land 5,2\land 7,2\land 9,\dots \}=\bigvee \{1\}=1.$

## Eigenschaften

Heyting-Algebren sind stets distributiv, d. h.
* $x\land (y\lor z)=(x\land y)\lor (x\land z)$ und
* $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 $x\wedge -$ als unterer Adjungierter einer Galois-Verbindung alle existierenden Suprema bewahrt. 1) ist aber nichts anderes als die Bewahrung binärer Suprema durch $x\wedge -$.
Mit einem ähnlichen Argument lässt sich folgendes infinitäres Distributivgesetz in vollständigen Heyting-Algebren zeigen:
    $x\wedge \bigvee Y=\bigvee \{\,x\wedge y\mid y\in Y\,\}$
für alle $x$ aus $H$ und Teilmengen $Y$ von $H$.
Ein Verband $A$ mit einer binären Operation $\rightarrow$ ist eine Heyting-Algebra genau dann, wenn:
* $(a\rightarrow a)=\top$,
* $a\wedge (a\rightarrow b)=a\wedge b$,
* $b\wedge (a\rightarrow b)=b$,
* $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 $H$ äquivalent:
* $H$ erfüllt beide De Morganschen Gesetze.
* $\lnot (x\wedge y)=\lnot x\vee \lnot y$, für alle $x,y\in H$.
* $\lnot x\vee \lnot \lnot x=\top$, für alle $x\in H$.
* $\lnot \lnot (x\vee y)=\lnot \lnot x\vee \lnot \lnot y$, für alle $x,y\in H$.
Das Pseudokomplement eines Elements $x$ aus $H$ ist das Supremum der Menge $\{\,y\mid y\wedge x=\bot \,\}$, und es gehört zu dieser Menge (d. h. es gilt $x\wedge \lnot x=\bot$).
Ein Element $x$ einer Heyting-Algebra $H$ heißt regulär, wenn eine der folgenden äquivalenten Bedingungen gilt:
* $x=\lnot \lnot x$.
* $x=\lnot y$ für ein $y$ aus $H$.
Eine Heyting-Algebra $H$ ist eine Boolesche Algebra genau dann, wenn eine der folgenden äquivalenten Bedingungen gilt:
* Jedes $x$ aus $H$ ist regulär.
* $x\vee \lnot x=\top$ für alle $x$ aus $H$.
In diesem Fall ist das Element $a\rightarrow b$ gleich $\lnot a\vee b$.
In jeder Heyting-Algebra sind das kleinste und das größte Element, $\bot$ und $\top$, 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 $H$ eine Heyting-Algebra, so kann es sein, dass der dazu duale Verband $H^{\text{op}}$ ebenfalls eine Heyting-Algebra ist. Falls das so ist, kann man zu einem Element $a\in H$ in $H^{\text{op}}$ das Pseudokomplement bilden und dieses als Element ${\bar {a}}$ von $H$ auffassen. Es gilt dann immer $\lnot a\leq {\bar {a}}$. In der anderen Richtung gilt die Ungleichung im Allgemeinen nicht: ${\bar {a}}\leq \lnot a$ ist äquivalent zu $a\lor \lnot a=\top$ und zu $a\land {\bar {a}}=\bot$.
Im Unterschied zu manchen mehrwertigen Logiken teilen Heyting-Algebren mit Booleschen Algebren die folgende Eigenschaft: Wenn die Negation einen Fixpunkt hat (also $\lnot a=a$ für ein $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 $((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 ist vom logischen Standpunkt aus gesehen eine Verallgemeinerung der üblichen Menge von Wahrheitswerten. Unter anderen entspricht dem größten Element $\top$ einer Heyting-Algebra der Wahrheitswert wahr; das kleinste Element $\bot$ entspricht falsch. Die übliche zweiwertige Logik ist das einfachste Beispiel einer Heyting-Algebra – sie besteht nur aus diesen beiden Elementen. Abstrakt gesagt ist die zwei-elementige Boolesche Algebra auch (wie jede Boolesche Algebra) eine Heyting-Algebra.
Klassisch gültige Formeln sind solche, die unter jeden möglichen Belegung der aussagenlogischen Variablen in der zweiwertigen Booleschen Algebra den Wert $\top$ (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 $\top$ ergeben. In der oben angegebenen dreielementigen Heyting-Algebra ist der Wert von Peirces Gesetz nicht immer $\top$: wenn man $P$ mit $M$ und $Q$ mit $\bot$ belegt, dann ist der Wert $((P\rightarrow Q)\rightarrow P)\rightarrow P$ nicht $\top$, sondern nur $M$. Nach oben Gesagtem bedeutet das, dass das Peircesche Gesetz intuitionistisch nicht gültig ist – klassisch ist es aber schon gültig.