Aufgabe 1
=========

a)
---

### Gegeben

$$
\overline{(A \cap \overline{B})}
$$

### Satz

$$
\overline{(A \cap \overline{B})} = \overline{A} \cup B
$$

### Beweis

$$
\begin{aligned}
& \quad \overline{A \cap \overline{B}} & \quad \text{|} & \quad \textit{DeMorgan} \\
= & \quad \overline{A} \cup B & \quad \square
\end{aligned}
$$

b)
---

### Gegeben

$$
\overline{\overline{(A \cap B) \cup C} \cap \overline{B}}
$$

### Satz

$$
\overline{\overline{(A \cap B) \cup C} \cap \overline{B}} = C \cup B
$$

### Beweis

$$
\begin{aligned}
& \quad \overline{\overline{(A \cap B) \cup C} \cap \overline{B}} & \quad \text{|} & \quad \textit{DeMorgan}\\
= & \quad ((A \cap B) \cup C) \cup B & \quad \text{|} & \quad \textit{Associative}\\
= & \quad (A \cap B) \cup C \cup B & \quad \text{|} & \quad \textit{Commutative + Associative}\\
= & \quad C \cup ((A \cap B) \cup B) & \quad \text{|} & \quad \textit{Absorption}\\
= & \quad C \cup B & \quad \square
\end{aligned}
$$

c)
---

### Gegeben

$$
\overline{A} \cup \overline{B} \cup (A \cap B \cap \overline{C})
$$

### Satz

$$
\overline{A} \cup \overline{B} \cup (A \cap B \cap \overline{C}) = \overline{A} \cup \overline{B} \cup \overline{C}
$$

### Beweis

$$
\begin{aligned}
& \quad \overline{A} \cup \overline{B} \cup (A \cap B \cap \overline{C}) & \quad \text{|} & \quad \textit{Associative}\\
= & \quad (\overline{A} \cup \overline{B}) \cup (A \cap B \cap \overline{C}) & \quad \text{|} & \quad \textit{DeMorgan}\\
= & \quad \overline{(A \cap B)} \cup (A \cap B \cap \overline{C}) & \quad \text{|} & \quad \textit{Associative}\\
= & \quad \overline{(A \cap B)} \cup ((A \cap B) \cap \overline{C}) & \quad \text{|} & \quad \textit{Distributive}\\
= & \quad (\overline{(A \cap B)} \cup (A \cap B)) \cap (\overline{(A \cap B)} \cup \overline{C}) & \quad \text{|} & \quad \textit{Inverse}\\
= & \quad \mathcal{U} \cap (\overline{(A \cap B)} \cup \overline{C})& \quad \text{|} & \quad \textit{Identity}\\
= & \quad \overline{(A \cap B)} \cup \overline{C}& \quad \text{|} & \quad \textit{DeMorgan}\\
= & \quad \overline{A} \cup \overline{B} \cup \overline{C} & \quad \square
\end{aligned}
$$

Aufgabe 2
=========

a)
---

### Satz

$$
A \cap (B \cup C) = (A \cap B) \cup (A \cap C)
$$

### Beweis _(ohne Distributive)_

#### _Es gilt:_

1. $A \cap (B \cup C) = \lbrace x \mid x \in A \wedge (x \in B \vee x \in C) \rbrace$
2. $(A \cap B) \cup (A \cap C) = \lbrace x \mid (x \in A \wedge x \in B) \vee (x \in A \wedge x \in C) \rbrace$

#### _Betrachte nun die Zugehörigkeitsfunktionen:_

1. $\chi_{A \cap ( B \cup C)} (x) = \begin{cases} 1 \text{, falls } x \in A \wedge (x \in B \vee x \in C) \\ 0 \text{, sonst} \end{cases}$
2. $\chi_{(A \cap B) \cup (A \cap C)} (x) = \begin{cases} 1 \text{, falls } (x \in A \wedge x \in B) \vee (x \in A \wedge x \in C) \\ 0 \text{, sonst} \end{cases}$

#### _Tabellarisch:_

