Verknüpfung – Serlo „Mathe für Nicht-Freaks“

Definition der VerknüpfungBearbeiten

Verknüpfungen sind dir bereits aus der Schule bekannt. Beispiele hierfür sind Addition und Multiplikation. Diese Verknüpfungen können wir als spezielle Abbildungen betrachten. Schauen wir uns dazu als Beispiel die Verknüpfung der Addition auf den reellen Zahlen genauer an:

Die Addition verknüpft zwei Zahlen   und   zu einer neuen Zahl  . Wir können somit die Addition als Abbildung vom   nach   auffassen. (Wiederholung:   ist die Menge aller geordneter Paare   mit   und  ). Der Definitionsbereich ist  , weil bei der Addition zwei reelle Zahlen miteinander verknüpft werden. Die Zielmenge ist  , da das Ergebnis der Addition zweier reeller Zahlen wieder eine reelle Zahl ist. Damit ist die Addition eine Abbildung  . Analog lässt sich auch die Multiplikation als Abbildung von   nach   mit der Zuordnungsvorschrift   auffassen.

Das obige Beispiel können wir nun verallgemeinern. Statt   betrachten wir jetzt irgendeine Grundmenge  . Die Addition ist eine Verknüpfung, die zwei Objekte zu einem neuen Objekt der Grundmenge verknüpft - wir wollen jetzt aber den allgemeineren Fall betrachten, dass eine Verknüpfung   Objekte zu einem neuen Objekt verknüpft. Analog zu unserem Beispiel ist dann eine solche Verknüpfung eine Abbildung  , welche auch  -stellige Verknüpfung genannt wird. Ein Synonym für das Wort „Verknüpfung“ ist der Begriff „Operation“

Definition (Verknüpfung)

Eine  -stellige Verknüpfung auf einer Grundmenge   ist eine Abbildung  .

Verständnisfrage: Zähle Beispiele für Verknüpfungen auf.

  • Addition  , Multiplikation   und Potenzbildung   sind zweistellige Verknüpfungen auf  .
  • Quadratfunktion  , Betragsfunktion   und Sinusfunktion   sind einstellige Verknüpfungen auf  .
  • Funktionskomposition von reellwertigen Funktionen ist eine binäre Verknüpfung auf der Menge aller Funktionen  .
  • Vereinigung, Differenz, Durchschnitt sind binäre Verknüpfungen auf der Potenzmenge einer gegebenen Grundmenge.
  • Komplementbildung ist eine einstellige Verknüpfungen auf der Potenzmenge einer gegebenen Grundmenge.

Binäre VerknüpfungenBearbeiten

Für zweistellige Verknüpfungen wird auch der Begriff binäre Verknüpfung gebraucht:

Definition (binäre Verknüpfung)

Eine binäre Verknüpfung ist eine zweistellige Verknüpfung. Eine binäre Verknüpfung auf einer Grundmenge   ist damit eine Abbildung  .

Betrachten wir eine binäre Verknüpfung   auf einer Grundmenge  . Damit lässt sich   als eine Abbildung   auffassen. Du kannst dir   als eine Maschine vorstellen, die zwei Elemente   und   aus der Menge   nimmt und daraus ein Element   aus   erzeugt:

Für binäre Verknüpfungen wird oft die Schreibweise   verwendet. Hier steht   stellvertretend für eine beliebige Verknüpfung wie die Addition   oder die Multiplikation  . Diese Schreibweise sollte nicht mit der Funktionskomposition verwechselt werden, die auch das Symbol   verwendet (Zwar ist die Funktionskomposition eine binäre Verknüpfung, aber nicht jede binäre Verknüpfung ist eine Funktionskomposition).

Eigenschaften binärer VerknüpfungenBearbeiten

Sei im Folgenden   eine beliebige Verknüpfung auf einer Grundmenge  . Wir betrachten nun die sogenannte Kommutativität beziehungsweise Assoziativität der binären Verknüpfung.

KommutativitätBearbeiten

Betrachten wir die Maschinenvorstellung einer binären Verknüpfung. Bei einer binären Verknüpfung besitzt die Maschine zwei Eingänge. In diese können wir zwei Objekte   und   aus der Grundmenge stecken. Ein Element stecken wir links in unsere Maschine und das andere rechts:

Ist die Reihenfolge, in der wir die Argumente in die Maschine stecken, egal? Kommt immer dasselbe raus, wenn wir   und   vertauschen?

