At school, I often wondered why my English is judged by tasks I would not even be able to solve in German. Like listening and repeating historic facts, or conversations I just heard, or expressing my opinion on a topic I do not care about. I hated that.

Well, today I had my "Internet Based TOEFL". Before it started, I had to sign a form, and copy (!!!) an agreement, explicitly not in printed form (I hope they can read Sütterlin). If I understood correctly, this agreement forbids to give information on the contents of that test, which is why I cannot share any examples. Because you know, if I did so, the prices for training materials could decrease - heaven forbid!

So there I was, finally, at a time as early as 9.30, after I had to take the train from Munich to Nuremberg, because there were no free places for a test in Munich at a sufficiently early date. Having payed 250 Euros to be allowed to talk to a computer for about 4 hours.

A few instructions on where to put my baggage, a quick check of my passport and a bad webcamshot of my face without glasses later, I was sitting in front of a screen on which my tired face smiled back at me - what an amazing technology! All that was missing now was the supervisor logging me (and the other students who have gathered there) into that system, and a quick calibration of the headset and the microphone.

The "reading section" began. And it was similar to the questions I saw in practice exams before - except that the text was shitty, and I could not have cared less about its topic. Same for the second text. The third one was better, though. Also, no luck with the topics in the "listening section". Some stupid questions about details that I did not consider meaningful while listening, but in general, I think it went good for me.

Then a break for 10 minutes - I actually do not see any reason why it is not possible to pause the test at another time. I mean, sometimes people need to go to the toilet or something. Whatever.

As all the people needed about the same time, the blabbering began - all students started with the "speaking section". I was a few seconds slower than my neighbour, which is why I could hear her start talking while I still had to prepare my answer, which was very distracting! You are asked about two "familiar topics" - which were both topics I have never thought about. So I came up with some shit I could make up during the twenty seconds of preparation time and tried to make the best out of it.

I mean, come on, what the fuck? I already gave talks about complicated scientific topics in English. You always find time to think about your answer for a minute. And this is an exam situation!

However, after the "writing section" was finished, I could finally leave. Some other students also left. All of us agreed on these tests being a rip-off. For 250 Euros, you could afford a real teacher testing you. At an appointment that fits you. Under fairer testing conditions.

So, here is this week's Link List:

http://browserling.com/ - interactive cross-browser testing

Kitchen Myths: Bread does not become stale by drying out - they do not give any evidence of this, though.

The scale of the Universe 2 - scrolling through objects of several sizes.

An illustrated history of scientology - interesting.

Single hand keyboard for tablets - probably it will never be possible to type as fast as with two hands on an ordinary keyboard, but with a bit of practice, it could get very useful. However, I cannot try it, as I do not have a multitouch tablet.

Debian Wheezy Artwork Contest - not that I really care.

Origami robots run only on air - a nice idea, very impressive.

Mario has an affair - sort of.

Two loaves of bread and a bagel.

KERNTYPE, a kerning game - a time killer, even though I do not like typography, and I am still satisfied with monospace fonts mostly.

Atheist Barbie

Hello World in many programming languages

Durch Fleischkonsum entsteht soziale Ungerechtigkeit - insbesondere wird auf das Argument, dass Vegetarier so viel Soja essen, eingegangen.

Meine Fernseh-Hits - Stereotypen ... es gibt sie.

Das erste gedankengesteuerte Linux-Spiel - sieht interessant aus. Auch wenn ich so ein Headset zu teuer finde.

Zwei Petitionen zu der Frage, ob Tierärzte eigene Hausapotheken haben dürfen - mit gewissen Ähnlichkeiten.

Anglizismus 2011 Gewählt - "Shitstorm"

Nibbles was a Snake-like game, which was part of MS-Dos, as an example file for QBasic. The name "Nibbles" (probably ?) came from the half-bytes - "nibbles" - since on the terminal, it uses characters that split every terminal character into two parts.

Well, there are a lot of newer Snake-like games out there. However, the special thing about cNibbles is that it is, as the original Nibbles, a pure terminal application.

