Anki Deck Changes

1. Assume countable: Suppose \(f: \mathbb{N} \to A\) is a bijection. Therefore we can enumerate elements of \(A\): \(a_1, a_2, a_3, \ldots\)
2. Represent elements: Let \(a_{i,j} \) represent the \(j\)-th number in the \(i\)-th element.
3. Construct diagonal element \(b\): Define \(b\) by setting each element
   • We need to have: \(b_i \neq a_{i,i}\) for all \(i\) 
   • \(b_i = 1 - a_{i,i}\) (flip the bit) or \(b_i = \begin{cases} 4 & \text{if } a_{i,i} \neq 4 \\ 5 & \text{if } a_{i,i} = 4 \end{cases}\) (simply change element)
4. Show \(b\) not in list: For any \(i\), we have \(b_i \neq a_{i,i}\)
   • Therefore \(b \neq a_i\) for all \(i\)
5. Contradiction: But \(b \in A\), yet \(b \notin \{a_1, a_2, \ldots\}\)
   • So \(f\) is not surjective → no bijection exists → \(A\) uncountable

Key idea: \(b\) differs from the \(n\)-th element in the \(n\)-th position, so it "escapes" any enumeration.

• Injektion finden: Konstruiere \(f : {0, 1}^\infty \rightarrow A\), sodass \(b \not = b’ \ \implies f(b) \not = f(b’)\).
• Funktion verifizieren: Zeige dass \(f\) well-defined und total ist, und \(f(b) \in A\) für alle \(b\).
• Injektivität beweisen: Zeige \(f(b) = f(b’) \ \implies b = b’\) oder direkt \(b \not = b’ \ \implies \ f(b) \not = f(b’)\).
• Schluss: We now know \(\{0, 1\}^\infty \preceq A\) as there's an injection.
  Annahme \(A \preceq \mathbb{N} \implies \{0, 1\}^\infty \preceq \mathbb{N}\) via transitivity -> Contradiction. Thus \(A\) is uncountable: \(\lnot (A \preceq\mathbb{N})\).