Title: ADM26 / Relation, Funktionen Mengen

Q: Was ist eine Äquivalenzrelation?
A: Eine Relation \( R \subseteq M \times M \) heißt Äquivalenzrelation, wenn sie folgende drei Eigenschaften erfüllt:
- Reflexiv:
\[ \forall x \in M: \; (x, x) \in R \] Jedes Element steht in Relation zu sich selbst.
- Symmetrisch:
\[ \forall x, y \in M: \; (x, y) \in R \Rightarrow (y, x) \in R \] Wenn \( x \) mit \( y \) in Relation steht, dann auch \( y \) mit \( x \).
- Transitiv:
\[ \forall x, y, z \in M: \; (x, y) \in R \land (y, z) \in R \Rightarrow (x, z) \in R \] Wenn \( x \) mit \( y \) und \( y \) mit \( z \) in Relation steht, dann auch \( x \) mit \( z \).
Merksatz:
Eine Äquivalenzrelation ist eine "wohlgeordnete Gleichheit":
Reflexiv + Symmetrisch + Transitiv ⇒ „Gleichartigkeit“ innerhalb einer Menge.

Q: Was ist eine Äquivalenzklasse?
A: Zu einer Äquivalenzrelation \( R \) auf einer Menge \( M \) ist die Äquivalenzklasse eines Elements \( x \in M \):
\[[x]_R := \{ y \in M \mid (x, y) \in R \}\]
Eigenschaften:
- Alle Elemente in derselben Klasse sind zueinander äquivalent gemäß \( R \).
- Alle Äquivalenzklassen sind entweder gleich oder disjunkt.

Q: Was bedeutet: Zwei Elemente sind äquivalent?
A: Gegeben eine Äquivalenzrelation \( R \) auf einer Menge \( M \):
Zwei Elemente \( x, y \in M \) heißen äquivalent, wenn gilt:
\[(x, y) \in R\]
Dies bedeutet: \( x \) und \( y \) gehören zur gleichen Äquivalenzklasse.

Q: Was ist eine Partition einer Menge?
A: Eine Partition einer Menge \( M \) ist eine Familie \( \{A_i\}_{i \in I} \) von Teilmengen von \( M \) mit folgenden Eigenschaften:
- Jede Teilmenge \( A_i \) ist nichtleer
- Die Teilmengen sind paarweise disjunkt: \( A_i \cap A_j = \emptyset \) für \( i \ne j \)
- Ihre Vereinigung ist die ganze Menge: \( \bigcup_{i \in I} A_i = M \)
Zusammenhang:
Jede Äquivalenzrelation auf \( M \) definiert eine eindeutige Partition von \( M \) in Äquivalenzklassen.

Q: Was ist das Bild einer Menge (Bild der Funktion)?
A: Das Bild der Funktion (auch: Wertebereich) ist die Menge aller Funktionswerte:
\[\operatorname{Bild}(f) = \{ f(a) \;|\; a \in A \}\]
Beispiel:
Für \( f(x) = x^2 \) mit \( A = \mathbb{R} \) ist:
\[\operatorname{Bild}(f) = \{ y \in \mathbb{R} \;|\; y \geq 0 \}\]

Q: Merktabelle: Abbildung, Bild, Urbild
A: Begriff | Bedeutung
Abbildung / Funktion | Zuordnung \( A \to B \)
Bild eines Elements | \( f(a) \)
Bild der Funktion | Alle Funktionswerte \( \{ f(a) \} \)
Urbild | Alle \( a \), die auf \( b \) abgebildet werden

Q: Wie hängt das Urbild mit der Bijektivität zusammen?
A: Eine Abbildung \( f: A \to B \) ist bijektiv genau dann, wenn jedes \( b \in B \) genau ein Urbild besitzt:
\[\forall b \in B: \ |f^{-1}(b)| = 1\]
Bijektivität ist Äquivalenz von Injektivität und Surjektivität.

Q: Wie prüft man, ob zwei Funktionen Umkehrfunktionen voneinander sind?
A: Man überprüft, ob beide Kompositionen die Identität ergeben:
\[f^{-1}(f(x)) = x \quad \text{für alle } x \in A\]
\[f(f^{-1}(y)) = y \quad \text{für alle } y \in B\]

Q: Was ist die Kommutativität der Konjunktion und Disjunktion?
A: Für Konjunktion:
\[A \wedge B \equiv B \wedge A\]
Für Disjunktion:
\[A \vee B \equiv B \vee A\]

Q: Was ist die Kontraposition einer Implikation?
A: \[(A \rightarrow B) \equiv (\neg B \rightarrow \neg A)\]
Die Implikation ist logisch äquivalent zu ihrer Kontraposition.