Often, I find some links to which I do not have to say much, except that they are there and you should follow them, and maybe a small comment about what they link to. So far, I made one post out of such links, and flagged them as "Link". But the more common way of doing this I saw on other blogs was to regularly give lists of interesting lists.

This is something I will try now. I plan to do this weekly, let us say every tuesday or wednesday or so, but I cannot promise this, of course. The links will be both German and English, and I will try not to post links that already spread through the (more famous parts of the) blogosphere.

So here we go for the first time:

http://www.smbc-comics.com/index.php?db=comics&id=2508 - gives a good illustration of the discussion on privacy and internet repression technology.

http://en.wikipedia.org/wiki/Globster - heard of it in a TV documentation about "paranormal" phenomena. Interesting.

Apple can update your twitter ... - True.

€200 KDE Plasma Active Tablet Announced - let us hope that this will be a success.

http://fatpita.net/?i=1036 - Second world war, simply explained.

I voted Republican - and all I lost was ...

Backdoor in TRENDnet IP cameras - One reason why I do not feel comfortable about too much surveillance.

Maman a dit que je peux - My mom said I could.

21 Facts that Evolutionists CAN'T ANSWER! - I am not sure whether this is satire. It is funny, though.

Various Things the Bible bans

Metazoa Ludens, via - a game for hamsters and humans.

Die KiK-Story: Die miesen Methoden des Textildiscounters - und die sind sicher nicht das einzige Unternehmen das sowas macht. Ich wäre da mal für ein staatliches Prüfsiegel, das die Käufer auf sowas hinweist. Weiß ansonsten jemand, wo man guten Gewissens Kleidung kaufen kann?

Beim Sex: Rentner erstickt an seinem Gebiss - Skurril.

Riesiges Alien-Raumschiff auf dem Mond entdeckt - sieht für mich eher aus wie ein Falzbein.




I am a vegetarian. I blogged about that in former blog posts, especially on my old blog. In the past, I used to explain the people about my feelings and opinions about meat. Meanwhile I am more careful with whom I tell that, not because I respect the decision of a person to eat meat in any way (I would probably sign a law that forbids eating meat immediately), but because I am tired of discussing, and I did not hear a single point which I did not know before, for years. Also, I am not vegan (yet).

However, of course, when there is dinner somewhere, I sometimes have to ask whether something contains meat. And more than one time I had to endure stupid comments from carnivores around me. To me, some people seemed to feel attacked when they see a vegetarian. Some psychological study now claims to prove this (however, I do not have access to the actual study).

I can understand that somehow. Vegetarism is morally superior, and people do not feel good about that. I can remember times when I thought that veganism was exaggerated - or at least I thought that I thought this. I actually always knew that veganism is morally superior to vegetarism, and I tried to be vegan, but I could not achieve that goal so far. I also think that frutarianism is morally superior, but I think that the world is not ready for that radical form of nutrition yet - which does not lower the honor I assign to people doing this.

My original intention was to write a post about ordinal numbers, but it turned out that it is a lot harder to give a clear and simple explanation than I expected. So I decided to do a little digression on ordering relations. It is not directly about infinity, but related and needed for the theory of ordinal numbers.

To understand this part 5 of my series, be sure to have read the previous parts 1, 2, 3 and 4. Especially, you should have an idea of what a bijection is, how infinity is defined, what a powerset is, and what countable and uncountable sets are.

And, to make that clear: The following part is hard. You have to say good bye to some of your "intuitive" thoughts on mathematical objects, and have to be open to new concepts that are abstract in a way that non-mathematicians usually decline. We are now entering a world, in which finally there is no place for "calculating" and visual conceptions. I will try to make it as simple as possible, omitting a lot of complicated parts, but still, the objects I will write about are not as intuitive as the objects discussed before were.

However, it should be understandable, but you might need to read a few parts of it at least twice.

So, this post is about the theory of ordering relations. Many parts of applied mathematics are, in the end, about orderings. Sorting algorithms, for example. Whenever you look for a name in an alphabetical list, you apply basic properties of ordering relations.

