In der Mathematik ist eine iterierte binäre Operation eine Erweiterung einer binären Operation auf einer Menge S zu einer Funktion auf endlichen Folgen von Elementen aus S durch wiederholte Anwendung. Häufige Beispiele sind die Erweiterung der Addition zur Summation sowie die Erweiterung der Multiplikation zum Produkt. Weitere Operationen, z. B. die mengentheoretischen Operationen Vereinigung und Schnitt, werden ebenfalls oft iteriert, aber die Iterationen haben keine eigenen Namen. In der Schreibweise werden Summation und Produkt durch spezielle Symbole dargestellt; andere iterierte Operatoren werden oft durch vergrößerte Varianten des Symbols der binären Operation notiert. Die Iterationen der vier genannten Operationen werden somit bezeichnet als: und .
Im Allgemeinen gibt es mehr als eine Möglichkeit, eine binäre Operation auf endliche Folgen zu erweitern, abhängig davon, ob die Operation assoziativ ist und ob ein neutrales Element existiert.
Definition
Sei aj,k, mit und , die endliche Folge der Länge von Elementen aus S, mit den Gliedern (ai) für . Falls , ist die Folge leer.
Für eine binäre Operation f : S × S → S definieren wir zwei Funktionen auf endlichen nichtleeren Folgen von Elementen aus S:
Ebenso:
Falls f ein eindeutiges linkes neutrales Element e besitzt, kann F_l auch auf leere Folgen erweitert werden, indem der Wert der leeren Folge als e definiert wird. Analog kann F_r erweitert werden, falls ein rechtes neutrales Element existiert.
Ist f assoziativ, dann gilt F_l = F_r, und man schreibt einfach F. Existiert ein neutrales Element e, so ist es eindeutig (siehe Monoid).
Ist f kommutativ und assoziativ, dann kann F auf endliche Multimengen angewendet werden, unabhängig von der Reihenfolge. Mit neutralem Element e ist dies auch für die leere Multimenge definiert. Ist f idempotent, lassen sich die Definitionen auf endliche Mengen erweitern.
Wenn S zusätzlich eine Metrik oder allgemein eine Topologie besitzt, in der Grenzwerte definiert sind, kann eine unendliche Iteration definiert werden, falls die Folge der endlichen Iterationen konvergiert. Beispielsweise ist für eine Folge reeller Zahlen das unendliche Produkt
definiert als , sofern dieser Grenzwert existiert.
Grundlegende iterierte Operationen +Iterierte Operationen Bereich der Mathematik Summe Produkt Name Operation Definition Symbol Name Operation Definition Symbol Arithmetik Summation Addition Summe von Zahlen Iteriertes Produkt Multiplikation Produkt von Zahlen Mengenlehre Vereinigung einer Folge von Mengen Vereinigung Alle Elemente der Mengen Schnitt einer Folge von Mengen Schnittmenge Gemeinsame Elemente Kategorientheorie Koprodukt Disjunkte Vereinigung Koprodukt von Objekten Produkt Kartesisches Produkt Produkt von Objekten
Notation Die iterierte binäre Operation wird geschrieben als:
Bedeutung der Symbole:
Symbol Bedeutung Symbol der iterierten binären Operation Indexvariable Untere Grenze Obere Grenze k-tes Element
Beispiel:
Allgemeine Form:
Eingeschränkte Form:
Unendliche Version:
Eigenschaften Sei eine Struktur mit assoziativer Operation :
Einzelnes Element:
Entwicklung:
Rekursion:
Rechtsrekursion:
Zerlegung:
Permutationsinvarianz:
Leeres Produkt (Monoid):
Idempotenz: falls , dann
Konstante Folge:
Neutrales Element und leere Menge Ist ein Monoid, dann gilt:
Leeres Produkt = neutrales Element Leere Summe = 0 (in arithmetischen Monoiden)
Referenzen
Weblinks Bulk action Parallel prefix operation Nuprl iterated binary operations Kategorie:Mathematik