Isomorphism: Intro (Math 0)

If two things are essentially the same from a certain perspective, and they only differ in unimportant details, then they are isomorphic.

Comparing Amounts

Consider the Count von Count. He cares only about counting things. He doesn't care what they are, just how many there are. He decides that he wants to collect items into plastic crates, and he considers two crates equal if both contain the same number of items.

Now Elmo comes to visit, and he wants to impress the Count, but Elmo is not great at counting. Without counting them explicitly, how can Elmo tell if two crates contain the same number of items?

Well, he can take one item out of each crate and put the pair to one side.

He continues pairing items up in this way and when one crate runs out he checks if there are any left over in the other crate. If there aren't any left over, then he knows there were the same number of items in both crates.

Since the Count von Count only cares about counting things, the two crates are basically equivalent, and might as well be the same crate to him. Whenever two objects are the same from a certain perspective, we say that they are isomorphic.

In this example, the way in which the crates were the same is that each item in one crate could be paired with an item in the other.

This wouldn't have been possible if the crates had different numbers of items in them.

Whenever you can match each item in one collection with exactly one item in another collection, we say that the collections are bijective and the way you paired them is a bijection. A bijection is a specific kind of isomorphism.

Note that there might be many different bijections between two bijective things.

In fact, all that counting involves is pairing up the things you want to count, either with your fingers or with the concepts of 'numbers' in your head. If there are as many objects in one crate as there are numbers from one to seven, and there are as many objects in another crate as numbers from one to seven, then both crates contain the same number of objects.

Comparing Maps

Now imagine that you have a map of the London Underground. Such a map is not to scale, nor does it even show how the tracks bend or which station is in which direction compared to another. They only record which stations are connected.

Your Spanish friend is coming to visit and you want to get them a version of the map in Spanish. But on the Spanish maps, the shape of the tracks is different and you can't read Spanish. What's more, not all the maps are of the London Underground! What do you do? Well, given a Spanish map and your English map, you can try to match up the stations (through trial and error) and if the stations are all connected to each other in the same ways on both maps then you know they are both of the same train system.

More precisely, consider the following smaller (fictional) example. There are stations Trafalgal, Marybone, Oxbridge, Eastweston and Charlesburrough on the English map. Marybone is connected to all the other stations, and Charlesburrough is connected to Eastweston. (There are no other connections)

%note: We don't want to worry about whether stations are connected to themselves. You can just assume no station is ever connected to itself.%

%note: If one station is connected to another, then the second station is also connected to the first. So since Marybone is connected to Eastweston then Eastweston is connected to Marybone. If it seems silly to even mention this fact, then don't worry to much. It's just that we might just have easily decided that there's a one-way train running from Marybone to Eastweston but not in the other direction.%

Assume the Spanish map has the following stations: Patata, Huesto, Carbon, Esteoeste, and Puente de Buey. Assume also that Huesto is connected to every other station, and that Carbon is connected to Esteoeste. (Again, there are no other connections).

Then the two maps are essentially the same for your purposes. They are isomorphic (as [-graph graphs], in fact), and the way that you matched the stations on the one map with those on the other is an isomorphism.

Isomorphisms

Imagine that you have a London Underground Official Spanish-to-English Train Station Dictionary that tells you how to translate the names of the train stations. So, for example, you can use it to convert Patata to Trafalgal. Then this dictionary is an isomorphism from the Spanish map to the English one.

In particular, the dictionary translates Huesto to Marybone, Patata to Tralfalgal, Puento de Buey to Oxbridge, Esteoeste to Eastweston, and Carbon to Charlesburrough.

You could also get a London Underground Official English-to-Spanish Train Station Dictionary. Then, if you were to use this dictionary to translate Tralfalgal, you'd get back Patata. Hence your first original translation of that station from English to Spanish has been undone.

In particular, the dictionary translates Marybone to Huesto, Tralfalgal to Patata. Oxbridge to Puento de Buey, Eastweston to Esteoeste, and Charlesburrough to Carbon.

In fact, if you take the English map and translate all of the stations into Spanish using the one dictionary and then translate back, you'd get back to where you started. Similarly, if you translated the Spanish map from Spanish into English with the one dictionary and back to Spanish with the other you'd get the Spanish map back. Hence both of these dictionaries are complete [-inverse inverses] of each other.

In fact, in category theory, this is exactly the definition of an isomorphism: if you have some translation (Morphism) such that you can find a backwards translation (morphism in the opposite direction), and using the one translation after the other is for all intents and purposed the same as not having translated anything at all (i.e., no important information is lost in translation), then the original translation is an isomorphism. (In fact, both of them are isomorphisms).

What if you had a different pair of dictionaries.

In particular, what if the Spanish-to-English dictionary translates Huesto to Marybone, Puento de Buey to Tralfalgal, Patata to Oxbridge, Carbon to Eastweston, and Esteoeste to Charlesburrough?

