Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Uncountable"

(→‎Proof that <math>\mathbb{R}</math> is uncountable)
m
 
(8 intermediate revisions by 6 users not shown)
Line 1: Line 1:
−
{{stub}}
+
A [[set]] <math>S</math> is said to be '''uncountable''' if there is no [[injection]] <math>f:S\to\mathbb{N}</math>. Assuming the [[Axiom of choice]], every set that is ''not'' uncountable is either [[finite]] or [[countably infinite]].  The most common example of an uncountable set is the set of [[real number]]s <math>\mathbb{R}</math>.
 +
 
 +
== Proof that <math>\mathbb{R}</math> is uncountable ==
  
−
A set <math>S</math> is said to be '''uncountable''' if there is no [[injection]] <math>f:S\to\mathbb{Z}</math>. A well-known example of an uncountable set is the set of [[real number]]s <math>\mathbb{R}</math>.
+
We give an [[indirect proof]] here. This is one of the most famous indirect proofs and was first given by [[Georg Cantor]].
  
−
=== Proof that <math>\mathbb{R}</math> is uncountable ===
+
Suppose that the set <math>A=\{x\in\mathbb{R}:0<x< 1\}</math> is countable. Let <math>\{\omega_1, \omega_2, \omega_3, ...\}</math> be any enumeration of the elements of <math>A</math> (in other words, take an injection <math>f: A \to \mathbb{N}</math>, and denote <math>\omega_i = f(i)</math>).
  
−
We give an indirect proof here. This is one of the most famous indirect proofs and was given by George Cantor.
+
Consider the [[decimal expansion]] of each <math>\omega_i</math>, say <math>\omega_i=0.b_{i1}b_{i2}b_{i3} \ldots</math> for all <math>i</math>.  Now construct a real number <math>\omega= 0.b_1b_2b_3 \ldots</math>, by choosing the digit <math>b_i</math> so that it differs from <math>b_{ii}</math> by at least 3 and so that <math>b_i</math> is never equal to 9 or 0.  It follows that <math>\omega</math> differs from <math>\omega_i</math> by at least <math>\frac{2}{10^i}</math>, so <math>\omega \neq \omega_i</math> for every <math>i</math>.  Thus, <math>\omega \not \in A</math>.  However, <math>\omega</math> is clearly a real number between 0 and 1, a [[contradiction]].  Thus our assumption that <math>A</math> is countable must be false, and since <math>\mathbb{R} \supset A</math> we have that <math>\mathbb{R}</math> is uncountable.
  
−
Suppose that the set <math>A=\{x\in\mathbb{R}:0<x< 1\}</math> is countable. Let <math>\{\omega_1, \omega_2, \omega_3, ...\}</math> be any  enumeration of the elements of <math>A</math>. Consider the binary expansion of each <math>\omega_i</math>. For diedic rationals, take only the expansion terminating in an infinite chain of zeros, so that we have a unique binary expansion for each element of <math>A</math>. Say <math>\omega_i=(.b_{i1}b_{i2}b_{i3}...)_2</math> for all <math>i</math>. Now construct <math>\omega=(.b_1b_2b_3...)_2</math> such that <math>b_i=1-b_{ii}</math> for all <math>i</math>. So <math>\omega</math> is different from <math>\omega_i</math> for all <math>i</math>. So <math>\omega\nin A</math>. But <math>\omega\in\mathbb{R}:0<\omega<1</math>, a'' contradiction''. So <math>\mathbb{R}</math> is uncountable.
+
An alternative proof uses [[Cantor's Theorem]], which says that for all sets <math>S</math>, we have <math>|S|<|\mathcal{P}(S)|</math>, where <math>\mathcal{P}(S)</math> is the [[power set]] of <math>S</math>. First, we note that the [[Cantor set]] <math>\mathcal{C}</math> has cardinality <math>2^{\aleph_{0}}>\aleph_{0}</math>, and since <math>\mathcal{C}\subset\mathbb{R}</math>, there is an injection <math>f:\mathcal{C}\rightarrow\mathbb{R}</math> and thus <math>|\mathbb{R}|\geq 2^{\aleph_{0}}>\aleph_{0}</math>, so <math>\mathbb{R}</math> is uncountable. In fact, it turns out that <math>|\mathbb{R}|=2^{\aleph_{0}}</math>.
  
 
==See Also==
 
==See Also==
Line 14: Line 16:
 
* [[Infinite]]
 
* [[Infinite]]
 
* [[Finite]]
 
* [[Finite]]
 +
 +
 +
{{stub}}
 +
 +
[[Category:Definition]]
 +
[[Category:Set theory]]

Latest revision as of 19:53, 13 October 2019

A set $S$ is said to be uncountable if there is no injection $f:S\to\mathbb{N}$. Assuming the Axiom of choice, every set that is not uncountable is either finite or countably infinite. The most common example of an uncountable set is the set of real numbers $\mathbb{R}$.

Proof that $\mathbb{R}$ is uncountable

We give an indirect proof here. This is one of the most famous indirect proofs and was first given by Georg Cantor.

Suppose that the set $A=\{x\in\mathbb{R}:0<x< 1\}$ is countable. Let $\{\omega_1, \omega_2, \omega_3, ...\}$ be any enumeration of the elements of $A$ (in other words, take an injection $f: A \to \mathbb{N}$, and denote $\omega_i = f(i)$).

Consider the decimal expansion of each $\omega_i$, say $\omega_i=0.b_{i1}b_{i2}b_{i3} \ldots$ for all $i$. Now construct a real number $\omega= 0.b_1b_2b_3 \ldots$, by choosing the digit $b_i$ so that it differs from $b_{ii}$ by at least 3 and so that $b_i$ is never equal to 9 or 0. It follows that $\omega$ differs from $\omega_i$ by at least $\frac{2}{10^i}$, so $\omega \neq \omega_i$ for every $i$. Thus, $\omega \not \in A$. However, $\omega$ is clearly a real number between 0 and 1, a contradiction. Thus our assumption that $A$ is countable must be false, and since $\mathbb{R} \supset A$ we have that $\mathbb{R}$ is uncountable.

An alternative proof uses Cantor's Theorem, which says that for all sets $S$, we have $|S|<|\mathcal{P}(S)|$, where $\mathcal{P}(S)$ is the power set of $S$. First, we note that the Cantor set $\mathcal{C}$ has cardinality $2^{\aleph_{0}}>\aleph_{0}$, and since $\mathcal{C}\subset\mathbb{R}$, there is an injection $f:\mathcal{C}\rightarrow\mathbb{R}$ and thus $|\mathbb{R}|\geq 2^{\aleph_{0}}>\aleph_{0}$, so $\mathbb{R}$ is uncountable. In fact, it turns out that $|\mathbb{R}|=2^{\aleph_{0}}$.

See Also


This article is a stub. Help us out by expanding it.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Uncountable&oldid=110292"