Giving BTRFS a second chance
Tue, 16 Feb 2016 23:21:53 GMT

External Content not shown. Further Information.

I've tried BTRFS before, and it was very unstable. Now that it is in the mainline kernel, I decided to give it another shot.

The main reason was online compression. My personal chat log files are larger than 4G now, when uncompressed, but they are very repetitive and therefore compress well. I could have written some logrotate(8) script. This is the common suggestion, especially on the Raspberry Pi, on which "every processor cycle is precious". The Raspberry Pi is 21 times faster than my first computer, and has 262144 times as much RAM, and had online compression. Honestly, this is 2016, not 1992.

The only filesystem from the standard packages of Raspbian that supports compression is NTFS. Reiser4 is also available and supports compression, but the snapshot facility of BTRFS convinced me. (Unfortunately, ZFS is not supported.)

On my raspi, since then, it works great. On my PC, I tried to convert an ext4 partition into BTRFS. Don't do that, at least not before doing a backup. However, now it works. And it runs faster than ext4, at least it feels like that.

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

Link List 200
Tue, 16 Feb 2016 19:10:33 GMT

External Content not shown. Further Information.

Now finally FF Sync works. There might be duplicates in this list, and not everything is "brand new". Sorry for that.

Popular Culture:

Nerd Culture:

Science, Software, Hardware:

Zeroth World:

Comics/Images/Audios/Videos/Games/Art:

Quotes:

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

Link List 199
Tue, 09 Feb 2016 18:19:56 GMT

External Content not shown. Further Information.

Popular Culture:

Nerd Culture:

Science, Software, Hardware:

Zeroth World:

Comics/Images/Audios/Videos/Games/Art:

Quotes:

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

Monitor
Mon, 08 Feb 2016 12:00:00 GMT

Panel 1: Two persons are standing next to each other. The right person holds a gadget in his left hand and says: "So this is our new cure against depression." The left person says: "It looks like a smartwatch." -- Panel 2: The right person says: "It's an ankle monitor. Whenever the subject tries to commit suicide, it will alert the local emergency call services." The left person says: "How is that supposed to be a cure?" -- Panel 3: The right person says: "What do you mean?" The left person looks angrily at the right person.

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

Well-orderings: The backbone of mathematics
Mon, 08 Feb 2016 08:01:46 GMT

Before we start

This was again a presentation for the Best mathematics club in the multiverse. It is meant for both younger and older students, as well as working mathematicians. Its objective therefore lied in breadth rather than depth. I removed lots of topics I wanted to talk about, as the talk I gave got too long. It is not a scientific talk. Comments and corrections are welcome.

Why well-orderings?

Why are well-orderings the backbone of mathematics? A similar claim for Zermelo-Fraenckel-Set-Theory (ZFC) was made by Oliver Deiser in his book Einführung in die Mengenlehre, about the constructible cardinal numbers. In ZFC, cardinal numbers are specific ordinal numbers, and ordinal numbers are sets which are well-ordered by the \in-Relation (roughly speaking). And in fact, the study of well-orderings is an important part of set theory. In recursion theory, well-orderings and well-quasi-orderings can be used for termination proofs, and are also important for newer foundational systems that base on type theory. In proof theory, well-orderings can measure the consistency strength of a theory. The axiom of choice is closely related to well-orderings, and it is an important principal in classical mathematics, specifically analysis, stochastics and topology.

A short definition

Definition. In short, a well-ordering is a linear ordering relation with no infinite descending chains.

That is, if we have some collection of objects ("Set") A, and a binary relation <_A on this collection, then the pair (A,<_A) is a well-ordering, if it satisfies:

  • linearity: \forall_{a,b\in A}. a <_A b \vee a = b \vee b <_A a.
  • irreflexivity: \forall_{a\in A}.\neg a <_A a
  • transitivity: \forall_{a,b,c\in A}. a <_A b \rightarrow b <_A c \rightarrow a <_A c
  • well-foundedness: Let B\subseteq A and B\neq\emptyset. Then B has a <_A-minimal element.

