AoPSWiki

Want to learn how to tackle those tough AMC/AIME/Olympiad counting and probability problems? Check out Art of Problem Solving's Intermediate Counting & Probability by David Patrick.

Personal tools

Search

Toolbox

Uncountable

From AoPSWiki

A set $S$ is said to be uncountable if there is no injection $f:S\to\mathbb{N}$ . 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$ . 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 not every $b_i$ is 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$ and $\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.

See Also

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

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/Uncountable"

Categories: Stubs | Definition | Set theory

Do you have what it takes to be the next brilliant trader, researcher, or developer at Jane Street Capital? Find out in the Careers in Mathematics Forum.

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us