| $x \in A$ | $x \in B$ | $x \in C$ | $x \in B \vee x \in C$| $\chi_{A \cap ( B \cup C)} (x)$ | $x \in A \wedge x \in B$ | $x \in A \wedge x \in C$ | $\chi_{(A \cap B) \cup (A \cap C)} (x)$ |
|:---------:|:---------:|:---------:|:---------------------:|:-------------------------------:|:------------------------:|:------------------------:|:---------------------------------------:|
|0 |0 |0 |0 |0 |0 |0 |0 |
|0 |0 |1 |1 |0 |0 |0 |0 |
|0 |1 |0 |1 |0 |0 |0 |0 |
|0 |1 |1 |1 |0 |0 |0 |0 |
|1 |0 |0 |0 |0 |0 |0 |0 |
|1 |0 |1 |1 |1 |0 |1 |1 |
|1 |1 |0 |1 |1 |1 |0 |1 |
|1 |1 |1 |1 |1 |1 |1 |1 |

$$
\begin{aligned}
\Rightarrow & \quad \forall x: \chi_{A \cap ( B \cup C)} (x) = \chi_{(A \cap B) \cup (A \cap C)} (x) \\
\Rightarrow & \quad A \cap (B \cup C) = (A \cap B) \cup (A \cap C) & \quad \square
\end{aligned}
$$

b)
---

### Satz

$$
A \cap (A \cup B) = A
$$

### Beweis _(ohne Absorption)_

#### _Es gilt:_ $A \cap (A \cup B) = \lbrace x \mid x \in A \wedge (x \in A \vee x \in B) \rbrace$

#### _Betrachte Zugehörigkeitsfunktionen:_

1. $\chi_{A}(x) = \begin{cases} 1 \text{, falls } x \in A \\ 0 \text{, sonst} \end{cases}$
2. $\chi_{A \cap (A \cup B)}(x) = \begin{cases} 1 \text{, falls } x \in A \wedge (x \in A \vee x \in B) \\ 0 \text{, sonst} \end{cases}$

#### _Tabellarisch:_

| $x \in A$ | $x \in B$ | $x \in A \vee x \in B$ | $\chi_{A}(x)$ | $\chi_{A \cap (A \cup B)}(x)$ |
|:---------:|:---------:|:----------------------:|:-------------:|:-----------------------------:|
|0 |0 |0 |0 |0 |
|0 |1 |1 |0 |0 |
|1 |0 |1 |1 |1 |
|1 |1 |1 |1 |1 |

$$
\begin{aligned}
\Rightarrow & \quad \forall x: \chi_{A}(x) = \chi_{A \cap (A \cup B)}(x) \\
\Rightarrow & \quad A = A \cap (A \cup B) & \quad \square
\end{aligned}
$$

Aufgabe 3
=========

a)
---

### Gegeben

* $A = \lbrace x \in \mathbb{R} \mid x \leq 0 \rbrace$
* $B = \lbrace x \in \mathbb{R} \mid x > 1 \rbrace$
* $C = \lbrace x \in \mathbb{R} \mid 0 \leq x < 1 \rbrace$

### Satz / Beweis

1. $A \cap B = \emptyset = \lbrace \rbrace$
2. $A \cup B \cup C = \mathbb{R} \setminus \lbrace 1 \rbrace = \lbrace x \in \mathbb{R} \mid x \neq 1 \rbrace$
3. $A \setminus C = \lbrace x \in \mathbb{R} \mid x < 0 \rbrace$
4. $B \setminus C = B$

b)
---

### Gegeben

$$
A= \lbrace 1, 2, \lbrace 2\rbrace \rbrace
$$

### Satz

#### _Folgende Aussagen sind falsch:_

* $\lbrace 1 \rbrace \in A$ (2)
* $\lbrace \lbrace 1 \rbrace \rbrace \subseteq A$ (4)

c)
---

### Satz

#### _Folgende Aussagen sind falsch:_

* $\emptyset \subsetneq \emptyset$ (3)
* $\emptyset \in \emptyset$ (4)

Aufgabe 4
=========

### Gegeben

$$
|2^A \setminus A| = 15
$$

### Satz

1. Es gilt: $|A| = 4$
2. $|2^A \setminus A| \Rightarrow |A| = log_{2}(n+1)$

### Beweis

#### _Zu 1:_

$$
\begin{aligned}
& \quad |2^A \setminus \lbrace A \rbrace| & \quad = & \quad 15\\
\Rightarrow & \quad |2^A| & \quad = & \quad |2^A \setminus \lbrace A \rbrace| + |\lbrace A \rbrace|\\
& \quad & \quad = & \quad 15 + 1 = 16\\
\textit{Nach Vorlesung gilt also:}\\
& \quad |2^A| & \quad = & \quad 2^{|A|} \\
\Leftrightarrow & \quad 16 & \quad = & \quad 2^{|A|}\\
\Leftrightarrow & \quad |A| & \quad = & \quad log_{2}(16)\\
\Leftrightarrow & \quad |A| & \quad = & \quad 4
\end {aligned}
$$

