Infinite processes in the real world

A long time ago, in ancient Greece, one of the philosophers asked a simple yet very important question - is matter infinitely divisible? He of course formulated the question in a much more intuitive way: what will happen if you take a stick and break it in half, than take one of the halves and break it in half again and so on. Thinking about this problem, he concluded that at some point we will not be able to continue breaking the stick. According to him, after a finite amount of time we will reach an indivisible component of matter. He named this indivisible component "atom".
As with any new idea, there were those who believed in it and those who concluded that this idea is wrong. Likely for both sides, there were no means to actually check it so they could argue as much as they wanted.

Even though we are much more advanced today we still don't know the answer to this problem. Ironically we have discovered particles which we named atoms only to find out that they can be split apart as well only a few years later. Although, to be really precise, we need to remember that the problem can be formulated as the "atom" being the basic component of a specific type of mater. In other words, one possible understanding of the problem is that it asks to find a "part" that if divided further looses the recognizable properties of the object we started with. If we formulate the problem in this way, then there are indeed such "atoms" - molecules.

At this point you are probably wondering what is this about and how is it connected to infinity. To understand this lets look on a somewhat famous paradox - the Thomson lamp. Consider a lamp with a toggle switch. Flicking the switch once turns the lamp on. Another flick will turn the lamp off. Now suppose a being able to perform the following task: starting a timer, he turns the lamp on. At the end of one minute, he turns it off. At the end of another half minute, he turns it on again. At the end of another quarter of a minute, he turns it off. At the next eighth of a minute, he turns it on again, and he continues thus, flicking the switch each time after waiting exactly one-half the time he waited before flicking it previously. The sum of all these progressively smaller times is exactly two minutes.
So, in the end, is the lamp on or off?

It turns out that there is no clear answer to this problem. While we know the state of the lamp at any time during the process, we cannot tell what is the state at the end. Now lets return to our original problem. Lets suppose for a second that "atoms" don't exist. With this in mind we can take the being from the lamp paradox and instead of it toggling the switch we will make it break sticks in half. Since there are no atoms, the process doesn't end before two minutes pass. But what do we have after two minutes?

In this case it is rather simple to look on the problem mathematically. Lets substitute the stick for the line [0,1]. The whole process can be described then as just a limit of [0,2^(-n)] when n goes to infinity. The limit is a single point, so that would mean that we will get a "particle" with size and mass equaling zero. However, that would suggest that the matter is build from particles with zero mass, and this is a rather bizarre conclusion.
The only possible result we can get from this line of thought is that if such a being actually exists then there are "atoms". However, if there is no such being then we cannot say anything.

While I would like to finish this post with at least a partial solution to the problems I presented, there is no solution as far as I know. There is, however, a funny "solution" to the Thomson lamp paradox. Lets assign numbers to the states of the lamp - 1 and 0. If we do this then the state of the lamp after n steps is: 1-1+1-1+...+(-1)^n.
Therefore, if we take the limit when n goes to infinity, we will get the state of the lamp after two minutes. So lets see what the limit is.

A=1-1+1-1+1-....

1-A=1-1+1-1+1-....=A
2A=1
A=0.5

As you can see, after two minutes the lamp is half on. :)

Sperner's lemma

If you take a glass of water and then shake it, it turns out that some point in the liquid will remain unmoved - this is known as a real world three dimensional example of the Brouwer fixed point theorem. However, as I once wrote in the past, this example works only if we assume that the matter is continues. If we start to think in terms of atoms, the theorem cannot be applied. While disappointing, it is not surprising. It is after all pretty obvious that a theorem that works with an infinite number of points will not work the same if we use instead a finite (but large) number. But what about the opposite? Can a theorem that is used to prove something about a finite number of objects be used to prove something about an infinite number of them?

The Sperner lemma is an example of such a case. This lemma is sometimes called a combinatorial analog of the Brouwer fixed point theorem. It is called so because it is rather simple to get the fixed point theorem for any dimension from the Sperner lemma for the same dimension. The two dimensional case is:

Given a triangle ABC, and a triangulation T of the triangle. The set S of vertices of T is colored with three colors in such a way that

1. A, B and C are colored 1, 2 and 3 respectively
2. Each vertex on an edge of ABC is to be colored only with one of the two colors of the ends of its edge. For example, each vertex on AC must have a color either 1 or 3.

Then there exists a triangle from T, whose vertices are colored with the three different colors. More generally, there must be an odd number of such triangles.

The general, n-th dimensional case, uses n-dimensional simplex instead of a triangle which is a 2D simplex.

There are a number of different proofs of the lemma, I personally know 3 of them. The usual idea is to show that the lemma works for the 2D space and then use induction to show that it works for all dimensions. While not difficult, this method of proof requires some thought and careful work. Interestingly enough there is also a proof that is both very short and doesn't require induction. It allows to prove the lemma for any given dimension in just one step. So for all those who prefer simple and easy proofs - read on:

To prove the lemma for the n-th dimension all we need to do is:
Let v be an inner vertice in T. Define a linear function of t that moves this vertice to the outer vertice of the same color when t goes from 0 to 1. The volume of any given simplex in T is the determinant of the vectors that correspond to the vertices of the simplex. Since all the vectors are linear functions of t, the volume is a polynomial of degree n. The sum of the volumes is thus also a polynomial of degree n. For t=0 the polynomial is obviously the volume of the outer simplex (for n=2 it is the volume of ABC). However if t is only slightly bigger then zero, we still have a triangulation so the sum of the volumes is the same and therefore the polynomial is a constant. For simplicity lets say that the volume is exactly 1. Now, when t=1 the volume of all the simplexes that are not colored in n colors becomes zero. On the other hand, the volumes of the other simplexes are either 1 or (-1) (depends on orientation). And with this we are done - if the sum of the volumes is 1 there are must be simplexes that have volume 1 but this is only possible if there is an odd number of simplexes with n colors.

Taking Notes

