BuK/IIm14/Studenten/s3jeleus

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Übungsaufgabe 1 == 

Prinzipiell Unlösbares:

- unscharfe Fragestellung
- Regeln zur Suche einer Antwort sind unklar
- zu viele abhängige Parameter
- emotionale Ebene
- exakte Vorhersagen 
- begrenzte Ressourcen
- Annäherung an Ergebnisse durch Methoden der KI


== Übungsaufgabe  2==

Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: $\mathbb{Z},  \mathbb{Q}$, die Menge der Primzahlen, die geraden Zahlen.

=== $\Z$ ist abzählbar unendlich ===

z.z. $\mathbb{Z}$ ist abzählbar unendlich, d.h. es existiert eine Funktion $\mathbb{f}: \mathbb{N} \xrightarrow{\text{bij.}}  \mathbb{Z}$

{| border="1" cellpadding="5" cellspacing="0"
|-
|| 0 || 1 || 2 || 3 || 4 || 5 || ...
|-
|| 0 || 1 || -1 || 2 || -2 || 3 || ...
|-
|}

$$f(n) = \begin{cases}
   \frac{n}{2}, & \text{wenn n gerade};\\
- \frac{n + 1}{2}, & \text{sonst }.\\
\end{cases}$$

==== Beweis durch vollständige Induktion ====

$$f(n) + 1 = f(n + 2)$$
$$f(2n) + 1 = f(2n + 2)$$

''' Induktionsanfang'''

$$f(2 \cdot 0) + 1 = f(2 \cdot 0 + 2) $$
$$f(0) + 1 = f(2)$$
$$\frac{0}{2} + 1 = \frac{2}{2}$$
$$1 = 1$$

''' Induktionsvoraussetzung'''

$$f(2n) + 1 = f(2n +2)$$

'''Induktionsbehauptung'''

$$ f(2(n + 1) + 1 = f(2(n +1) + 2)$$
$$ \frac{2(n + 1)+ 1}{2} =  \frac{f(2(n+ 1)+ 2}{2}$$
$$ n + 1 +1 = n + 1 + 1$$
$$ n + 2 = n + 2$$
$$ n = n $$

=== $\Q$ ist abzählbar unendlich ===

z.z. $\mathbb{Q}$ ist abzählbar unendlich, d.h. es existiert eine Funktion $\mathbb{f}: \mathbb{N} \xrightarrow{\text{bij.}}  \mathbb{Q}$

$$f(n) = \begin{cases}
   1, & \text{wenn  n = 1};\\
   f(\frac{n}{2}) + 1, & \text{wenn n gerade};\\
  \frac{1}{f(n-1)}, & \text{sonst }.\\
\end{cases}$$

{| border="1" cellpadding="5" cellspacing="0"
!$\N^+$ \ $\Z$
!$-1$
!$ 1$
!$-2$
!$2$
!$-3$
!...
|-
|| 1 || -1/1 || 1/1 || -2/1 || 2/1 || -3/1 || ...
|-
|| 2 || -1/2 || 1/2 || -2/2 || 2/2 || -3/2 || ...
|-
|| 3 || -1/3 || 1/3 || -2/3 || 2/3 || -3/3 || ...
|-
|| 4|| -1/4 || 1/4 || -2/4 || 2/4 || -3/4 || ...
|-
|| 5 || -1/5 || 1/5 || -2/5 || 2/5 || -3/5 || ...
|-
|| ... || ... || ... || ... || ... || ... || ...
|-
|}

Durch das cantorschn Diagonalverfahren 1. Art lässt sich zeigen, dass die Menge $\Q$ abzählbar unendlich ist.

=== Die Primzahlen sind abzählbar unendlich===

1. Die Menge der Primzahlen P ist unendlich (nach Satz von Euklid).

2. Die Menge der Primzahlen P ist abzählbar unendlich, da gilt: P $\subset \N$.


=== Die geraden Zahlen sind abzählbar unendlich === 

1. Die geraden Zahlen G sind unendlich (per Definition) und abzählbar unendlich, da gilt: G $\subset \Z$.

== Übungsaufgabe 3 ==

Beweisen Sie den folgenden Satz: Wenn $M_1, M_2, M_3, ... ∞$
abzählbare Mengen sind, dann ist auch die Menge 􏰄 $M_n n=1$
abzählbar.

Eine Menge $M$ ist endlich sofern eine surjektive Abbildung auf diese Menge existiert.

z.z. Es existiert eine Funktion $ f: \N \xrightarrow{\text{sur.}} \cup_{n = 1}^{∞} M_n$

<code id="552e94541ee0b">(define f 
    (lambda (n) 
        (if (= n 1)
            1
            (if (= (modulo n 2) 0)
                (+ 1 (f (/ n 2)))
                (/ 1 (f (- n 1)))
            )
        )
    )
)</code>

<run id="552e94541ee7c"></run>


Umkehrfunktion:

$$ f^{-1}(n) = \begin{cases}1, & n = 1 \\ f^{-1}(n-1) * 2, & n > 1 \\ f^{-1}(\frac{1}{n}) + 1, & sonst\end{cases} $$

Reele Zahlen

Indirekter Beweis: R ist abzählbar unendliche Menge, d.h es existiert eine Funktion $f: \N \xrightarrow{\text{bij.}} \R$

$n_{ij} \in [0,9]$

Es lässt sich stets eine neue Zeile, die eine neue reele Zahl repräsentiert, hinzufügen.

$$n_i = \begin{cases}
   n_{ii} + 1, & \text{wenn  $n_{ii} \neq 9$};\\
  0, & \text{sonst }.\\
\end{cases}$$

{| border="1" cellpadding="5" cellspacing="0"
!$\R$ \ $\N$
!$0$
!$1$
!$2$
!$...$
!$j$
!...
|-
|| $n_{1}$ || $n_{10}$ || $n_{11}$ || $n_{12}$ || ... || $n_{1j}$ || ...
|-
|| $n_{2}$ || $n_{20}$ || $n_{21}$ || $n_{22}$ || ... || $n_{2j}$ || ...
|-
|| $n_{3}$ || $n_{30}$ || $n_{31}$ || $n_{32}$ || ... || $n_{3j}$ || ...
|-
|| ...  || ... || ... || ... || ... || ... || ...
|-
|| $n_{i}$ || $n_{i0}$ || $n_{i1}$ || $n_{i2}$ || $n_{i3}$ ||  $n_{ij}$  || ...
|-
|}