BuK/IIm21

Wiki-Quelltext dieser Seite.

<h1>Berechenbarkeit und Kreativität (TODO)</h1>

<h3>Beweise für unendliche Mengen</h3>

<b>TODO: Beweismöglichkeiten für abzählbare Mengen (zB.: sortieren, surjektive Abbildungen aufstellen, ...), Widerspruchsbeweise für Abzählbarkeit übersichtlich in einer Grafik darstellen!</b>

<b>abzählbar unendliche Mengen</b> = Menge ist gleichmächtig zu den natürlichen Zahlen

Vorstellungsvermögen: Wenn man als Beispiel eine bijektive Abbildung zählt und bei natürlicher zahl (1 Billion) und der dazugehörigen Zahl der Vergleichsmenge (40) ankommt, dann könnte man erstmal denken, dass Vergleichsmenge weniger mächtig ist, weil 40 kleiner als 1 Billion, aber es geht um die ANZAHL DER ELEMENTE (KARDINALITÄT) BEIDER MENGEN und dahingehend sind beide gleich.

Beweis über eine surjektive Abbildung.

z.B.: Beweis, dass ganze Zahlen (Z) abzählbar unendlich sind:

1 -> 1

2 -> -1

3 -> 2

4 -> -2

5 -> 3

...

Beweis, dass gerade Zahlen (G) abzählbar unendlich sind:

1 -> 2

2 -> 4

3 -> 6

4 -> 8

...

Zudem gilt: G Teilmenge von N

Beweis, dass rationale Zahlen (Q) abzählbar unendlich sind: Sequenz (Reihenfolge) der bijektiven Abbildung zwischen N und Q kann mithilfe von Cantor'sches Diagonalverfahren 1. Art bestimmt werden.

Beweis, dass M1 vereinigt M2 abzählbar unendlich sind, wobei M1 und M2 jeweils abzählbar unendliche Mengen sind:

Möglichkeit 1: Bestimmung der Sequenz der Abbildung über Cantor' Diagonalverfahren 1. Art

Möglichkeit 2:

1 -> M1(1. Element)

2 -> M2(1. Element)

3 -> M1(2. Element)

4 -> M2(2. Element)

5 -> M1(3. Element)

...

überabzählbar unendliche Mengen:

siehe Cantor'sches Diagonalverfahren 2. Art

Idee dahinter:
Man hat eine beliebige Menge an Wörtern. An dieser Menge wird die Hauptdiagonale angelegt. Anschließend wird ein neues Wort erzeugt, indem für (n, a) das Zeichen geändert wird.
Die Änderung des Zeichens für das neue Wort muss dabei einer Regel erfolgen, die auf Basis des aktuellen Zeichens ein anderes Zeichen des Alphabets verwendet.

(x, y) : (Zeile, Spalte); n : durchlaufende Zeile; a : Spalte innerhalb der Hauptdiagonale

Beispiel:

A = {a, b}

Regel: wenn a -> b; wenn b -> a

<table>
<tr>
<th></th>
<th>z1</th>
<th>z2</th>
<th>z3</th>
<th>z4</th>
<th>...</th>
</tr>
<tr>
<td>w1</td>
<td>a</td>
<td>b</td>
<td>b</td>
<td>a</td>
<td>...</td>
</tr>
<tr>
<td>w2</td>
<td>b</td>
<td>a</td>
<td>a</td>
<td>a</td>
<td>...</td>
</tr>
<tr>
<td>w3</td>
<td>a</td>
<td>a</td>
<td>a</td>
<td>a</td>
<td>...</td>
</tr>
<tr>
<td>w4</td>
<td>a</td>
<td>a</td>
<td>b</td>
<td>b</td>
<td>...</td>
</tr>
<tr>
<td>wn</td>
<td>b</td>
<td>b</td>
<td>b</td>
<td>a</td>
<td>...</td>
</tr>
</table>

z = Zeichen; w = Wort; wn = neues Wort

Auf Basis dessen kann man als Wort auch ein Zahlwort verwenden. Um zu beweisen, dass die reellen Zahlen (R) überabzählbar unendlich sind, wurde dieses Verfahren verwendet.
Da von jedem Zahlwort eine Ziffer verändert wird, erhält man ein neues Zahlwort.

<b>FRAGE: Würde man nicht aber auch immer ein unterschiedliches Zahlwort erhalten, wenn man die rationalen Zahlen auf das Cantor'sche 2. Diagonalverfahren anwendet?

Idee: Vielleicht??, aber alle rationalen Zahlen können neben der Dezimalschreibweise auch als p/q dargestellt werden, wobei sowohl p als auch q in p/q natürliche Zahlen sind.</b>

<h3>Entscheidbarkeit</h3>

<h1>Definitionen und Beweise</h1>

<h1>Übungen</h1>

Vorlesung 3 [[BuK/IIm21/Vorlesung 3 Hildebrand]]