# Algebra und Zahlentheorie 1: Blatt 1

## Aufgabe 1

Überprüfen Sie für die folgenden Gleichungen,
ob sie für beliebige Mengen A, B, C richtig oder falsch sind.

a) $A \cap (B \backslash C) = (A \cap B) \backslash C$

Die Gleichung ist richtig.
Beweis:
Sei $x \in A \cap (B \backslash C)$. Dann gilt $x \in A$ und $x \in B \backslash C$. Dies ist äquivalent zu $x \in A$ und $x \in B$ und $x \notin C$ $\Leftrightarrow x \in A \cap B$ und $x \notin C$ $\Leftrightarrow x \in (A \cap B) \backslash C$.

b) $(A \cup B) \backslash B = (A \backslash B) \cup B$

Die Gleichung ist falsch.
Gegenbeispiel: Sei $A = \{0, 1, 2\}$ und $B = \{2, 3\}$, also $A \cup B = \{0, 1, 2, 3\}$ sowie $A \backslash B = \{0, 1\}$. Wir erhalten $(A \cup B) \backslash B = \{0, 1\} \neq \{0, 1, 2, 3\} = (A \backslash B) \cup B$.

c) $A \backslash (A \backslash B) = A \cap B$

Die Gleichung ist richtig.
Beweis:
Sei $x \in A \backslash (A \backslash B)$. Dann gilt $x \in A$ und $x \notin A \backslash B$, was äquivalent ist zu $x \in A$ und $x \in \lnot(A \backslash B)$ $\Leftrightarrow x \in A \land \lnot(x \in A \land x \notin B) \Leftrightarrow x \in A \land (x \notin A \lor x \in B)$ $\Leftrightarrow x \in A \land x \in B \Leftrightarrow x \in A \cap B$.

Hierbei bezeichne
$A \backslash B := \{x \in A | x \notin B\} = A \cap B^C$
die Differenzmenge.

## Aufgabe 2

Beweisen Sie, dass die Beziehungen
$\mathcal{P}(A) \cap \mathcal{P}(B) \subseteq \mathcal{P}(A ∩ B)$
und
$\mathcal{P}(A) \cup \mathcal{P}(B) \subseteq \mathcal{P}(A \cup B)$
für beliebige Mengen $A$ und $B$ gelten.
Gilt jeweils sogar die Gleichheit?

Es bezeichne $X$ eine Menge.

Für die erste Aussage gilt Gleichheit, also $\mathcal{P}(A) \cap \mathcal{P}(B) = \mathcal{P}(A \cap B)$.
Beiweis:
$"\subseteq"$: Sei $X\in \mathcal{P}(A) \cap \mathcal{P}(B)$. Dann gilt $X\in \mathcal{P}(A)$ und $X\in \mathcal{P}(B)$, also $X \subseteq A$ und $X \subseteq B$. Es folgt $X \subseteq A \cap B$, also $X \in \mathcal{P}(A \cap B)$.

$"\supseteq"$: Sei $X \in \mathcal{P}(A \cap B)$. Dann gilt $X \subseteq A \cap B$, also $X \subseteq A$ und $X \subseteq B$. Folglich $X \in \mathcal{P}(A)$ und $X \in \mathcal{P}(B)$, was $X \in \mathcal{P}(A) \cap \mathcal{P}(B)$ impliziert.

Für die zweite Aussage gilt nur die gegebene Inklusion.
Beweis:
$"\subseteq"$: Sei $X \in \mathcal{P}(A) \cup \mathcal{P}(B)$. Dann gilt $X \in \mathcal{P}(A)$ oder $X \in \mathcal{P}(B)$, also $X \subseteq A$ oder $X \subseteq B$, woraus $X \subseteq A \cup B$ und damit $X \in \mathcal{P}(A \cup B)$ folgt.

Die Inklusion $"\supseteq"$ gilt i. A. nicht. Sei z. B. $A = \{0, 1\}$ und $B = \{2, 3\}$, also
$A \cup B = \{0, 1, 2, 3\}$. Dann gilt $X = \{1, 2\} \in \mathcal{P}(A \cup B)$, aber $X \notin \mathcal{P}(A)$ sowie $X \notin \mathcal{P}(B)$ und somit $X \notin \mathcal{P}(A) \cup \mathcal{P}(B)$.

## Aufgabe 3

Welche Eigenschaften einer Äquivalenzrelation sind jeweils erfüllt?
Geben Sie gegebenenfalls die Äquivalenzklassen an.

a) $X = \mathbb{R}, x R y :⇔ |x − y| < 1$

Die Relation ist

- reflexiv: $xRx \Leftrightarrow |x-x|=0<1$
- symmetrisch: $xRy \Leftrightarrow |x-y| < 1, yRx \Leftrightarrow |y-x| <1$,
allerdings $|x-y|=|y-x| \Rightarrow xRy \Leftrightarrow yRx$
- nicht transitiv: Gegenbeispiel: $x = 3, y = 2,5, z = 2$.
Es gilt $xRy, yRz$, also $|3-2,5| < 1, |2,5-2| <1$.
Allerdings $|x-z|=|3-2| = 1 \nless 1$, damit nicht $xRz$.

b) $X = \mathbb{N}×\mathbb{N}, (a, b) R (c, d) :⇔ a + d = b + c$

Die Relation ist

- reflexiv: $(a,b) R (a,b) \Leftrightarrow a+b = a+b$
- symmetrisch: $(a,b) R (c,d) \Leftrightarrow a+d = b+c
\Leftrightarrow b+c = a+d \Leftrightarrow (c,d)R(a,b)$
- transitiv: Es gelte $(a,b) R (c,d) \Leftrightarrow a+b = c+d$
und $(c,d) R (e,f) \Leftrightarrow c+f = e+d$.
Dann gilt $a+b = c+d \Leftrightarrow a-b = c-d$
und $c+f = e+d \Leftrightarrow c-d = e-f$.
$\Rightarrow a-b = e-f \Leftrightarrow a+f = b+e \Leftrightarrow (a,b)R(e,f)$

Die Relation ist somit eine Äquivalenzrelation mit Äquivalenzklassen
$[(a,b)]_R:=\{(c,d)\in \mathbb{N}×\mathbb{N}|a+d = b+c\}$.

c) $X = \mathcal{P}({1, . . . , n}), A R B :⇔ \#A = \#B$

Die Relation ist

- reflexiv: $A R A \Leftrightarrow \#A = \#A$
- symmetrisch: $A R B \Leftrightarrow \#A = \#B = \#A \Leftrightarrow B R A$
- transitiv: Es gelte $A R B, B R C \Rightarrow \#A = \#B \land \#B = \#C
\Rightarrow \#A = \#B = \#C \Leftrightarrow A R C$

Die Relation ist somit eine Äquivalenzrelation mit Äquivalenzklassen
$[A]_R:=\{B \in \mathcal{P}({1, . . . , n})|\#A = \#B\}$.

Geweth Christina, 103194
Jamine Stenzel, 80925