Lineare Algebra I
zum Anfassen.

Eine Aussage ist ein Satz, dem man sinnvoll und objektiv einen Wahrheitswert zuordnen kann: wahr (w) oder falsch (f). \(1 + 1 = 2\) ist eine wahre, \(1 + 1 = 3\) eine falsche Aussage. Keine Aussagen sind dagegen Aufforderungen, Terme wie \(x^3 - 3x^2 - 3x + 1\) oder vage Sätze wie „\(10^{100}\) ist eine große Zahl“.

Ein Satz wie \(a^2 + b^2 = c^2\) ist ein Aussagenschema: Er wird erst zur Aussage, wenn man die Parameter \(a, b, c\) belegt. Daraus folgt die wichtigste Schreibregel überhaupt: Keine Bezeichnung benutzen, die vorher nicht festgelegt wurde.

Aussagen werden mit \(\neg\) (nicht), \(\wedge\) (und), \(\vee\) (oder), \(\Rightarrow\) (daraus folgt) und \(\Leftrightarrow\) (genau dann, wenn) verknüpft. Der Wahrheitswert des Ganzen hängt nur von den Wahrheitswerten der Teile ab – und genau das hält eine Wahrheitstafel fest.

Nach Cantor ist eine Menge eine Zusammenfassung wohlunterschiedener Objekte – ihrer Elemente. Zwei Mengen sind genau dann gleich, wenn sie dieselben Elemente haben; Reihenfolge und Wiederholung spielen keine Rolle. \(x \in M\) heißt „\(x\) ist Element von \(M\)“, \(M \subseteq N\) heißt „jedes Element von \(M\) liegt auch in \(N\)“.

Mengen beschreibt man durch Aufzählen, \(\{1, 2, \dots, 7\}\), oder durch eine definierende Bedingung: \(\{c \in M \mid \phi(c)\}\) enthält genau die \(c \in M\), für die \(\phi(c)\) wahr ist. So übersetzen sich die Mengenoperationen direkt in Logik:

\(x \in A \cap B \Leftrightarrow x \in A \wedge x \in B\)  ·  \(x \in A \cup B \Leftrightarrow x \in A \vee x \in B\)  ·  \(x \in A \setminus B \Leftrightarrow x \in A \wedge x \notin B\)

Dazu kommen das kartesische Produkt \(A \times B = \{(a, b) \mid a \in A \wedge b \in B\}\) und die Potenzmenge \(\mathcal{P}(A) = \{B \mid B \subseteq A\}\).

Ist \(\phi(x)\) ein Aussagenschema, entstehen mit den Quantoren zwei Aussagen: \(\forall x \in M : \phi(x)\) heißt, \(\phi(c)\) ist für jedes \(c \in M\) wahr, also \(\{c \in M \mid \phi(c)\} = M\). \(\exists x \in M : \phi(x)\) heißt, \(\phi(c)\) ist für mindestens ein \(c \in M\) wahr, also \(\{c \in M \mid \phi(c)\} \neq \emptyset\).

Daraus ergeben sich die Beweisstrategien: Für „\(\forall\)“ beginnt man mit „Sei \(c \in M\).“ und benutzt danach nur, dass \(c\) in \(M\) liegt. Für „\(\exists\)“ genügt ein einziger, konkret angegebener Zeuge. Beim Verneinen tauschen die Quantoren die Rollen: \(\neg \forall x \in M : \phi(x) \Leftrightarrow \exists x \in M : \neg \phi(x)\) und \(\neg \exists x \in M : \phi(x) \Leftrightarrow \forall x \in M : \neg \phi(x)\).

Eine Relation auf \(X\) ist eine Teilmenge \(R \subseteq X \times X\); statt \((x, y) \in R\) schreibt man \(xRy\). Bei endlichem \(X\) passt sie in eine Tabelle: ein Kreuz an der Stelle \((x, y)\), wenn \(xRy\) gilt. Entscheidend sind vier Eigenschaften:

• reflexiv: \(xRx\) für alle \(x\) – die ganze Diagonale ist angekreuzt.
• symmetrisch: \(xRy \Rightarrow yRx\) – die Tabelle ist spiegelbildlich zur Diagonale.
• anti-symmetrisch: \(xRy \wedge yRx \Rightarrow x = y\) – außerhalb der Diagonale nie beide Kreuze.
• transitiv: \(xRy \wedge yRz \Rightarrow xRz\).

Reflexiv, anti-symmetrisch und transitiv ergibt eine Halbordnung; sind zusätzlich je zwei Elemente vergleichbar, eine Totalordnung. Reflexiv, symmetrisch und transitiv ergibt eine Äquivalenzrelation.

Ist \(\sim\) eine Äquivalenzrelation, so heißt \([x]_\sim = \{y \in X \mid x \sim y\}\) die Äquivalenzklasse von \(x\). Zwei Klassen sind entweder gleich oder disjunkt, und jedes Element liegt in seiner eigenen Klasse – die Klassen bilden also eine Zerlegung von \(X\). Umgekehrt liefert jede Zerlegung eine Äquivalenzrelation: „liegen in derselben Teilmenge“.

Das wichtigste Beispiel ist die Kongruenz modulo \(n\): \(a \equiv_n b \Leftrightarrow n \mid (a - b)\). Ihre Klassen sind die Restklassen \(a + n\mathbb{Z}\), und \(\mathbb{Z}/n\mathbb{Z} = \{\bar 0, \bar 1, \dots, \overline{n-1}\}\) hat genau \(n\) Elemente.

Eine Abbildung \(f\colon X \to Y\) ist eine Relation zwischen \(X\) und \(Y\), bei der zu jedem \(x \in X\) genau ein \(y\) mit \((x, y) \in f\) existiert – dieses \(y\) heißt \(f(x)\). \(f\) heißt injektiv, wenn aus \(f(x_1) = f(x_2)\) stets \(x_1 = x_2\) folgt; surjektiv, wenn jedes \(y \in Y\) getroffen wird; bijektiv, wenn beides gilt.

Genau die bijektiven Abbildungen haben eine Umkehrabbildung \(f^{-1}\) mit \(f^{-1} \circ f = \mathrm{id}_X\) und \(f \circ f^{-1} = \mathrm{id}_Y\) (Satz 4.8). Bild und Urbild von Teilmengen gibt es dagegen immer: \(f(U) = \{f(x) \mid x \in U\}\) und \(f^{-1}(V) = \{x \in X \mid f(x) \in V\}\).

Eine Menge \(A\) hat \(n\) Elemente, wenn es eine Bijektion \(\{1, \dots, n\} \to A\) gibt. Für endliche Mengen gilt

\(|A \cup B| = |A| + |B| - |A \cap B|\)  ·  \(|A \times B| = |A| \cdot |B|\)  ·  \(|\mathcal{P}(A)| = 2^{|A|}\)  ·  \(\binom{n}{k} = \frac{n!}{k!\,(n-k)!}\)

Für unendliche Mengen heißen \(A\) und \(B\) gleichmächtig, wenn es eine Bijektion \(A \to B\) gibt. \(A\) ist abzählbar unendlich, wenn \(A\) gleichmächtig zu \(\mathbb{N}\) ist, und überabzählbar, wenn \(A\) nicht einmal höchstens abzählbar ist. Überraschend: \(\mathbb{N} \times \mathbb{N}\) ist abzählbar – man zählt diagonal –, und abzählbare Vereinigungen abzählbarer Mengen bleiben abzählbar.