In this post I want to share some ways of working with course notes that I am currently using. As you all know taking notes is one of the most basic parts of studying. While it is possible to do well without it, it usually only means that you are borrowing somebody else notes (or downloading them). However, taking notes and using them are two totally different things. Firstly, handwritten notes tend to differ greatly in quality due to people handwriting and the lecturer. In my case my notes are close to being unreadable for anyone except for me (for some reason I can read what I wrote easily enough, but I have problems reading other people notes). Also, if the lecturer speaks in a disorganized way the notes become difficult to read and understand.
Obviously handwriting and organization of notes is not much of a problem - it is after all perfectly possible to take notes on a computer. Actually, if I were studying a subject that don't have formulas I would use a computer to take notes myself. Since I study math, I do not believe that I should try to take notes on a computer, although I know people who do just that.

However, the really difficult part comes when you need to go over your notes. In the first and second year the lecturers tend to give you all the material in a very detailed way, but with time they stop doing this. Instead you are now supposed to figure all the extra stuff yourself. As a result, you basically need to add to your notes on your own. So how do you do this, while still keeping the notes organized and in a format that allows you go over them easily?

At this point of time I cannot honestly say that I found a real solution to this question. But I managed to come to the conclusion that I need two things. The first thing is to make sure that I have the notes made in an organized way. To do this I make a second (also handwritten) copy of my course notes. In this copy I write all the definitions and theorems (with their proofs) with as much details as I need to understand them. This copy is later used when I need to prepare for the exams.
The second thing is basically a reference list. The idea is to make a list of all the definitions and theorems, as well as links to any useful source of extra information on the topic. It is obvious that such a list should be done on a computer. The end result is basically another version of your notes, but instead of being detailed and organized it is easily to search. This makes it easy to check any general fact you are unsure of. It is especially useful if you want to check some specific definition of the wording of a theorem. Obviously you can do the same thing just by searching on Wikipedia, but using such a reference list makes it much easier - you are able to see what you look for by just taking a glance on it, instead of searching a whole site. Also, making such a list on the computer allows (depending on what software you use) to add extra notes and to modify them easily. Since I do not want to type math formulas myself I ended using Google notebook to clip content (mainly from Wikipedia) and then edit and categorize it the way I want. Unfortunately, Google notebook is the only service I managed to find that had all the features that I wanted.

If you follow all this you will end with three different sets of notes (plus, if available, a textbook). Obviously this is a lot of work, but I feel that this approach allows me to understand the material as well as I can.

Complex numbers and roots

Complex numbers appeared initially as a way to solve equations that don't have real solutions. However, what are we getting from this? We can write that i is the solution to x^2=-1, but what exactly is this result? It is an imaginary number, so it is not something that can represent for example area. The obvious result from this line of thinking is - are complex numbers really needed? What problems do they solve?

Somewhat surprisingly complex numbers solve a lot of different problems or at least make them easier. In this post I want to introduce one particular problem that is solved by using complex numbers. The problem is to define a^b for all values of b and for all values of a except zero. We can partially solve this problem without complex numbers. For example, we can agree that the functions log and exp are defined as usual and then:

a^b=exp(b*Log(a))

This will work for all values of b but only as long as a>0. This is as far as we can get without using complex numbers. It is important to note, that any solution of this problem must agree with the partial solution that we have here. In other words, in order to solve this problem we must basically extend the functions exp and log in such a way that log will be defined for negative values and exp will be defined for all values of log.

As a start, lets try to define exp(z) and log(z):

exp(z)=exp(x+iy)=exp(x)exp(iy)
exp(iy)=cos(y)+isin(y)

We now need to check what we got from this definition. Firstly, if y=0 then exp(z)=exp(x) as we wanted. Secondly:

exp(z+w)=exp(x+iy+a+ib)=exp(x+a)exp(iy+ib)
exp(x+a)exp(iy+ib)=exp(x)exp(a)[cos(y+b)+isin(y+b)]
cos(y+b)+isin(y+b)=cos(y)cos(b)-sin(y)sin(b)+isin(y)cos(b)+icos(y)sin(b)
cos(y+b)+isin(y+b)=[cos(y)+isin(y)][cos(b)+isin(b)]
exp(z+w)=exp(x)exp(a)exp(iy)exp(ib)
exp(z+w)=exp(x)exp(iy)exp(a)exp(ib)
exp(z+w)=exp(x+iy)exp(a+ib)=exp(z)exp(w)

The last last thing we want to check is the derivative. This is done in a similar way, and is left as an exercise.
As you can see it is rather easy to extend exp to the complex numbers. Extending log is more difficult. Lets start with what we want the function to do. We want that for any complex number z:

exp(log(z))=z

So, we want to say that if exp(w)=z then log(z)=w.

Unfortunately, we cannot use this as a definition for log. The problem is that there are many different complex numbers that satisfy this equation. According to the definition of exp:

exp(w+2(pi)i)=exp(w)exp(2(pi)i)=exp(w)[cos(2pi)+isin(2pi)]=exp(w)=z

This is obviously a problem. To solve this problem we must remove part of the complex numbers. There are many different ways to do this removal. In this post I decided to remove the numbers {z|z=ik, k=0 or k>0}.
Now that we do not have these numbers we can define log. We know that any complex number z can be written as z=r*exp(it), where t represents the angle between the line that connects zero and z. Obviously exp(it)=exp(it+2(pi)i). However, since we have some numbers removed we cannot go in a circle around zero. Therefore, for numbers that have a negative real or complex part we will take t to be 2pi minus the angle. This solves our little problem because we now have exactly one value of t assigned to every z. And now we can define log exactly as we tried to do before. Since the negative numbers were not removed we have log defined for negative numbers as well. For example: log(-1)=i*pi.

Now that we have this we can indeed define that for all real a,b such that a is not zero:

a^b=exp(b*Log(a))

This is true for complex numbers as well, but this a different topic.

A common misunderstanding

A few days ago, one of the lectures in the university told us about a funny (but real) news report he once heard on TV. It was shortly after the discovery that 2^(42,643,801)-1 is a prime. (For more information about this go to Mersenne prime search website). On this TV program a reporter was interviewing a math professor. The conversation went like this: (R= reporter, P=professor)