Every ordering relation has a domain D, which is the set of elements which it compares. Orderings are usually denoted by a relation symbol R in infix-notation, which means that you denote it by aRb for two elements a,b\in D. For example, the default ordering on \mathbb{N} is denoted by a\le b, for a,b\in\mathbb{N}. We denote this ordering as pair (R,D), for example, the default order on \mathbb{N} we denote by (\le,\mathbb{N}).

There are several axioms for several purposes which can be postulated for orderings, but the one thing that all orderings have in common is transitivity: If aRb and bRc, then aRc. This should be pretty clear when looking at the given example (\le,\mathbb{N})! And if you look at other ordering relations, like the alphabetical (lexicographical) ordering of names, you will notice that you implicitly assume this property: When searching in a phone book, you look up one item, then decide whether you have to browse further, and find a second item, and then decide whether the item you search for lies between those two items.

While transitivity is an important property of orderings, it is not sufficient. For example, the relation (=,\mathbb{N}) is also transitive, but it is not an ordering relation (it is a so-called equivalence relation, another class of relations we will not discuss here). We need to give account to the "direction" of the ordering somehow. This is done by the axiom of antisymmetry: If aRb and bRa, then a=b. Again, for (\le,\mathbb{N}), you should immediately accept that.

A third axiom, the axiom of reflexivity, is less intuitive: aRa for all a. It holds for (\le,\mathbb{N}). The problem here is that there are two major concepts of ordering relations, the strict ordering relations and the partial ordering relations. An example for a strict order would be (<,\mathbb{N}). In general, partial orders are orders of the type "less-than-or-equal", while strict orders are of the type "less-than". We will only deal with partial ordering relations, for which reflexivity holds.

So the axioms for (R,D) to an ordering relation are:
  • Reflexivity: For all a\in D we have aRa.
  • Antisymmetry: For all a,b\in D, from aRb and bRa follows a=b.
  • Transitivity: For all a,b,c\in D, from aRb and bRc follows aRc.
Make sure you fully understand that. Use the example (\le,\mathbb{N}) if necessary. We give some further examples.

Of course, there are the canonical examples (\le,\mathbb{Z}), (\le,\mathbb{Q}), (\le,\mathbb{R}).

Another common example is the divisibility relation between non-negative integers: For two integers a,b\in\mathbb{N}_0 we say a|b (a divides b), if there is an x\in\mathbb{N}_0 such that a\cdot x=b, or equivalently, if \frac{b}{a}\in\mathbb{N}_0 (where in this case we set \frac{0}{0}=1). For example, 1|2, 2|4, but 2\not |3. Clearly, a|0 for a\in\mathbb{N}_0, but 0\not |a for a\in\mathbb{N}_0\backslash\{0\}.
Trivially, a|a.
If a|b and b|a, then both \frac{a}{b}\in\mathbb{N}_0 and \frac{b}{a}\in\mathbb{N}_0, so clearly, a=b.
If a|b and b|c, then \frac{b}{a}\in\mathbb{N}_0 and \frac{c}{b}\in\mathbb{N}_0, so \frac{c}{a}=\frac{c}{b}\cdot\frac{b}{a}\in\mathbb{N}_0, therefore a|c.
Thus, (|,\mathbb{N}_0) is an ordering relation.

People familiar with arithmetics will know that we can extend the divisibility relation to negative integers, in the same way. However, this would not be an ordering in our sense anymore (exercise: why?).

Somewhat related to the divisibility relation is the subset relation \subseteq on powersets, which turns out to also be an ordering relation: Say you consider \mathfrak{P}(A), the powerset of A, then of course, by definition, B\subseteq B for B\in\mathfrak{P}(A). Let B\subseteq C, and C\subseteq B, then x\in B implies x\in C and vice versa, so B=C. Let B\subseteq C and C\subseteq D, then x\in B implies x\in C, and x\in C implies x\in D, so B\subseteq D. Therefore, for every set A, (\subseteq,\mathfrak{P}(A)) is an ordering relation.

