On Infinity 6 - Well-Orderings
Tue, 13 Mar 2012 13:30:00 GMT

Be sure to read the former parts 1, 2, 3, 4 and especially part 5 about orderings, before you read this part.

There are a lot of people trying to tell about what mathematics or a more specific topic is actually about - and they are often right in some sense, looking at it from a certain perspective. However, mostly those perspectives are missing something. Therefore, I will not make the claim that talking about infinitary objects is talking about orderings. However, what I can say is that ordering relations play an important role.

For example, many important definitions on \mathbb{R} can be made in terms of the default ordering \le, like convergence and openness.

However, there is one sort of ordering relations which especially suits the purpose of describing connections between infinitary objects: the well-orderings. We will introduce this concept here.

In part 1, we gave axioms for natural numbers. These were

  • Every number has a unique successor
  • Every number except 0 has a predecessor
  • Every non-empty set has a smallest element
We now want to generalize these. To generalize something, the axioms must be loosened. Loosening the first axiom would lead to a structures mathematicians would call trees (yes, like the plant), but we do not want to discuss these here - we keep the axiom of unique successors. We have seen that the third axiom is useful in proofs. The property is called well-foundedness. We will also keep this one. So the only thing we can loosen is the second: We will allow additional elements which have no predecessor.

Now consider the set \mathbb{N}_0\times\mathbb{N}_0 of pairs of natural numbers. We give an ordering (\sqsubseteq, \mathbb{N}_0\times\mathbb{N}_0) by

