Wie viele Relationen existieren auf M?

Question

Aufgabe:

Census I
Sei \( M \) eine endliche Menge mit \( n \) Elementen. Wie viele Relationen existieren auf \( M ? \) Wie viele dieser Relationen sind symmetrisch, wie viele reflexiv? Wie viele Äquivalenzrelationen existieren auf \( M \) für \( n \leqslant 4 \) ?

Answer 1

Wie viele Relationen existieren auf \( M ? \)

Wie viele Teilmengen hat \(M\times M\)?

Wie viele dieser Relationen sind symmetrisch, wie viele reflexiv?

Die Adjazenzmatrix einer Relation \(R\) gibt zu jedem \((a,b)\in M\times M\) an, ob \((a,b)\in R\) ist (Eintrag in der Matrix ist \(1\)) oder ob \((a,b)\notin R\) ist (Eintrag in der Matrix ist \(0\)).

Beispiel. \(M = \{1,2,3\}\), \(R = \{(0,0), (3,0), (2,3)\}\). Die Adjazenzmatrix von \(R\) ist dann

        \( \begin{pmatrix}1&0&0\\0&0&1\\1&0&0\end{pmatrix}\).

Überlege dir, wie die Adjazenzmatrix aussehen muss, damit die Relation symmetrisch ist. Zähle wieviele solche Adjazenzmatrizen es gibt.

Überlege dir, wie die Adjazenzmatrix aussehen muss, damit die Relation reflexiv ist. Zähle wieviele solche Adjazenzmatrizen es gibt.