Chill Out Math

Naive Isomorphism

2009-10-01T01:04:00.003+03:00

As one of my imaginary friends says "the mathematics are the science of form and quantity; mathematical reasoning is merely logic applied to observation upon form and quantity. The great error lies in supposing that even the truths of what is called pure algebra, are abstract or general truths". In this post I will try to observe and deduce properties of algebraic objects, escaping the usual structure theorem1 => theorem2 => theorem3. So, we will play in the backyard of group theory focusing on the first isomorphism theorem.

The simplest example of a group is the set of integers ℤ with addition. Another relatively simple group is the additive group of integers modulo n. For the particular case when n = 3, we have the group G = (ℤ3 ,*). We can see that these groups are somehow related, each element from ℤ can be put under the modulus operator,that is we divide it by 3 and take the remainder, and will yield an element of ℤ3. Formally, we write this:
let f : ℤ ->; ℤ3 be a mapping such that f(x) = x mod 3
It can also be noticed that f(x+y) = ( (x+y) mod 3) = (x mod 3) + (y mod 3) = f(x)+f(y), that is, the operation is the same(preserved) on both sides of the mapping. This is structure preserving property is important because if we know something about the structure of a group we can say something about the structure of all the groups homomorphic with it.
A more careful look at the structure of those groups will uncover another useful facts:

for every element of ℤ3 we have a corresponding element of ℤ which means the function is surjective

every element of ℤ which is a divisible by 3 is mapped on the identity of ℤ3

If we now look at the additive group of all elements in ℤ divisible by 3 A={...-9,-6,-3,0,3,6,9...} and ℤ3 we can come up with a different homomorphism (which is both surjective and injective) from the set of sets A'={g+A/ for every g in ℤ} and ℤ3.
I will let you think what this homomorphism might be and in the mean time lets see what other useful information can be extracted from this. Suppose we've found this mapping from A' to ℤ3 ,lets call it θ, then we have the following homomorphic mappings:
- f from ℤ to ℤ3
- g from ℤ3 to ℤ3 the identity function ( g(y) = y )
- θ from A' to ℤ3
- h from ℤ to A' , h(x) = x+A

So we can decompose the mapping f in f = g * θ * h.

Now, that we've quite enjoyed ourselves with this concrete example, lets state these properties in an abstract form so they could be applied for all other groups with different mappings between them(i.e. complex numbers, symmetries, dihedral groups, etc).

The first isomorphism theorem

Let G and H be groups and φ : G → H a group homomorphism. Then:

Im φ is a subgroup of H
Ker φ is a normal subgroup of H
Im φ is isomorphic with the quotient group G/Ker φ

The first statement makes use of the basic notions of groups and homomorphisms. Being groups, G and H are sets with binary operations(the binary operation on G can be different from the one on H). For the group to exist the binary operation must respect the following laws:

closure law: let x,y be elements of the group G, then x • y is still in G
associative law: (x • y) • z = x • (y • z), for all x,y,z in G
identity law: there exist e in G such that e • x = x • e = x, for all x in G
inverse law: for all x in G there exists y in G such that x • y = y • x = e

A subgroup of a group G is a subset G' ⊆ G such that G' is a group relative to the binary operation in G.
The binary operation • is a function from G × G to G, that is, the elements with the binary operation can't spawn elements that are not in G. It can be easily seen that there are n^(n^2) possible binary operations, where n = |G|, because |G × G| = n^2 and for every element of G × G there are n possible mappings in G. For example for two sets |A| = 2 and |B| = 3 we have for the first element of A 3 choices in B and for the second element in A another 3 choices in B, but the second time those 3 choices can be combined with the previous 3 choices of the first element resulting in 9 choices, that is, 3^2.

The homomorphism φ is a mapping from G to H having the structure-preserving property: φ(x • y) = φ(x) • φ(y). If the mapping is also bijective then it is called isomorphism. It's origins are in the Greek language: homos morphe meaning "similar shape", and isos morphe meaning "equal shape".

The image and the kernel of a mapping are both subsets, the first of H and the second one of G:
Im φ = {y in H / y = φ(x) for x in G} ⊆ H;
Ker φ = {x in G / φ(x) = e, where e is the identity in H} ⊆ G.

It is called a normal subgroup of a group G ⊆ G', a subgroup G' if x • G' • x^-1 ⊆ G' for every x in G. If G is abelian then every subgroup of G is normal since x • g' • x^-1 = x • x^-1 • g' = g', for each g' in G' and x in G. The converse, however, is not true: a group can have it's subgroups normal and not necessarily be commutative. A trivial counterexample to sustain this is the quaternion group which is a non-abelian group with 8 elements under multiplication:
Q={-1, i, j, k / (-1)^2 =1, i^2=j^2=k^2=ijk=-1}.
For any subgroup G' we can define an equivalence relation x ~ y if and only if x = y • g', for g' in G'. The equivalence classes for this relation are called cossets and defined as follows:
xG' = {x • g' / g' is an element of G'} -- left cosset of G' in G , similarly :
G'x = {g' • x / g' is an element of G'} -- right cosset of G' in G.

If G' is a normal subgroup of G we have xG' = G'x, for every x in G because:
x • G' = x • G' • e = x • G' • x^-1 • x = (x • G' • x^-1 ) • x = G' • x ■

Which means that the left cossets of a normal subgroup are the same with the right cossets. And since we no longer distinguish between them we write G/G' to denote the set of all cossets of G' in G. This forms a group under multiplication called the quotient group of G in G'.

I've put it all together in a small drawing for a better overview. I have denoted by θ the isomorphism between the quotient group G/Kerφ and Imφ.