We write a >_A b for b <_A a, and a \le_A b for a <_A b \vee a = b and a \ge_A b for b \ge_A a. In most cases it is clear from the context which relation we mean, so we shall leave the index out and write < instead of <_A, etc. We often just write A instead of (A, <_A) if the ordering we mean is clear (or no specific order is given).

Canonical examples for well-orderings are the default ordering on \mathbb{N}_0, and on all its subsets – especially also all of its finite subsets, and the empty set (no axiom sais that there has to be an element at all).

Exercise: Show that if < is a well-ordering, then \le is reflexive, transitive, antisymmetric (\forall_{a,b}.a\le b\rightarrow b\le a\rightarrow a=b) and every decreasing sequence is stationary.

Definition: We call orderings which are reflexive, transitive, antisymmetric, and in which every decreasing sequence is stationary, weak well-orderings.

Most people have probably heard of the concepts of homomorphism and isomorphosm. The idea is that, given two structures, there is a "renaming" between these structures that preserves the structure fully or partially.

Definition: Let A and B be well-orderings, and f:A\rightarrow B, such that \forall_{a_1,a_2\in A}. a_1 <_A a_2 \rightarrow f(a_1) <_B f(a_2). Then f is called a homomorphism. A bijective homomorphism is called isomorphism.

(Notice that by definition, every homomorphism is injective.)

Let us define [n]:=\{m\in\mathbb{N}_0\mid m<n\}, with the canonical ordering on it.

Lemma: For all m,n\in\mathbb{N}_0, m\le n if and only if there exists a homomorphism f : [m]\rightarrow[n].

Proof. "\Rightarrow": Just set f x = x. "\Leftarrow": This is an instance of the well-known Pigeonhole principle.

Lemma: Every finite subset X\subset\mathbb{N}_0 with n elements is isomorphic to [n].

