Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 4

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Vorli mag alle Menschen und achtet nicht auf Äußerlichkeiten. Ihr besonderes Talent ist aber, ...




Verknüpfungen

In den beiden folgenden Vorlesungen werden wir die algebraischen Begrifflichkeiten zusammenstellen, die immer wieder verwendet werden und zu einem Großteil aus den Anfängervorlesungen bekannt sein dürften.


Definition  

Eine Verknüpfung auf einer Menge ist eine Abbildung

Eine Verknüpfung macht also aus einem Paar

ein einziges Element

Eine Vielzahl von mathematischen Konstruktionen fällt unter diesen Begriff: Die Addition, die Differenz, die Multiplikation, die Division von Zahlen, die Verknüpfung von Abbildungen, der Durchschnitt oder die Vereinigung von Mengen, etc. Als Verknüpfungssymbol kommt eine ganze Reihe in Frage, z.B. u.s.w. Je nach dem gewählten Symbol spricht man statt Verknüpfung auch von Multiplikation oder Addition, ohne dass man damit eine inhaltliche Bedeutung verbinden sollte. Wichtige strukturelle Eigenschaften einer Verknüpfung werden in den folgenden Definitionen aufgelistet.


Definition  

Eine Verknüpfung

auf einer Menge heißt kommutativ, wenn für alle die Gleichheit

gilt.


Definition  

Eine Verknüpfung

auf einer Menge heißt assoziativ, wenn für alle die Gleichheit

gilt.


Definition  

Es sei eine Menge mit einer Verknüpfung

gegeben. Dann heißt ein Element neutrales Element der Verknüpfung, wenn für alle die Gleichheit gilt.

Im kommutativen Fall muss man natürlich für das neutrale Element nur eine Reihenfolge betrachten.


Definition  

Es sei eine Menge mit einer Verknüpfung

und einem neutralen Element gegeben. Dann heißt zu einem Element ein Element inverses Element, wenn die Gleichheit

gilt.


Definition  

Ein Monoid ist eine Menge zusammen mit einer Verknüpfung

und einem ausgezeichneten Element derart, dass folgende beiden Bedingungen erfüllt sind.

  1. Die Verknüpfung ist assoziativ, d.h. es gilt

    für alle .

  2. ist neutrales Element der Verknüpfung, d.h. es gilt

    für alle .

Die natürlichen Zahlen bilden mit der Addition das kommutative Monoid und mit der Multiplikation das kommutative Monoid .


Beispiel  

Es sei eine Menge und

die Menge aller Abbildungen von in sich. Durch die Hintereinanderschaltung von Abbildungen liegt eine Verknüpfung auf vor, die aufgrund von Lemma 3.15 (Mathematik für Anwender (Osnabrück 2019-2020)) assoziativ ist. Dagegen ist sie nicht kommutativ. Die Identität auf ist das neutrale Element. Eine Abbildung besitzt genau dann ein inverses Element, wenn sie bijektiv ist; das inverse Element ist einfach die Umkehrabbildung.




Potenzen

Es sei ein multiplikativ geschriebenes Monoid. Zu und eine positive natürliche Zahl setzt man

und nennt dies die -te Potenz von . Weiter setzen wir

Man beachte, dass bei der Potenz die Basis aus dem Monoid und der Exponent eine natürliche Zahl ist. Der Ausdruck mit aus dem Monoid hat im Allgemeinen keine Bedeutung.

Wie für die natürlichen Zahlen (siehe Lemma Anhang 1.10) gelten in jedem (kommutativen) Monoid die folgenden Potenzgesetze.


Lemma

Es sei ein Monoid, und . Dann gelten die folgenden Potenzgesetze.

  1. Wenn kommutativ ist, so ist

Beweis

Siehe Aufgabe 4.11.


Wenn das Monoid additiv geschrieben wird, so schreibt man für die -fache Summe von mit sich selbst und spricht von Vielfachen statt von Potenzen. Es gelten dann die entsprechenden Vielfachgesetze, nämlich



Kommutative Halbringe

Wir betrachten nun algebraische Strukturen, bei denen es wie bei den natürlichen Zahlen zwei Verknüpfungen gibt.


Definition  

