Heyting-Algebra
# 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 0)$, wobei 0 das kleinste Element der Heyting-Algebra ist. Es gilt $a\wedge \lnot a=0$, und zudem ist $\lnot a$ das größte Element mit dieser Eigenschaft. Jedoch gilt im Allgemeinen nicht $a\vee \lnot a=1$, 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}1&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 { 0, ½, 1 } mit folgenden Operationen:

$a\land b$ :

| $b$ $a$ | 0 | ½ | 1 |
| - | - | - | - |
| 0 | 0 | 0 | 0 |
| ½ | 0 | ½ | ½ |
| 1 | 0 | ½ | 1 |

$a\lor b$ :

| $b$ $a$ | 0 | ½ | 1 |
| - | - | - | - |
| 0 | 0 | ½ | 1 |
| ½ | ½ | ½ | 1 |
| 1 | 1 | 1 | 1 |

$a\rightarrow b$ :

| $b$ $a$ | 0 | ½ | 1 |
| - | - | - | - |
| 0 | 1 | 1 | 1 |
| ½ | 0 | 1 | 1 |
| 1 | 0 | ½ | 1 |
| $a$ | $\neg a$ |
| 0 | 1 |
| ½ | 0 |
| 1 | 0 |

    Man sieht, dass ${\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 $A\rightarrow 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 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 1 | M / \ L R \ / 0 ist ein minimales Beispiel mit Elementen $x$, für die $\lnot \lnot x\leq x$ gilt, aber nicht $1\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)$).

## 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)=1$,
* $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=1$, 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=0\,\}$, und es gehört zu dieser Menge (d. h. es gilt $x\wedge \lnot x=0$).

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=1$ 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, 0 und 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 $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=1$ und zu $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 $\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 1 einer Heyting-Algebra der Wahrheitswert wahr; das kleinste Element 0 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 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 $P$ mit ½ und $Q$ mit 0 belegt, dann ist der Wert $((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.