(a,b)\sqsubseteq (c,d) :\Leftrightarrow \left\{\begin{array}{cl} b\le d & \mbox{for } a=c \\ a<c & \mbox{otherwise}\end{array}\right.

That is, we first sort by the left element, and then, if the left elements are equal, by the right element. This is called the lexicographical order on \mathbb{N}_0\times\mathbb{N}_0. It is, in fact, an ordering (exercise).

This relation satisfies our two remaining axioms: The unique successor of a pair (a,b) is obviously (a,b+1). To get the minimum of a set X\subseteq \mathbb{N}_0\times\mathbb{N}_0, we first notice that \{a|(a,q)\in X\mbox{ for some }q\}\subseteq\mathbb{N}_0 has a minimal element m, as it is a subset of \mathbb{N}_0, and  then \{q|(m,q)\in X\}\subseteq\mathbb{N}_0 also has a smallest element b, and then, (m,b) is a minimal element of X. The "zero" of this ordering, that is, the smallest element, is obviously (0,0).

A further example for a pair with no predecessor is (1,0). Even though there are infinitely many pairs, namely (0,0), (0,1), (0,2), (0,3), \ldots smaller than (1,0), none of them is the predecessor of (1,0).

Now, keep in mind that we still want a generalization of the order of the natural numbers. We can embed (\le,\mathbb{N}_0) into (\sqsubseteq,\mathbb{N}_0\times\mathbb{N}_0) using the injective homomorphism n\rightarrow(0,n). As mathematicians are lazy, we will now just identify the naturals by this homomorphism, that is, we will actually write n instead of (0,n). With this inclusion, (1,0) becomes the first element that is larger than all the "naturals". We will - for now - write \omega for (1,0), and \omega+n for (1,n), and - to make it even more confusing - \omega\cdot m+n for (m,n).




Source: Wikipedia

In fact, we can then do addition with these new objects, and multiplication with a new object and a natural, as we did with naturals - with distributive and associative laws:

(\omega m_1+n_1)+(\omega m_2+n_2)=\omega(m_1+m_2)+(n_1+n_2)
(\omega m+n)k=\omega mk+nk

However, what we cannot do yet is multiplying two of these new objects: \omega\cdot\omega is not defined yet. We can generalize the above concept by looking at infinite sequences of natural numbers, which end in a sequence of zeroes, that is, (1, 0, 0, 0, 0, 0, \ldots), (2, 9, 7, 2, 55, 0, 0, 0, 0, \ldots), etc., and apply the lexicographical order on their reversed sequences:

(a_1,a_2,\ldots) \sqsubseteq (b_1,b_2,\ldots) :\Leftrightarrow\left\{\begin{array}{cl} \mbox{true} & \mbox{for} \{j|a_j\neq b_j\}=\emptyset \\ a_i<b_i &\mbox{for }i=\max\{j|a_j\neq b_j\}\end{array}\right.

That is, we get for the largest index i such that a_i\neq b_i, and use its order. Our former ordering of pairs can be embedded by (a,b)\rightarrow (b,a,0,0,0,\ldots).

Now, \omega=(0,1,0,0,0,\ldots), and \omega^2=(0,0,1,0,0,0,\ldots), and generally, \omega^n=(\underbrace{0,\ldots,0}_{n\times},1,0,0,0,\ldots), and we can write a sequence (a_0,a_1,a_2,\ldots) as \ldots+\omega^3 a_3+\omega^2 a_2+\omega a_1+a_0. This definition is only provisional: the actual definition is more complicated, especially, addition is not commutative, 1+\omega\neq\omega+1. Our definition works well if we always have larger numbers on the left side of the addition, and we will silently ignore the fact that we did not define it for other cases.


Source:Wikipedia

Ordering relations like \sqsubseteq are called well-orderings: A well-ordering (R,A) on a set A is an ordering, for which every subset B\subseteq A has a smallest element.

As you have seen in the examples, with well-orderings we can get beyond the tower of natural numbers, into "transfinite" numbers. However, well-orderings have a surprising property, which makes them suitable for analysis of infinity:

Let (R,A) be a well-ordering, and \vec{a}=a_1,a_2,\ldots be a strictly decreasing sequence of elements of A. Then \vec{a} is of finite length.
Proof: The set of sequence elements \{a_1,a_2,\ldots\} must have a smallest element. As \vec{a} is strictly decreasing, after reaching this element, \vec{a} must end immediately.

Interestingly, we can now find an ordering relation on well-orderings: Let (R,A) and (S,B) be well-orderings, then there is either an injective homomorphism A\rightarrow B or an injective homomorphism B\rightarrow A or both, when they are isomorphic - as this is a bit harder to prove, we omit the proof.

So we can find a relation \sqsubseteq between well-orderings, where (R,A)\sqsubseteq(S,B) shall mean that there exisit an injective homomorphism A\rightarrow B. If we have (R,A)\sqsubseteq(S,B) and (S,B)\sqsubseteq(R,A), then the well-ordernigs are isomorphic, we write (R,A)\equiv(S,B) for that.

The collection \mbox{OT}(W)=\{x|x\equiv W\} contains all the well-orderings isomorphic to a well-ordering W, and as it contains all the relevant structural information of the ordering, it is called the ordering type of W.

And now ... it gets complicated. We defined \mbox{OT}(W) as a collection, but not as a set! The axioms of set theory require sets to obey some restrictions - and this collection does not do so. It is a so-called proper class, that is a collection which is too big to be a set. However, it is not necessary to understand the reasons right now, and so I will not give any. The important thing is that being proper classes makes ordering types pretty hard to handle, which is why mathematicians had to invent a different method. For every ordering type, they gave a representative, that is a well-ordering which is isomorphic to the others, but has an additional property that uniquely determines it. These representatives are called ordinal numbers.

While originally I wanted to discuss ordinal numbers in detail with this post, the post turns out to become longer than I expected. I think, for this time, the amount of new knowledge floating through my dear readers' brains is enough.

Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)

Link List 6
Mon, 12 Mar 2012 23:00:00 GMT

And the next link list ... shorter, but hopefully more interesting this time.

The unix-jun72 project has scanned in a printout of 1st Edition UNIX from June 1972, and restored it to an incomplete but running system - in which one has to use ed as editor. I wonder how much modern software could be ported to this.

http://pdp11.aiju.de/ - a pdp11 emulator for the browser, also with an old UNIX.

Unix 2nd edition manual - for those who are stuck with the above.

Digraphs and trigraphs - because on that old terminals, not all characters were supported. Somewhat similar problems like we have today.

Turingmaschine mit sed

Pagekite - bring your localhost servers on-line. I have a vserver now, but this might be nice.

The Cartoon Guide to Löb's Theorem

The completeness and compactness theorems of first-order logic

Deutschland fördert die Ausbildung von Kindersoldaten

Umfassende Steuertipps für Studenten und wie Studenten sich Steuern von Morgen sparen

Amazonas-Pilz verzehrt Plastik

Deutschland im medienpolitischen Steinzeitalter

Zehn Jahre Arch Linux - grats!
Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)

