Even “More” Infinite Sets

May 20, 2009 17:41 by scibuff

In my previous post (you should read it first before continuing here), I wrote about a little bit about infinite sets and how we can get a sense of size for some of them. This time, I will give a solution to a problem which will, together with the previous result, demonstrate that sets with infinitely many elements have a “measure” of size, and that not all infinite sets are “equally” infinite.

Problem: Show set of real numbers between 0 and 1 with decimal representations consisting of 1s or 9s, i.e. $S=\left \{0.1, 0.9, 0.11, 0.99\cdots \right \}$ is uncountable.

Solution: To solve this problem we will use a proof by contradiction just as we did before.

Suppose, that similarly as in the last problem, we can put our $S$ into a one-to-one correspondence with the set of natural numbers $\mathbb{N}=\left \{0, 1, 2, 3,\cdots \right \}$. In other words, we can create a list of ALL elements in our set (just as we did before) like so:

$0\rightarrow s_{0}$

$1\rightarrow s_{1}$

$2\rightarrow s_{2}$

$\vdots$

Now, consider any such arbitrary listing of the elements of $S$, for example, this one:

$s_{0}=0.111111\cdots$

$s_{1}=0.999999\cdots$

$s_{2}=0.191919\cdots$

$s_{3}=0.919191\cdots$

For the following argument the order of the elements on the list is irrelevant. The important thing is we have listed them ALL. Now, suppose with create a number $s$ in the following way:

• Make the first (decimal) digit of $s$ be different from the first (decimal) digit of $s_{0}$, i.e. 9
• Then make the second (decimal) digit of $s$ be different from the second (decimal) digit of $s_{1}$, 1
• The third (decimal) digit of $s$ to be different from the third (decimal) digit of $s_{2}$, i.e. 9
• The fourth(decimal) digit of $s$ to be different from the fourth (decimal) digit of $s_{3}$, i.e. 1
• etc …

It is relatively easy to show that a number created in such a way as $s$ CANNOT be on our list. If $s$ were on the list then $s = s_{n}$ for some $n\in \mathbb{N}$. So, in particular, the n-th (decimal) digit of $s$ must be equal to the n-th (decimal) digit of $s_{n}$. But that is not possible by the very definition of $s$.

On the other hand, set $S$ is the set of all real numbers between 0 and 1 with decimal representations consisting of 1s or 9s, in particular, $s\in S$.

The assumption that $S$ is countable led us to conclude that $s\notin S$ and at the same time $s\in S$, which is impossible. Therefore $S$ must be uncountable.

On a side note: $S$ can actually be put into one-to-one correspondence with the entire set of real numbers (which also true of any open interval of non-zero length)

Infinite Sets

May 20, 2009 13:56 by scibuff

I distinctly remember one day in second grade when the day after our first class on multiplication my friend infamously claimed that

$\frac{1}{0}=\infty$

Although he was definitely incorrect in his thinking and reasoning, because division be zero has no meaning when it comes to real numbers (or integers), there are cases, such as  The Riemann Sphere or a one-element field where the multiplicative identity coincides with the additive identity, when the equation above is actually true (and well defined).

It is sometimes quite tempting (and even useful) to consider

$\lim_{x\to 0}\frac{1}{x}=\frac{\lim_{x\to 0}1}{\lim_{x\to 0}x}=\frac{1}{0}=\infty$

The main problem with allowing the division by zero is that it results in logical fallacies such as 1=0 (actually, one can equate any two numbers using it). Eventually, mathematicians found a way to define limits rigorously without infinitesimal quantities needed by Newton and Leibnitz when Cauchy and Weierstrass laid down the foundation of modern analysis.

The next question from Yahoo Answers is related to a different kind of infinity – the kind that deals with sets. The works of Georg Cantor between 1874 and 1884 are the origin of set theory in which he established the importance of one-to-one correspondence between sets, defined infinite and well-ordered sets, and proved that the real numbers are “more infinite” than the natural numbers. The diagonalization argument he used demonstrates a powerful and general technique that has since been used in a wide range of proofs such as this one.