#### _Zu 2:_

$$
\begin{aligned}
\textit{Sei } & \quad |2^A \setminus \lbrace A \rbrace| & \quad = & \quad n\\
\Rightarrow & \quad |2^A| & \quad = & \quad |2^A \setminus A| + |\lbrace A \rbrace|\\
& \quad & \quad = & \quad n + 1\\
\textit{Also gilt dann analog zu 1:}\\
& \quad |2^A| & \quad = & \quad 2^{|A|}\\
\Leftrightarrow & \quad n + 1 & \quad = & \quad 2^{|A|}\\
\Leftrightarrow & \quad |A| & \quad = & \quad \underline{log_{2}(n+1)} & \quad \square
\end{aligned}
$$

Aufgabe 5
=========

### Gegeben

* $A = \lbrace 1, 2, 3 \rbrace$
* $B = \lbrace 2, 3, 4, 5, 6 \rbrace$

### Satz

#### _a)_

$$
2^A = \lbrace \emptyset, \lbrace1 \rbrace, \lbrace 2 \rbrace, \lbrace 3 \rbrace, \lbrace 1, 2 \rbrace, \lbrace 1, 3 \rbrace, \lbrace 2, 3 \rbrace, \lbrace 1, 2, 3 \rbrace \rbrace
$$

#### _b)_

$$
2^{A \cap B} \setminus \lbrace A \cap B \rbrace = \lbrace \emptyset, \lbrace 2 \rbrace, \lbrace 3 \rbrace \rbrace
$$

#### _c)_

$$
|A \cup B| = 6
$$

### Beweis

#### _a) ist klar._

#### _Zu b):_

$$
\begin{aligned}
& \quad \textit{Es gilt:}\\
&\quad & \quad A \cap B & \quad = & \quad \lbrace 1, 2, 3 \rbrace \cap \lbrace 2, 3, 4, 5, 6 \rbrace\\
& \quad &\quad & \quad = & \quad \lbrace 2, 3 \rbrace\\
&\quad \textit{Also:}\\
& \quad & \quad 2^{A \cap B} & \quad = & \quad \lbrace \emptyset, \lbrace 2 \rbrace, \lbrace 3 \rbrace, \lbrace 2, 3 \rbrace\rbrace\\
& \quad \Rightarrow & \quad 2^{A \cap B} \setminus \lbrace A \cap B \rbrace & \quad = &\quad \lbrace \emptyset, \lbrace 2 \rbrace, \lbrace 3 \rbrace \rbrace
\end{aligned}
$$

#### _Zu c):_

$$
\begin{aligned}
\textit{Es gilt:}\\
& \quad A \cup B & \quad = & \quad \lbrace 1, 2, 3 \rbrace \cup \lbrace 2, 3, 4, 5, 6 \rbrace\\
& \quad & \quad = & \quad \lbrace 1, 2, 3, 4, 5, 6 \rbrace\\
\Rightarrow & \quad |A \cup B| & \quad = & \quad 6 &\quad \square
\end{aligned}
$$

Aufgabe 6
=========

a)
---

#### _reflexiv:_

Voraussetzung für reflexiv ist, dass a~a, also a=a gilt. Es lässt sich also sagen, dass x=y gilt, sodass $x+y$ auch formuliert werden kann als:
$$
\begin{aligned}
&x+x= 2\cdot x
\end{aligned}
$$
Durch Faktor $2$ ist die Zahl $x+x$ immer gerade, sodass die Bedingung für Reflexivität gegeben ist.
$\,$

#### _nicht transitiv:_

Gegenbeispiel:
$$
\begin{aligned}
&(\underbrace{2\sim4}_{gerade}~\land~\underbrace{5\sim3)}_{gerade}\not\rightarrow~\underbrace{2\sim5}_{ungerade}. \\
\end{aligned}
$$
$\,$

#### _symmetrisch:_

Voraussetzung für Symmetrie ist, dass (a~b) $\rightarrow$ (b~a) gilt. Aufgrund des Geltens des Kommutativgesetzes bei Additionen gilt:
$$
\begin{aligned}
&x+y=y+x. \\
\end{aligned}
$$
$\,$