Q: Was besagt die erste de Morgansche Regel (Negation der Konjunktion)?
A: \[\neg (A \wedge B) \equiv (\neg A) \vee (\neg B)\]
„Nicht (A und B)“ ist äquivalent zu „Nicht A oder Nicht B“.

Q: Wie funktioniert der Beweis durch Kontraposition?
A: Um \( A \rightarrow B \) zu beweisen, zeigt man stattdessen \( \neg B \rightarrow \neg A \).
Man nutzt dabei die Äquivalenz der Kontraposition.

Q: Definition: Vereinigung (Union)
A: \[A \cup B = \{ x \mid x \in A \vee x \in B \}\]
Erklärung:
Die Vereinigung enthält alle Elemente, die in mindestens einer der beiden Mengen enthalten sind.
Bezug zu ADM:
Entspricht der logischen Disjunktion (\( \vee \)) in der Aussagenlogik.
Wichtig in der Kombinatorik bei Fallunterscheidungen.

Q: Definition: Durchschnitt (Schnittmenge / Intersection)
A: \[A \cap B = \{ x \mid x \in A \wedge x \in B \}\]
Erklärung:
Die Schnittmenge enthält alle Elemente, die in beiden Mengen gleichzeitig enthalten sind.
Bezug zu ADM:
Entspricht der logischen Konjunktion (\( \wedge \)) in der Aussagenlogik.
Wichtig bei Berechnungen von Wahrscheinlichkeiten.

Q: Definition: Mengendifferenz (relative Differenz)
A: \[A \setminus B = \{ x \mid x \in A \wedge x \notin B \}\]
Erklärung:
Die Differenz enthält alle Elemente, die in \( A \), aber nicht in \( B \) sind.
Bezug zu ADM:
Wichtig für Komplementbildung und bei Beweisen von Mengengleichungen.

Q: Definition: Komplement
A: Voraussetzung: Universum \( U \)
\[\overline{A} = U \setminus A\]
Erklärung:
Das Komplement enthält alle Elemente, die nicht in \( A \) enthalten sind.
Bezug zu ADM:
Entspricht der logischen Negation.
Wichtig in der Wahrscheinlichkeitstheorie (Gegenereignisse).

Q: Definition: Symmetrische Differenz
A: \[A \triangle B = (A \setminus B) \cup (B \setminus A)\]
Erklärung:
Enthält alle Elemente, die in genau einer der beiden Mengen enthalten sind (exklusives Oder).
Bezug zu ADM:
Entspricht dem exklusiven Oder (XOR) in der Aussagenlogik.
Wichtig auch in der algebraischen Struktur der booleschen Algebren.

Q: Was ist eine Halbordnung?
A: Eine Relation \( \preceq \) auf einer Menge \( M \) heißt Halbordnung, wenn sie folgende drei Eigenschaften erfüllt:
- Reflexivität:
\[ \forall a \in M: \quad a \preceq a \]
- Transitivität:
\[ \forall a, b, c \in M: \quad (a \preceq b \land b \preceq c) \implies a \preceq c \]
- Antisymmetrie:
\[ \forall a, b \in M: \quad (a \preceq b \land b \preceq a) \implies a = b \]

Q: Gib ein Beispiel für eine Halbordnung!
A: Beispiel: \( (\mathcal{P}(\{1,2\}), \subseteq) \)
Menge:
\[\mathcal{P}(\{1,2\}) = \{ \emptyset, \{1\}, \{2\}, \{1,2\} \}\]
Relation: \( A \subseteq B \)
✅ Reflexiv, transitiv, antisymmetrisch → Halbordnung.

Q: Was ist eine Totalordnung?
A: Eine Totalordnung ist eine Halbordnung, bei der zusätzlich die Totalität (Vergleichbarkeit) gilt:
\[\forall a, b \in M: \quad a \preceq b \quad \text{oder} \quad b \preceq a\]
Merkhilfe: Jedes Element ist mit jedem anderen vergleichbar.

Q: Gib ein Beispiel für eine Totalordnung!
A: Beispiel: \( (\mathbb{N}, \leq) \)
Menge: \( \{1, 2, 3\} \), Relation \( \leq \)
✅ Reflexiv, transitiv, antisymmetrisch und total → Totalordnung.

Q: Was ist die Potenzmenge einer Menge?
A: Die Potenzmenge \( \mathcal{P}(M) \) ist die Menge aller Teilmengen von \( M \):
\[\mathcal{P}(M) = \{ A \,|\, A \subseteq M \}\]
Wichtig: \( |\mathcal{P}(M)| = 2^{|M|} \).