Problem: Determine whether the set of real numbers between 0 and 1 with decimal representations consisting of 1s, i.e. $S=\left \{0.1, 0.11, 0.111,\cdots \right \}$ is countable or uncountable?

Definitions:

• A function $f:A\rightarrow B$ is bijective if and only if for every $b\in B$ there is exactly one $a\in A$ such that $f(a)=b$
• A set $S$ is said to be countable if there exists a bijective function $f:\mathbb{N}\rightarrow S$ where $\mathbb{N}=\left \{0, 1, 2, 3,\cdots \right \}$ is the set of natural numbers.

Solution:

Let us look at set $S=\left \{0.1, 0.11, 0.111,\cdots \right \}$ and consider the following list:

$0:\ 0.1$

$1:\ 0.11$

$2:\ 0.111$

$\vdots$

It is easy to see that our set $S$ can be easily put into a one-to-one correspondence with the set of natural numbers $\mathbb{N}=\left \{0, 1, 2, 3,\cdots \right \}$, e.g. the correspondence is given by the list (function defined) above.

To be precise, let $f:\mathbb{N}\rightarrow S$ be given by

$f(n)=\overset{k=n}{\underset{k=0}{\sum}}10^{-(k+1)}$

To show that $f$ is bijective, we need to show that  for every $s_{n}\in S$ there is exactly one, i.e. a unique, $n\in \mathbb{N}$ such that $f(n)=s_{n}$.

Consider an arbitrary $s_{m}\in S$. Since

$s_{m}=0.\overset{m}{\overbrace{111\cdots 111}}$

we have

$s_{m}=0.1+0.01+\cdots+0.\overset{m\ 0s}{\overbrace{000\cdots 000}}1 =10^{-1}+10^{-2}+\cdots + 10^{-(m+1)}$

and so by taking $n=m$ we get

$s_{m}=10^{-1}+10^{-2}+\cdots + 10^{-(m+1)}=\overset{k=m}{\underset{k=0}{\sum}}10^{-(k+1)}=f(m)$

Therefore, for every $s_{n}\in S$ we have proven the existance of (at least one) $n\in \mathbb{N}$ such that $f(n)=s_{n}$.

To show uniqueness, we need to demonstrate that if $f(n)=f(m)$ then $n=m$. The easiest way to accomplish this is to use proof by contrapositive, that is, the fact that

$f(n)=f(m)\Rightarrow n=m$

is equivalent to

$n\neq m\Rightarrow f(n)\neq f(m)$

Let $n,m\in \mathbb{N}$ be such that $n\neq m$. Without loss of generality, assume $n < m$ (otherwise rename them). Then it follows that there exist $l>0:l\in \mathbb{N}$ such that $n=m+l$. Therefore

$f(n)=f(m+l)$

$f(m+l)=10^{-1}+10^{-2}+\cdots+10^{-m}+10^{-(m+1)}+10^{-(m+2)}+\cdots+10^{-(m+l+1)}$

$f(m+l)=\overset{f(m)}{\overbrace{10^{-1}+10^{-2}+\cdots+10^{-m}+10^{-(m+1)}}}+10^{-(m+2)}+\cdots+10^{-(m+l+1)}$

$f(m+l)=f(m)+10^{-(m+2)}+\cdots+10^{-(m+l+1)}$

$f(m+l)=f(m)+10^{-(m+1)}\overset{f(l-1)}{\overbrace{(10^{-1}+\dots+10^{-l})}}$

$f(m+l)=f(m)+10^{-(m+1)}f(l-1)$

Since $l>0$ it follows that $f(l-1)\geq10^{-1}>0$ and so we have

$f(n)-f(m)=f(m+l)-f(m)=10^{-(m+1)}f(l-1)>0$

$f(n)-f(m)\neq 0$

$f(n)\neq f(m)$

thus proving the uniqueness. Therefore $f:\mathbb{N}\rightarrow S$ is a bijective function and so $S$ is countable.