• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Warum ist Q abzählbar?

Contents

  • Warum ist Q abzählbar?
    • Material
This is a quick article I had for quite a while as a draft. It might not be finished or have other problems, but I still want to share it.
Eine Menge B heißt abzählbar $: \Leftrightarrow \exists (a_n) \in B: B = \{a_1, a_2, a_3, ...\}$ $\Leftrightarrow \exists f : \mathbb{N} \rightarrow B $ mit $f$ surjektiv.

Die natürlichen Zahlen sind abzählbar.

Beh.: \(\mathbb{N}\) ist abzählbar.

Bew.: direkt Sei \(f: \mathbb{N} \rightarrow \mathbb{N}\) definiert durch \(f(n) := n\). \(f\) ist also die identität und damit bijektiv und insbesondere surjektiv \(\blacksquare\)

Die ganzen Zahlen sind abzählbar.

Beh.: \(\mathbb{Z}\) ist abzählbar.

Bew.: direkt Sei \(f: \mathbb{N} \rightarrow \mathbb{Z}\) definiert durch

$$f(n) := \begin{cases} \frac{n-1}{2} & \text{, falls n ungerade} \\ - \frac{n}{2} & \text{, falls n gerade} \end{cases}$$

Also: \(\forall z \in \mathbb{Z}: \exists x \in \mathbb{N} : f(x) = z\)

da:

$$\forall x \in \mathbb{Z}: n = \begin{cases} - 2 \cdot x & \text{, falls x negativ} \\ 2 \cdot x + 1 & \text{, falls x positiv} \end{cases}$$

Es gibt also für jede ganze Zahl z eine natürliche Zahl n, die ich in \(f\) stecken kann um z zu erhalten \(\blacksquare\)

Beh.: \(\mathbb{N} \times \mathbb{N}\) ist abzählbar.

Bew.: direkt Sei \(f: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\) rekursiv definiert durch \(f(1,1) := 1\) und

$$f (m, n) := \begin{cases} f(m + 1, n - 1) + 1 & \text{, falls } n \neq 1 \\ f(1, m - 1) & \text{sonst} \end{cases}$$

Diese Abbildung sieht wie folgt aus:

Function that transforms N times N to N
Abbildung, die N x N auf N abbildet

Ich finde es ist intuitiv klar, dass diese Funktion bijektiv ist. Hat jemand dafür einen sauberen Beweis?

Also gibt es eine Umkehrfunktion (die auch bijektiv ist). Also ist \(\mathbb{N} \times \mathbb{N}\) abzählbar \(\blacksquare\)

Beh.: \(\mathbb{Q}^+\) ist abzählbar.

Bew.: über \(N \times N\) Jede Zahl \(x \in \mathbb{Q}^+\) kann mit zwei natürlichen Zahlen dargestellt werden: \(x = \frac{p}{q}\). Also gibt es eine Funktion \(f: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{Q}\) mit \(f(m, n) := \frac{m}{n}\). Diese Abbildung ist offensichtlich surjektiv. \(\blacksquare\)

Material

Die LaTeX-Dateien für die Bilder sind in diesem Repository zu finden.


Published

Dez 30, 2014
by Martin Thoma

Category

German posts

Tags

  • analysis 7
  • mathematics 59

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor