Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 4/kontrolle
- 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.
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.
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.
Es sei eine Menge mit einer Verknüpfung
und einem neutralen Element gegeben. Dann heißt zu einem Element ein Element inverses Element (zu ). wenn die Gleichheit
gilt.
Ein Monoid ist eine Menge zusammen mit einer Verknüpfung
und einem ausgezeichneten Element derart, dass folgende beiden Bedingungen erfüllt sind.
- Die Verknüpfung ist assoziativ, d.h. es gilt
für alle .
- 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 .
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 2023-2024)) 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.
Es sei ein Monoid, und . Dann gelten die folgenden Potenzgesetze.
- Wenn
kommutativ
ist, so ist
Beweis
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.
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:
- Die Addition ist eine kommutative, assoziative Verknüpfung, für die das neutrale Element ist.
- Die Multiplikation ist eine kommutative, assoziative Verknüpfung, für die das neutrale Element ist.
- Es gilt das Distributivgesetz, also
für alle
.
Die natürlichen Zahlen
bilden einen kommutativen Halbring.
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.
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.
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 .
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.
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.
Es sei ein kommutativer Halbring und es seien Elemente aus .
Dann gilt das allgemeine Distributivgesetz
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 . Es sei also , sodass der linke Faktor einfach eine fixierte Zahl ist. Wir wollen die Aussage in dieser Situation für beliebiges zeigen. Bei ist die Aussage klar. Es sei die Aussage nun für ein
schon bewiesen. Dann ist
nach dem Distributivgesetz und der Induktionsvoraussetzung.
Es 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
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.
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.
Wir führen Induktion nach . Für steht einerseits und andererseits . Es 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 .