Ein kommutativer Halbring ist eine Menge mit Verknüpfungen und (genannt Addition und Multiplikation) und mit zwei ausgezeichneten Elementen und derart, dass folgende Bedingungen erfüllt sind:

  1. Die Addition ist eine kommutative, assoziative Verknüpfung, für die das neutrale Element ist.
  2. Die Multiplikation ist eine kommutative, assoziative Verknüpfung, für die das neutrale Element ist.
  3. Es gilt das Distributivgesetz, also

    für alle

    .



Korollar  

Die natürlichen Zahlen

bilden einen kommutativen Halbring.

Beweis  

Dies folgt unmittelbar aus Lemma Anhang 1.5 und aus Lemma Anhang 1.9.


Neben den natürlichen Zahlen gibt es viele weitere Halbringe, beispielsweise die ganzen Zahlen , die rationalen Zahlen , die reellen Zahlen oder die komplexen Zahlen .

Wir lassen das Produktzeichen häufig weg, wenn das nicht zu Missverständnissen führen kann und wir benutzen allgemein die Klammerkonvention, dass Punktrechnung stärker bindet als Strichrechnung, d.h. wir schreiben einfach statt . An weiteren Notationen verwenden wir (gemäß den oben eingeführten Bezeichnungen für Monoide) für ein Halbringelement und eine positive natürliche Zahl die Schreibweisen (-tes Vielfaches von und -te Potenz von ) und . Statt schreiben wir einfach (bzw. manchmal ), d.h. jede natürliche Zahl findet sich in jedem Halbring wieder. Die Schreibweise könnte man dann auch als das Produkt

(mit Einsen) lesen, was aber aufgrund des Distributivgesetzes mit der -fachen Summe von mit sich selbst übereinstimmt. Für

ist dies jedenfalls als im Halbring zu lesen, was nicht ohne weiteres gleich sein muss (aber in allen für uns wichtigen Beispielen gleich ist). Weiter setzen wir

Mit diesen Bezeichnungen gilt nach Lemma 4.8 beispielsweise

und

für natürliche Zahlen (man mache sich klar, was hier jeweils die Multiplikation bezeichnet).

Wie bei den natürlichen Zahlen verwenden wir das Summenzeichen und das Produktzeichen . Für indizierte Elemente aus ist also

und

Die beiden folgenden extremen Beispiele zeigen, wie verschieden ein Halbring von dem Halbring der natürlichen Zahlen sein kann. Dennoch gelten alle aus den Halbringaxiomen ableitbaren Eigenschaften auch in diesen beiden Beispielen.


Beispiel  

Die einelementige Menge kann man zu einem kommutativen Halbring machen, indem man sowohl die Addition als auch die Multiplikation auf die einzig mögliche Weise erklärt, nämlich durch und . In diesem Fall ist , dies ist also ausdrücklich erlaubt. Die Rechengesetze in einem Halbring sind hier trivialerweise erfüllt, da bei jeder zu erfüllenden Gleichung links und rechts sowieso immer herauskommt. Diesen Halbring nennt man den Nullring.


Nach dem Nullring ist der folgende Ring (sogar Körper, siehe die nächste Vorlesung) der zweitkleinste Halbring.


Beispiel  

Wir suchen nach einer Halbringstruktur auf der Menge . Wenn das neutrale Element einer Addition und das neutrale Element der Multiplikation sein soll, so ist dadurch schon viel festgelegt. Nach Lemma 4.13 muss

gelten. Ferner legen wir

fest. Die Verknüpfungstabellen (oder Operationstafeln) sehen somit wie folgt aus.



und



Durch etwas aufwändiges Nachrechnen stellt man fest, dass es sich in der Tat um einen kommutativen Halbring handelt.


Eine „natürliche“ Interpretation dieses Halbringes gewinnt man, wenn man sich die geraden natürlichen Zahlen durch und die ungeraden natürlichen Zahlen durch repräsentiert denkt. Beispielsweise ist die Summe zweier ungerader Zahlen stets gerade, was der obigen Gleichung entspricht. Wie oben erwähnt lassen sich in jedem kommutativen Halbring die natürlichen Zahlen eindeutig interpretieren, dabei können aber, wie in den beiden Beispielen, verschiedene Zahlen gleich werden. Im Beispiel wird jede gerade Zahl zu und jede ungerade Zahl zu .



Lemma  

In einem kommutativen Halbring gilt

Beweis  

Dies ergibt sich aus


Das folgende Beispiel zeigt, dass in einem kommutativen Halbring im Allgemeinen nicht die Gleichung

