Isomorphism: Intro (Math 0)

https://arbital.com/p/Isomorphism_intro_math_0

by Mark Chimes Jun 17 2016 updated Jul 13 2016

Things which are basically the same, except for some stuff you don't care about.


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.

Equivalent Crates

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.

Pairing one pair of items

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.

Pairing all items in one crate with items in the other

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.

Pairing all items in one box with items in the other

Bijection between crates

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

Different numbers of items

No way to pair items

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.

Bijection between crates

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

Another bijection between crates

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.

Map of the London Underground

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)

Fictional London Underground Map

%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).

Fictional Spanish Map

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.

English Stations Paired Up with Spanish Stations

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.

Another Way of Pairing English Stations with Spanish Stations

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.

Spanish Map with Only Four Stations When English Map has Five

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.

Spanish Map with Six Stations When English Map has Five

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.

Huesto is Connected to Everything With No Other Connections. English Map Still Has the Same Connections

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.

Both Maps Have Five Connections but Are 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.

Empty Balanced Scales

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

Empty Scales Tilting Left

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

Scales With Heavy Object on Left, 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.

Scales With Same Object on Both Sides, Scales Flat

Scales With Heavy Object on Right, Scales Flat

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!”


Comments

Eric Rogstad

Imagine you are the Count von Count\. You care only about counting things\. You don't care what it is you count, you just care how many there are\. You decide that you want to collect the objects that you count into boxes, and you consider two boxes equal if there are the same number of items in both boxes\. How do you know if two boxes have the same number of items? You take one element out of each box and put them to one side\. You continue pairing elements up in this way and when one box runs out you check if there are any left over in the other box\. If there aren't any left over, then the boxes are bijective and the way that you paired them up is a bijection\. A bijection is a simple form of an isomorphism and the boxes are said to be isomorphic\.

I might try to introduce these terms one at a time, and a bit more slowly -- the paragraph up to this point reads like Simple English (good!), and then in the last two sentences I've got two terms thrown at me.

I think if a reader doesn't yet know what an isomorphism is, it would be helpful to spend more time building the intuition that there's something the same about both boxes, maybe like this:

If there aren't any left over, then you know there were the same number of items in each box. So to Count von Count, who only cares about counting things, the two boxes are basically equivalent, and might as well be the same box. Whenever two objects are the same from a certain perspective, we say that they are isomorphic.

In this example, the way in which the boxes were the same is that you could pair up each item in one box with an item in the other (which you wouldn't have been able to do if the boxes had different numbers of elements). Whenever you can match each item in one set with exactly one item in another set, we say that the sets are [-bijective] and the way you paired them is a [-bijection]. %%note: Note that two sets have to have the same number of elements to be bijective, but that's not enough — you also need some way to say which item in one should be paired with which item in the other. In the case above, we paired the items up using the order in which they were removed from their boxes.%% A bijection is a kind of isomorphism.

What do you think?

Mark Chimes

Joke stolen shamelessly from the latest post on slatestarcodex.com

Mark Chimes

Eric Rogstad The post has been updated with an isomorphic version of what you suggested. Thanks!

Patrick Stevens

More precisely, if there are stations Marybone, Eastweston, Charlesburrough and Tralfalgal, on the English map, and you pair them with 壹 \(1\), 貳 \(2\), 叁 \(3\) and 肆 \(4\) respectively on the Chinese map, then if Marybone is connected to Eastweston and Charlesburrough but not Tralfalgal, and Eastweston is connected to Tralfalgal and these are all the connections, and if similarly 壹 \(1\) is connected to 貳 \(2\) and 叁 \(3\) but not 肆 \(4\) and 貳 \(2\) is connected to 肆 \(4\) with no other connections, then the two maps are essentially the same for your purposes\. They are isomorphic \(as graphs, in fact\) and the way that you matched the stations on the one map with those on the other is an isomorphism\.

I think this probably wants a diagram of the two graphs, being differently laid out in the plane but isomorphic.

Mark Chimes

Patrick Stevens I agree completely. Along with some other pictures. However, due tomy current circumstances I can't make any pictures at thr moment.

If someone else is willing to, I would be very grateful. Otherwise I could probably do it in about a month? Month and a half?

Eric Rogstad

Imagine you are the Count von Count\. You care only about counting things\. You don't care what they are, you just care how many there are\. You decide that you want to collect items into plastic crates, and you consider two crates equal if both contain the same number of items\. Without counting them explicitly, how can you tell if two crates contain the same number of items?

Why not just count explicitly?

I think the answer is, "because we want to teach what a bijection is," but readers might be confused why we're doing this. Maybe some of the flavor text about the Count should say that he's not actually good at counting? :P (Though if we did that, I'd be worried about starting to be too long-winded.)

Or maybe there should just be a parenthetical saying there's a reason for not counting explicitly, which we'll come back later. And then we'd need to come back to that when we introduce "bijection" further down the page.

Mark Chimes

Eric Rogstad Elmo comes to visit. Does that seem fine you think?

Mark Chimes

Eric Rogstad But… but… poset office was a pun, not a typo.

Eric Rogstad

Oh, I thought it might be a pun. But nothing about the surrounding description sounded like a poset (weights are totally ordered, right?), so I figured it was a typo :P

Eric Rogstad

I support the creation of a poset-office, but it's gotta be about posets!