text: # Lecture 15: Uncountable sets
  
  • $$ℝ$$, $$2^ℕ$$ are uncountable.
  • Set of (finite) strings is countable.
  • Finite cardinality
  
  ## $$ℝ$$ is uncountable
  
  Claim: The set of real numbers $$ℝ$$ is uncountable.
  
  Proof: in fact, we will show that the set of real numbers between 0 and 1 is uncountable; since this is a subset of $$ℝ$$, the uncountability of $$ℝ$$ follows immediately.
  
  We proceed by contradiction. Suppose that $$ℝ$$ were countable. Then there would exist a surjection $$f : ℕ → ℝ$$. We could expand the digits of $$f$$ in a table; for example, if $$f(0) = 0$$, $$f(1) = 1/2$$, $$f(2) = π - 3$$, $$f(3) = φ - 1$$, then the table would look as follows:
  
  $$n$$ $$f(n)$$ digits of $$f(n)$$
  0 0 $$0.00000\cdots$$
  1 1/2 $$0.50000\cdots$$
  2 $$π - 3$$ $$0.14159\cdots$$
  3 $$φ - 1$$ $$0.61803\cdots$$
  
  Given such a table, we can form a real number $$x_D$$ that is not in the table by changing the $$i$$th digit of the $$i$$th number; perhaps by adding 5 (wrapping around, so that 7 + 5 = 2, for example).
  
  In the example, $$x_D = 0.5565\cdots$$.
  
  Now $$x_D$$ cannot be in the table, because $$x_D$$ differs from $$f(i)$$ in the $$i$$th digit. But this contradicts the fact that $$f$$ is surjective, thus completing the proof.
  
  Note: this technique is called diagonalization.
  
  ### What good is countability?
  
  • the existence different sizes of infinity is pretty neat.
  
  • diagonalization is used to prove that there are specifications with no program that implements them. One such problem is determining whether a program crashes or not. It would be nice to have a compiler that guarantees that your program never crashes. However, diagonalization can be used to show that no such program exists. We may discuss this more when we talk about computability; it is also discussed in MCS.
  
  • this proof is also quite closely related to notions of truth and provability, which we will discuss later in the course.
  
  ## Finite cardinality
  
  Definition: If $$X$$ is a set and $$n \in ℕ$$, the expression "|X| = n" means $$|X| = \{1,2,\dots,n\}$$.
  
  This matches the usual notion of the number of things in the set.
  
  Claim: If $$|A| = a$$ and $$|B| = b$$, and if $$A$$ and $$B$$ are disjoint, then $$|A \cup B| = a + b$$.
  
  Note: This can be shortened to "$$|A \cup B| = |A| + |B|$$, as long as you keep in mind that this equation only makes sense if $$|A|$$ and $$|B|$$ are numbers (i.e. if $$A$$ and $$B$$ are finite)
  
  Proof: Since $$|A| = a$$, there exists a bijection $$f : A → \{1,2,\dots,a\}$$. Similarly, there exists $$g : B → \{1,2,\dots,b\}$$. We can build a function $$h : A \cup B → \{1,2,\dots,a+b\}$$ by defining $h(x) := \left\{\begin{array}{ll} f(x), & \text{if x \in A} \\ g(x), & \text{if x \in B} \end{array}\right.$
  
  To complete the proof, we need to show that $$h$$ is a bijection. We left this as an exercise. While you're doing the exercise, make sure you use the fact that $$A \cup B = \emptyset$$.
metadata: {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}