At this point the first two conclusion of the theorem should be clear and the reader should be able to prove them easily. For the third conclusion, if you haven't already figured out what the second isomorphism in the example was, you might want to check this mapping:
θ(xG) = φ(x)

Why your recently bought software is crappy?

2009-09-23T11:05:00.002+03:00

You just cobble something together to sell, it may not be any good . As long as you can fool people into buying it, you can also make better versions later. So, then you get these version numbers ... even with decimals, version 2.6 or 2.7 . That nonsense ... while version 1 should have been the finished product.

(Edsger W. Dijkstra)

Since Dijkstra made the cited comment above, programming languages and compilers reached new levels. They can prevent the programmers from doing mistakes by limiting their actions and by automatically generating critical parts of the code(memory management, hardware interference etc). Modern languages like C# or Java can be used with poor programing or mathematical knowledge with almost the same efficiency for most practical purposes.

But it seems that most software is still full of bugs or works slow even on powerful machines. If you are wondering how can this be, let's take a closer look at what is really happening.

Raj and the software industry

It's 10:00 AM and the office is quite empty today. Raj is one of the few employees that came to work. It's not that he wasn't scared, but his behavior should make an example to all his team, so he took this as one of the ugly things that must sometimes be done in order to stay above the pile.

This time the bomb was 5 miles away from their “high security” software park. The bastards got bored waiting for the Starcraft 2 release and started blasting their own brothers in the real world. Isn't there someone to tell them “GG, you won, go home” or are we all waiting for the American Battlecruisers to arrive ?

His meditation on the subject is abruptly ended by the ringing phone. On the other side the American CEO is not happy, their clients seems to be complaining. They are talking about some promised feature that is not working and they must fix it in 2 days. But why they have to make such a big deal out of it ? ... fucking rednecks ...This couldn't come in a more inappropriate time, when half of the development team is not there and all it's members are new. Almost all the experienced programmers have quited in order to work in the US and they made the decision to hire only students or unskilled developers and train them on specific tasks. This may seem a bad decision since the salary for a experienced programmer is by a few degrees smaller than in a civilized part of the world, but greed is known as the main characteristic of the human nature and here it makes no exception.

"Treason!" shouted his Majesty King Pest the First.
"Treason!" said the little man with the gout.
"Treason!" screamed the Arch Duchess Ana-Pest.
"Treason!" muttered the gentleman with his jaws tied up.
"Treason!" growled he of the coffin.

(King Pest -- Edgar Allan Poe)

The deadline is quickly arriving and Raj knows there is no time to think about these decisions now. He gathers the whole team in a conference in order to solve the problem. Even if they are quite new, they know by now that this situation requires a lot of overtime. They are not computer scientists, their knowledge being limited at “For Dummies” series. Names like Tanenbaum or Knuth are thought as the Christmas tree, or the name of a polar bear, so the only thing left to do is praying to the Google god for help.

Raj is not a born leader, he became manager after 5 years of hard working as a programmer, almost at the same time he got his bachelor degree in computer science at the local university. But in this kind of business experience is more important and he manages to keep the situation under control by breaking the task in smaller parts and assigning one to every member (he sure doesn't need studies for this).

After the lunch break the internet connection runs very slow, making everyone nervous. They blame the old servers , which may give new meaning to the word primitive, but after a quick inspection a torrent is found on one of the main servers. It was downloading some pirated movies.

-A torrent !?!? Who started it ? Asks Raj hardly breathing. A more thorough investigation must be made.

A few minutes passed and the responsible programmer is found. He receives a mail to come in one of the meeting rooms so Raj can force a certain amount of wisdom upon him.

A simple warm-up routine in set theory

2009-09-08T16:32:00.037+03:00

Since time usually flows only in one direction and this is my first post, I will tackle some aspects from the foundations of mathematics: set theory. Actually this post is trying to solve(hopefully is solving) an interesting problem that I found in The Art and Craft of Problem Solving by Paul Zeitz.

Putnam 1995:

Let S be a set of real numbers that is closed under multiplication(that is, if a and b are in S, then so is ab). Let T and U be disjoint subsets of S whose union is S. Given that the product of any three (not necessarily distinct) elements of T is in T and that the product of any three elements of U is in U, show that at least one of the two subsets T, U is closed under multiplication.

You may want to consider trying to solve this yourself before reading any further. Also I have to mention that this is not it's standard proof, it is just a proof that I thought of, there may be other, similar or totally different, proofs. If you've found a different solution or you found a leach in mine please let me know.

Solution:

∀ a, b, c in T we have abc ∈ T

∀ a', b', c' in U we have a'b'c' ∈ U

T ∪ U = S and T ∩ U = ∅

I'm going to use proof by contradiction to show that T or U is closed under multiplication.

So lets assume T and U are not closed under multiplication. This means that there exists two elements a, b in T such that ab is not in T. But if ab is not in T, then it must be in U because S is closed under multiplication. The same goes for two elements a' and b' in U : their product is not in U because we supposed U is not closed under multiplication, so it must be in T. If we multiply all of them we get aba'b' which must be an element of T since a, b, a'b' are three elements of T and their product must be in T. By the same reasoning aba'b' is an element of U since ab, a', b' are three elements of U.

So abba'b' is in T ∩ U, but T ∩ U is empty and we reached a contradiction which means that the assumption that both T and U are not closed under multiplication is false.

I have chosen this problem because despite it's simplicity it displays some important ideas:

-proof by contradiction

-symmetry

-reducing the problem by ignoring less important information(like the fact that the elements of S are real numbers)