R: So what do you have to say about the discovery of the largest prime number 2^(42,643,801)?
P: The number 2^(42,643,801) is not prime since it is an even number. You must have ment to say 2^(42,643,801)-1.
R: Well, they are close enough. The important thing is that this is the largest prime number.
P: It is not the largest. Euclid proved that there is an infinite number of prime numbers so there is no such thing as the largest prime.
R: Is it still correct today that there are infinity many prime numbers?

I really find it hilarious how some people think that a mathematical proof is something that is subject to changes. Sure, sometimes we have errors or we find better proof, but the there is no change in the fact itself. I suppose it is somewhat understandable why people act like this - they are too used to seeing things change. But it is still hilarious to watch, as long as you not part of the discussion.

Analysis and Combinatorics

We often hear about how all mathematics is interconnected, but rarely see clear and simple examples of such connections. In this post I want to show one example in which theorems developed in Calculus are used to solve a range of combinatoric problems.

To begin lets consider the following problem. For any natural number K what is the number of ways it can be written as a sum of powers of two, if we allow each of them to be used only ones? Lets suppose that the number of ways is a(k). It is obvious that a(1)=1, a(2)=1. Lets define a function:

f(x)=a(0)+a(1)x+a(2)x^2+....
a(0)=1

It is easy to see that if a(k) is defined this way then it is also true that:

f(x)=(1+x)(1+x^2)(1+x^4)(1+x^8)......

This is true because if we open the brackets we will get that x^k appears exactly a(k) times. Now lets multiply f(x) by (1-x). It is easy to show that:

(1-x)f(x)=1

You show this by looking on a finite multiplication and then taking limit. However, now we got that:

f(x)=1/(1-x)=1+x+x^2+x^3+x^4+.....

This is true because this is the formula for the sum of the geometric series for any 0<1. style="text-align: center;">F(n)=F(n-1)+F(n-2) , F(0)=0, F(1)=1
f(x)=F(0)+F(1)x+F(2)x^2+....

Lets look on the following multiplications xf(x), x^2f(x). Because of the recursive formula we get:

f(x)(1-x-x^2)=F(0)+(F(1)-F(0))=1

f(x)=1/(1-x-x^2)

The only thing left to do is to calculate the series and we are done. This part is left as an exercise for the bored reader. The important thing is that the same idea works for any different series - this is not something that is true only in a specific case. As such this is indeed an example of how mathematics is interconnected and how calculus that is the study of infinite can be used to solve finite combinatoric problems.

Gabriel's Horn

I didn't write anything about paradoxes for a long time, so here is a little something. Lets look on the volume we get by rotating the graph of the function y=1/x, for x>1. The object we get is called Gabriel's Horn. It is easy enough to show that its volume is finite and in is equal to pi. If we cut the horn in any finite point a we will get that the volume is exactly:If we now take the limit when a goes to infinity we will get that the volume is indeed pi. However the surface area is infinite. For any finite a we will get that it is exactly:


But the limit of this expression is infinity. Now that we know this , we can go on to the description of the paradox. Suppose that you want to paint the Horn with finite amount of paint. Obviously, it is not possible because the surface area is infinite. But you can fill it with a finite amount of paint. Lets now suppose that Horn is made from a transparent plastic. In this case, filling it with paint is the same thing as painting it.

As a result we get that it is both impossible and possible to paint the Horn with finite amount of paint. So which one is true? The solution is in fact rather simple. Firstly lets look on the graph of y=1/2x. Obviously this is again Gabriel's horn, but in a scaled down version. Lets put it inside the original while it is still filled with paint. In this way we painted it from the outside. How did we do it? The answer to this is in the distribution of paint. The thickness of paint is given by g=1/x-1/2x=1/2x. And this is the whole trick. We can paint even an infinite surface, the only thing we need to worry about is allowing the thickness of paint to approach zero in a way similar to this example (we need the integral of the paint distribution to be finite).

Collecting and storing books

For a long time buying books was considered at the very least practical. As long as it was economically sound, having a nice small library at home was without doubt a useful thing. However is this still true now? Naturally, I am not talking about buying fiction (this is after all a math blog).

To better illustrate the question, lets consider the following example. About a year ago some friends of my grandfather gave me a good multi volume encyclopedia. Obviously it is not something that is expected to be used everyday, but I didn't open it even once in all this time. The reason for this is simple - if I want information about some specific subject, it is easier for me to search in the Internet. It is almost certain that there will be an article on this subject on Wikipedia, or some other place.
To a certain degree the same is true even for my math textbooks\notes. Frequently enough I prefer to search on the Internet for a specific definition or proof of a certain theorem. Unfortunately, this is often less successful than searching for staff one can find in an encyclopedia.

As a result we get the following situation - while we have lots of available books it doesn't seem practical to invest money in buying them. This is especially true about buying new editions of books we already have, or books that cover the same topic but use different approaches. This is especially true considering how overpriced some books are.
A possible solution to this is downloading books (for free). While not all books can be downloaded for free from the net, it is possible to find good books on any given topic. For example there is currently a collection of over 600 math books available on bittorent. There is also a nice collection of calculus books on the same site. The only problem with those collections is that they will not remain available forever. In other words, it is a good idea to download it even if you don't need it right now.

