Saturday, September 25, 2010

A glimpse of Cantor's paradise

This is an article I wrote for a maths newsletter



Modern ideas about infinity provide a wonderful playground for mathematicians and philosophers. I want to lead you through this garden of intellectual delights and tell you about the man who created it — Georg Cantor.
George Ludwig Phillipp Cantor was born St. Petersburg, Russia in 1845. When he was eleven years old his family moved to Germany and settled in Frankfurt, the home city of his father. Cantor ultimately became famous because of the mathematical talent on his father's side.
First he attended Polytechnic college, Zurich to study engineering because his father wanted him to be a shining star in Engineering firmament. After a semester, he asked his father's permission to transfer to University of Berlin, where he could study mathematics. As a university student in Berlin he was president of the mathematical society and met his friends every week in a wine house...to discuss mathematics! Within four years he completed both undergraduate and doctorate degrees. In 1872 he was appointed extraordinary professor at Halle, and began his life-long study of infinite sets.
A mathematical challenge by a colleague at Halle led Cantor to his study of the infinite in 1870s. Cantor was not the first mathematician to formalize the concept of the infinite. Prior to Cantor, Richard Dedekind made the first step by introducing the concept of recognizing the infinite rather than constructing it. Dedekind took the natural numbers 1,2,3,4,..... as the paradigm example of an infinite set and defined a set as infinite if the natural numbers an be put into a one-to-one correspondence with the that set, or a subset of it. Thus the natural numbers are infinite by definition and so are the integers, rational numbers and the real numbers.

The simplest infinite set is the set of natural numbers

N = {1, 2, 3, 4,......}
Let's see how does this compare to other infinite sets.
Consider this example
{1001, 1001, 1002, ….}

You might say this set is smaller than N, hence it contains 1000 fewer numbers.

But according to Dedekind's concept of infinite, an one-to-one correspondence can be made with N as follows.
1 -------------> 1001
2 -------------> 1002
3 -------------> 1003
. .
. .

Since each element in N pairs off with one element in {1001, 1002, 1003,....} and vice versa, the sets must have the same "size", or, to use Cantor's language, the same cardinality.
Cantor had two interesting questions : First, can infinity be recognized without making reference to the natural numbers? Second, are there different degrees of infinity?
Cantor answered his first question by defining a set as infinite if it can be put into an one-to-one correspondence with a proper subset of itself, that is a subset other than itself. Set of natural numbers obviously satisfies this condition.
Just consider this mapping
0->1, 1->2, 2->3,.........
This shows that any set that satisfies Dedekind's definition automatically satisfies Cantor's definition. His answer to the first question opened the possibility of there being different degrees of the infinite. He introduced two new terms to distinguish different sets, cardinality, that is, how many members it has and order type. He noted that although the positive and negative integers have equal cardinality, they differ in order-type. So Cantor used Hebrew letter $\aleph $, (pronounced "aleph") to denote cardinality and Greek letter ω to denote order-type. Order-type is the attribute which distinguishes the sets that has a least element, but a greatest and sets that has a greatest element, but a least.

He defined two sets as equinumerous if they could be put to an one-to-one correspondence. Then he showed positive rational numbers are equinumerous with positive integers. But positive rational numbers couldn't be put into a less-than/ greater-than relation as in natural numbers, so he arranged in an ingenious way!

So all the rational numbers can be written as a list as follows:
1/1, 2/1, 1/2, 1/3, …...

Then he tackled the problem of finding the cardinality of the set of real numbers and proved that they are not equinumerous with integers. There are strictly more real numbers than integers.


If the real numbers between zero and one are equinumerous with the positive integers, than they can be listed out in a sequence like this

    1. 0.12034
    2. 0.41233
    3. 0.398554
    4. 0.777776
    5. 0.146231
    6. 0.238765
Here comes Cantor's great insight. What he did was take a diagonal of digits as which are highlighted above and add 1 to each digit. This constructs a new real number 0.229846.... that can't be in the table because it differs from each number listed. This contradicts our first assumption that the set of real numbers and the set of natural numbers have the same cardinality — is false.