#### _nicht antisymmetrisch:_

Gegenbeispiel:
$$
\begin{aligned}
&(\underbrace{3\sim5}_{gerade}~\land~\underbrace{5\sim3}_{gerade})\rightarrow~3\not\equiv5.
\end{aligned}
$$
$\,$

b)
---

#### _nicht reflexiv:_

Gegenbeispiel:
$$
\begin{aligned}
&3\cdot 3 = \underbrace{9}_{ungerade}.
\end{aligned}
$$
$\,$

#### _nicht transitiv:_

Gegenbeispiel:
$$
\begin{aligned}
&(\underbrace{3\sim4}_{gerade}~\land~\underbrace{4\sim5}_{gerade})\not\rightarrow \underbrace{3\sim5}_{ungerade}.
\end{aligned}
$$
$\,$

#### _symmetrisch:_

Voraussetzung für Symmetrie ist, dass (a~b) $\rightarrow$ (b~a) gilt. Aufgrund des Geltens des Kommutativgesetzes bei Multiplikation gilt:
$$
\begin{aligned}
&x\cdot y = y\cdot x.
\end{aligned}
$$
$\,$

#### _nicht antisymmetrisch:_

Gegenbeispiel:
$$
\begin{aligned}
&(\underbrace{3\sim2}_{gerade}~\land~\underbrace{2\sim3}_{gerade})\not\rightarrow~3\not\equiv2.
\end{aligned}
$$

c)
---

#### _nicht reflexiv:_

Gegenbeispiel:
$$
\begin{aligned}
&2\not<2.
\end{aligned}
$$
$\,$

#### _transitiv:_

Da eine Zahl a, die kleiner als b ist, bei b kleiner als c, auch immer kleiner als c ist:
$$
\begin{aligned}
&\underbrace{a<b<c}_{a<c}.
\end{aligned}
$$
$\,$

#### _nicht symmetrisch:_

Gegenbeispiel:
$$
\begin{aligned}
& (\underbrace{1\sim2}_{1<2})\not\rightarrow~(\underbrace{2\not\sim1}_{2\not<1}).
\end{aligned}
$$
$\,$

#### _antisymmetrisch:_

Aufgrund fehlender Symmetrie ist die Bedingung $(a\sim b)\land (b\sim a)$, die nötig für Antisymmetrie wäre ohnehin nicht gegeben, sodass eine Antisymmetrie besteht.

Aufgabe 7
=========

a)
---

Um aus $R_1$ eine antisymmetrische Relation zu machen, muss entweder $(a,b)$ oder $(b,a)$ entfernt werden. D.h.: mindestens ein Element muss entfernt werden.
$\,$

b)
---

Um aus $R_2$ eine transitive Relation zu machen, müssen $4$ Elemente hinzugefügt werden:
**(a,b)**
**(a,c)**
**(b,c)**
**(c,b)**
$\,$

c)
---

#### _reflexiv_

#### _nicht transitiv_

Gegenbeispiel:
$$
\begin{aligned}
&(b\sim a~\land~a\sim c) \not\rightarrow b\not\sim c.
\end{aligned}
$$

#### _symmetrisch_

#### _nicht antisymmetrisch_

Gegenbeispiel:
$$
\begin{aligned}
&(a\sim b~\land~b\sim a) \not\rightarrow a\not\equiv b.
\end{aligned}
$$

Aufgabe 8
=========

### Gegeben

* Menge $A$ mit $|A| = n$
* $R, R_1, R_2$ Relationen auf $A$

### Satz

#### _zu a):_

$$
|R| \geq n \nRightarrow R \text{ reflexiv}
$$

#### _zu b)_:

Sei $R_1 \subseteq R_2$. Dann gilt:

1. $R_1 \text{ reflexiv} \Rightarrow R_2 \text{ reflexiv}$
2. $R_1 \text{ symmetrisch} \nRightarrow R_2 \text{ symmetrisch}$
3. $R_1 \text{ antisymmetrisch} \nRightarrow R_2 \text{ antisymmetrisch}$
4. $R_1 \text{ transitiv} \nRightarrow R_2 \text{ transitiv}$

#### _zu c)_:

$$
R \text{ Äquivalenzrelation} \Rightarrow n \leq |R| \leq n^2
$$

### Beweis

#### _zu a):_

Definiere: $A = \lbrace 1, 2, 3 \rbrace$ und $R = \lbrace (1, 2), (2,1 ), (1, 3)\rbrace \subseteq A \times A$

