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"

m (fixed spelling error "diedic")
(categories)
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>. A well-known example of an uncountable set is the set of [[real number]]s <math>\mathbb{R}</math>.
 
A set <math>S</math> is said to be '''uncountable''' if there is no [[injection]] <math>f:S\to\mathbb{N}</math>. A well-known example of an uncountable set is the set of [[real number]]s <math>\mathbb{R}</math>.
  
−
=== Proof that <math>\mathbb{R}</math> is uncountable ===
+
== Proof that <math>\mathbb{R}</math> is uncountable ==
  
 
We give an indirect proof here. This is one of the most famous indirect proofs and was given by George Cantor.
 
We give an indirect proof here. This is one of the most famous indirect proofs and was given by George Cantor.
Line 14: Line 12:
 
* [[Infinite]]
 
* [[Infinite]]
 
* [[Finite]]
 
* [[Finite]]
 +
 +
 +
{{stub}}
 +
 +
[[Category:Definition]]
 +
[[Category:Set theory]]

Revision as of 20:58, 7 December 2007

A set $S$ is said to be uncountable if there is no injection $f:S\to\mathbb{N}$. A well-known 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 given by George 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 binary expansion of each $\omega_i$. For dyadic rationals, take only the expansion terminating in an infinite chain of zeros, so that we have a unique binary expansion for each element of $A$. Say $\omega_i=(.b_{i1}b_{i2}b_{i3}...)_2$ for all $i$. Now construct $\omega=(.b_1b_2b_3...)_2$ such that $b_i=1-b_{ii}$ for all $i$. So $\omega$ is different from $\omega_i$ for all $i$. So $\omega\not\in A$. But $\omega\in\mathbb{R},0<\omega<1$, a contradiction. So $\mathbb{R}$ is uncountable.

See Also


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

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