für alle gilt. Für die natürlichen Zahlen und in jedem kommutativen Ring gilt diese Eigenschaft. Es ist also keineswegs so, dass man jede von den Zahlenbereichen her vertraute Eigenschaft aus dem Begriff eines kommutativen Halbringes ableiten kann.


Beispiel  

Wir suchen nach einer Halbringstruktur auf der dreielementigen Menge . Wenn das neutrale Element einer Addition und das neutrale Element der Multiplikation sein soll, so ist dadurch schon viel festgelegt. Wir legen die Verknüpfungen durch die Verknüpfungstabellen

und

fest. Durch etwas aufwändiges Nachrechnen stellt man fest, dass es sich in der Tat um einen kommutativen Halbring handelt.


Die folgende Aussage heißt das allgemeine Distributivgesetz.



Satz  

Es sei ein kommutativer Halbring und es seien Elemente aus .

Dann gilt das allgemeine Distributivgesetz

Beweis  

Wir machen eine Doppelinduktion nach und nach . D.h. wir beweisen die Aussage für jedes feste durch Induktion nach (innere Induktion) und erhöhen dann in einem eigenen Induktionsdurchgang (äußere Induktion). Bei ist nichts zu zeigen, da dann die Summen links und rechts leer sind, also gleich . Sei also , so dass der linke Faktor einfach eine fixierte Zahl ist. Wir wollen die Aussage in dieser Situation für beliebiges zeigen. Bei ist die Aussage klar. Sei die Aussage nun für ein

schon bewiesen. Dann ist

nach dem Distributivgesetz und mit der Induktionsvoraussetzung folgt die Aussage. Sei die Aussage nun für ein festes und jedes bewiesen. Dann ist wieder mit dem Distributivgesetz und der Induktionsvoraussetzung


Das allgemeine Distributivgesetz gilt auch für mehr als zwei Faktoren, siehe Aufgabe 4.21.



Die Potenzmenge als kommutativer Halbring



Lemma  

Zu einer Menge sei die Potenzmenge zu .

Dann ist mit der Vereinigung als Addition und der leeren Menge als und mit dem Durchschnitt als Multiplikation und der Gesamtmenge als ein kommutativer Halbring.

Beweis  

Die Eigenschaften sind allenfalls bis auf das Distributivgesetz klar. Letzteres besagt die Identität

Wenn ein Element links dazugehört, so gehört es zu und es gehört zu . Somit gehört es zu oder zu und damit auch zu oder zu , also jedenfalls zur rechten Seite. Wenn es rechts dazu gehört, sagen wir zu , was wir wegen der Symmetrie der Situation annehmen können, so gehört es erst recht zu .

Im vorstehenden Beispiel kann man die Rollen der Addition und der Multiplikation vertauschen, da das Distributivgesetz auch in der Form

gilt.



Der binomische Lehrsatz

Die folgende allgemeine binomische Formel oder binomischer Lehrsatz bringt die Addition, die Multiplikation und die Potenzierung in einem kommutativen Halbring und insbesondere für die natürlichen Zahlen miteinander in Beziehung.



Satz  

Es sei ein kommutativer Halbring und . Ferner sei eine natürliche Zahl.

Dann gilt

Beweis  

Wir führen Induktion nach . Für steht einerseits und andererseits . Sei die Aussage bereits für bewiesen. Dann ist


Den vorstehenden Satz kann man sich auf folgendermaßen klar machen. Beim Ausmultiplizieren von

muss jeder Summand gemäß dem allgemeinen Distributivgesetz (in jedem Faktor) mit jedem Summanden multipliziert werden. Für jedes Teilprodukt muss man sich bei jedem Faktor entscheiden, ob man den vorderen Summanden oder den hinteren Summanden nimmt. Die einzelnen Produkte haben die Form , wobei die Anzahl der Faktoren ist, bei denen gewählt wurde und die Anzahl der Faktoren ist, bei denen gewählt wurde. Wenn man fixiert, so kann man sich fragen, auf wie viele Arten das Produkt zustande kommen kann. Eine solche Möglichkeit ist dadurch gegeben, dass man unter den Faktoren bestimmt, an welchen von ihnen gewählt wird. Die Anzahl der Möglichkeiten ist also die Anzahl der -elementigen Teilmengen von , also gleich .


<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)