Dann gilt: $|A| = 3 = n = |R|$

Aber: $R$ ist dann offensichtlich nicht reflexiv

#### _zu b):_

Sei also jeweils $R_1 \subseteq R_2 \subseteq A \times A$

1. $R_1 \text{ reflexiv} \Rightarrow \forall a \in A: aR_{1}a \underbrace{\Rightarrow}_{R_1 \subseteq R_2} \forall a \in A: aR_{2}a \Rightarrow R_2 \text{ reflexiv}$
2. $A = \lbrace 1, 2 \rbrace \wedge R_1 = \lbrace \rbrace \wedge R_2 = \lbrace (1, 2) \rbrace \Rightarrow R_1 \text{ symmetrisch, aber } R_2 \text{ nicht symmetrisch}$
3. $A = \lbrace 1, 2 \rbrace \wedge R_1 = \lbrace \rbrace \wedge R_2 = \lbrace (1, 2), (2, 1) \rbrace \Rightarrow R_1 \text{ antisymmetrisch, aber } R_2 \text{ nicht antisymmetrisch}$
4. $A = \lbrace 1, 2,3 \rbrace \wedge R_1 = \lbrace \rbrace \wedge R_2 = \lbrace (1, 2), (2, 3) \rbrace \Rightarrow R_1 \text{ transitiv, aber } R_2 \text{ nicht transitiv}$

#### _zu c):_

Sei $R \subseteq A \times A$ mit $|A| = n$ eine Äquivalenzrelation. Dann gilt:
1. $R \text{ Äquivrel.} \Rightarrow R \text{ reflexiv} \Rightarrow \forall x \in A: (x,x) \in R \Rightarrow |R| \geq n$
2. $R \subseteq A \times A \Rightarrow |R| \leq |A \times A| = n^2$

Also folgt: $n \leq |R| \leq n^2 \quad \square$

Aufgabe 9
=========

#### _reflexiv:_

Wenn a~a gilt, gilt auch x=y, sodass:
$$
\begin{aligned}
&x^2 - x^2 = 0.
\end{aligned}
$$
Da 0 immer durch 3 teilbar ist, ist diese Aussage also immer wahr.

#### _transitiv:_

#### Definition:
$$
\begin{aligned}
&\exists~a,b,c,m,n,o\in\mathbb{Z}
\end{aligned}
$$
#### Satz:
aus $a^2-b^2 = 3\cdot m$ und $b^2 - c^2 = 3\cdot n$ folgt, dass auch $a^2-c^2=3\cdot o$ gilt.
#### Beweis:
$$
\begin{aligned}
&b^2-c^2 &=&~3\cdot n & \, & |~+c^2 \\
&b^2 &=&~3\cdot n +c^2 &\,&|~setze~ein~in~a² -b^2=3\cdot m \\
&a^2 - (3\cdot n+c^2) &=&~3\cdot m \\
&a^2 - 3\cdot n -c^2 &=&~3\cdot m &\,&|~+3\cdot n \\
&a^2 - c^2 &=&~3\cdot (m+n)
\end{aligned}
$$
Da $o$ auch ein kombiniertes Element aus $m$ und $n$ sein kann und der Faktor $3$ ausgeklammert werden kann, ist auch $a^2 -c^2$ durch $3$ teilbar.
<div style="text-align: right"> q.e.d. </div>

#### _symmetrisch:_

#### Definition:
$$
\begin{aligned}
\exists~a,b,m,n\in\mathbb{Z}
\end{aligned}
$$
#### Satz:
Da $(a\sim b)\Rightarrow~(b\sim a)$ gilt, muss hierbei auch $(a^2-b^2 = 3\cdot m)\Rightarrow~(b^2-a^2=3\cdot n)$ gelten.
#### Beweis:
$$
\begin{aligned}
&a^2-b^2 &=&~ 3\cdot m &\,&|~\cdot(-1) \\
&-a^2 + b^2 &=&~-3\cdot m \\
&b^2-a^2 &=&~-3\cdot m \\
\end{aligned}
$$
Da $n$ in diesem Fall immer $-1\cdot m$ ist und so immernoch durch den Faktor $3$ durch $3$ teilbar ist, gilt hier die Symmetrie.
<div style="text-align: right"> q.e.d. </div>