Q: Gib ein Beispiel für eine Potenzmenge!
A: Sei \( M = \{1,2\} \), dann:
\[\mathcal{P}(\{1,2\}) = \{ \emptyset, \{1\}, \{2\}, \{1,2\} \}\]
Anzahl der Elemente: \( 2^2 = 4 \).
Formel: \( 2^n = |P(n)| \).

Q: Was ist eine Kette in einer Halbordnung?
A: Eine Kette ist eine Teilmenge \( K \) einer Halbordnung, in der alle Elemente miteinander vergleichbar sind:
\[\forall a, b \in K: \quad a \preceq b \quad \text{oder} \quad b \preceq a\]

Q: Gib ein Beispiel für eine Kette!
A: Beispiel in \( (\mathcal{P}(\{1,2\}), \subseteq) \):
Die Menge \( \{\emptyset, \{1\}, \{1,2\}\} \) ist eine Kette, da:
\[\emptyset \subseteq \{1\} \subseteq \{1,2\}\]

Q: Was besagt das Hausdorffsche Maximialitätsprinzip?
A: In jeder Halbordnung, in der jede Kette eine obere Schranke besitzt, existiert ein maximales Element.
Kurzform:
Jede ketten-vollständige Halbordnung enthält ein maximales Element.

Q: Was ist ein maximales Element?
A: Ein Element \( m \in M \) ist maximal, wenn gilt:
\[\forall x \in M: \quad m \preceq x \implies m = x\]
Intuition: Es gibt kein größeres Element bezüglich der Ordnung.

Q: Was ist eine Funktion (Abbildung) im strengen ADM-Sinn?
A: Wann ist eine Relation total definiert (ADM-Terminologie)?
Eine Relation \( f \subseteq A \times B \) ist total definiert, wenn:
\[\forall a \in A \; \exists b \in B : (a, b) \in f\]
Intuition: Zu jedem Element \( a \in A \) existiert mindestens ein zugeordnetes \( b \in B \).
Merksatz: „Kein \( a \in A \) bleibt ohne Bild.“

Q: Summenregel (Additionsprinzip):
A: Voraussetzungen:
Seien \( A_1, A_2, \dotsc, A_k \) paarweise disjunkte endliche Mengen:
\[A_i \cap A_j = \emptyset \quad \text{für alle } i \neq j.\]
Aussage:
\[\left| \bigcup_{i=1}^{k} A_i \right| = \sum_{i=1}^{k} |A_i|.\]
Bemerkung:
Die Disjunktheit ist Voraussetzung für die direkte Anwendbarkeit der Summenregel.

Q: Was ist eine Relation zwischen zwei Mengen \(A\) und \(B\)?
A: Seien \(A,B\) Mengen.
Eine Relation \(R\) zwischen \(A\) und \(B\) ist eine Teilmenge des kartesischen Produkts: \[R \subseteq A \times B\]
Schreibweise: \[(a,b) \in R \quad \text{oder} \quad a\,R\,b\]
Intuitive Erklärung:
Eine Relation legt fest, welche Paare erlaubt sind.
Zu einem \(a \in A\) können kein, ein oder mehrere \(b \in B\) gehören.

Q: Was ist eine Funktion (Abbildung) \(f : A \to B\)?
A: Antwort:
Eine Funktion \(f : A \to B\) ist eine Relation mit der Eigenschaft: \[\forall a \in A \; \exists! \, b \in B : (a,b) \in f\] (das Ausrufezeichen bedeutet „genau ein“)
Intuitive Erklärung:
Jedem Element aus \(A\) wird genau ein Element aus \(B\) zugeordnet.
Typischer Prüfungsfehler:
„Jedem \(a\) wird ein \(b\) zugeordnet“ → unvollständig, da die Eindeutigkeit fehlt.
Aufbauend auf:
Relationen, Quantorenlogik.

Q: Wann ist eine Abbildung \(f : A \to B\) injektiv?
A: \(f\) heißt injektiv, genau dann wenn: \[\forall a_1,a_2 \in A : f(a_1) = f(a_2) \Rightarrow a_1 = a_2\]
Äquivalent: \[a_1 \neq a_2 \Rightarrow f(a_1) \neq f(a_2)\]
Intuitive Erklärung:
Verschiedene Elemente im Definitionsbereich haben verschiedene Bilder.
Aufbauend auf:
Implikationen, Funktionen, Mengenabbildungen.

Q: Wann ist eine Abbildung \(f : A \to B\) surjektiv?
A: Antwort:
\(f\) heißt surjektiv, genau dann wenn: \[\forall b \in B \; \exists a \in A : f(a) = b\]
Intuitive Erklärung:
Jedes Element des Zielbereichs wird mindestens einmal getroffen.
Typischer Prüfungsfehler:
„Für jedes \(a\) gibt es ein \(b\)“ → das gilt für jede Funktion und ist keine Surjektivität.

