Dezember 2011 Archive

Happy New Year to everybody!

I have a bit too much work to write many posts right now, but I have a lot of ideas. I hope that all of my remaining, old and new readers, will enjoy reading them.

I myself would enjoy to read a few more comments on my posts than last year.

This is part 3 of my series on infinity.

In part 2 we have seen that there are infinitary processes with a finite outcome. In this part, we will see something, which can at least "philosophically" be considered as the other way around: How to embed infinity into finite objects.

In the end of part 1, we have already seen the following bijection:
It embeds the whole real line into a finite open interval, so reasonings about the real line become reasonings about this interval, and reasonings about this interval become reasonings about the whole real line. However, this is a bijection, mapping something of infinite length onto something of finite length, but it is not directly something we intuitively consider as an "embedding", and we might ask the question whether it is possible for a finite object to contain a line of infinite length, for example. Now consider the following construction: You start with a square (of side length 1). You cut this square into two halfs, and into the left half, you put an isosceles triangle of height 1 and width 0.5. You cut the other half again into two halfs, and put an isosceles triangle of height 1 and width 0.25 into the left one. Proceed this infinitely often, cutting the right rectangle into two halfs, and embedding an isosceles triangle into the left one. The following graphic shows this:


The length of the isosceles lines (blue in the graphic) of the <m>n</m>-th triangle have length <m>2\sqrt{1+\frac{1}{4^{n+2}}}</m> (which follows by one of Pythagoras' theorems), but the important fact is that it is always strictly greater than <m>2</m>, since the height is already <m>1</m>, and each of the two lines must trivially be longer. All of the isosceles lines together form a line, the line colored blue in the graphic, and this line must be of infinite length. So in fact, it is possible for a square to contain an infinite line.

Here, the special character of lines must be taken to account: Lines have no width. Lines are ideal objects, which only have a length, but do not have a width. Of course, every line we draw is not ideal, in the sense that - to be able to see it - it needs to have a width. Every line which is actually drawn is only an approximation of lines. Still, the ideal object "line" is not useless: It is a formal object which can be approximated with (probably) arbitrary precision, and its definition was a success and is implicitly used in huge parts of science.

Let us consider another graphic: Assume you draw a square of side length 1. Then centrized into this square, you draw a square of side length 0.5, and inside this, you draw a further square of side length 0.25, and so on. The following graphic shows this:


The circumference of  the <m>n</m>-th square has length <m>\frac{4}{2^{n-1}}</m>. So the sum of the lengths is a geometric series, as we saw in Part 2, and we have <m>\sum\limits_{i=1}^\infty\frac{4}{2^{i-1}} = \sum\limits_{i=0}^\infty\frac{4}{2^i}=\frac{4}{1-\frac{1}{2}}=8</m>, that is, all the lines we have drawn together are of length <m>8</m>. So, informally speaking, we can draw this "with a pen": We will not need an infinite amount of color to draw it, even though it has infinitely many parts.

So far for this time. We have seen some nice examples of the interplay between finity and infinity, when talking about lengt. Next time it gets a bit harder, we will again look at the countability of sets.

This is the second post of my series on infinity, be sure to read the first one.

We start this chapter with a nice story, "Achilles and the Tortoise", one of Zeno's Paradoxes, though we slightly adapt it. So, Achilles races against a tortoise. He gives the tortoise a 1 mile head start. Assuming Achilles is four times as fast as the tortoise, when he arrives 1 mile, the tortoise is at 1.25 miles. When he arrives 1.25, the tortoise is at 1.3125 miles. When he arrives at 1.3125, the tortoise is at 1.328125. And so on. Whenever Achilles reaches the point the tortoise was when he started, the tortoise already went further. This way, Achilles would have to go through infinitely many points, before reaching the tortoise.

Of course, this is not really a paradoxon. The problem lies in the fact that we have an infinitary process in here. As mathematicians do, we write the problem down more formally. Let <m>a_i</m> be the <m>i</m>-th point where Achilles stands, and <m>t_i</m> the point where the tortoise stands. We have <m>a_0 = 0</m> and <m>t_0=1</m>, respectively. By definition, we have <m>a_{n+1} = t_n</m>, because Achilles always reaches the former point of the turtle. As the turtle has a 1 mile head start, and has <m>\frac{1}{4}</m> times of Achilles' speed, we set <m>t_{n+1}=1+\frac{a_{n+1}}{4}</m>, which is <m>t_{n+1}=1+\frac{t_{n}}{4}</m>. It is easy to see, that <m>t_n = 1+\frac{1}{4}+\frac{1}{16}+\ldots+\frac{1}{4^n}</m>, that is, <m>t_n=\sum\limits_{i=0}^n \frac{1}{4^i}</m>, which is a shorter mathematical notation for such sums.

Using the axioms we saw in Part 1, we can prove this formally (if you are already a little confused, just skip this proof, it is not necessary for the further understanding): Assume there is an <m>n</m> such that <m>t_n\neq\sum\limits_{i=0}^n\frac{1}{4^n}</m>, then there is a smallest such <m>n</m>. Clearly, <m>t_0=1=\frac{1}{4^0}=\sum\limits_{i=0}^0\frac{1}{4^i}</m>, so <m>n\neq 0</m>. Therefore, it has a predecessor <m>n-1</m>, for which we must have <m>t_{n-1}=\sum\limits_{i=0}^{n-1}\frac{1}{4^i}</m>, since <m>n</m> was minimal. But then, <m>t_{n} = 1+\frac{t_{n-1}}{4} = 1+\frac{1}{4}\cdot\sum\limits_{i=0}^{n-1}\frac{1}{4^i}=1+\sum\limits_{i=1}^{n}\frac{1}{4^i}=\sum\limits_{i=0}^{n}\frac{1}{4^i}</m>. Contradiction.

Obviously, Achilles will pass the tortoise at some point, and obviously, this point is greater than all <m>t_n</m>. We want to find out more about this point where he passes the tortoise.

The point we are looking for, is <m>\frac{4}{3}</m>. In fact, this is provable. But it is a bit harder than the above induction.  What we have here, is a so-called geometric series. As we have <m>t_{n}=1+\frac{1}{4}+\frac{1}{16}+\ldots+\frac{1}{4^n}</m>, we have <m>\frac{1}{4}t_{n}=\frac{1}{4}+\frac{1}{16}+\ldots+\frac{1}{4^{n+1}}</m>, that is, <m>\frac{1}{4}t_{n}</m> and <m>t_{n}</m> differ in the terms <m>1</m> and <m>\frac{1}{4^{n+1}}</m>, and thus we have
(source)

(Based on a true story.)

Normalerweise halte ich nichts von den staatlichen Versuchen, Videospiele zu verteufeln, aber dieses Video (vorsicht, laut dieser Seite nicht geeignet für Kinder unter 12 Jahren) brachte mich zum Lachen, also insbesondere der Teil ganz am Ende.

(Direktlink)

#! /bin/bash                                                                                         

width=22
text=0110110011011101111001011010110101110111011\
000001000010111011101100110101101011101110110011\
0101101000100011001

(
 textlen=$(echo -n "$text" | wc -c)
 height=$((textlen/width))
 echo new $((8*width)),$((8*height))
 echo fill 10,10,255,255,255
 j=0; while [ "$j" -lt "$height" ]; do
  i=0; while [ "$i" -lt "$width" ]; do
   ftext=${text:0:1}
   text=${text:1}
   if [ "$ftext" "=" "0" ]; then
    echo frect $((8*i)),$((8*j)),$((8*i+8)),$((8*j+8)),0,0,0;
   fi
   ((i++))
  done
  ((j++))
 done
 echo output hi.gif
) | flydraw

Infinity. One central mathematical concept on which many myths have spread, especially in the world outside science. Therefore, I had the idea of writing a series of blog-posts about several aspects of "Infinity".

These posts are not scientific, they are for non-Mathematicians, to demystify the concept of "infinity". But neither is it one of those texts that try to include a lot of "history" and interesting side facts. I just want to give a slight understanding of infinity to non-Mathematicians.

So, in this first post, we shall have a short look at the numbers as such. First, everyone knows the non-negative integers <m>\{0,1,2,\ldots\}</m>. There are "infinitely many" of them, since every number <m>n</m> has a unique successor <m>n+1</m>. This should be intuitive to everybody, and in fact, it is an axiom of arithmetic: Every number has a unique successor. Additionally, we have to postulate that every number except <m>0</m> has a predecessor.

Another thing you quickly notice: Take an arbitrary sequence of decreasing non-negative integers (that is, start somewhere, and then "count down", possibly leaving steps out), then this sequence will be of finite length: You will soon or later bump into <m>0</m>. A bit more complicated, think of an arbitrary set <m>S</m> of non-negative integers. Take, for example, the primes, the odd numbers, the even numbers, the phone numbers of your neighbourhood. You will notice that also every of these sets has a minimal element, even though the set itself may contain infinitely many non-negative integers. That is another axiom of arithmetic: Every non-empty set <m>S</m> of non-negative integers has a smallest element.

These two axioms plus the existence of <m>0</m> are, in fact, sufficient for elementary arithmetic. A whole lot of theorems can just be implied by these axioms. A simple example: Every number is either of the form <m>2n</m> or <m>2n+1</m> - of course, this is not very profound, it essentially states that every number is odd or even, but we only want to give a simple example. To prove it, assume there was some number <m>p</m> which cannot be written in that way, then by our axiom, there exists a minimal such <m>p</m>. Since <m>0=2\cdot 0</m>, we know that <m>p\neq 0</m>, and therefore, by axiom, it has a predecessor <m>p-1</m>, and as <m>p</m> was the smallest number which can not be written in that form, we know  that there is an <m>n</m> such that <m>p-1=2n</m> or <m>p-1=2n+1</m>. If <m>p-1=2n</m>, then <m>p=2n+1</m>, which we did not allow for <m>p</m>. If <m>p-1=2n+1</m>, then <m>p=2n+2=2(n+1)</m>, which is also not allowed. This is a contradiction! So, such a <m>p</m> cannot exist: All numbers may be written in that form.


Found at KnowYourMemeNow, of course, there are further objects that are commonly called "numbers". When doing accounting, you are certainly familiar with negative integers. So we get the set of all integers, <m>\mathbb{Z}=\{\ldots, -2, -1, 0, 1, 2, \ldots\}</m>. They do not share the property that every set of them has a smallest element. There are infinitely many of them into "both sides". So intuitively, there are "more" integers than non-negative integers - of course, the latter is a subset of the first.
But what does it mean for two sets of objects to have the same "number" of elements? Let us first look at the finite case. Let us say you are counting apples. You will take one of them and say "one", then a second one, saying "two", and a third one, saying "three", and so on, until no apple is left that was not counted. Let as assume you counted ten apples. You think you just counted the apples, but what you actually did was giving a one-to-one-mapping between apples and the set <m>\{1,2,3,4,5,6,7,8,9,10\}</m>. Of course, you probably did not memorize the order you chose the apples - because it does not matter which mapping you chose, the important fact is that there is such a mapping. Such a one-to-one-mapping between two sets is called a bijection. Even in our example, there are many such bijections (calculating the actual number is left as an exercise), and you only chose one by random.

So, for the finite case, we can conclude that two sets have the same number of elements, if there is a bijection between them. For the infinite case, this becomes the definition. Two infinite sets are of equal size, if and only if there is a bijection between them.

Now, let us go back to the integers. We tried to conclude that since the non-negative integers are a subset of the integers, there must be less of them. But on the other hand, define a mapping <m>\varphi(n)=(-1)^n\lceil\frac{n}{2}\rceil</m>, that is, <m>\varphi(0),\varphi(1),\varphi(2),\varphi(3),\varphi(4),\ldots</m> is <m>0,-1,1,-2,2,-3,3,-4,4,\ldots</m>. This is a bijection. So in fact, there are as many non-negative integers, as there are integers at all - even though this might not be intuitive, when looking at the finite case.

In fact, this strange behaviour of infinite sets can be used to classify them: A set is finite if and only if there is no bijection into one of its proper subsets. As there are other (mostly equivalent) definitions of finity and infinity, the concept defined here is sometimes called Dedekind-Finity.


Found at Fukung. This concept is probably hard to understand for a non-Mathematician. The problem is that "finity" is such an intuitive concept, that every non-Mathematician will postulate it was "clear". But this is not the mathematical way of thinking. We will get deeper into this topic in one of the following posts on infinity, when we look at cardinalities. For now, let us get back to numbers.

Of course, even a non-Mathematician knows that there is more than integers. We can extend the numbers to fractions. The set of fractions is called <m>\mathbb{Q}</m>, and it contains all fractions of the form <m>\frac{a}{b}</m> where <m>a</m> and <m>b</m> are integers, where <m>b\neq 0</m>. Fractions have a nice property: between two distinct fractions, there is always a third one. For example, between <m>0</m> and <m>1</m>, there is <m>\frac{1}{2}</m>. Even worse, from this directly follows that between two distinct fractions, there are always infinitely many other fractions.

For example, between <m>0</m> and <m>1</m>, there are the fractions <m>\frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \ldots</m>. We have "infinity on finite place", so infinity does not yield distance in any sense. Even worse, we will later show that there is a bijection between integers and fractions: Even though we can squeeze infinitely many of them between <m>0</m> and <m>1</m>, there are not "more" fractions than integers in the above sense.

As everybody should know from school, every fraction can also be written as a decimal fraction, with either finitely many digits or as a recurring fraction. However, we always find finitely many digits to specify them exactly.

And as many of you will probably know, there are also numbers that do not have this property. For example, <m>\pi</m>, the constant to calculate the area of a circle, has no finite nore a recurring decimal representation, only approximations can be written that way. In general, every infinite sequence of digits which has a dot after finitely many steps can be considered a number, like <m>\pi</m>, <m>\sqrt{2}</m>, etc., and the set of these numbers are called the real numbers, and their set is called <m>\mathbb{R}</m>. It can be proved that <m>\mathbb{R}</m> is actually bigger than <m>\mathbb{Z}</m>. We will later see, how this is done.


Found at Mighty Wombat. Usually, the general education stops at <m>\mathbb{R}</m>, even though there is a larger set of numbers, the complex numbers, <m>\mathbb{C}</m>, which many non-Mathematicians do not consider as numbers, because it goes further than what they usually do with numbers. However, it is relevant in science, and mathematically, it is probably more beautiful than <m>\mathbb{R}</m>. Besides all real numbers, it contains, for example, the imaginary unit <m>i</m>, for which we have <m>i^2=-1</m>, it is (one) "square root" of <m>-1</m>, which we do not have in <m>\mathbb{R}</m>.


An object which is often associated with <m>\mathbb{R}</m> is the real line: The real numbers can be considered an infinite line which contains all of them. Then, the following graphic illustrates a bijection between the real numbers between <m>0</m> and <m>1</m> and all real numbers:



Especially interesting is that <m>0</m> and <m>1</m> can somehow be considered as the images of the negative and positive "infinity".

So far for this time.

A great article, with interesting references, and as it is about something many people do not seem to understand, worth reading:

> The abstraction-optimization tradeoff

List man auch nicht jeden Tag: Schwein ersticht Mann.

Kurzgefasst: Rumänien, illegales Schlachtfest, Schwein wehrt sich, tritt Mann mit Messer in der Hand und rammt ihm dieses in den Hals. Mann Tot.

Von einem "tragischen" Ende ist in dem Artikel die Rede. Tragisch ist meiner Meinung nach hier nur, dass solche Advents-Schlachtfeste überhaupt noch stattfinden, dass man Tieren nicht einmal eine EU-Genormte Schlachtung zugesteht.

Welches Schw Wer am Ende abgestochen wird ist mir dabei allerdings einerlei.

Found at Fukung. At the station where I leave the train every week, there is a tunnel where often street musicians play their music. Mostly, their play is so bad and annoying that you want to pay them rather for stopping it, than for playing. However, today, I heard some nice melody from this tunnel, and I thought, maybe a band or something is playing there.

Approaching the source, I saw an old woman, playing on a small electrical piano. Looking a little closer, I found that some keys were missing on the keyboard, and obviously, she was only pretending to play - her keystrokes did not sync with the music, the music was obviously played by that gadget automatically.

I am not sure whether this person was snaky, or just naive to think that nobody will notice, or both. However, at least she knew how to play this gadget in a way that it does not make annoying sounds, even though that only means to choose a track and play it, it is better than what the other people do. And that wtf-feel about it somehow made me smile. I gave her 50 cent, to help her repairing the missing keys on her keyboard.