Aufgabensammlung Mathematik: Maximale Anzahl binärer Relationen auf einer Menge

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Maximale Anzahl binärer Relationen auf einer Menge

Wie viele binäre Relationen sind auf einer m-elementigen Grundmenge definierbar?

Lösung

Schritt 1: Die Anzahl aller möglichen binären Relationen ist die Kardinalität von

Eine Relation auf einer Grundmenge ist nach Definition eine Teilmenge des kartesischen Produkts . Da jede Teilmenge von eine mögliche binäre Relation ist, musst du hier die Anzahl der möglichen Teilmengen von bestimmen, also die Kardinalität (Mächtigkeit) der Potenzmenge zu bestimmen.

Schritt 2: Bestimmung der Kardinalität von

Es ist

Da ist, folgt

.

Es gibt also mögliche binäre Relationen.