Then if we translate from Spanish into English, and then translate back with the original English-to-Spanish dictionary, then Patata is first translated to Oxbridge, but then it is translated back into Puente de Buey. So it does not reverse the translation. Hence this is not an isomorphism.

However, what if the English-to-Spanish Dictionary translates Marybone to Huesto, Oxbridge to Patata. Eastweston to Puento de Buey, Tralfalgal to Esteoeste, and Charlesburrough to Carbon? Then the translations are reverses of each other. Hence this is another isomorphism. There may be many isomorphisms between two isomorphic maps.

Non-Isomorphic Maps

Imagine you had the English map from above. As a reminder the stations were: Marybone, Eastweston, Charlesburrough, Tralfalgal, and Oxbridge.

If, now, you find a Spanish map with only four stations on it, it can't possibly be isomorphic to your English map; there would be some station appearing on the English map which isn't named on the Spanish one.

Similarly, if the Spanish map has six stations, then they aren't isomorphic either since there is an extra station on the Spanish map not appearing on the English one.

What if there are five stations on the Spanish map. Is it then definitely isomorphic to the English one?

Recall that: Marybone is connected to every other station, and Eastweston is connected to Charlesburrough.

But what if now instead on the Spanish map, Huesto is still connected to everything, but nothing else is connected to anything else.

Then the translation taking Marybone to Huesto, Tralfalgal to Patata. Oxbridge to Puento de Buey, Eastweston to Esteoeste, and Charlesburrough to Carbon is not an isomorphism. Eastweston is connected to Charlesburrough on the English map, but the corresponding stations on the Spanish map, Esteoeste and Carbon, are not connected to each other. Hence this translation is not an isomorphism, since under these translations, the maps represent different things.

But even though this way of pairing up the stations isn't an isomorphism, maybe there is another way of pairing them up which is? But no, even this is doomed to failure because the number of connections in both cases is different. For example, Eastweston is connected to two stations, but no station on the Spanish map is connected to two other stations. Hence there cannot be any translation that works. No isomorphism exists between the two maps.

If no isomorphism exists between two structures, then they are non-isomorphic.

Notice, in fact, that the two maps do not have the same total number of connections. There are five connections on the English map, but only four on the Spanish map. Hence they cannot be isomorphic.

What if the Spanish map has the following connections? Patata to everything except Carbon, and Carbon to Huestoand Esteoeste. Then there still cannot be an isomorphism, since, again, Marybone is connected to four other stations, but nothing on the Spanish map is connected to four stations. In this case, both maps have five connections. Hence even if both maps have the same total number of connections, they may still be non-isomorphic.

Comparing Weights

Not all isomorphisms need be mappings between structures. Consider if you work at the post-office and must weigh packages. You do not care about the size and shape of the packages, only their weight. Then you consider two packages isomorphic if their weights are equal.

Imagine, then, that you have two packages, say one containing a book %note: The Official London Underground History of Train Stations% and the other is a plastic crate %note: "To the Count, with love"%.

You also have a half-broken pair of brass scales: they have a pair of pans on which items can be placed.

However, they can only tip to the left or remain flat.

If the item on the left is heavier than the one on the right, then the scales tilt left.

Otherwise, if they are of equal weight or the item on the left is lighter than the one on the right, the scales remain level.

Place the book on the left pan of the scale, and the crate on the right. If the scales balance then either the book is lighter than the crate or it is the same weight as the crate. Now swap them. If they remain level, then either the crate is lighter than the book or it is the same weight as the book. Since the book cannot be lighter than the crate whilst the crate is simultaneously lighter than the book, they must be the same weight. Hence they are isomorphic.

This very act of balancing the scales is an isomorphism. It has an inverse: just swap the two packages around! Start with the book on the left pan and the crate on the right. Then place the crate on the left pan and the book on the right. The fact that the scales balance both times tells you (the obvious fact) that the book weighs the same as itself. Since you already know this, doing this actually tells you as much about the book's weight compared to itself as doing nothing at all.

If this last part seems silly or confusing, don't worry too much about it. It's just to illustrate how the idea of an isomorphism is intricately tied with having an inverse.

An Isomorphism Joke

A man walks into a bar. He is surprised at how the patrons are acting. One of them says a number, like “forty-two”, and the rest break into laughter. He asks the bartender what’s going on. The bartender explains that they all come here so often that they’ve memorized all of each other’s jokes, and instead of telling them explicitly, they just give each a number, say the number, and laugh appropriately. The man is intrigued, so he shouts “Two thousand!”. He is shocked to find everyone laughs uproariously, the loudest he's heard that evening. Perplexed, he turns to the bartender and says “They laughed so much more at mine than at any of the others." "Well of course," the bartender answers matter-of-factly, "they've never heard that one before!”