# 2. Tutorium

## Aufgabe 1

Betrachten Sie auf der Menge $X = \{a, b, c, d\}$
die Ordnungsrelation $R := \{(a, b),(a, c),(a, d),(c, d)\} ∪ ∆X$.
Skizzieren Sie das zugehörige Ordnungsdiagramm.

Bestimmen Sie alle maximalen und größten Elemente,
sowie alle minimalen und kleinsten Elemente bzgl. R.

- maximal: b,d
- größtes: /
- minimal: a
- kleinstes: a

## Aufgabe 2

Sei $(X, ≤)$ eine geordnete Menge. Zeigen Sie:

### Aufgabe 2a)

Sind $a, b ∈ X$ größte Elemente, so gilt $a = b$.

$a$ größtes Element bedeutet $\forall x \in X: x \leq a
\Rightarrow b \leq a$.
$b$ größtes Element bedeutet $\forall x \in X: x \leq b
\Rightarrow a \leq b$.
$\Rightarrow a=b$.

### Aufgabe 2b)

Ein größtes Element ist stets maximal.

$a$ größtes Element bedeutet $\forall x \in X: x \leq a$.
$a$ maximales Element bedeutet $\forall x \in X: x \geq a \Rightarrow x = a$.
Sei $a$ größtes Element, $x_i \in X$, $x_i \geq a$.
Da $a$ größtes Element muss gelten $x_i \leq a$.
Also $x_i = a \space \space \forall x_i \in X$.
Dies ist allerdings die Voraussetzung, dass $a$ maximales Element ist.

### Aufgabe 2c)

Ist $a ∈ X$ größtes Element und ist $b ∈ X$ maximal, so gilt $a = b$.

$a$ größtes Element bedeutet $\forall x \in X: x \leq a$.
$b$ maximales Element bedeutet $\forall x \in X: x \geq b \Rightarrow x = b$.
$a \in X \Rightarrow a \geq b.$
$b \in X \Rightarrow b \geq a. \space \Rightarrow a=b$.

### Aufgabe 2d)

Gibt es zwei verschiedene maximale Elemente in $X$,
so kann es kein größtes Element geben.

Seien $a,b \in X$ maximale Elemente, $a \neq b$.
D.h. $\forall x \in X: x \geq a \Rightarrow x = a, x \geq b \Rightarrow x = b$.
Sei nun $c \in X$ größtes Element. D.h. $\forall x \in X: x \leq c$.
Da $a,b \in X$: $a \leq c \land b \leq c$.
Außerdem, da $a,b$ maximale Elemente:
$c \geq a \Rightarrow c = a \land c \geq b \Rightarrow c = b$.
Widerspruch zur Annahme $a \neq b$...

## Aufgabe 3

Sei $M = \{a, b, c\}$ eine drei-elementige Menge und
$X := \mathcal{P}(M)$ deren Potenzmenge.
Betrachten Sie die Kardinalitätsabbildung $f : X → N , A \mapsto |A|$
und die zugehörige Relation $∼_f$ auf $X$, definiert durch
$A ∼_f B :⇔ f(A) = f(B)$.
Geben Sie die Kreuztabelle der Aquivalenzrelation $∼_f$ an,
sowie die zugehörige Zerlegung der Menge $X$.

| $∼_f$ | {a} | {b} | {c} | {a,b} | {a,c} | {b,c} | {a,b,c} | {} |
| ----------- | --- | --- | --- | ----- | ----- | ----- | ------- | --- |
| **{a}** | x | x | x | | | | | |
| **{b}** | x | x | x | | | | | |
| **{c}** | x | x | x | | | | | |
| **{a,b}** | | | | x | x | x | | |
| **{a,c}** | | | | x | x | x | | |
| **{b,c}** | | | | x | x | x | | |
| **{a,b,c}** | | | | | | | x | |
| **{}** | | | | | | | | x |

z.B. $A=\{a\}, f(A)=1$.

Zerlegung:
$x_1 = \{\{a\},\{b\},\{c\}\}$,
$x_2 = \{\{a,b\},\{b,c\},\{a,c\}\}$,
$x_3 = \{\{a,b,c\}\}$,
$x_4 = \{\{\}\}$

## Aufgabe 4

Zeigen Sie, dass die Menge $\mathbb{Z}$ abzählbar ist.
Geben Sie eine Bijektion $\varphi: \mathbb{N} → \mathbb{Z}$ an,
sowie deren Umkehrabbildung $\varphi^{−1}: \mathbb{Z} → \mathbb{N}$.

Annahme: $0 \in \mathbb{N}$.
Falls $\varphi$ konstruiert ist, dann ist $\mathbb{Z}$ abzählbar, da $\varphi^{−1}.
Sei $\varphi: \mathbb{N} → \mathbb{Z}$,
$n \mapsto \begin{cases} n/2 & \text{if n is even}
\\-(n+1)/2 & \text{if n is odd} \end{cases}$

$\varphi$ injektiv: Seien $n_1,n_2 \in \mathbb{N}$ mit $n_1 \neq n_2$.
Falls $n_1$ gerade und $n_2$ ungerade,
gilt $\varphi(n_1)=n_1/2 \neq (-n_2+1)/2 = \varphi(n_2).$
Falls $n_1$ und $n_2$ gerade,
gilt $\varphi(n_1)=n_1/2 \neq n_2/2 = \varphi(n_2)$, sonst $n_1 = n_2$.
Falls $n_1$ und $n_2$ ungerade, analog.

$\varphi$ surjektiv: Sei $a \in \mathbb{Z}$.

1. Fall: $a \geq 0$. Dann ist $\varphi(2a)=2a/2=a$.
2. Fall: $a \leq 0$. Dann ist $\varphi(-2a-1)=(2a-1+1)/2=a$.

Also ist $\varphi$ bijektiv.

$\varphi^{-1}: \mathbb{Z} → \mathbb{N},
z \mapsto \begin{cases} 2z & \text{if } z \geq 0
\\-2z-1 & \text{if } z \leq 0 \end{cases}$

Es genügt zu zeigen:
$\varphi^{-1}(\varphi(n))=n \space \forall n \in \mathbb{N}$.

1. Fall: n gerade: $\varphi^{-1}(\varphi(n)) = $\varphi^{-1}(n/2) = 2(n/2)=n$
2. Fall: n ungerade: $\varphi^{-1}(\varphi(n)) = $\varphi^{-1}((-n+1)/2) = 2(-n+1-1)=n$

$\Box$

## Aufgabe 5

Seien $X, Y$ Mengen mit einer Injektion $f : X → Y$ . Beweisen Sie:

### 5a)

Ist $Y$ endlich, so auch $X$.

$\exists n \in \mathbb{N}$ und Injektion $g: Y \rightarrow \{1,2,...,n\}$.
Somit ist $g \circ f: X \rightarrow \{1,2,...,n\}$ Injektion.
$\Rightarrow X$ endlich.

### 5b)

Ist $Y$ abzählbar, so auch $X$.

$\exists$ Injektion $g: Y \rightarrow \mathbb{N}$.
Somit ist $g \circ f: X \rightarrow \mathbb{N}$ Injektion.
$\Rightarrow X$ abzählbar.

###### tags: `Lineare Algebra 2` `Tutorium` `Mathematik` `Uni`