Minix
Wed, 07 Mar 2012 16:30:00 GMT

If there is something that can be said about Software, that is that it sucks and it is boring, at least in most cases. With currently two previews for big projects, Windows 8 and Ubuntu 12, the new release of Minix is somewhat deemed to the background - without deserving it, in my opinion.

With Windows constantly crashing in my VirtualBox, and having a design that gives me the feel of looking at a bad PowerPoint File, and Ubuntu not really having anything remarkable at all except wallowing in the crap of app-stores and cloud services, the small but stable Minix system is really refreshing.

While most people seem to prefer a fully over-engineered interface to live out their subtle hate against computers, I like to see a new system with new concepts and new ways of solving problems beyond the color and shape of buttons.

However, of course, as a productive System, Minix seems more mature than GNU Hurd, but is probably still not usable for everyday work, due to the lack of drivers and software. However, that can also be seen as a chance: There is still work to do, and you can be the one doing this work and getting expierience.

Knowing how to use a computer is something very important in those days - computers are more than machines - in the same way as engines are more than machines. They changed our world in a way that nobody would have imagined. And Unix means more than a bunch of standards, it means the knowledge of generations of coders.

Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)

Link List 5
Tue, 06 Mar 2012 15:00:00 GMT

This week, there were less interesting links, but still, I have a few ... A lot of image links this time.

The popular orange/blue contrast

Make any photo 3d using the Gimp - impressive, but I have not tried it myself yet.

Memes in the year 2030

Voltalinux - a GNU/Linux distribution based on Slackware Linux and the pkgsrc package system 

Doktor House - Do I Look Like An Idiot? - that show is so awesome!

The Internet of Yesterday and Today

Giant Prehistoric Penguins Stood Nearly 5 Feet Tall

http://9gag.com/gag/2875781 - I like growing tomatos, as you may remember.

Unicode Character 'PILE OF POO' - what the world needs!


Verein für den Erhalt der bayerischen Wirtshauskultur - aber sowas von!

Eine Odyssee durch die griechische Bürokratie - ziemlich idiotisch, aber bevor man auf die Griechen schimpft ...

Mangelnde Transparenz: Deutschland nicht besser als Sri Lanka - zumindest wenn es darum geht, wofür die Steuern ausgegeben werden.

DNP - Wundermittel oder gefährlicher Wahnsinn? - Naja, ich finde Bodybuilding generell irgendwie Wahnsinn, aber gut dass die Leute sich mit sowas auseinandersetzen. Es gibt zwar viele Möglichkeiten der Unterstützung beim Abnehmen, aber Sport und gesunde Ernährung sind nicht optional.
Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)

Visual Lambda Calculus
Sun, 04 Mar 2012 13:00:00 GMT

If you ever wanted to explain the lambda calculus to eight year old children, maybe this is what you are looking for, a visualisation of the lambda calculus, using crocodiles and their eggs. The rules are rather simple, and they yield an alternative notation for lambda terms.

Another notation is the bubble notation, it uses colored circles, and denotes variables by empty circles. The notation may not be as clear as the crocodile notation, but the animations look nice. It can be generated via the software Visual Lambda - unfortunately I found no possibility to actually export the animations, so I made a screencast for the calculation of the factorial of 3.



(Youtube-Direktlink)
Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)

Parrots
Fri, 02 Mar 2012 22:25:41 GMT

