AoPSWiki

Looking for a challenging algebra text? Preparing for MATHCOUNTS or the AMC exams?
Check out Art of Problem Solving's Introduction to Algebra by Richard Rusczyk.

Personal tools

Search

Toolbox

Uncountable

From AoPSWiki

(Redirected from Uncountably many)

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

Add a glimpse of the Art of Problem Solving Forum to your own site!
Click here for details!

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