03 Relationen

→ siehe auch

• 01 Mengen
• 04 Spezielle Relationen
• 06 Hasse Diagramme
• Wichtige Eigenschaften

Allgemein

• Eine Relation ρ zwischen zwei Mengen A und B ist eine Teilmenge von A×B:
  $\rho \subseteq A\times B$
• $a\rho b$ bedeutet $(a,b)\in \rho$.
• ${\rho }^{\ast }\stackrel{\mathrm{def}}{=}\cup P_{\rho }\text{mit}{P}_{\rho }=\{\rho ,{\rho }^2,{\rho }^3,\dots \}$
• 04 Spezielle Relationen

---

Identitätsrelation

• $i{d}_A=\{(a,a)\mid a\in A\}$
• Bedeutung: Jedes Element steht nur zu sich selbst in Relation.
• Beispiel: $i{d}_{\mathbb{Z}}=\{(0,0),(1,1),(2,2),...\}$
• Enthalten in jeder reflexiven Relation:
  $i{d}_A\subseteq \rho$

---

Inverse

• Definition:
  $\hat{\rho }=\{(b,a)\mid (a,b)\in \rho \}$
• Die Richtung der Paare wird vertauscht.
• $a\rho b⟺b\hat{\rho }a$
• Bspw. von „ist Elternteil von“ zu „ist Kind von“
• $\hat{\le }=\ge$

---

Komposition von Relationen

• Definition: $\rho \circ \sigma =\{(a,c)\mid \exists b((a,b)\in \rho \wedge (b,c)\in \sigma )\}$
• Bedeutung: Verbindung zweier Relationen über ein Zwischenelement b.
• Achtung, Kreis hat verkehrte Bedeutung als z.B. bei Funktionen. Achtung LLM’s machen das oft umgekehrt, also aufpassen
• Bspw.
  • $\rho$: „ist Elternteil von“
    $\sigma$: „ist Elternteil von“
    → $\rho \circ \sigma$: „ist Großelternteil von“
  • Wenn $a\le b$ und $b\le c$, dann $a\le c$
    → $\le \circ \le =\le$

Info

Kompositionen von Relationen sind assoziativ und nicht kommutativ

---

Wichtige Eigenschaften

Eigenschaft	Formel	Bedeutung	Beispiel
reflexiv	$id\subseteq \rho$	Jedes a steht zu sich selbst	$a\le a$
irreflexiv	$id\cap \rho =\varnothing$	Kein a steht zu sich selbst (z.B. <)
symmetrisch	$\rho =\hat{\rho }$	Wenn a ρ b, dann b ρ a	”verheiratet mit”
antisymmetrisch	$\rho \cap \hat{\rho }\subseteq id$	Beide Richtungen nur, wenn gleich	$a\le b$ und $b\le a\Rightarrow a=b$
transitiv	$\rho \circ \rho \subseteq \rho$	Wenn a ρ b und b ρ c, dann a ρ c (z.B. <, $\le$)	$a\le b\text{und}b\le c\Rightarrow a\le c$

Kann symmetrisch und antisymmetrisch gleichzeitig sein, z.B. = in $\mathbb{Z}$

→ siehe auch 06 Hasse Diagramme, inkl. Transitive Closure

---

Kongruenz modulo m

$3{\equiv }_{7}10$, weil $\frac{10}{7}$ hat gleich viel Rest wie $\frac{3}{7}$

---

---