Q: Was ist das kartesische Produkt zweier Mengen \(A\) und \(B\)?
A: Seien \(A,B\) Mengen.
Das kartesische Produkt von \(A\) und \(B\) ist definiert als: \[A \times B := \{ (a,b) \mid a \in A \land b \in B \}\]
Intuitive Erklärung:
Das kartesische Produkt enthält alle geordneten Paare, deren erstes Element aus \(A\) und deren zweites Element aus \(B\) stammt.
Die Reihenfolge ist dabei wesentlich: \((a,b) \neq (b,a)\) im Allgemeinen.
Wichtiger Hinweis (prüfungsrelevant):
Ein Element von \(A \times B\) ist immer ein Paar, kein einzelnes Element.

Q: Was bedeutet „erfüllbar“ und „gültig“ für aussagenlogische Formeln?
A: Antwort:
Eine Formel ist:
- erfüllbar, wenn es mindestens eine Belegung gibt, die sie wahr macht
- gültig, wenn sie für alle Belegungen wahr ist
Wichtig:
„erfüllbar, aber nicht gültig“ ⇔ wahr für manche, falsch für andere Belegungen.
Benötigt für:
MC-Fragen zu logischen Formeln.

Q: Wie lauten die De-Morgan-Regeln für Mengen?
A: Antwort:
Für Teilmengen \(A,B \subseteq E\) gilt: \[(A \cap B)' = A' \cup B'\] \[(A \cup B)' = A' \cap B'\]
Intuition:
„Nicht (A und B)“ entspricht „nicht A oder nicht B“.

Q: Was ist eine komplexe Zahl?
A: Antwort:
Die Menge der komplexen Zahlen ist definiert als \[\mathbb{C} = \{ z = a + ib \mid a,b \in \mathbb{R} \}.\] Dabei heißt:
- \(a = \Re(z)\) der Realteil,
- \(b = \Im(z)\) der Imaginärteil,
- \(i\) die imaginäre Einheit mit \(i^2 = -1\).

Q: Wie werden komplexe Zahlen geometrisch dargestellt?
A: Antwort:
Komplexe Zahlen werden in der Gaußschen Zahlenebene dargestellt:
- x-Achse: Realteil \(a = \Re(z)\)
- y-Achse: Imaginärteil \(b = \Im(z)\)
  Die komplexe Zahl \(z = a + ib\) entspricht dem Punkt \((a,b)\) bzw. einem Zeiger vom Ursprung.

Q: Was ist der Betrag einer komplexen Zahl?
A: Antwort:
Für \(z = a + ib\) ist der Betrag definiert als \[|z| = \sqrt{a^2 + b^2}.\] Geometrisch ist \(|z|\) die Länge des Zeigers von \(0\) nach \(z\) in der Gaußschen Ebene.

Q: Was ist das Argument einer komplexen Zahl?
A: Antwort:
Das Argument \(\varphi = \arg(z)\) ist der Winkel zwischen dem Zeiger von \(z\) und der positiven reellen Achse. Zusammen mit dem Betrag ergibt sich die Polardarstellung: \[z = [r,\varphi]\] Dabei gilt: \[a = r \cos \varphi, \quad b = r \sin \varphi.\] Das Argument ist nur modulo \(2\pi\) eindeutig bestimmt.

Q: Wie hängen kartesische und Polarkoordinaten zusammen?
A: Antwort:
Für \(z = a + ib = [r,\varphi]\) gilt: \[r^2 = a^2 + b^2, \quad \tan \varphi = \frac{b}{a}.\] Dabei ist \(\varphi\) abhängig vom Quadranten von \(z\) korrekt zu wählen.

Q: Wie löst man eine quadratische Gleichung über den komplexen Zahlen?
A: Antwort:
Für \[z^2 + pz + q = 0 \quad (p,q \in \mathbb{C})\] gilt: \[z_{1,2} = -\frac{p}{2} \pm \sqrt{\frac{p^2}{4} - q}.\] Über \(\mathbb{C}\) besitzt jede quadratische Gleichung immer zwei (evtl. gleiche) Lösungen.

Q: Wie berechnet man die n-ten Wurzeln einer komplexen Zahl?
A: Antwort:
Ist \(z = [R,\psi]\), dann sind die n-ten Wurzeln: \[w_j = \left[\sqrt[n]{R}, \frac{\psi + 2\pi j}{n}\right], \quad j = 0,1,\dots,n-1.\] Es gibt genau \(n\) verschiedene n-te Wurzeln.