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

Maximale Anzahl binärer Relationen auf einer Menge

Wie viele binäre Relationen sind auf einer m-elementigen Grundmenge $(m\in \mathbb {N} _{\geq 1})$ definierbar?

Lösung

Schritt 1: Die Anzahl aller möglichen binären Relationen ist die Kardinalität von ${\mathcal {P}}(M\times M)$

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

Schritt 2: Bestimmung der Kardinalität von ${\mathcal {P}}(M\times M)$

Es ist

$\left|M\times M\right|=\left|M\right|\cdot \left|M\right|=m\cdot m=m^{2}$

Da $\left|P(A)\right|=2^{|A|}$ ist, folgt

$\left|P(M\times M)\right|=2^{\left|M\times M\right|}=2^{m^{2}}$.

Es gibt also $2^{m^{2}}$ mögliche binäre Relationen.