Panel 1: Person A: "Hey! What are you doing?" Person B (holding a radio, playing music to a parrot): "Hey. Teaching my parrot the new Gemaboys song." -- Panel 2: Person A: "Why do you do that?" Person B (Now pointing a camera at his singing parrot): "To make a film of it." Person A: "What for?" -- Panel 3: A YouTube window with the parrot is shown. Person B: "To publish it on YouTube." Person A: "Why would anyone want to see that?" -- Panel 4: Person B: "Just uploading the song infringes copyright laws. But teaching that song to my parrot and then uploading a video of it does not." Person A: "Are you sure about that?"
Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)

Link List 4
Tue, 28 Feb 2012 06:16:38 GMT

This week's link list:

Promises (via) - a nice minimalistic game about promises and their value.

How Does A Touchscreen-Phone Work

Sony Foam City - a well-known image comes from there.

How To Create An Invisible Folder In Windows - well, sort of, at least.

Top To Bottom Land/Sea - interesting chart showing objects at several heights on our planet.

Artificial Burger Just around the Corner? - Well, probably it will take some more years, but anyway, this kind of research is interesting!

A deep-sea fish with a transparent head and tubular eyes - a weird creature.

Lifter Technology - I wonder whether this effect will be used for something someday.

How to Hack WPA WiFi Passwords by Cracking the WPS PIN

Fish Mimicking Robot - may be used to lead fishes someday.

Oscar The Bionic Cat - There is more interesting stuff about cats than lolcats.

Animated Screenshots

jhead - Exif JPEG Header Manipulation Tool

Coin Game - A coin can be placed anywhere it is touching two other coins.

Die Bibel soll umgeschrieben werden - naja, so ganz stimmt das nicht, aber man könnte schon auf die Idee kommen, zumindest wenn die zitierten Aussagen wirklich wahr sind.

Youtube mahnt Nutzer wegen Vogelgezwitscher ab - ich frage mich ja, was passieren würde, wenn man einem Papagei beibringt, ein urheberrechtlich geschütztes Werk zu singen.

Alkoho vs. Canabis - wow, und das auf einem Mainstream-Sender.

Der Iran macht unsere Bratwürste teuer - und so hat alles auch seine guten Seiten.

Mac OS X Lion erlaubt virtualisierung - allerdings weiß offenbar niemand, ob auch auf nicht-mac-hardware.

Blogs abonnieren, wie funktioniert das? - damit es auch endlich jeder weiß!
Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)

Guess what this interesting structure is ...
Fri, 24 Feb 2012 23:16:45 GMT

Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)

Zeitschrift "Das Parlament" zum Tierschutz
Fri, 24 Feb 2012 19:00:00 GMT

Auf der Seite des Bundestages gibt es Texte, die offenbar als Beilage der Zeitschrift "Das Parlament" gedruckt wurden, und sich mit dem Themenkomplex Tierschutz in unserer Gesellschaft befasst. Weder war mir diese Zeitschrift bisher bekannt, noch habe ich alle Texte ganz durchgelesen, es scheint aber generell interessant zu sein. Außerdem finde ich es gut, dass das Thema inzwischen in der Gesellschaft angekommen ist.

Inwieweit allerdings solche Diskussionen auf halbwegs hohem Niveau sinnvoll sind, ist natürlich fraglich, denn letztlich werden die moralischen Entscheidungen die der Gesellschaft am Ende per Gesetz aufgezwungen werden auf Stammtischen entschieden.

Ich las vor Allem einen eher Tierrechtskritischen Artikel, "Das Bein in meiner Küche". In ihm wird die Position vertreten, dass eine Gleichbehandlung von Menschen und Tieren menschenfeindlich sei, und dass der Zusammenhalt von Menschen als solcher nicht durch deren biologische Verwandtschaft, sondern durch deren gesellschaftliche Bindungen gerechtfertigt ist, weshalb auch Haustiere wie Hunde in dieser Gesellschaft eine gewisse Sonderstellung haben, trotz des Fehlens einer biologischen Verwandtschaft, weil sie am gesellschaftlichen Leben teilnehmen.

