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.

Inhaltsverzeichnis

Formale Definition

Eine Heyting-Algebra H ist ein 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 \le 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: H \to 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 fa Linksadjungierte einer Galoisverbindung sind. In diesem Fall ist der jeweilige Rechtsadjungierte ga 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

Die freie Heyting-Algebra über einem Generator (Rieger–Nishimura-Verband)
  • Jede totale Ordnung, die ein beschränkter Verband ist, ist auch eine Heyting-Algebra, in der \lnot a = 0 für alle a verschieden von 0 gilt.
  • Jede Boolesche Algebra ist eine Heyting-Algebra, mit pq definiert als ¬pq.
  • 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 ½\lor\neg½ = ½\lor0 = ½ 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 Ac und B, wobei Ac 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 von propositionaler intuitionistischer Logik ist eine Heyting-Algebra. Sie ist definiert als die Menge aller propositionalen Formeln, geordnet durch die logische Folgerungsrelation: für zwei Formeln F und G sei F \le G genau dann wenn F \models G. Dabei ist \le allerdings nur eine Quasiordnung, die eine partielle Ordnung induziert, welche dann die gewünschte Heyting-Algebra ist.
  • Die globalen Elemente des Unterobjekt-Klassifikators Ω eines Elementartopos bilden eine Heyting-Algebra; es ist die Heyting-Algebra der Wahrheitswerte der von dem Topos induzierten intuitionistischen Logik höherer Stufe.

Eigenschaften

Heyting-Algebren sind stets distributiv, d.h. ein Verband A mit einer binären Operation \rightarrow ist eine Heyting-Algebra genau dann wenn:

  1. a\rightarrow a = 1
  2. a\wedge(a\rightarrow b)=a\wedge b
  3. b\wedge(a\rightarrow b)= b
  4. a\rightarrow (b\wedge c)= (a\rightarrow b)\wedge (a\rightarrow c) (Distributivgesetz)

Das Distributivgesetz wird manchmal als ein Axiom postuliert, aber es folgt schon aus der Existenz relativer Pseudokomplemente. Der Grund dafür ist dass \wedge als unterer Adjungierter einer Galois-Verbindung alle existierenden Suprema bewahrt. Distributivität ist aber nichts anderes als die Bewahrung binärer Suprema durch \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 : y \in Y\}

für alle x aus H und Teilmengen Y von H.

Nicht jede Heyting-Algebra erfüllt die beiden De Morganschen Gesetze. Allerdings sind folgende Aussagen in jeder Heyting-Algebra H äquivalent:

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

Das Pseudokomplement eines Elements x aus H is das Supremum der Menge \{ y : 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:

  1. x=\lnot\lnot x.
  2. 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:

  1. jedes x aus H ist regulär.[1]
  2. x\vee\lnot x=1 für alle x aus H.[2]

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.

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 zu einzuführen, war die Klärung der Bedeutung von intuitionistischer Logik für die Grundlagen der Mathematik. Das Piercesche Gesetz ((PQ)→P)→P illustriert die Rolle, die Heyting-Algebren für die Semantik intuitionistischer Logik spielen. Es ist kein einfacher Beweis bekannt, der zeigt, dass das Piercesche Gesetz nicht mittels der Beweisregeln für intuitionistische Logik abgeleitet werden kann.

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 propositionalen 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 alle Booleschen Algebren betrachtet werden.) Intuitionisch 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 Pierces Gesetz nicht immer 1: wenn wir P mit ½ und Q mit 0 belegen, dann ist der Wert ((P → Q) → P) → P nicht 1, sondern nur ½. Nach oben Gesagtem bedeutet das, dass das Piercesche Gesetz intuitionistisch nicht gültig ist - klassisch ist es aber schon gültig.

Literatur

  • Daniel Edwin Rutherford: Introduction to Lattice Theory. Oliver and Boyd 1965
  • F. Borceux, Handbook of Categorical Algebra 3, In Encyclopedia of Mathematics and its Applications, Vol. 53, Cambridge University Press, 1994.
  • G. Gierz, K.H. Hoffmann, K. Keimel, J. D. Lawson, M. Mislove and D. S. Scott, Continuous Lattices and Domains, In Encyclopedia of Mathematics and its Applications, Vol. 93, Cambridge University Press, 2003.
  • P.T. Johnstone, Stone Spaces, In Cambridge Studies in Advanced Mathematics, Vol. 3, Cambridge University Press, 1986.
  • Marcello Bonsangue, Bartholomeus Paulus Franciscus Jacobs, Joost N Kok, Duality Beyond Sober Spaces: Topological Spaces and Observation Frames, Vrije Universiteit, 1994.

Einzelnachweise

  1. Rutherford (1965), Th.26.2 p.78.
  2. Rutherford (1965), Th.26.1 p.78.

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Heyting algebra — In mathematics, Heyting algebras are special partially ordered sets that constitute a generalization of Boolean algebras, named after Arend Heyting. Heyting algebras arise as models of intuitionistic logic, a logic in which the law of excluded… …   Wikipedia

  • 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,… …   Deutsch Wikipedia

  • Complete Heyting algebra — In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra which is complete as a lattice. Complete Heyting algebras are the objects of three different categories; the category CHey, the category Loc of locales,… …   Wikipedia

  • Algebra (disambiguation) — Algebra is a branch of mathematics.Algebra may also mean: * elementary algebra * abstract algebra * linear algebra * universal algebra * computer algebraIn addition, many mathematical objects are known as algebras. * In logic: ** Boolean algebra… …   Wikipedia

  • Algebra (Begriffsklärung) — Algebra bezeichnet in der Mathematik: Algebra, ein Teilgebiet der Mathematik mit den weiteren Teilgebieten Elementare Algebra Abstrakte Algebra Lineare Algebra Kommutative Algebra Universelle Algebra Computeralgebra Außerdem bezeichnet man mit… …   Deutsch Wikipedia

  • Heyting arithmetic — In mathematical logic, Heyting arithmetic is an axiomatization of arithmetic in accordance with the philosophy of intuitionism. It is named after Arend Heyting, who first proposed it.Heyting arithmetic adopts the axioms of Peano arithmetic, but… …   Wikipedia

  • Heyting — Arend Heyting (* 9. Mai 1898 in Amsterdam; † 9. Juli 1980 in Lugano) war ein niederländischer Mathematiker und Logiker. Er war Schüler von L. E. J. Brouwer und befasste sich mit der intuitionistischen Logik, für die er 1930 das erste… …   Deutsch Wikipedia

  • Algebra — This article is about the branch of mathematics. For other uses, see Algebra (disambiguation). Algebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from… …   Wikipedia

  • Álgebra de Heyting — En matemáticas, las álgebras de Heyting (Su creador fue Arend Heyting) son conjuntos parcialmente ordenados especiales que constituyen una generalización de las álgebras de Boole. Las álgebras de Heyting se presentan como modelos de la lógica… …   Wikipedia Español

  • Álgebra de Heyting — En matemáticas, las álgebras de Heyting son conjuntos parcialmente ordenados especiales que constituyen una generalización de las álgebras de Boole. Las álgebras de Heyting se presentan como modelos de la lógica intuicionista, una lógica en la… …   Enciclopedia Universal

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”