Universelle Algebra und Verbandstheorie

Vorlesung: Do, 14-16, R 016, Geb. 45
Übungen: Di, 16-18, R 022, Geb. 46 (MPI)
 
Teilgebiet: Die Vorlesung (2V + 2Ü) ist eine Vertiefungsvorlesung im Bereich ``Theoretische Informatik''.
 
Vorkenntnisse: Vordiplom
 
Voraussetzungen zur Scheinvergabe: Erfolgreiche Teilnahme an den Übungen und an der Klausur
 
Zweck der Veranstaltung: Die klassische Aufgabe der Algebra war das Studium der Lösbarkeit von Gleichungen. Zu diesem Zweck wurden algebraische Strukturbegriffe wie Gruppe, Ring, Körper usw. eingeführt. Es stellte sich heraus, daß diese Art Strukturen geeignet waren, auch bei der Lösung ganz andersartiger Probleme zu helfen. So entstanden die verschiedenen algebraischen Strukturtheorien, wie z.B. Gruppentheorie, Ringtheorie, usw.

Die universelle Algebra stellt eine weitere Abstraktionsstufe dar, indem sie solche Klassen algebraischer Strukturen selbst zum Gegenstand ihrer Untersuchungen macht und ein systematisierendes Fundament bildet, welches solche Theorien miteinander verbindet. In den letzten Jahren haben Konzepte aus der Theorie der universellen Algebren Anwendungen in verschiedenen Zweigen der Informatik (Theorie algebraischer Automaten, Spezifikation und Verifikation von Datenstrukturen und Datentypen) oder Logik gefunden.

Die Vorlesung bespricht zuerst die grundlegenden Konzepte der universellen Algebra. Diese allgemeinen Resultate werden im zweiten Teil der Vorlesung auf konkrete Klassen von Algebren, wie z.B. Verbände und Boolesche Algebren angewandt. Anwendungen von universellen Algebren in der Spezifikation von Datentypen und Datenstrukturen, und Verknüpfungen zwischen Verbandstheorie und Elektrotechnik (Schaltalgebra) und Aussagenlogik, sowie algorithmische Aspekte werden auch besprochen.
 
Behandelter Stoff:

1.

Universelle Algebren

• Grundlegende Konzepte
  Unteralgebren, Erzeugendensysteme, Prinzip der algebraischen Induktion;
  Homomorphismen, Kongruenzrelationen, Faktoralgebren;
  die Homomorphie- und Isomorphiesätze; Direkte und subdirekte Produkte;
  Terme, Termalgebren, Identitäten (Quasi-identitäten) und Modelle;
  (Quasi-)Varietäten, freie Algebren, Birkhoff's Satz;
  Gleichungslogik.
• Anwendungen: Spezifikation von Datentypen und Datenstrukturen
• Algorithmische Aspekte

2.

Verbände als algebraische Strukturen

• Definitionen und Eigenschaften: modulare und distributive Verbände; Boolesche Algebren;
• Darstellungen: Darstellungssätze für endliche Boolesche Algebren und endliche distributive Verbände; Stone's Darstellungssatz für Boolesche Algebren;
• Anwendungen: nichtklassische Logiken
• Algorithmische Aspekte

 
 
Vermittelte Fähigkeiten:

• Beherrschung von grundlegenden Konzepten der universellen Algebra und Verbandstheorie;
• Erwerben von Wissen über die Art und Weise, wie diese Konzepte angewandt werden können;

 

 
Literatur: Die Vorlesung wird sich nach S. Burris and H.P. Sankappanavar, ``A Course in Universal Algebra'' (universelle Algebra) sowie B.A. Davey and H.A. Priestley, ``Introduction to Lattices and Order'' (Verbandstheorie) richten.

Weitere Literatur:

G. Birkhoff. Lattice Theory. American Mathematical Society, Providence, RI, 1984.

S. Burris and H.P. Sankappanavar. A Course in Universal Algebra. Graduate Texts in Mathematics. Springer Verlag, 1981.

P.M. Cohn Universal Algebra. D. Reidel, Dordrecht, Holland, 1981.

B.A. Davey and H.A. Priestley. Introduction to Lattices and Order. Cambridge University Press, 1990.

R. Freese, J. Jezek, and J.B. Nation, Free lattices. American Mathematical Society, Providence, RI, 1995.

G. Grätzer. General Lattice Theory. Birkhäuser Verlag, Basel - Stuttgart, 1st edition: 1978; 2nd edition: 1998.

G. Grätzer. Universal Algebra. Springer-Verlag, 1979.

H.-J. Kreowski. Algebra für Informatiker. Technische Universität Berlin (Schriftliches Material zur gleichnamigen Lehrveranstaltung ws 82/83), 1983.

H. Lugowski. Grundzüge der universellen Algebra. Teubner-Texte zur Mathematik, Teubner, 1976.

R.N. McKenzie, G.F. McNulty and W.F. Taylor. Algebras, Lattices, Varieties (Vol I). The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole, 1987.

G. Pilz. Algebra. Ein Reiseführer durch die schönsten Gebiete. Universitätsverlag Rudolf Trauner, Linz, 1984.

W. Wechler. Universal Algebra for Computer Scientists. EATCS Monographs on Theoretical Computer Science 25, 1992.