Something you should basically know from phone books and dictionaries is the lexicographic order. It bases on an already given order (R,O), for example, the set of letters with alphabetical order, but every other ordered set is sufficient, too. You then look at the set O^{<\omega} of finite sequences, and define the ordering (R_{lex},O^{<\omega}) by

  • () R_{lex} a for all sequences a, that is, the sequence of length 0 is smaller than everything else (in dictionaries, however, this is usually not needed, as there is no such word)
  • (a_1,\ldots,a_n) R_{lex} (b_1,\ldots,b_m) if and only if either a_i=b_i for 1\le i \le n and m>n, or for j=\min\{i|a_i\neq b_i\} we have a_i R b_i - in words, either (b_1,\ldots,b_m) starts with (a_1,\ldots,a_n), or for the smallest j in which they differ, we have a_j R b_j
You should convince yourself that this is actually the intuitive lexicographical order.

As mathematicians have to deal with a lot of structures, they try to find similarities between them, and use techniques found for known structures on unknown ones. That is why they rather talk about a general "ordering relation" than about a concrete given order - there are many principles that simply hold for every such structure. From this desire comes the technique of finding morphisms between structures. Morphisms are (usually) structure-preserving functions, that is, functions that you can apply on elements without losing special relations between them. This is a highly abstract concept and we will not discuss it here in detail, but knowing this may be motivating. So, we are going to see certain kinds of morphisms between ordering relations. Keep in mind that this is abstract - if you do not understand its purpose, write it down with concrete given relations for a better chance of understanding.

Now, let two ordering relations (R,D) and (Q,C) be given. A function f:D\rightarrow C between the domains is called (order-)homomorphism, if aRb implies f(a) Q f(b). If additionally f is bijective, it is called (order-)isomorphism. If such an f exists, then the ordering relations are called homomorphic/isomorphic.

An intuitive understanding of this should be best given when thinking about homomorphisms and isomorphisms as some sort of "renamings" of the elements, which is permitted without losing relevant properties. That is, if you have some true proposition about (R,D), and rename every occurence of a\in D by f(a)\in C, and every occurence of R by Q, then you will (mostly) get a true proposition again.

Let us look at the above examples. Obviously, from (\le,\mathbb{N}), there is a homomorphism, namely f(x)=x, into (\le,\mathbb{R}) - as \mathbb{R} is just a superset of \mathbb{N}. But also, g(x)=2\cdot x+9 is a homomorphism, since a\le b is equivalent to 2\cdot a+9\le 2\cdot b+9. However, as there cannot be a bijection between \mathbb{N} and \mathbb{R}, both orders are clearly not isomorphic.

Of course, f and g are also homomorphisms between (\le,\mathbb{Z}) and (\le,\mathbb{Q}), and the question arises, whether these orderings are isomorphic. On the other hand, between two distinct rational numbers there are always infinitely many other rational numbers, and this is not the case for integers, so both orderings cannot be isomorphic.

If a|b, then a\le b for a,b\in\mathbb{N}_1. Thus, f is also a homomorphism from (|,\mathbb{N}_1) into (\le,\mathbb{N}_1) (note that the same does not hold for \mathbb{N}_0). To see that (|,\mathbb{N}_1) and (\le,\mathbb{N}_1) are not isomorphic, notice that there is exactly one element a=2 which has exactly two smaller elements (1 and 2), while there are infinitely many a with exactly two divisors, namely all the primes.

You may have noticed that we did not yet give an example for isomorphic orderings. That is due to the fact that it is rather hard to find such orderings which are mathematically interesting, not overkill, and not somehow "artificial" - mathematically, isomorphic structures need not be distinguished, and most theorems over structures are only "up to isomorphism". However, there are some examples, one is (\le,\mathbb{Q}) and (\le,\mathbb{Q}^{>0}). That is right, they are the same ordering, just that the one's domain is bounded. One isomorphism can be given by

h(x) =\left\{\begin{array}{cl}\frac{1}{1-x} & \mbox{for } x\le 0 \\ x+1 & \mbox{for } x>0 \end{array} \right.

We leave the proof as an exercise (it should be provable by school math).

It turns out that an even more special kind of ordering relations, the well-orderings, are useful to describe infinitary objects, and get a way of "enumerating" them. However, we will discuss this in the next part.