Ich teile beide Meinungen natürlich nicht, aber mir ist ungefähr klar, wie der Autor zu seiner Gesinnung kommt - daran sind auch inhaltliche Fehler und Denkfehler beteiligt. Der Autor kann sich zum Beispiel nicht vorstellen, dass man aus einem brennenden Haus zuerst ein Tier rettet, und dann erst einen Menschen - ich hingegen hoffe einfach, dass ich niemals in die Situation kommen werde, mich zwischen zwei Leben entscheiden zu müssen. Ich wüsste nicht, ob ich einen Serienmörder eher retten würde, als einen Minensuchhund.

Letztendlich ist eine Begründung der Bevorzugung des Menschen durch gesellschaftliche Bindungen auch wieder ein Problem, denn es gibt auch genügend Menschen, die nicht an der menschlichen Gesellschaft teilnehmen, vor Allem Schwerbehinderte, oder schlichtweg Außenseiter.

Wir haben hier die Schwierigkeit, dass es sich um menschliche Moralvorstellungen handelt, die durch die Umstände nicht unbedingt begünstigt werden. Wir müssen töten um zu leben, ob es nun Tiere oder Pflanzen sind. Die ganze belebte Natur ist eigentlich ein einziges fressen und gefressen werden. Wir haben das Bedürfnis, uns darüber hinwegzusetzen, doch die Natur macht es uns nicht leicht, dafür einen sinnvollen Rahmen zu finden. Man würde gerne irgendwo die Grenze ziehen, und hätte gerne eine intuitive Begründung dafür, das Finden einer solchen Begründung zu einer gezogegen Grenze hält aber selten einer Hinterfragung stand. Wir wollen nicht einfach "Mensch sein" als moralisch sinnvolles Maß akzeptieren, aber außer der für uns nicht befriedigenden Ähnlichkeit der Erbinformationen gibt es nicht viel was alle Menschen gemeinsam haben - nicht den Verstand, nicht das gesellschaftliche Leben, noch nicht einmal das anthropomorphe Aussehen. Es gibt nahezu beliebig starke Ausreißer (die man meistens im Spektrum schwerer Krankheiten findet), denen wir aber ebenfalls Menschenrechte zuweisen wollen. Wir möchten "Leidensfähigkeit" als Maß nehmen, aber was ist Leid?

Wir werden uns in Zukunft voraussichtlich noch größeren Problemen zu stellen haben. Noch vor Jahrzehnten war es unvorstellbar, dass man Erbinformationen zwischen Lebewesen übertragen kann, oder gar künstlich herstellen kann. Wer weiß ob man irgendwann das reine "Retortenbaby" zumindest theoretisch herstellen kann. Oder zumindest den nicht von einem Menschen zu unterscheidenden Androiden. Dann wird selbst unser Begriff von "Leben" relativiert, wie einst unser Begriff von Menschlichkeit.
Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)

Link List 3
Tue, 21 Feb 2012 01:00:00 GMT

And the third link list:

DuoLingo - Learn a language for free, and simultaneously translate the web.

Talking Robot Mouth Mimics Human Speech (via) - impressive, and somehow terrifying.

The future of our world - A small glimpse into a timeline of epic scale.

http://fatpita.net/?i=5025 - a nice, somewhat disturbing comic.

10 random video game facts

An Excerpt from the book "Dumbing Down our Kids" by Charles Sykes

Markets are efficient if and only if P = NP (via) - I have not actually read it, and I doubt the claims made there, but still worth linking.

Debian Position on Software Patents - Very interesting.

Boy dies after masturbating 42 times - but who counted it?

How Commercial Journals Could Add Value - this is not going to happen, as it would mean actual work for them.



Making Crash Bandicout (which was btw also written in Lisp)

Scumbag DNA - I love the memes!

Spongiforma squarepantsii - I don't want to live on this planet anymore!

Ende der Parkwache in Stuttgart - Zwei andere junge Männer hatten sich in einem Zelt mit ihren Unterarmen einbetoniert und mussten mit Spezialwerkzeug losgemacht werden.

Russisches Klopapier empört Kasachen - wenn sie sonst keine Probleme haben, passts ja.

Darum darf Werner N. legal kiffen - eigentlich traurig, dass man in solchen fällen überhaupt noch diskutieren muss.

Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)