This however brings us to a second problem. While it is possible to download lots of books from the net, we also need some way to organize them so that it will be possible to use them. Another problem is keeping an up to date backup (you wouldn't want to lose 10GB of books suddenly would you?).
I must admit that I don't feel that I managed to make any serious progress in solving either of these two problems. For backup, I long ago decided that burning my files to CD or DVD is not a good idea. It becomes difficult to keep track of the backups, and also the discs tend to be damaged so it is not very safe. Another option, is to keep a copy of your files on the web. I personally use Google Docs. It can only be used for pdf files up to 10mb, so some books I cannot upload, but it is really reliable and the way it is build makes organizing books relatively easy. Some times ago I tried to use Scribd for storing some of the large books I have. Unfortunately, it didn't work. They check the files that you upload, and if they notice that you have books that are copyrighted they will delete them. I also tried to use DivShare, but it is rather unreliable and overall not something I would recommend.

In the end the decision whether to have a digital book library or not is a personal one. In my case I decided to do it out of pure love for books. I just cannot say no to an opportunity to have a library. I do hope however that I will manage to make use of all those books I collected...

My library

Over the years I made a little online collection of math and other books. In order to organize and manage this collection better, as well as to share it with other people, I decided to post links to all these books here, on my blog. I hope that you will find this collection of links useful. As of now it is rather small, but I plan to add more books. There is a surprising number of such books available online for free - but it takes time to find them. Some If you have a problem with your book linked from here, please let me know and I will remove the link immediately.
Since most of these books are available for free on the author page, I just linked those pages. In some case, the book is on a site that has no connection with the author. In such a case it is possible that it is an illegal copy - use it on your own risk. I provide the links for educational use only.

If you want to recommend a link for addition, you can leave a comment. In order to keep this post as tidy as possible I will not publish the comment, but I will consider adding the book(s). In order for a book to "qualify" it must be about math, physics or programing and it must be large enough (that is, not an article but an actual book). If a link a broken please leave a comment about it, I will try to fix it if possible.



Math:
1. Elements of Abstract and Linear Algebra - E. H.Connell (author page)
2. Foundations of Combinatorics with Applications - Edward A. Bender, S. Gill Williamson (author page)
3. Graph Theory 3rd Edition - Springer-Verlag Heilderberg (order / author page)
4. Algebraic Topology - Allen Hatcher (author page)
5. A Problem Course in Mathematical Logic - Stefan Balaniuk (author page)
6. Multivariable Calculus - George Cain and James Herod (author page)
7. Calculus - Gilbert Strang (author page )
8. Linear Methods of Applied Mathematics - Evans M. Harrell II and James V. Herod (author page - this book has a rather nasty license)
9. Complex Analysis - George Cain (author page)
10. Linear Algebra, Infinite Dimensional Spaces, and MAPLE - James Herod (author page)
11. Linear Algebra - Jim Hefferon (author page ) This book has complete solutions of exercises.
12. The Geometry and Topology of Three-Manifolds - William P. Thurston (author page)
13. Introduction to Probability - Charles M.Grinstead (author page)
14. Elementary Linear Algebra - Keith Matthews (author page) This book has complete solutions of exercises.
15. Understanding Calculus (author page - this is an online book, you can download it for 5$)
16. Elementary Calculus: An Infinitesimal Approach - H. Jerome Keisler (author page)
17. Combinatorics - Russell Merris (link)
18. Real Analysis - Royden (link)

Programing:
1. Dive into Greasemonkey (author page)
2. SQL server 2008 (link)

General:
1. Flatland: A Romance of Many Dimensions - Edwin A. Abbott (link - there are lots of other books on this site)

Bittorent links:
1. Mathematics - a collection of over 600 math books on different subjects.
2. Calculus Book Folder - a small collection of calculus books. Alternative link.
3. 100 Great Problems of Elementary Mathematics - link.
4. Mathematics As a Science of Patterns - link.

Indescribable numbers

This post is an attempt to explain what the term indescribable number means. Unfortunately, while this is a relatively well know term I frequently see it being misused. To understand it, we must firstly look on the proof that such numbers exist. It is a rather basic proof from set theory. What we need to do is to define two sets:

A={all the mathematical symbols and all the letters}
B={finite words in A}

Now, it is obvious that A is finite. B is not finite but it is only countably infinite (this is the smallest infinity). Therefore, B is smaller than the set of all numbers - R. Since all the possible descriptions are in B we conclude that there are numbers in R that cannot be described at all. Moreover, if you take away all the numbers that can be described the size of R will not change (this is a basic theorem in set theory). From this we can conclude that in fact most numbers are indescribable. This is a perfectly valid example of nonconstructive proof.

Unfortunately, this simple and short proof (I didn't proof all I said, but it is all just basic theorems of set theory) does little to explain what an indescribable number is. Lets consider some examples. For the first example, look on the following set:

C={words in A shorter than one hundred letters}

It is obvious that C is finite. Therefore there is a maximum number described by C. The next integer number (lets call it Y) is thus "the first integer number that cannot be described in 100 letters". But this description is less then 70 letters long. And this means that this number should be in C. Obviously this is a paradox. We got a number that is both in C and not in C.

Here is another example of a similar problem. It is possible to proof that if you randomly choose a real number the probability of it being an indescribable number is 1. So lets randomly choose a number (since we are choosing only one number we don't need the choice axiom). Naturally we get an indescribable number. Well, lets call this number "indescribable number 1". In the case you didn't notice I just gave a description to an indescribable number.

What really is going on is just an indexing problem. It is important to understand that both B and C are just sets of index numbers. If we have such a set we can use it to index another (in our case the set R). Mathematically, description as it was used in those examples is just a function from B to R (or from C to R). But the way we apply the indexing is arbitrary - we can choose any function we want. Lets first look on the 100 letters case. When we defined the set C what we really defined is the pair (C, f). In this pair f is a description function that for any x in C returns a specific number in R (I suppose that all the words in C describe some number, but you can do without it). Since we cannot define Y without firstly defining (C,f) the word ""the first integer number that cannot be described in 100 letters" is assigned by f to some random number. Then when we got a description for Y, we basically created a new pair (C, g). In this pair g is a new function that agrees with f on all C except for one word - ""the first integer number that cannot be described in 100 letters". To this word it assigns Y. For us this may seem illogical, because we think about meaning of words. But in this proof meaning is not important - the words are just a way to index.

With this in mind, lets consider the second example. In this case the number we choose belongs to a set R\f(B). When we gave it a description all we did was to change f in such a way that now this number belongs to f(B). It is obviously not a problem to do such a change (if we wanted to change the function for an infinite amount of values it might have been a problem, but for one index it is always easy to do).

So, what is an indescribable number? After all, we just saw that it is possible to describe any random number. The answer to this is actually simple. Mathematically it is a number that was not indexed by the function f. In normal language it means that it is a number that wasn't described. Form a normal person point of view this is a weird definition, but mathematically it actually makes a lot of sense. The basic idea is that while we have the option to choose any function f, we can only choose one and we cannot change our choice to another function latter on (this is because we need our language to be consistent). Under this conditions it becomes obvious that both examples are just a misunderstanding of what an indescribable number is. You cannot take a number that is not described and give it a description, because the description is already in use and you can have only one number for one description .
But then, what is the point in saying that such numbers exit? It is after all obvious that there are numbers that are not described as of now. Unfortunately this is not what the theorem is about. The point of this theorem is not to say that there are numbers that we didn't describe. This theorem says that no matter what function f we use there are always numbers that are not in f(B). In other words, there are always will be numbers that we didn't describe even if we used all of B for the purpose of such description.

Fractals

A few days ago I stumbled on an excellent collection of fractals. According to the site the collection is no longer updated, but nevertheless the images there are among the best fractal images I ever saw. There is also more fractals by the same author available here. I am somewhat worried about the site disappearing so I am going to download all the images on it to my computer and then upload them to a private Picasa album. This way I am not breaching the copyright on the images and if the page indeed closed down, please leave a comment on this post and I will link my Picasa album to this post.

In the case that you want even more fractal images, here is another site with hundreds of excellent fractals - Fractal world gallery.

Also, I noticed that a lot of visitors to my blog are actually after mathematical wallpapers. Form my own attempts to find such wallpapers I know that they are somewhat of a rarity (at least good ones). I currently have 14 math wallpapers in my Picasa albums, but this is obviously too little (and unfortunately not all of them are good enough to put on a screen). Since there seems to be a demand for such wallpapers I am going to try and get more maybe I will even attempt to draw some myself.

Correct math wrong results

In the previous post I mentioned that in some situations even the math we used is correct, the result we arrive at might not be correct or it might not apply in the real world. In this post I intend to discuss three such examples.

The first example is known as the Tompson lamp problem. Imagine the following situation: You switch a lamp on, than after one minute you switch it off. After 30 seconds you switch it on again, and then after 15 seconds you turn it off. We continue like this for two minutes. Now, is the lamp on or off? There is no real mathematical solution to this problem. One proposed solution is to say that the state of the lamp after two minutes is independent of its state before. So for all we know, after two minutes the lamp could have mutated into a pumpkin. Seriously.
Another solution originates from noticing that the behavior of the lamp can be though of as the infinite sum: 1-1+1-1+1-1+.... So if we find the sum we will get the solution. Consider the following:

S=1-1+1-1+1-1+...
1-S=1-(1-1+1-1+1-1+...)=1-1+1-1+1-1+...=S
1-S=S
1=2S
S=0.5

And thus we found the sum. The result is usually interrupted as the lamp being half on. I don't know about you but I never saw a lamp being in that state.
What would happen if we are to do this switching in reality? Thats simple - the switch will break.
As you can see in this case modeling the situation mathematically fails completely.

The second example is an implementation of a theorem to a situation it cannot be applied in. The theorem I am talking about is the Brouwer's fixed point theorem. It is one of many fixed point theorems, which state that for any continuous function f with certain properties there is a point x0 such that f(x0) = x0. Sometime ago I read a statement that according to this theorem, if you take a glass of water and then mix it in anyway, there always will be a small part of the water that didn't change its position. If you are not careful this may seem reasonable. After all, mixing the water is a continues process. Unfortunately, this is simply wrong. The theorem itself is of course correct, but it cannot be used to discribe water in a glass. For this theorem to be used the body it is used on must be continues, but the water is discrete - it is composed from atoms. Because of this the theorem cannot be applied to such a situation, and the result we get by applying it forcefully is wrong.

The third example is known as the Banach–Tarski paradox. It is a theorem in set theoretic geometry which states that a solid ball in 3-dimensional space can be split into a finite number of non-overlapping pieces, which can then be put back together in a different way to yield two identical copies of the original ball. The reassembly process involves only moving the pieces around and rotating them, without changing their shape. Obviously this is not something that is possible to do in reality.
Again, the theorem is perfectly fine. The problem is that it cannot be applied to actual balls. During the proof of the theorem (at least the proof I am familiar with) we get a countable infinity of finite degree polynomials of the form p(sinx)=q. We need to choose x in such a way that for all the polynomials q is not 0. Since any polynomial have a finite number of roots, there is at most a countable infinity of values for x that doesn't give us what we want. Therefore we can always choose a value that will work.
Unfortunately x is the angel of rotation of the ball. If we want to choose a specific x we need firstly to make sure that we can rotate the ball by such an angel. Surprisingly this is not always possible. The reason for this is physical and not mathematical, so I am not going to explain it in detail, but the main idea is that we cannot make "moves too small" in the real world.

Mathematics is often said to be describing the real world. Personally I don't think so. Those and other similar examples have one common trait - correct math that cannot be applied in our world (at least not the way we want it to). But it can be used to describe a world of math.

Painting the roads

Consider the following problem - given a road system is it possible to have a set of instruction which if followed will cause you to end in one specific point regardless of were you started? Obviously this depends on the road system. It is very easy to give examples of road systems for both cases. It turns out however that there are really simple conditions that guarantee the existence of such an instruction set.
In order to discuss this mathematically we will need to define a few things. Firstly we are not going to talk about roads but about finite directional graphs. Secondly for every vortex on the graph we will allow exactly d (d is the same for all vortexes) edges to come out from it and an unspecified number of edges to go to it. In such situation talking about "turning right" is meaningless so we will instead use colors. Thus every "color" is a function that for a given vortex tells us were to go. Naturally there is d colors. In this blog post I will denote colors with letters - for example (a), (b). Only one color means doing only one "step", so for longer steps we need "words" instead of letters. For example (abdc) means to execute (c) then (d) then (b) and finally (a). In this notation we are looking for a word that when executed will result in us landing on a vortex V regardless of our starting point. We will call such a word a sync word.

Required conditions
Firstly, lets see what obvious conditions are required. Basically we want a graph that is possible to color in such a way that there will be a sync word. So lets demand the following conditions:
1. The graph is strongly connected - there is a path between any two different vortexes.
2. The graph is not cyclic. To be more precise what we want is:
a. The greatest common divisor of the lengths of all the closed paths in the graph is 1.
b. It is not possible to divide the graph to a finite number of sets S1,....Sk such that for all i the edges go from Si to Si+1.

Theorem
The conditions listed above are enough.

Prove history
I am not going to prove this theorem here. It is possible, but it requires a bit too much explanations and the explanations are hard to understand without drawings. Because of this I am not going to prove the theorem, but I will shortly discuss the history behind the prove and some important points behind the proof. If you want to read the actual prove it should be available online (somewhere).

There were three main stages in the attempt to prove the theorem. The first stage was done by Friedman. He defined a weight function of the graph, and showed that if the weigh of the graph is a prime number than there is a way to get a sync word unless the maximum weight (the maximum weight is the weight of the largest (by weight) subset of the graph that can be synced) is 1. As you can see this result is very far from proving the theorem, but it turned out to be an important step - the weight function he defined turned out to be useful in future attempts to prove the theorem.
The second stage was done by Kari. He proved that if the graph also has a fixed number of edges entering each vortex and this number is also d, then there is a way to get the sync word. While this is not what is needed this is a much better result than the previous one. It is also interesting to note that he managed to use induction in his prove, by finding a way to reduce the problem of finding a sync word for a large graph to finding such a word in a smaller graph.
The third and last stage was done by Abraham Tracman. This was done only in 2007. As I already said his prove requires complex explanations so I am not going to say much about it. The only thing that is important to say is that in the prove we look closely on the results of continuously using the same function on the graph. By analyzing the result we find out that in all the cases we can get two vortexes that satisfy a condition needed for Kari proof to work. Basically he showed that it is not needed to ask for a fixed number of edges entering the vortex, and by this completed the proof. In a way this is an interesting example of how people build on other people work.

Conclusion
I hope that by now it is clear that the problem has absolutely nothing to do with roads. Well, except for the name. Originally this problem originated from symbolic dynamics. However the name road coloring sound much better and it is possible to use the result in road building, although it is rather pointless to do so. All we managed to do is to show that there is a way to color the graph, so if we color the roads in the appropriate way we will be able to get the needed instruction set but it will require a more complex road system that what we have now.

In this particular case mathematical analysis of a problem gave a solution that is accurate and possible to use in the real world - but is this always correct? In the next post I will discuss some rather famous cases where correct math leads to solutions that are impossible in the real world.

Ordinals

I once read about a theory that said that numbers can be described as a common property of two groups that have nothing in common excluding their size. For example the number three is a common property of the following groups - three deers, three stones and three trees.
In modern mathematics we have a sort of an extension to this idea - ordinals. An ordinal is a well ordered set such that if A is an ordinal and x is in A and y is in x then y is in A. The first ordinals are phi (=empty set), {phi}, {phi,{phi}}, {phi,{phi}, {phi,{phi}}}. Those ordinals correspond to 0,1,2,3.
As you probably noticed there is a very simple rule that produces the next ordinal - if A is an ordinal than A(union){A} is the next ordinal. From this we can conclude that: The set of all ordinals is a well ordered set and the union of any number of ordinals is an ordinal.

What makes the ordinals truly interesting for me is the fact that in for them "infinity plus one" is not equal to infinity. This is very simple to see, infinity is the so called least infinite ordinal - w. It can be defined as the union of all finite ordinals. The next ordinal is w+1=w(union){w}. It is rather obvious that the two sets are not equal and therefore w+1 is not equal to w.
Ordinals are not the only example of infinity not being equal to infinity and one, but in my opinion they are extremely intuitive in this regard. After all, all we basically do with ordinals is to constantly "add one". This is the same thing we did with natural numbers long ago, but it appears that the natural numbers don't follow our basic intuition that says that "it is always possible to add one"

In the beginning of the post I told that numbers can be described as a common natural property. This however brings an interesting philosophical question - if our intuition is a product of our world than why do natural numbers that come from it don't follow our intuition after a specific point? A possible answer is that "infinity is not natural" and therefore there is no reason for it to follow our intuition in any way. However, infinity appeared as a concept a lot of time ago. At first it appeared as "many" which basically told that there was no known number large enough.When a new number (or even a number system) where invented the "many" was replaced by an appropriate number. And this brings us to the following thought: Is it possible that we are in the same condition again? That is, should we use ordinals instead of natural numbers? After all, they are pretty much an extension of the natural numbers.

Project Euler

I recently found an interesting site called Project Euler. This site attempts to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context. This is being done by publishing different mathematical problems of varying difficulty.
I liked the concept so I thought about joining the site, but after taking a closer look on the problems I lost my motivation - most of the problems are meant to be solved using a computer. I just can't feel motivated to write a program in order to sum all the primes less than 2 million (this is problem number 10). However, if you like this type of problems this is clearly an excellent site. They have lots of problems of varying difficulty and new problems are constantly added.

For those who like my don't like using computer to solve problems there are problems that don't require a computer to solve - for example the first problem: "Add all the natural numbers below one thousand that are multiples of 3 or 5." This one is a very simple problem, so I guess it will be fine to post a hint to a solution. All you need to do is to sum the arithmetic progressions 3,6,9,..... and 5,10,15..... If you add the sums you will get the result, but the numbers that are multiples of both 3 and 5 will be counted twice.
I also really liked problem number 205. It is pretty easy to solve, but it requires some thinking and there is no need for a computer.

Infinitesimals

In the previous post, I wrote about division by zero. In this post I want to talk about one particular case when such division, and its definition are important. As you probably guessed from the title, this post is about calculus. (In this post I am talking only about one variable calculus).

One of the most basic questions in calculus is finding slopes of functions. The simplest example of such a problem is to find the slope of a linear function, f(x)=mx+b.
In this case we get a straight line, so the slope is uniform. To find is we need to calculate the difference in y divided by the difference in x:

(f(x+h)-f(x))/h=(m(x+h)+b-mx-b)/h=m(h)/h=m

For a less friendlier functions, we cannot talk about globe slope, but only about slope of a certain part of the function, or even only in one single point. And this is were the problem appeared. We want to know the slope in every point, but how can we calculate it? Firstly we need to define what such a slope is. For example lets look on the function f(x)=x^2 and on the point x=3. Lets look on the points f(3.5) and f(3). If we connect those two points by a straight line, we can calculate the slope of that line. If we draw this on a paper, you will see that the function and the line are really close to each other on a small area around 3. Therefore we can thing about the slope of this line as an approximation to the slope of the function. But, obviously if instead of 3.5 we will take 3.1, we will get a better approximation. In the end we can think about the slope as:

slope=(f(3+h)-f(3))/h , h=0

And here we have it - devision by zero. It is obvious that there is no way around it. If h is not zero we get only an approximation and one which can be improved easily enough. The solution to this problem was found by Newton and Leibniz. Their idea was to define a non negative "number" that is smaller that any positive number. Such a number is called infinitesimal. The only real infinitesimal is zero, but if we agree to imagine that there is another such number, they we get many such numbers. This is because if dx is an infinitisimal that 0.5dx is also an infinitisimal. Since dx is not zero, we can divide by it. And becasue it is smaller than any positive number we can disregard it as if it was zero. It is simple to find the slope of x^2 usinig dx:

slope=(f(3+dx)-f(3))/dx=(9+6dx+dx^2-9)/dx=(6dx+dx^2)/dx=6+dx=6

Although the result is correct, we no longer use infinitesimals, but use limits instead. The reason for this is that infinitesimals are problematic. The problem lies in the very definition - it is not clear what do we mean by a number that is smaller than any positive number, but not negative or zero. We also treat it as both zero and as not zero. However, they are still in use in physics. The reasons for this is that while they are not rigorous enough for mathematicians to use, they give good intuition and they appear rather naturally in physical problems.

Division by Zero

We all know that division by zero is undefined. But what does it mean? Firstly, it is not "completely" undefined. For example, it is possible to say that:

1/0=lim1/x, x->0

This particular definition is not very good, because the limit doesn't exist. But we can always suppose that we look only on positive x and the the limit is defined to be infinity. Alternatively, it is possible to use geometric series. The formula for the sum of the geometric series says that:

1+q+q^2=q^3+...=1/1-q,

If we will take q to be 1 we will get: 1/0=1+1+1+1+....=infinity

As you can see I just wrote two different definitions to division be zero. However, this doesn't solve anything. The problem is that infinity is not a number. We could just as well say that 1/0=watermelon. Mathematically it is basically the same. Therefore when we divide by zero we no longer deal with numbers, and this what makes such division undefined.
Now, what about other definitions? A very long time ago, when "zero" appeared in mathematics there was an attempt to define division be zero by simply stating that division by zero gives a fraction whose denominator is zero. But this is again not a number.
We also cannot define 1/0=a where a is a number. The reason for this is that in this case we get:

1=0*1/0=0*a=0

And if this happens we get that the only number that we have is 0, because all the "other" numbers are equal to it. Obviously this is not an interesting situation. Because of this it is necessary that the devision by zero is not defined.

Lets look on some other example of undefined identities. The first one is 0^0. The reason this one is undefined is very simple:

0^0=0^(1-1)=0^1*0^-1=0/0=0*1/0

And we are back to division by zero. It is important to note that it is sometimes assumed that 0^0=1, but this is mostly done as an alternative to saying that in a polynomial x^n in which n can be zero x is not zero.
A more complex example is (-3)^x where is a real number (that is, x is not rational). Obviously, there is nothing special in number (-3), this expression is undefined for all negative numbers. For positive numbers the definition uses limits. For example:

3^x=lim(3^q), limq=x, q- rational

This definition works well for positive numbers, but for negarive numbers we have the problem that the square root is not real. Because of this if we don't allow complex numbers we get many undefined points in the series, and if we allow such numbers the series doesn't converge.

As a bonus, here is a little proof that 2=1. Can you see where is the error?

a=b.
a^2=ab ,
a^2+a^2=a^2+ab,
2a^2=a^2+ab,
2a^2-2ab=a^2-ab,
2(a^2-ab)=1(a^2-ab)
2(a^2-ab)/(a^2-ab)=1(a^2-ab)/(a^2-ab)
2=1

Tautology and theories

What is a tautology? Simply put it is a statement that is always true. More specifically, it is a statement that is true because of its structure. Usually such a statement is not informative. The easiest way to explain this is by example, so lets look on the following statements:

1. All apples are round.
2. All apples are either round or not round.

I have never seen an apple that wasn't round, so the first statement is a correct one. However it is not a tautology. It is perfectly possible for a square shaped apple to exist, you just need to make it grow inside a box. Therefore this statement is not always true.
The second statement is always true, and therefore a tautology, but it doesn't say anything. That is, if all we know about apples is that an apple is either round or not round we don't know anything about apples.
It doesn't mean that tautologies are useless, they have both use and importance in certain cases.

Lets look on tautologies in a more formalistic way. In the example above I assumed we have an object "apple" and a property "round". However, this is not necessary. All we need to write this example is two symbols: P, Q. If we rewrite the example using this symbols we get:
1. P->Q
2. P->(Q(or)(notQ))

I don't want to explain the notation, if you don't know it you are welcome to use wikipedia.
This notation is far better that the previous one. With this notation we are free to chose the meaning of the symbols. For example we can suppose that the meaning of P is x=7, and the meaning of Q is x+4=0. In this case 1 is usually false (but not always) but 2 is true.
From this we see that the second statement is completely independent from reality. It doesn't matter if we use it to tell something about apples or about mathematics, it will always remain true. This is the true meaning of being a tautology.

Sometime ago I read a post that claimed that all theories are tautologies. From the above it should be obvious that this is wrong. But there is a certain moment that causes this confusion. A theory is basically a collection of statements (theorems) that can be logically concluded from a certain set of prepositions. Those prepositions are divided in two groups - tautologies and axioms. (We don't really need to include tautologies, but because they are always true they get included automatically). Axioms are not tautologies. They are just "rules" that we choose by ourselves. In physics, those rules are based on reality and experiment, but this doesn't have to be the case. For example - the parallel postulate of Euclid. It seems natural to us to think that it is correct. But it is possible to built a geometry without it. Naturally in such a geometry all the statement that were derived from the parallel postulate are no longer correct (they might be correct, but not necessarily).

To sum up this discussion, a theory is correct as long as the axioms from which it was built are correct. However, if we try to apply it to a "world" in which the axioms are not true, the theory will not work. By the way, this is a major problem for physics and economics. They can build wonderful theory only to find out that the world we live in is different from their initial assumptions. In mathematics this is not a problem because there is no desire to describe our world, but to built a mathematical structure.
This also makes easy to explain the statement that a theorem once proved is true forever - a theorem is dependent only on its own conditions, so as long as they are satisfied the theorem will always be true.

Limits of applicability

A question: In physics, the world is considered to be continues. We can see this for example in the fact that we use integrals instead of finite sums in mechanics. However, we know that the objects in our world are made of atoms, which are in turn made of more elementary particles so they cannot be considered continues in a mathematical meaning. So can we apply mathematical result that are based on the assumption that the world is continues, to solve physical problems?

Since as I already said we use integrals in mechanics, it should be obvious that we can do this. But this is not true in all cases. For example lets consider the following theorem:

For any compact and convex set K in R^n and any continues function F from K to K, there is a point x in K such that F(x)=x.

This theorem is known as the general version of the Brouwer Fixed Point Theorem.

It should be obvious that a glass of water can be viewed as a compact and convex set in R^3. Also mixing the water using a spoon can be considered a continues function. Therefore, according to the theorem there is a point that didn't move. But this is obviously wrong. This is because the theorem gives us a point, but that point doesn't have to correspond to a particle and therefore saying that it didn't move is meaningless.

Why can we consider the world to be continues in one case and not the other? The reason for this is size. When we want to solve a problem in our scale (that is, we are dealing with objects that we can see and with results that can be observed directly), we can safely assume that the world is continues and use the corresponding tools. But this is only because the atoms are so small that for us there is no practical difference if we assume that the objects are continues.
But when like in the example with the water, the result we want to calculate (in that case a point) is not something we can see with our own eyes (we cannot see if an atom moved or not) assuming that the world is continues is wrong.

The above classification is very basic and inaccurate but it gives a general understating of the situation. In the next post, I plan to continue with this topic by discussing applicability of theories to reality.

Geometrical representation of numbers

This post s a response to a comment I got today. I was asked if there are numbers that cannot be represented at all using geometry.
The answer to this question depends greatly on what you consider to be a number, and what you consider to be a geometrical representation.

What is a number?
One possible approach is to define that x is a number if and only if it belongs to R (the set of all real numbers). There are different ways to define this set, but it can be proven that all those definitions give the same set, so this definition of a number doesn't have any problems.
However, there are objects that don't belong to R but are considered numbers (at least by some people). The most obvious example is the complex numbers. It can be easily shown that the "number" sqrt(-1)=i doesn't belong to R, so if we want to consider it as a number we need to extend our definition to include all the complex numbers - in other words x is a number if and only if it belongs to C (the set of all complex numbers).
It turns out however that even this definition can be extended. In addition to i we have other imaginary "numbers" - the infinitesimals (a non negative number smaller than any positive number) and infinity. Neither of them belong to R or to C.
Surprisingly, even this is not the end. There are also cardinal numbers - a cardinal number is basically a size of a set, so for finite sets this is just a natural number. For infinite sets a cardinal is a "number" (and there are infinitely many different sizes of infinite sets, so there is an infinite os such cardinals) that doesn't belong to any of the sets mentioned above (except for the cardinal of the set of the natural numbers).
It is possible to bring more examples of objects that can be called numbers but, in my opinion the best definition is the first one - x is a number if and only if it belongs to R. But you are free to chose the one you like.
Geometrical representation
It is important to notice that there are two different definition of what a geometrical representation is. The definitions are:
1. A number has a geometrical representation if there is a point on the real line that corresponds to this number.
2. A number has a geometrical representation if a line segment of a corresponding length can be constructed geometrically (using compass and straightedge alone).

Since R can be viewed as the real line, it follows immediately that all the numbers in R has a geometrical representation according to the first definition. It turn out that if you extend this definition of the numbers to include all C, there is also a geometrical representation, because every complex number can represented by a point on a plane. Infinitesimals, infinity and cardinals don't have such a representation.

The second definition is much more strict. The ancient Creeks never asked if there are numbers that cannot be represented in such a way, but it turned out (at about the 16 century I think) that there are such numbers. To better understand this, lets first see some examples. Lets look on the following numbers - 2, 9, sqrt(2) , pi.
It is obvious that we can construct the first two. All we need to do is to decide what we call a line segment of length one, and we are done. We can now draw 2 such segment to get 2 and 9 to get 9. For sqrt(2) it is a bit more complex, we need to make a right triangle with sides 1 and then we will get that the third side is sqrt(2). Generally it has been proven that a number that is a root of a polynomial with rational coefficients can be somehow constructed under the restrictions we put on ourselves. It was also proven that a number that is not a root of any such polynomial cannot be constructed in such a way. Not so long ago (in the last century) it was shown by Cantor that most numbers (numbers according to the first definition) are not constructible. Such numbers are called transcendental.
It is important to note that numbers that belong to C also can be constructed (not all of them, but some of them) this happens because C and R are sets of the same cardinality so you can assign a number in R for any number in C.