#### _Äquivalenzklassen:_
$$
\begin{aligned}
&a=3|b \Leftrightarrow \exists k \in\mathbb{Z}:b=k\cdot3+a \\ \, \\
&\mathbb{Z}= Equiv(0,R)\cup Equiv(1,R)\cup Equiv(2,R)
\end{aligned}
$$

Aufgabe 10
==========

a)
---

### Gegeben

* $R_1 = \lbrace (x, y) \mid x, y \in \mathbb{R}, \quad y = 2x + \frac{\pi}{2} \rbrace$
* $R_2 = \lbrace (x, y) \mid x, y \in \mathbb{R}, \quad 1-x^2 = |y| \rbrace$
* $R_3 = \lbrace (x, y) \mid x, y \in \mathbb{R}, \quad y^4 = x \rbrace$
* $R_4 = \lbrace (x, y) \mid x, y \in \mathbb{Z}, \quad y = 4x^2 \rbrace$

### Satz

#### _Totale Funktionen:_

* $R_1$ ist *eine* totale Funktion
* $R_2$ ist *keine* totale Funktion
* $R_3$ ist *keine* totale Funktion
* $R_4$ ist *eine* totale Funktion

Sei $f$ die Funktion beschrieben durch $R_1$
Sei $g$ die Funktion beschrieben durch $R_4$

#### _Bild von f:_
$$
f(\mathbb{R}) = \mathbb{R}
$$

#### _Bild von g:_
$$
f(\mathbb{Z}) = \lbrace \mathbb{y \in \mathbb{N}_0 \mid \exists x \in \mathbb{N}_0: y = 4x^2} \rbrace
$$

$R_2, R_3$ sind keine Funktionen und daher ist kein Bild zu bestimmen.

### Beweis

* $R_1$ ist eine Funktion, da offensichtlich $\forall x \in \mathbb{R}: \exists! y \in \mathbb{R}: y = 2x + \frac{\pi}{2}$
* $R_2$ ist keine Funktion, da z.B $x = 2 \Rightarrow \forall y \in \mathbb{R}: 1-x^2 \neq |y|$ _(Definitionslücke)_
* $R_3$ ist keine Funktion, da z.B $x= -1 \Rightarrow \forall y \in \mathbb{R}: y^4 \neq x$ _(Definitionslücke)_
* $R_4$ ist eine Funktion, da offensichtlich $\forall x \in \mathbb{Z}: \exists! y \in \mathbb{Z}: y = 4x^2$

b)
---

### Gegeben

* $f_1: \mathbb{N}_0 \rightarrow \mathbb{N}_0 \setminus \lbrace n \mid n \in \mathbb{N}_0 \wedge 2 \nmid n \rbrace$
* $f_2: \mathbb{N}_0 \rightarrow \mathbb{Z}$
* $f_3: \mathbb{N}_0 \times \mathbb{N}_0 \rightarrow \mathbb{N}_0$
* $M_1 = \lbrace 2, 4, 6, 8 ,10 \rbrace$
* $M_2 = \lbrace -2, -1, 0, 1 ,2 \rbrace$
* $M_3 = \lbrace 1, 2, 3, 4 ,5 \rbrace$

### Satz

* Mit $f_1(x) = 2x$ ist $f_1$ bijektiv
* Mit $f_2(x) = \begin{cases} \frac{x}{2} \text{, falls } x | 2 \\ -\frac{x+1}{2} \text{, sonst} \end{cases}$ ist $f_2$ bijektiv
* Mit $f_3((x,y)) = x$ ist $f_3$ surjektiv aber nicht injektiv

Mit den wie oben definierten Funktionen ergeben sich folgende Urbilder:

* $f_1^{-1}(M_1) = \lbrace 1, 2, 3, 4, 5 \rbrace$
* $f_2^{-1}(M_2) = \lbrace 3, 1, 0, 2, 4 \rbrace$
* $f_3^{-1}(M_3) = \lbrace (x, y) \in {\mathbb{N}_{0}}^{2} \mid x = 1 \vee x = 2 \vee x = 3 \vee x = 4 \vee x =5 \rbrace$

### Beweis

$f_3$ wie oben definiert ist nicht injektiv, da das Ergebnis $x$ nur auf die linke Komponente vom Eingabetupel zurückzuführen ist und die rechte Komponente keinen Einfluss auf das Ergebnis hat. Da aber alle $x \in \mathbb{N}_0$ abgedeckt sind ist die Funktion trotzdem surjektiv.