Es gibt solche Verknüpfungen, bei dem die Reihenfolge der Argumente egal ist. Bei solchen Verknüpfungen ist stets   unabhängig davon, welche Argumente   und   gewählt wurden. Ein Beispiel hierfür ist die Addition   auf den reellen Zahlen. Für die Addition gilt nämlich stets  .

Weil diese Eigenschaft praktisch ist, bekommt sie einen eigenen Namen. Wir sprechen hier von Kommutativität beziehungsweise nennen solche Verknüpfungen kommutative Verknüpfungen. Der Begriff kommt vom lateinischen Wort commutare, was „vertauschen“ bedeutet. Es ist also:

Definition (Kommutativität)

Eine binäre Verknüpfung   heißt kommutativ, wenn für alle   gilt:  .

Beispiel (Beispiel und Nichtbeispiel für Kommutativität)

  • Die Addition   auf den reellen Zahlen ist kommutativ. Für alle reellen Zahlen   und   ist nämlich  .
  • Die Subtraktion   auf den reellen Zahlen ist nicht kommutativ. So ist  , aber  , also  .

Assoziativität Bearbeiten

Was passiert, wenn wir mehr als zwei Objekte miteinander verknüpfen wollen? Nehmen wir die Addition als Verknüpfung und betrachten wir die Summe  . Wie können wir diese Operation ausführen, wenn die Addition als zweistellige Verknüpfung definiert ist, also genau zwei Argumente zu einem Ergebnis zusammenfasst?

Hier haben wir zwei Möglichkeiten: Zum einen können wir zunächst die Summe von   und   bilden und dann   hinzuaddieren. So berechnen wir  . Zum anderen kann zunächst   und   miteinander addiert werden, um danach die Summe aus   und dem Ergebnis der ersten Summe zu bilden. Hier wird   gerechnet.

So haben wir bei jeder Verknüpfung   zwei Möglichkeiten, um   zu berechnen. Zum einen kann dieser Ausdruck als   und zum anderen als   berechnet werden. Im folgenden Diagramm sind beide Möglichkeiten mit dem Maschinenmodell dargestellt. Dabei stellt sich die Frage: Ist es egal, welche der beiden Methoden wir verwenden? Ist das Endergebnis gleich, egal in welcher Reihenfolge die einzelnen Verknüpfungen ausgerechnet werden?

Bei der Addition ist es egal, in welcher Reihenfolge die Verknüpfungen ausgerechnet werden. So ist   für alle reellen Zahlen  ,   und  . Verknüpfungen wie die Addition, bei der die Reihenfolge der Verknüpfungsausrechnung egal ist, nennt man assoziativ. Das Wort kommt vom lateinischen associare und bedeutet „vereinigen“ beziehungsweise „verbinden“.

Definition (Assoziativität)

Eine binäre Verknüpfung   heißt assoziativ, wenn für alle   gilt:  .

Beispiel (Beispiel und Gegenbeispiel für Assoziativität)

  • Die Addition   auf den reellen Zahlen ist assoziativ. Die Aussage, dass   für alle reellen Zahlen  ,   und   ist, nennt man auch Assoziativgesetz.
  • Die Subtraktion   auf den reellen Zahlen ist nicht assoziativ. So ist  , aber  . Es ist also  .

Weil bei einer assoziativen Verknüpfung die Reihenfolge egal ist, in der die einzelnen Verknüpfungen ausgewertet werden, können wir Klammern weglassen. Dies gilt für drei und auch für mehr Operanden. Du kannst dann also statt   oder   auch einfach   schreiben. Beachte, dass eine Schreibweise wie   ohne Klammern nur dann sinnvoll ist, wenn die Verknüpfung assoziativ ist. Bei nicht assoziativen Verknüpfungen musst du immer die Klammern setzen.

ÜbungsaufgabenBearbeiten

Kommutativität und AssoziativitätBearbeiten

Aufgabe

Welche der folgenden Verknüpfungen sind kommutativ und welche sind assoziativ?

  • Addition   auf  
  • Subtraktion   auf  
  • Multiplikation   auf  
  • Potenzbildung   auf   (x positiv, da sonst keine Verknüpfung)
  • Funktionskomposition
  • Durchschnitt auf der Potenzmenge einer Menge

Lösung

binäre Verknüpfung assoziativ kommutativ
Addition   auf   X X
Subtraktion   auf  
Multiplikation   auf   X X
Potenzbildung   auf  
Funktionskomposition X
Durchschnitt auf der Potenzmenge einer Menge X X