The next question asked by Cantor remains open to this day : Are there only two types of infinite subsets of the real numbers, those equinumerous to the real numbers and those equinumerous to the integers? He believed that there are only two types, but he couldn't prove it. This conjecture known as Continuum hypothesis is not yet proven or dis-proven.
Twenty two years after Cantor's death Kurt Gödel showed that the continuum hypothesis cannot be disproved using standard mathematics, and after another 23 years Paul Cohen showed that neither can it be proved. Today mathematicians and logicians are still debating this fascinating question.

Sunday, June 27, 2010

Fermat’s last theorem

A beautiful documentary which narrates the story of Andrew Wiles, who proved Fermat’s last theorem in 1994. Ten-year-old Andrew Wiles read about this 400 years old problem in his local Cambridge library, he dreamt of solving the problem that had haunted so many great mathematicians.

"Here was a problem, that I, a ten-year-old, could understand and I knew from that moment that I would never let it go. I had to solve it."

When he reached college, he spent time studying various approaches that great mathematicians of 18th and 19th century who tried to prove the conjecture. In 1986 Another mathematician found a link between some properties of elliptic curves (Taniyama-Shimura conjecture) and the problem.

After six years of working alone in 1993 he managed to achieve his childhood dream.

"You can't really focus yourself for years unless you have undivided concentration, which too many spectators would have destroyed"

What other mathematical documentaries are you fond of?

This would be a great place to share them :)

Technorati Tags: ,

Wednesday, May 12, 2010

The road not taken


I shall be telling this with a sigh
Somewhere ages and ages hence:
Two roads diverged in a wood, and I--
I took the one less traveled by,
And that has made all the difference
Robert Frost

Saturday, May 1, 2010

Dangerous Knowledge



A timeless documentary looking at four brilliant mathematicians (Georg Cantor, Ludwig Boltzmann, Kurt Gödel and Alan Turing) whose genius has profoundly affected us, but which tragically drove them insane and eventually led to them all committing suicide.

It starts with the presenter David Malone saying
"Beneath the surface of the world...
are the rules of science.But beneath them, there is
a far deeper set of rules.
A matrix of pure mathematics,
which explains the nature
of the rules of science,and how it is we can understand
them in the first place."


These four great mathematicians shook the foundation of mathematics and science and introduced a whole new world of mathematics.

Thursday, December 31, 2009

Happy new Decade !


It's last few minutes of another year, not just an year it's a decade. WE are going to set foot on the second decade of this millennium.

The new year starts for us in the best way, with exams starting on 11th January :P.
I hope to blog more in the coming year.

May all your wishes come true in new decade!

Saturday, July 18, 2009

Convert linux package files one to another easily

This is a familiar problem for most of the people who are using Linux. Software for Linux are available in many formats. Most popular package managers are rpm on RedHat related distributions(Fedora, CentOS, SUSELinux...) and deb on debian related dists( Debian, ubuntu, Mint...). If they are distributed as .deb or .rpm it's relative easy to install with a single command line.
Sometimes it's very difficult to find deb for an rpm only (or vice versa).
I spent some time searching for a tool to convert .deb to .rpm(still google chrome is ditributed as .deb only).
So I found this tool written in Perl very useful. It's Alien, a script which can convert between .rpm, .deb, .slp and tar.gz(.tgz)
Download it from here .
Unzip it and makesure your system has perl installed and perl version is 5.004 or greater .If not install the latest version by

$sudo apt-get install perl (on Debian distributions)

go into the folder from terminal and type to start installing.
$ perl Makefile.PL
$ make
sudo make install

and it will be installed, and check its man pages for more details.
Its very easy to convert a foriegn package format to the native packaging format of your distribution.
Like
to convert an rpm to .deb on Ubuntu

sudo alien -d file_name.rpm

file_name.deb will be generated.
But converting vice versa is a different story, such as converting a .deb to an .rpm on Ubuntu will give dependency problems. :(
Using verbose option as an command line argument, you can see what alien is doing behind the scenes.


So, no more problems of searching for rpms for deb only softwares :-)

May, Google be with you :P