We accepted that although a set (for example rational numbers) was infinite, it could be countable. But all infinite sets are not countable. We should show that real numbers are uncountable.
At first, we show that $\mathbb{R}=(-\infty,\infty)$ is corresponding to open interval $(0,1)$. It is very simple, because we have only to arrange the function
\[ f(x)=\tan \left(x-\frac{1}{2}\right)\pi, \quad x\in (0,1) \]
It may be kind of weird. But the function must have been familiar to you.
Hence, we decide to show that open interval $(0,1)$ is uncountable. The proof is by contradiction. Let the open interval $(0,1)$ be the set $I$. If $I$ is countable, then all elements $x$ of $I$ can be listed in any order.
$x_1=0.c_{11}c_{12}c_{13}\cdots$
$x_2=0.c_{21}c_{22}c_{23}\cdots$
$x_3=0.c_{31}c_{32}c_{33}\cdots$
$\quad \cdots \cdots \cdots$
$x_n=0.c_{n1}c_{n2}c_{n3}\cdots$
$\quad \cdots \cdots \cdots$
In here, $c_{ij}$ is a single digit figure from $0$ to $9$ and suppose that for a $i$, all $c_{ij} (j=0,1,\cdots \infty)$ of $x_i$ are not nine and are not zero, because $0.999\cdots =1$ and $0.000\cdots =0$ are out of interval.
This list is with no limit. However, after listing, we are able to make a new number $y$ by the following procedure.
Let $y$ be $0.d_1d_2d_3\cdots$ where $d_i (i=0,1,\cdots \infty)$ is also a single digit figure. Then, we pick a number different from $c_{11}$ as $d_1$. Next, we pick a number different from $c_{22}$ as $d_2$, and also do a number different from $c_{33}$ as $d_3$. Furthermore we keep carrying on this choice with no limit. As a result, the number $y$ becomes a new number different from every $x_i$. Although all $x_i$ is all elements of $I$, we have gotten a new number $y$. It is a contradiction. Therefore, open interval $I$ is not countable and real numbers become uncountable.
It is the famous Cantor's diagonal argument. How do you feel about two procedures with no end?
2013/02/27
2013/02/20
countable sets
A one-to-one correspondence of two sets means that there is a injective or surjective function between them. That is, two sets are one-to-one correspondent if and only if there is a into or onto mapping.
If one of two sets is the domain $\mathbb{N}$ and the other is the range $A=\left\{ a_n | n\in\mathbb{N}, a_n\in \mathbb{R} \right\}$, the function expresses a infinite real number sequence as follow.
\[ f : n\in\mathbb{N}\rightarrow a_n\in A \]
You may not suspect that the number of $a_n$ is countable with no limits.
[countable or uncountable]
A set is said to be countable, if it is finite or countably infinite. Otherwise, a set is uncountable.
In other words, if there is a one-to-one correspondence between $\mathbb{N}$ and a set $A$, then $A$ is countable. If a range set $A$ is finite, it bothers nobody. Even if the range set is infinite, it is possible for the set to be countable as a sequence noted above.
In this point of view, rational numbers are countably infinite. We will be able to accept it by making the sequence as follow.
\[ \frac{1}{1}, \frac{1}{2}, \frac{2}{2}, \frac{1}{3}, \frac{2}{3}, \frac{3}{3}, \frac{1}{4}, \frac{2}{4}, \frac{3}{4}, \frac{4}{4}, \cdots \]
This sequence is clearly countable and becomes rational numbers in addition to a plus or minus sign and zero. It may be most simple than any other proofs.
If one of two sets is the domain $\mathbb{N}$ and the other is the range $A=\left\{ a_n | n\in\mathbb{N}, a_n\in \mathbb{R} \right\}$, the function expresses a infinite real number sequence as follow.
\[ f : n\in\mathbb{N}\rightarrow a_n\in A \]
You may not suspect that the number of $a_n$ is countable with no limits.
[countable or uncountable]
A set is said to be countable, if it is finite or countably infinite. Otherwise, a set is uncountable.
In other words, if there is a one-to-one correspondence between $\mathbb{N}$ and a set $A$, then $A$ is countable. If a range set $A$ is finite, it bothers nobody. Even if the range set is infinite, it is possible for the set to be countable as a sequence noted above.
In this point of view, rational numbers are countably infinite. We will be able to accept it by making the sequence as follow.
\[ \frac{1}{1}, \frac{1}{2}, \frac{2}{2}, \frac{1}{3}, \frac{2}{3}, \frac{3}{3}, \frac{1}{4}, \frac{2}{4}, \frac{3}{4}, \frac{4}{4}, \cdots \]
This sequence is clearly countable and becomes rational numbers in addition to a plus or minus sign and zero. It may be most simple than any other proofs.
2013/02/15
coffee break
Recently, almost in Jan/2013, I enjoyed following entertainments. All is made in Japan or is translated into Japanese.
[Translated Novels]
☆☆The Grayman (Mark Greaney)
☆☆Mission M.I.A. (J.C.Pollock)
☆☆Dead Shot (Jack Coughlin with Donald A.Davis)
☆☆Soft Target (Stephen Hunter)
[Japanese Novels]
☆☆Diner (Yumeaki Hirayama)
☆☆Shukusin 4 (Baku Yumemakura) -completed
☆☆Sora no Kobushi (Mitsuyo Kakuta)
☆☆Jyugan (Arimasa Oosawa)
[Comics]
☆☆☆☆Kyo no necomura-san 4,5 (Yoriko Hoshi) -to be continued
[Movies]
☆☆☆☆Mahoro eki mae Tada Benriken(Eita, Ryuhei Matsuda)
☆☆Shodou girls(Youko Narumi, Rio Yamashita, Nanami Sakuraba)
[Games]
☆☆☆☆Ninja Gaiden sigma(ps3)
☆☆☆Ninja Gaiden sigma2(ps3)
☆☆Ninja Gaiden 3(ps3)
As there are many holidays from end of December to January, I enjoyed many books. However, I was not able to find exciting books which I want to push.
Movie "Mahoro eki mae Tada Benriken" was nice. It is better than the original(Novel awarded the prize of Naoki-sho, Shion Miura). I think it owed good performances of actors Eita and Ryuhei Matsuda. The sequel is broadcast on the TV program by same casts.
In series of games "Ninja Gaiden", "sigma " which is the first work is best. As the number of the work goes on, the contents become more joyless. No cigar. Originals are made in Xbox360 and I do not have those. As those are said to be different from ps3 works, I regret it.
[Translated Novels]
☆☆The Grayman (Mark Greaney)
☆☆Mission M.I.A. (J.C.Pollock)
☆☆Dead Shot (Jack Coughlin with Donald A.Davis)
☆☆Soft Target (Stephen Hunter)
[Japanese Novels]
☆☆Diner (Yumeaki Hirayama)
☆☆Shukusin 4 (Baku Yumemakura) -completed
☆☆Sora no Kobushi (Mitsuyo Kakuta)
☆☆Jyugan (Arimasa Oosawa)
[Comics]
☆☆☆☆Kyo no necomura-san 4,5 (Yoriko Hoshi) -to be continued
[Movies]
☆☆☆☆Mahoro eki mae Tada Benriken(Eita, Ryuhei Matsuda)
☆☆Shodou girls(Youko Narumi, Rio Yamashita, Nanami Sakuraba)
[Games]
☆☆☆☆Ninja Gaiden sigma(ps3)
☆☆☆Ninja Gaiden sigma2(ps3)
☆☆Ninja Gaiden 3(ps3)
As there are many holidays from end of December to January, I enjoyed many books. However, I was not able to find exciting books which I want to push.
Movie "Mahoro eki mae Tada Benriken" was nice. It is better than the original(Novel awarded the prize of Naoki-sho, Shion Miura). I think it owed good performances of actors Eita and Ryuhei Matsuda. The sequel is broadcast on the TV program by same casts.
In series of games "Ninja Gaiden", "sigma " which is the first work is best. As the number of the work goes on, the contents become more joyless. No cigar. Originals are made in Xbox360 and I do not have those. As those are said to be different from ps3 works, I regret it.
2013/02/07
functions
In the preceding post (real number system 5), we assumed any point on a real number line was corresponding to a real number with no fail. Nobody will not believe it. If two sets (in the case, a real number line and real numbers) have some kind of relationship, there will be a function. Let us define a function.
[function, domain, and range]
A relation from a set $X$ to a set $Y$ which is many to one or one to one is called a function from $X$ to $Y$. Then, a set $X$ is said to be the domain of the function and a set $Y$ is said to be the range of the function. These relations are written by
\[ f : X\rightarrow Y \]
or, in familiar form,
\[ f(x)=y,\quad (x\in X, y\in Y) \]
Here, $x$ is said to be a argument of the function, and $y$ is said to be a value of the function.
The expressions, which you have known enough, could be extended in general. For instance, the following forms are available.
\[ f : X\times X\rightarrow Y, \quad or\quad f(x_1,x_2)=y,\quad (x_1,x_2\in X, y\in Y) \]
If every element of the range of the function is related to some elements of the domain of the function, the function is surjective, or is said to be the mapping from $X$ onto $Y$. That is, for all $y\in Y$, there are some $x$ such that $f(x)=y$. Do not confuse, it is not always true that $x$ is one. The term of 'mapping ' is equivalent to 'function '.
If one element of the range of the function is related to only one element of the domain of the function, the function is one to one, or injective, or is said to be the mapping from $X$ into $Y$. That is, if $f(x_1)=f(x_2)$, then $x_1=x_2$. The contrapositive of the statement is that if $x_1\ne x_2$, then $f(x_1)\ne f(x_2)$.
Especially, two sets $X$ and $Y$ are said to be in one-to-one correspondence if there exists a one to one surjective function with domain $X$ and range $Y$. A One-to-one correspondence means the mapping from $X$ onto and into $Y$. Hence, two sets in one-to-one correspondence have the same number of elements.
[function, domain, and range]
A relation from a set $X$ to a set $Y$ which is many to one or one to one is called a function from $X$ to $Y$. Then, a set $X$ is said to be the domain of the function and a set $Y$ is said to be the range of the function. These relations are written by
\[ f : X\rightarrow Y \]
or, in familiar form,
\[ f(x)=y,\quad (x\in X, y\in Y) \]
Here, $x$ is said to be a argument of the function, and $y$ is said to be a value of the function.
The expressions, which you have known enough, could be extended in general. For instance, the following forms are available.
\[ f : X\times X\rightarrow Y, \quad or\quad f(x_1,x_2)=y,\quad (x_1,x_2\in X, y\in Y) \]
If every element of the range of the function is related to some elements of the domain of the function, the function is surjective, or is said to be the mapping from $X$ onto $Y$. That is, for all $y\in Y$, there are some $x$ such that $f(x)=y$. Do not confuse, it is not always true that $x$ is one. The term of 'mapping ' is equivalent to 'function '.
If one element of the range of the function is related to only one element of the domain of the function, the function is one to one, or injective, or is said to be the mapping from $X$ into $Y$. That is, if $f(x_1)=f(x_2)$, then $x_1=x_2$. The contrapositive of the statement is that if $x_1\ne x_2$, then $f(x_1)\ne f(x_2)$.
Especially, two sets $X$ and $Y$ are said to be in one-to-one correspondence if there exists a one to one surjective function with domain $X$ and range $Y$. A One-to-one correspondence means the mapping from $X$ onto and into $Y$. Hence, two sets in one-to-one correspondence have the same number of elements.