Eigenschaften von VerknüpfungenBearbeiten

Aufgabe (Einige Beispiele für Verknüpfungen)

Wir betrachten die folgenden drei Verknüpfungen:

  •   auf  
  •   auf  
  •   auf  

Entscheide, ob die folgenden Aussagen wahr oder falsch sind:

  1. Die Verknüpfung   ist auf   kommutativ.
  2. Die Verknüpfung   ist auf   assoziativ.
  3. Es gibt eine ganze Zahl  , sodass für alle   gilt:   und  .
  4. Zu jedem   gibt es ein  , sodass gilt:  .
  5. Die Verknüpfung   ist auf   kommutativ.
  6. Die Verknüpfung   ist auf   assoziativ.
  7. Es gibt eine reelle Zahl  , sodass für alle   gilt:   und  .
  8. Es gibt  ,  , und  , sodass gilt:  
  9. Die Verknüpfung   ist auf   kommutativ.
  10. Die Verknüpfung   ist auf   assoziativ.
  11. Es gibt eine natürliche Zahl  , sodass für alle   gilt:   und  .

Lösung (Einige Beispiele für Verknüpfungen)

  1. Wahr: Wir überprüfen, ob   für alle   gilt:
    • Linke Seite:  
    • Rechte Seite:  
    Weil die Verknüpfungen   und   auf   kommutativ sind, sind diese beiden Ergebnisse gleich. Also ist die Verknüpfung   auf   kommutativ.
  2. Wahr: Wir überprüfen, ob für alle   gilt:  . Die linke Seite ist:
     

    Und auf der rechten Seite erhalten wir:

     

    Da Addition und Multiplikation in   kommutativ sind, können wir die Reihenfolge der Terme vertauschen. Wir sehen dann schnell, dass linke und rechte Seite übereinstimmen. Daher ist die Verknüpfung   auf   kommutativ.

  3. Wahr: Wir überprüfen, ob es eine ganze Zahl   gibt, sodass für jede ganze Zahl   gilt:   und  . Erste Gleichung:
     

    Dies muss nun für alle   gelten. Also setzen wir 1 als Wert für   ein, denn die Gleichung muss insbesondere auch dann gelten. Damit erhält man die Gleichung:  . Also ist  . Bisher haben wir nur ein Element   gefunden, das die Gleichung   für   erfüllt. Deswegen prüfen wir jetzt, ob die Gleichung mit   für alle ganzen Zahlen   gilt. Wir setzen   in die Verknüpfung ein und erhalten die allgemeingültige Aussageform  . Damit haben wir gezeigt, dass die erste Gleichung für alle ganzen Zahlen   gilt.

    Zweite Gleichung:

     

    Wir gehen vor wie bei der ersten Gleichung: Da auch die zweite Gleichung für alle   gelten muss, muss insbesondere auch für   die folgende Gleichung richtig sein:  . Daraus folgt unmittelbar  . Umgekehrt erfüllt   auch die Gleichung   für beliebige Werte  .

  4. Falsch: Wir wollen herausfinden, ob es für jede ganze Zahl   eine ganze Zahl   gibt, sodass   und   ist. Betrachten wir zuerst die erste Gleichung:
     

    Achtung: Auf den ersten Blick sieht die letzte Zeile dieser Gleichungsumformung so aus, als ob wir für jede Zahl   auch eine Zahl   berechnen könnten, die   erfüllt. Aber die Zahl   muss auch eine ganze Zahl sein. Das ist zum Beispiel für   nicht der Fall, wie wir durch Einsetzen in   sehen: Hier ist  . Also haben wir ein Gegenbeispiel zu unserer Aussage gefunden, weil es zu   kein ganzzahliges   gibt, sodass   gilt.

  5. Wahr: Wir müssen überprüfen, ob   für alle   gilt:
    • Linke Seite:  
    • Rechte Seite:  
    Da die Addition in   kommutativ ist, stimmen rechte und linke Seite überein. Also ist die Verknüpfung   kommutativ.
  6. Falsch: Wir wollen überprüfen, ob die Verknüpfung assoziativ ist, also ob für alle   gilt:
     
    • Linke Seite:  
    • Rechte Seite:  

    Vergleichen wir diese Seiten, dann vermuten wir schnell, dass diese nicht übereinstimmen. Wir können konkrete Werte für   einsetzen und sehen

     

    Also ist die Verknüpfung   nicht assoziativ.

  7. Falsch: Wir müssen untersuchen, ob es eine reelle Zahl   gibt, sodass für alle   gilt:   und  . Die beiden Gleichungen sind äquivalent, da wir ja schon gesehen haben, dass die Verknüpfung kommutativ ist. Wir kümmern uns also nur um die Gleichung  . Willst du ein solches   finden oder seine Existenz widerlegen, gehst du immer gleich vor: Du nimmst die Gleichung und stellst sie um, damit du Dinge über   erfahren kannst. Da die Gleichung für alle   gelten muss, kannst du auch konkrete Werte für   einsetzen und so etwas über   erfahren. Probieren wir das einfach mal aus. Wir betrachten die Gleichung   und stellen sie um:
     

    Diese Gleichung soll also für alle   gelten. Du musst nur zwei verschiedene Werte von   einsetzen und schon siehst du, dass das unmöglich ist. Wie sollte denn gleichzeitig   (für  ) und   (für  ) gelten? Also existiert kein   mit der geforderten Eigenschaft.

  8. Wahr: Zunächst solltest du erkennen, dass diese Aussage zwar sehr ähnlich zur Assoziativität aussieht, aber der Allquantor durch einen Existenzquantor ersetzt wurde. Wir müssen also nur ein Beispiel von Zahlen   finden, das die altbekannte Eigenschaft   erfüllt. Als wir gezeigt haben, dass   nicht assoziativ ist, haben wir die die beiden obigen Terme ausgerechnet:
     

    Wie kannst du jetzt   und   wählen, damit die beiden rechten Seiten gleich sind? Du könntest zum Beispiel   wählen. Und schon hast du die Existenz der Zahlen bewiesen und bist fertig.

  9. Falsch: Wir wollen untersuchen, ob die Gleichung   für alle natürlichen Zahlen   und   erfüllt ist. Wie üblich setzen wir zunächst die Verknüpfungsvorschrift ein und erhalten:
    • Linke Seite:  
    • Rechte Seite  
    Sicherlich siehst du, dass beiden Seiten für die meisten Werte von   und   nicht übereinstimmen. Wir setzen zum Beispiel   und   und sehen:
     

    Also ist die Verknüofung   nicht kommutativ.

  10. Falsch: Wir müssen wieder das Assoziativgesetz   für beliebige   nachrechnen.
    • Linke Seite:  
    • Rechte Seite:  
    Auf der linken Seite kommt   höchstens quadratisch vor, wohingegen   auf der rechten Seite sogar in vierter Potenz vorkommt. Das ist ein ganz typisches Indiz dafür, dass die beiden Seiten im Allgemeinen nicht übereinstimmen können. Allerdings ist ein Indiz eben noch kein Beweis. Was wäre denn, wenn es irgendwelche anderen Terme gäbe, die diesen Unterschied in den Größenordnungen kompensieren könnten, die wir aber einfach nicht beachten würden? Um einen stichhaltigen Beweis für die Ungleichheit anzugeben, wollen wir Zahlen   wählen, bei denen man die verschiedenen Werte der beiden Seiten konkret sieht. Wir wollen natürlich möglichst einfache Werte einsetzen. Wir wählen dafür  . Dazu wählen wir  , damit der Unterschied zwischen   und   zum Tragen kommt. Jetzt vergleichen wir wieder die beiden Seiten:
    • Linke Seite:  
    • Rechte Seite:  
    Da die beiden Seiten sich unterscheiden, kann die Verknüpfung   nicht assoziativ sein.
  11. Falsch: Wir müssen wieder prüfen, ob eine natürliche Zahl   existiert, sodass   für alle   gilt. Wir betrachten zunächst nur die linke Gleichung und wollen einsehen, dass es kein   gibt, das diese Gleichung im Allgemeinen erfüllt. Wie immer stellen wir die Gleichung dafür um:
     

    Nun sollen wir also einen festen Wert   finden, der gleich   ist – und zwar für alle natürlichen Zahlen  . Wir müssen nur zwei verschiedene Werte   einsetzen und sehen schon, dass das nicht funktionieren kann. Du solltest dir auch bewusst sein, dass die Zahl   in jedem Fall eine natürliche Zahl sein müsste.

Hinweis

Das Element   in 3. nennen wir neutrales Element bezüglich   in  . Neutrale Elemente spielen eine wichtige Rolle in der Algebra. Genauso ist   in 7. das neutrale Element bezüglich   in  , in 11. bezüglich   in  .