Proof. By induction. For n=0 this follows from extensionality. As step, notice that X is non-empty, and therefore has a minimal element, say x. By induction, there is an isomorphism f : [n-1] \rightarrow X\backslash\{x\}. Then trivially, gz:=\left\{\begin{array}{cl} x & \mbox{ for } z = n \\ f z & \mbox{ otherwise}\end{array}\right. is an isomorphism.

Lemma: Every infinite subset X\subseteq\mathbb{N}_0 is isomorphic to \mathbb{N}.

Proof. Let us define

\left<n\right>:=\left\{ \begin{array}{rl} \emptyset & \mbox{ for } n = 0 \\ \left<n-1\right>\cup\min(X\backslash\left<n-1\right>) & \mbox{ otherwise }\end{array}\right.

From our previous lemma, we get isomorphisms f_n:\left<n\right>\rightarrow[n]. Notice that the graphs G_n=\{(x,y)\mid f_n x=y\} of these isomorphisms are strictly increasing, that is, G_0\subsetneq G_1\subsetneq G_2\subsetneq\ldots. Therefore, we can define G_\omega:=\bigcup_i G_i, and this must be the graph of a bijective function f_\omega:X\rightarrow\mathbb{N}.

Lemma: Induction is equivalent to well-ordering on \mathbb{N}.

Proof. "\Rightarrow": Let X\subseteq\mathbb{N}, and X\neq\emptyset. Then there is some n\in X. We do induction on n. For n = 0, n is trivially minimal. Now in the step, if we already know that all sets containing a number < n have a minimum, and n\in X, either n is already the minimum of X, or X contains a smaller element. "\Leftarrow": Assume there was some set X such that 0\in X, X+1\subseteq X but X\neq\mathbb{N}. Then there is some minimal element in n\in\mathbb{N}\backslash X. Trivially, n\neq 0 and n-1\not\in X. Contradiction.

Side Note: This lemma is related to Markov's Principle, which is a theorem about intuitionistic logic. It is an example for a theorem which holds for every instance, but is not provable in general.

Exercise: If this is new to you: Before you read on, can you think of infinite well-orderings which are not isomorphic to \mathbb{N}?

Solution. Of course, there is no unique solution to this. One simple example is the canonical ordering on \{\lim_{m\rightarrow n}(1 - \frac{1}{m})\mid n\in\mathbb{N}_0\}. Essentially, it is almost the same as \mathbb{N}, with one exception: 1 is larger than all other elements.

Comparing and combining well-orderings

Something very common in mathematics is to view structures "up to isomorphism". For example, one talks about the "Field F_2", even though in the common mathematical theories it is not unique. We will do the same with well-orderings now: We identify isomorphic well-orderings. Therefore, we can say, all finite well-orderings are given by [0],[1],[2],\ldots. We already began comparing finite well-orderings by their homomorphisms, and we will just continue doing so by saying, a well-ordering a is less-than-or-equal a well-ordering b, written a\le b, if there is a homomorphism a\rightarrow b. Then, we go even further, and leave out the squared brackets, that is, we write 0,1,2,\ldots for the finite well-orderings.

We have already seen that the smallest infinite well-ordering is the canonical ordering on \mathbb{N}, which we will call \omega.

Lemma: Let (x, <) be a well-ordering, and y\in x. Then (\{z\in x\mid z<y\}, <) is also a well-ordering which is not isomorphic to (x, <).

Proof. Trivially, (\{z\in x\mid z<y\},<) is also a well-ordering. Assuming there was an isomorphism f:\{z\in x\mid z<y\}\rightarrow x, then \{z\in x\mid f(z)\neq z\} is non-empty and contains a smallest element m such that f(m)\neq m. Then there must be some n\in x such that f(n)=m, but as m was minimal and n\neq m, we know that n>m, therefore f(n)>f(m), so m>f(m), which means that f(f(m))=f(m) since m was minimal, and therefore f(m)>f(f(m))=f(m). Contradiction.

Lemma and Definition: For every two well-orderings a,b, the sum a+b is defined as the disjoint union of a and b with the ordering that makes every element of a smaller than every element of b. a+b is a well-ordering.

Proof. Exercise.

Notice: The addition of well-orderings is not commutative. 1+\omega=\omega, while \omega+1 is the well-ordering in our above example.

Lemma and Definition: For every two well-orderings a,b, the product a\cdot b is the lexicographical ordering on a\times b: (a_1, b_1) < (a_2, b_2) :\Leftrightarrow a_1<a_2\vee(a_1=a_2\wedge b_1<b_2).

Notice: The product of well-orderings is not commutative. 2\cdot\omega=\omega, but \omega\cdot 2=\omega + \omega.

Notice: The finite well-orderings with addition and multiplication are essentially \mathbb{N}.

Well-orderings in set theory

While currently, in the realm of logic, there are new tools being built to cope with this problem, for well-orderings the problem has been solved in an elegant way inside set theory, which is currently the one which is most well developed.

Ordinal Numbers

Definition: A set x is called an ordinal number if for all y\in x we have y\subseteq x and x is well-ordered by \in. The class of all ordinals is called On.

Lemma: \emptyset\in x for x\in On.

Proof. x contains a minimum y. Assume there was some z\in y, then also z\in x, and y would not be minimal anymore. Contradiction. Thus, y=\emptyset.

Lemma: If y\in x and x\in On, then y\in On.

Proof. As y\in x, also y\subseteq x, so trivially, y is well-ordered by \in. Assuming z\in y and t\in z, by transitivity we have t\in y, so every element of y is a subset. y\in On.

Theorem: If x and y are ordinals whose well-orderings regarding \in are isomorphic, then x=y.

Proof. Call the isomorphism f. Assuming f\neq id, there must be a minimal z\in x such that f(z)\neq z. Trivially, f(\emptyset)=\emptyset, so z\neq\emptyset. Therefore, there is some t\in z. Trivially, we have f(z)=\{f(t)\mid t\in z\}=\{t\mid t\in z\}=z. Contradiction.

Lemma: If x\in On, y\subseteq x, y\neq\emptyset, then \exists_{a\in y}\forall_{b\in y}. a\in b \vee a = b.

Proof. By the foundation axiom, we get an a\in y such that a\cap y=\emptyset. Take any b\in y. b\not\in a, because a\cap y = \emptyset. By linearity of x therefore a\in b\vee a = b.

Lemma: If a is a set of ordinals, then \bigcap a is an ordinal.

Proof. We first prove that \bigcap a is an ordinal number. If x\in\bigcap a, then \forall_{b\in a}, x\in b, therefore \forall_{b\in a}, x\subseteq b, therefore x\subseteq\bigcap a. We still have to prove that \in is a well-ordering on \bigcap a. Irreflexivity follows from the foundation axiom: No set may contain itself. For linearity, consider b,c\in\bigcap a, that is, b\in d, c\in d for all d\in a. Since d is an ordinal, linearity holds for b,c. Well-foundedness of \in follows from the foundation axiom. Transitivity is left as an exercise.

Chaining a few more technical proofs, we could prove:

Theorem: For any two a,b\in On, we have a\in b\vee a=b\vee b\in a.

Corollary: Every set of ordinals is well-ordered by the \in relation.

We can generalize induction on \mathbb{N} to induction on On:

Theorem (Transfinite Induction): If for some proposition P we have P(\emptyset), and \forall y\in On.(\forall x\in y. P(x))\rightarrow P(y), then \forall x\in On. P(x).

Proof. Assume not. Then there is some x\in On with \neg P(x), and therefore \{y\le x\mid\neg P(y)\} is a well-orderet set and has a minimum \alpha, which is also the absolute minimum value with \neg P(\alpha). Trivially, \alpha\neq\emptyset, and by its minimality, also \forall x\in\alpha P(x), but this would imply P(\alpha). Contradiction.

Lemma: On is not a set.

Proof. If On was a set, On\in On. Contradiction.

Lemma: Every well-ordering (A,<) is isomorphic to some ordinal number.

Proof Sketch. Define f(\emptyset) = \min A. Now let f be defined for all \alpha\in\beta. If there is still an m\in A remaining, set f(\beta):=m. Otherwise, proceed. Since we assumed that A is a set, this procedure must terminate at some point.

The nice thing is that in this theory we have concrete objects to talk about, namely the ordinal numbers.

Zorn's Lemma

Zorn's Lemma is one of the three classically equivalent axioms independent of ZF: The well-ordering theorem, which says that every set has some well-ordering; the axiom of choice; and Zorn's Lemma. It is probably the one that is used most often explicitly outside of set theory.

Zorn's Lemma: If (P, <) is transitive, reflexive and every non-empty chain has an upper bound, then P contains a maximal element.

Notice: A maximal element might not be comparable with many other elements.

Definition: A Well-quasi-ordering is a well-ordering except for it may be nonlinear.

In some sense this generalizes the notion of trees. Zorn's Lemma can be reduced to some stronger property about well-quasi-orders:

Theorem: If (P, <) is transitive, reflexive and every non-empty well-ordered subset has an upper bound, then for all x\in P, P contains a maximal element which is comparable to x.

This essentially sais that if every branch of the tree is bounded, then there are leaves.

(Linear) Algebra

A vector space (V, +, \cdot) over a field F is defined by a few axioms that can easily be looked up in wikipedia.

Theorem: Every vector space has a base.

Proof 1. Take an arbitrary element. If the hull of the element is the whole space, you are done. Otherwise, take an element which is not in the hull and proceed. As the vector space is a set, this process must "end" after infinitely many steps: After "set" many steps.

Proof 2. All chains of bases are bounded. Therefore, by ZL, there is a basis.

Proof 1 is normally only done in the finite case, but also works in the infinite case, because of transfinite induction. Proof 2 uses Zorn's Lemma. Similarily, algebraic closure and many other theorems use Zorn's Lemma.

Fun Fact: The groups (\mathbb{R}, +) and (\mathbb{C}, +) are isomorphic.

Proof. It is easy to show that both are vector spaces over \mathbb{Q}, and as such, they have a countable base.

Recursion Theory

Consider a simple programming language: You have an arbitrary number of registers a[i] which are initially 0 and can store natural numbers. You have a command a[i]++ which increments the register a[i], and a[i]-- which decrements it if it is not 0. (We do not allow constructs like a[a[i]], the i must be constants.) You have an exit command. Furthermore, you have a command if a[i] == 0 then goto l1 where l1 is the line number to jump to. It is easy to show that this language is turing complete. So especially, it is generally undecidable, whether a program terminates.

However, we can change the semantics a bit: Attach every program line with an additional function f from ordinal numbers into ordinal numbers (or, if you want to implement it on a real computer, other well-orderings), which must satisfy the condition that it is strictly sublinear, that is, f\alpha < \alpha for all \alpha>0. In the beginning, you start with some ordinal number, that will, at every step, be decreased through the corresponding function. The program terminates on exit as before, or as soon as the ordinal is 0.

All programs in such a language terminate. What programs can be expressed depends on the values of the original ordinal number that we allow. By the way, this is not pure theory.

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

Link List 198
Thu, 04 Feb 2016 17:58:53 GMT

External Content not shown. Further Information.

I've lost track of which of my bookmarks I already posted. So … there might be duplicates from former Link Lists.

Popular Culture:

Nerd Culture:

Science, Software, Hardware:

Zeroth World:

Comics/Images/Audios/Videos/Games/Art:

Quotes:

  • I saw a guy today at Starbucks. He had no smartphone, tablet or laptop. He just sat there drinking his coffee. Like a psychopath.
  • Hipsters is what happens when you tell every child they're special
Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)

RSS Plzkthx?
Wed, 03 Feb 2016 20:45:47 GMT

External Content not shown. Further Information.

I am currently cleaning up my feed list. Omg, so many pages do not maintain their feeds. Many of them abandonned them entirely. Why would an admin do this?

Ah, of course. It's because feeds were simple, worked well, were not centralized and controlled by a big company. Sorry for asking.

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

Caulking
Mon, 01 Feb 2016 12:00:00 GMT

Panel 1: Two persons in front of a bathtub with mold. The left person says: "Sir, I hear you had a complaint." The right person says: "Yes, there is mold all over the caulking. Isn't the slogan of this hotel to offer guests the best of everything?" -- Panel 2: The left person takes some of the mold on his finger and says: "Yes, we do. That's Penicillium roqueforti. Have some! It's delicious."Panel 1: Two persons in front of a bathtub with mold. The left person says: "Sir, I hear you had a complaint." The right person says: "Yes, there is mold all over the caulking. Isn't the slogan of this hotel to offer guests the best of everything?" -- Panel 2: The left person takes some of the mold on his finger and says: "Yes, we do. That's Penicillium roqueforti. Have some! It's delicious."

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

Blog Pause till March
Tue, 26 Jan 2016 21:05:55 GMT

I have a lot of stuff to do, so during February, don't expect too many new posts. Furthermore, all my bookmarks are on another computer, that should have been synced using Firefox Sync, but somehow wasn't. So I cannot finish this week's link list now.

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

Childish fun is best fun
Mon, 25 Jan 2016 12:00:00 GMT

Panel 1: Teaching room with an oscilloscope and some kind of digital circuit on a breadboard. Its connected to the oscilloscope. The oscilloscope shows a christmas tree. The teacher is saying "Now find out how we did it. Then build your own". Panel 2: Two students are depicted. One is saying: "Hey, lets plot a penis". The other one answers: "Nah, that'd be too hard". Panel 3: The two students are childishly laughing their lungs out.

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