Quelltext der Seite Heyting-Algebra

In der [[Mathematik]] sind '''Heyting-Algebren''' spezielle [[partielle Ordnung]]en; gleichzeitig ist der Begriff der Heyting-Algebra eine Verallgemeinerung des Begriffs der [[Boolesche Algebra|Booleschen Algebra]]. Heyting-Algebren entstehen als Modelle [[Intuitionistische Logik|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 (Mathematik)|Topologie]].

Die Heyting-Algebra ist nach [[Arend Heyting]] benannt.

== Formale Definition ==

Eine Heyting-Algebra <math>H</math> ist ein beschränkter [[Verband (Mathematik)|Verband]] mit der Eigenschaft, dass es für alle <math>a</math> und <math>b</math> in <math>H</math> ein größtes Element <math>x</math> in <math>H</math> gibt mit

:<math> a \wedge x \le b.</math>

Dieses Element wird das '''relative Pseudokomplement''' von <math>a</math> bezüglich <math>b</math> genannt und  <math>a \rightarrow b</math> geschrieben.

Eine äquivalente Definition kann mittels folgender Abbildungen gegeben werden:

<math>f_a\colon H \rightarrow H</math> definiert als <math>f_a(x) = a\wedge x,</math>

für festes <math>a</math> in <math>H</math>. Ein beschränkter Verband <math>H</math> ist eine Heyting-Algebra genau dann, wenn alle Abbildungen <math>f_a</math> [[Linksadjungiert]]e einer [[Galoisverbindung]] sind.  In diesem Fall ist der jeweilige Rechtsadjungierte <math>g_a</math> gegeben durch <math>g_a(x) = (a \rightarrow x)</math>, wobei <math>\rightarrow</math> 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''' <math>\lnot x</math> eines Elements <math>x</math> definieren durch <math>\lnot x = (x \rightarrow \bot)</math>, wobei <math>\bot</math> das kleinste Element der Heyting-Algebra ist. Es gilt <math>a\wedge \lnot a = \bot</math>, und zudem ist <math>\lnot a</math> das größte Element mit dieser Eigenschaft. Jedoch gilt im Allgemeinen nicht <math>a\vee\lnot a = \top</math>, so dass <math>\lnot</math> nur ein Pseudokomplement und kein echtes [[Komplement (Verbandstheorie)|Komplement]] ist.

== Beispiele ==
[[Datei:Rieger-Nishimura.svg|mini|280px|Die [[Linksadjungiert|freie]] Heyting-Algebra über einem Erzeuger (Rieger–Nishimura-Verband)]]

* Jede [[Totale Ordnung#Totalordnung|totale Ordnung]], die ein beschränkter Verband ist, ist auch eine Heyting-Algebra mit <math>(a \to b) = \begin{cases}\top & a\leq b\\b & \text{sonst.}\end{cases}</math>

* Jede Boolesche Algebra ist eine Heyting-Algebra, mit <math>a \to b</math> definiert als <math>\lnot a \lor b</math>.

* Jeder vollständige Verband <math>A</math>, in dem für alle <math>x \in A, Y \subseteq A</math> gilt <math>x \land \bigvee Y \le \bigvee \{x \land y \mid y \in Y\}</math> ist bereits eine vollständige Heyting-Algebra mit <math>(a \to b) = \bigvee\{x \in A \mid a \land x \le b\}</math>. 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]]
: <math>\begin{array}{ccccc}
\top \\
\mid \\
M \\
\mid \\
\bot
\end{array}</math>
: Man sieht, dass <math>M \lor\neg M = M \lor \bot = M</math> den Satz vom ausgeschlossenen Dritten verletzt.
* Der Verband der [[Offene Menge|offenen Mengen]] eines [[Topologischer Raum|topologischen Raums]] ist eine vollständige Heyting-Algebra. In diesem Fall ist <math>A \rightarrow B</math> die Vereinigung aller offenen Mengen <math>F</math>, die <math>F \cap A \subseteq B</math> erfüllen. Unter Verwendung klassischer Logik lässt sich zeigen, dass dies das [[Innerer Punkt|Innere]] der Vereinigung von <math>A_c</math> und <math>B</math> ist, wobei <math>A_c</math> das Komplement der offenen Menge <math>A</math> bezeichnet. Nicht alle vollständigen Heyting-Algebren sind auf diese Weise erzeugbar. Damit zusammenhängende Fragen werden in der [[Punktfreie Topologie|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 <math>F</math> und <math>G</math> sei  <math>F \le G</math> genau dann, wenn <math>F \models G</math>. Dabei ist <math>\le</math> allerdings nur eine [[Quasiordnung]], die eine partielle Ordnung induziert, welche dann die gewünschte Heyting-Algebra ist.

* Die globalen Elemente des Unterobjekt-Klassifikators <math>\Omega</math> 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
:<math>\begin{array}{ccccc}
&&\top \\
&&\mid \\
&&M\\
&\diagup&&\diagdown \\
L&&&&R \\
&\diagdown&&\diagup \\
&& \bot
\end{array}</math> 
:ist ein minimales Beispiel mit Elementen <math>x</math>, für die <math>\lnot\lnot x \leq x</math> gilt, aber nicht <math>\top \leq x \lor \lnot x</math> (nämlich: L und R), wie auch ein minimales Beispiel mit Elementen <math>p,q,r</math>, für die <math>p \to q \lor r \leq (p \to q) \lor (p \to r)</math> nicht gilt (nämlich:<math>(p,q,r) = (M,L,R)</math>).

* Für eine natürlich Zahl <math>n \ne 0</math> ist der [[Teilerverband]] von <math>n</math> endlich, distributiv und beschränkt, und somit eine vollständige Heytingalgebra. Diese ist eine Boolesche Algebra gdw. <math>n</math> [[quadratfrei]] ist.
* <math>\mathbb N</math> mit Teilerrelation als Ordnungsrelation ist zwar<!-- jedenfalls mit klassischer Logik--> ein vollständiger Verband (größtes Element ist 0, kleinstes Element ist 1, <math>\bigvee M = \mathrm{kgV}(M)</math>, bei unendlichen <math>M</math> ist das 0), jedoch keine vollständige Heytingalgebra, und somit auch keine Heytingalgebra, da die Distributivität von <math>\land</math> über <math>\bigvee</math> nicht gilt: <math>2 \land \bigvee \{3,5,7,9,\dots\} = 2 \land 0 = 2</math>, während <math>\bigvee \{2 \land 3, 2 \land 5, 2 \land 7, 2 \land 9, \dots\} = \bigvee \{1\} = 1.</math>

== Eigenschaften ==
Heyting-Algebren sind stets [[Distributivgesetz|distributiv]], d.&nbsp;h.
# <math>x \land (y \lor z) = (x\land y) \lor (x\land z)</math> und
# <math>x \lor (y \land z) = (x\lor y) \land (x \lor z)</math>.
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 <math>x \wedge -</math> als unterer Adjungierter einer Galois-Verbindung alle existierenden [[Supremum|Suprema]] bewahrt. 1) ist aber nichts anderes als die Bewahrung binärer Suprema durch <math>x \wedge -</math>.

Mit einem ähnlichen Argument lässt sich folgendes infinitäres Distributivgesetz in vollständigen Heyting-Algebren zeigen:
:<math>x\wedge\bigvee Y = \bigvee \{\, x \wedge y \mid y \in Y \,\}</math>
für alle <math>x</math> aus <math>H</math> und Teilmengen <math>Y</math> von <math>H</math>.

Ein Verband <math>A</math> mit einer binären Operation <math>\rightarrow</math> ist eine Heyting-Algebra genau dann, wenn:
#<math>(a\rightarrow a) = \top</math>,
#<math>a\wedge(a\rightarrow b) = a\wedge b</math>,
#<math>b\wedge(a\rightarrow b) = b</math>,
#<math>a\rightarrow (b\wedge c) = (a\rightarrow b)\wedge (a\rightarrow c)</math>.

Nicht jede Heyting-Algebra erfüllt die beiden [[De Morgansche Gesetze|De Morganschen Gesetze]]. Allerdings sind folgende Aussagen über eine beliebige Heyting-Algebra <math>H</math> äquivalent:
# <math>H</math> erfüllt beide De Morganschen Gesetze.
# <math>\lnot(x \wedge y)=\lnot x \vee \lnot y</math>,  für alle <math>x,y\in H</math>.
# <math>\lnot x \vee \lnot\lnot x = \top</math>,  für alle <math>x\in H</math>.
# <math>\lnot\lnot (x \vee y) = \lnot\lnot x \vee \lnot\lnot y</math>,  für alle <math>x, y\in H</math>.
Das Pseudokomplement eines Elements <math>x</math> aus <math>H</math> ist das [[Supremum]] der Menge
<math>\{\, y \mid y \wedge x = \bot \,\}</math>, und es gehört zu dieser Menge (d.&nbsp;h. es gilt
<math>x \wedge \lnot x = \bot</math>).

Ein Element <math>x</math> einer Heyting-Algebra <math>H</math> heißt '''regulär''', wenn eine der folgenden äquivalenten Bedingungen gilt:
# <math>x=\lnot\lnot x</math>.
# <math>x=\lnot y</math> für ein <math>y</math> aus <math>H</math>.
Eine Heyting-Algebra <math>H</math> ist eine [[Boolesche Algebra]] genau dann, wenn eine der folgenden äquivalenten Bedingungen gilt:
# Jedes <math>x</math> aus <math>H</math> ist regulär.<ref name="Rutherford">{{Literatur |Autor=Edward M. Patterson, Daniel E. Rutherford |Titel=Elementary Abstract Algebra |Verlag=Oliver & Boyd |Ort=Edinburgh u. a. |Datum=1965 |Seiten=78}}</ref>
# <math>x\vee\lnot x=\top</math> für alle <math>x</math> aus <math>H</math>.<ref name="Rutherford" />

In diesem Fall ist das Element <math>a \rightarrow b</math> gleich <math>\lnot a \vee b</math>.

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 <math>H</math> eine Heyting-Algebra, so kann es sein, dass der dazu duale Verband <math>H^{\text{op}}</math> ebenfalls eine Heyting-Algebra ist. Falls das so ist, kann man zu einem Element <math>a\in H</math> in <math>H^{\text{op}}</math> das Pseudokomplement bilden und dieses als Element <math>\bar a</math> von <math>H</math> auffassen. Es gilt dann immer <math>\lnot a \leq \bar a</math>. In der anderen Richtung gilt die Ungleichung im Allgemeinen nicht:
<math>\bar a \leq \lnot a</math> ist äquivalent zu
<math>a \lor \lnot a = \top</math> und zu
<math>a \land \bar a = \bot</math>.

Im Unterschied zu manchen [[Mehrwertige Logik|mehrwertigen Logiken]] teilen Heyting-Algebren mit Booleschen Algebren die folgende Eigenschaft: Wenn die Negation einen [[Fixpunkt (Mathematik)|Fixpunkt]] hat (also <math>\lnot a = a</math> für ein <math>a</math>), 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 [[Charles S. Peirce|Peircesche]] Gesetz <math>((P\rightarrow Q)\rightarrow P)\rightarrow P</math> 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 [[Wahrheitswert]]en. Unter anderen entspricht dem größten Element <math>\top</math> einer Heyting-Algebra der Wahrheitswert ''wahr;'' das kleinste Element <math>\bot</math> entspricht ''falsch.'' Die übliche zweiwertige Logik ist das einfachste Beispiel einer Heyting-Algebra&nbsp;– 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 <math>\top</math> (wahr) ergeben, d.&nbsp;h. die üblichen aussagenlogischen [[Tautologie (Logik)|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 <math>\top</math> ergeben.
In der oben angegebenen dreielementigen Heyting-Algebra ist der Wert von Peirces Gesetz nicht immer <math>\top</math>: wenn man <math>P</math> mit <math>M</math> und <math>Q</math> mit <math>\bot</math> belegt, dann ist der Wert <math>((P\rightarrow Q)\rightarrow P)\rightarrow P</math> nicht <math>\top</math>, sondern nur <math>M</math>. Nach oben Gesagtem bedeutet das, dass das Peircesche Gesetz intuitionistisch nicht gültig ist&nbsp;– 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|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 Heinrich Hofmann|Karl H. Hofmann]], Klaus Keimel, Jimmie D. Lawson, Michael W. Mislove, [[Dana Scott|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 Johnstone (Mathematiker)|Peter T. Johnstone]]: ''Stone Spaces.'' (= ''Cambridge Studies in Advanced Mathematics.'' 3). Cambridge University Press, Cambridge u. a. 1986, ISBN 0-521-33779-8.
* [[Daniel Edwin Rutherford|Daniel E. Rutherford]]: ''Introduction to Lattice Theory.'' Oliver and Boyd, Edinburgh u. a. 1965.

== Einzelnachweise ==
<references />

[[Kategorie:Verband (Mathematik)]]
[[Kategorie:Algebra]]
[[Kategorie:Mathematische Logik]]
[[Kategorie:Ordnungstheorie]]
[[Kategorie:Verbandstheorie]]