Isomorphism: Intro (Math 0)

If two things are es­sen­tially the same from a cer­tain per­spec­tive, and they only differ in unim­por­tant de­tails, then they are iso­mor­phic.

Com­par­ing Amounts

Con­sider the Count von Count. He cares only about count­ing things. He doesn’t care what they are, just how many there are. He de­cides that he wants to col­lect items into plas­tic crates, and he con­sid­ers two crates equal if both con­tain the same num­ber of items.

Now Elmo comes to visit, and he wants to im­press the Count, but Elmo is not great at count­ing. Without count­ing them ex­plic­itly, how can Elmo tell if two crates con­tain the same num­ber of items?

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

He con­tinues 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 num­ber of items in both crates.

Since the Count von Count only cares about count­ing things, the two crates are ba­si­cally equiv­a­lent, and might as well be the same crate to him. When­ever two ob­jects are the same from a cer­tain per­spec­tive, we say that they are iso­mor­phic.

In this ex­am­ple, 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 pos­si­ble if the crates had differ­ent num­bers of items in them.

When­ever you can match each item in one col­lec­tion with ex­actly one item in an­other col­lec­tion, we say that the col­lec­tions are bi­jec­tive and the way you paired them is a bi­jec­tion. A bi­jec­tion is a spe­cific kind of iso­mor­phism.

Note that there might be many differ­ent bi­jec­tions be­tween two bi­jec­tive things.

In fact, all that count­ing in­volves is pairing up the things you want to count, ei­ther with your fingers or with the con­cepts of ‘num­bers’ in your head. If there are as many ob­jects in one crate as there are num­bers from one to seven, and there are as many ob­jects in an­other crate as num­bers from one to seven, then both crates con­tain the same num­ber of ob­jects.

Com­par­ing Maps

Now imag­ine that you have a map of the Lon­don Un­der­ground. Such a map is not to scale, nor does it even show how the tracks bend or which sta­tion is in which di­rec­tion com­pared to an­other. They only record which sta­tions are con­nected.

Your Span­ish friend is com­ing to visit and you want to get them a ver­sion of the map in Span­ish. But on the Span­ish maps, the shape of the tracks is differ­ent and you can’t read Span­ish. What’s more, not all the maps are of the Lon­don Un­der­ground! What do you do? Well, given a Span­ish map and your English map, you can try to match up the sta­tions (through trial and er­ror) and if the sta­tions are all con­nected to each other in the same ways on both maps then you know they are both of the same train sys­tem.

More pre­cisely, con­sider the fol­low­ing smaller (fic­tional) ex­am­ple. There are sta­tions Trafal­gal, Mary­bone, Oxbridge, East­we­ston and Charles­bur­rough on the English map. Mary­bone is con­nected to all the other sta­tions, and Charles­bur­rough is con­nected to East­we­ston. (There are no other con­nec­tions)

noteWe don’t want to worry about whether sta­tions are con­nected to them­selves. You can just as­sume no sta­tion is ever con­nected to it­self.

noteIf one sta­tion is con­nected to an­other, then the sec­ond sta­tion is also con­nected to the first. So since Mary­bone is con­nected to East­we­ston then East­we­ston is con­nected to Mary­bone. If it seems silly to even men­tion this fact, then don’t worry to much. It’s just that we might just have eas­ily de­cided that there’s a one-way train run­ning from Mary­bone to East­we­ston but not in the other di­rec­tion.

As­sume the Span­ish map has the fol­low­ing sta­tions: Patata, Huesto, Car­bon, Es­teoeste, and Puente de Buey. As­sume also that Huesto is con­nected to ev­ery other sta­tion, and that Car­bon is con­nected to Es­teoeste. (Again, there are no other con­nec­tions).

Then the two maps are es­sen­tially the same for your pur­poses. They are iso­mor­phic (as graphs, in fact), and the way that you matched the sta­tions on the one map with those on the other is an iso­mor­phism.

Isomorphisms

Imag­ine that you have a Lon­don Un­der­ground Offi­cial Span­ish-to-English Train Sta­tion Dic­tionary that tells you how to trans­late the names of the train sta­tions. So, for ex­am­ple, you can use it to con­vert Patata to Trafal­gal. Then this dic­tio­nary is an iso­mor­phism from the Span­ish map to the English one.

In par­tic­u­lar, the dic­tio­nary trans­lates Huesto to Mary­bone, Patata to Tral­fal­gal, Puento de Buey to Oxbridge, Es­teoeste to East­we­ston, and Car­bon to Charles­bur­rough.

You could also get a Lon­don Un­der­ground Offi­cial English-to-Span­ish Train Sta­tion Dic­tionary. Then, if you were to use this dic­tio­nary to trans­late Tral­fal­gal, you’d get back Patata. Hence your first origi­nal trans­la­tion of that sta­tion from English to Span­ish has been un­done.

In par­tic­u­lar, the dic­tio­nary trans­lates Mary­bone to Huesto, Tral­fal­gal to Patata. Oxbridge to Puento de Buey, East­we­ston to Es­teoeste, and Charles­bur­rough to Car­bon.

In fact, if you take the English map and trans­late all of the sta­tions into Span­ish us­ing the one dic­tio­nary and then trans­late back, you’d get back to where you started. Similarly, if you trans­lated the Span­ish map from Span­ish into English with the one dic­tio­nary and back to Span­ish with the other you’d get the Span­ish map back. Hence both of these dic­tio­nar­ies are com­plete in­verses of each other.

In fact, in cat­e­gory the­ory, this is ex­actly the defi­ni­tion of an iso­mor­phism: if you have some trans­la­tion (mor­phism) such that you can find a back­wards trans­la­tion (mor­phism in the op­po­site di­rec­tion), and us­ing the one trans­la­tion af­ter the other is for all in­tents and pur­posed the same as not hav­ing trans­lated any­thing at all (i.e., no im­por­tant in­for­ma­tion is lost in trans­la­tion), then the origi­nal trans­la­tion is an iso­mor­phism. (In fact, both of them are iso­mor­phisms).

What if you had a differ­ent pair of dic­tio­nar­ies.

In par­tic­u­lar, what if the Span­ish-to-English dic­tio­nary trans­lates Huesto to Mary­bone, Puento de Buey to Tral­fal­gal, Patata to Oxbridge, Car­bon to East­we­ston, and Es­teoeste to Charles­bur­rough?

Then if we trans­late from Span­ish into English, and then trans­late back with the origi­nal English-to-Span­ish dic­tio­nary, then Patata is first trans­lated to Oxbridge, but then it is trans­lated back into Puente de Buey. So it does not re­verse the trans­la­tion. Hence this is not an iso­mor­phism.

How­ever, what if the English-to-Span­ish Dic­tionary trans­lates Mary­bone to Huesto, Oxbridge to Patata. East­we­ston to Puento de Buey, Tral­fal­gal to Es­teoeste, and Charles­bur­rough to Car­bon? Then the trans­la­tions are re­verses of each other. Hence this is an­other iso­mor­phism. There may be many iso­mor­phisms be­tween two iso­mor­phic maps.

Non-Iso­mor­phic Maps

Imag­ine you had the English map from above. As a re­minder the sta­tions were: Mary­bone, East­we­ston, Charles­bur­rough, Tral­fal­gal, and Oxbridge.

If, now, you find a Span­ish map with only four sta­tions on it, it can’t pos­si­bly be iso­mor­phic to your English map; there would be some sta­tion ap­pear­ing on the English map which isn’t named on the Span­ish one.

Similarly, if the Span­ish map has six sta­tions, then they aren’t iso­mor­phic ei­ther since there is an ex­tra sta­tion on the Span­ish map not ap­pear­ing on the English one.

What if there are five sta­tions on the Span­ish map. Is it then definitely iso­mor­phic to the English one?

Re­call that: Mary­bone is con­nected to ev­ery other sta­tion, and East­we­ston is con­nected to Charles­bur­rough.

But what if now in­stead on the Span­ish map, Huesto is still con­nected to ev­ery­thing, but noth­ing else is con­nected to any­thing else.

Then the trans­la­tion tak­ing Mary­bone to Huesto, Tral­fal­gal to Patata. Oxbridge to Puento de Buey, East­we­ston to Es­teoeste, and Charles­bur­rough to Car­bon is not an iso­mor­phism. East­we­ston is con­nected to Charles­bur­rough on the English map, but the cor­re­spond­ing sta­tions on the Span­ish map, Es­teoeste and Car­bon, are not con­nected to each other. Hence this trans­la­tion is not an iso­mor­phism, since un­der these trans­la­tions, the maps rep­re­sent differ­ent things.

But even though this way of pairing up the sta­tions isn’t an iso­mor­phism, maybe there is an­other way of pairing them up which is? But no, even this is doomed to failure be­cause the num­ber of con­nec­tions in both cases is differ­ent. For ex­am­ple, East­we­ston is con­nected to two sta­tions, but no sta­tion on the Span­ish map is con­nected to two other sta­tions. Hence there can­not be any trans­la­tion that works. No iso­mor­phism ex­ists be­tween the two maps.

If no iso­mor­phism ex­ists be­tween two struc­tures, then they are non-iso­mor­phic.

No­tice, in fact, that the two maps do not have the same to­tal num­ber of con­nec­tions. There are five con­nec­tions on the English map, but only four on the Span­ish map. Hence they can­not be iso­mor­phic.

What if the Span­ish map has the fol­low­ing con­nec­tions? Patata to ev­ery­thing ex­cept Car­bon, and Car­bon to Huestoand Es­teoeste. Then there still can­not be an iso­mor­phism, since, again, Mary­bone is con­nected to four other sta­tions, but noth­ing on the Span­ish map is con­nected to four sta­tions. In this case, both maps have five con­nec­tions. Hence even if both maps have the same to­tal num­ber of con­nec­tions, they may still be non-iso­mor­phic.

Com­par­ing Weights

Not all iso­mor­phisms need be map­pings be­tween struc­tures. Con­sider if you work at the post-office and must weigh pack­ages. You do not care about the size and shape of the pack­ages, only their weight. Then you con­sider two pack­ages iso­mor­phic if their weights are equal.

Imag­ine, then, that you have two pack­ages, say one con­tain­ing a book noteThe Offi­cial Lon­don Un­der­ground His­tory of Train Sta­tions and the other is a plas­tic crate note”To the Count, with love”.

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

How­ever, they can only tip to the left or re­main flat.

If the item on the left is heav­ier than the one on the right, then the scales tilt left.

Other­wise, if they are of equal weight or the item on the left is lighter than the one on the right, the scales re­main level.

Place the book on the left pan of the scale, and the crate on the right. If the scales bal­ance then ei­ther the book is lighter than the crate or it is the same weight as the crate. Now swap them. If they re­main level, then ei­ther the crate is lighter than the book or it is the same weight as the book. Since the book can­not be lighter than the crate whilst the crate is si­mul­ta­neously lighter than the book, they must be the same weight. Hence they are iso­mor­phic.

This very act of bal­anc­ing the scales is an iso­mor­phism. It has an in­verse: just swap the two pack­ages 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 bal­ance both times tells you (the ob­vi­ous fact) that the book weighs the same as it­self. Since you already know this, do­ing this ac­tu­ally tells you as much about the book’s weight com­pared to it­self as do­ing noth­ing at all.

If this last part seems silly or con­fus­ing, don’t worry too much about it. It’s just to illus­trate how the idea of an iso­mor­phism is in­tri­cately tied with hav­ing an in­verse.

An Iso­mor­phism Joke

A man walks into a bar. He is sur­prised at how the pa­trons are act­ing. One of them says a num­ber, like “forty-two”, and the rest break into laugh­ter. He asks the bar­tender what’s go­ing on. The bar­tender ex­plains that they all come here so of­ten that they’ve mem­o­rized all of each other’s jokes, and in­stead of tel­ling them ex­plic­itly, they just give each a num­ber, say the num­ber, and laugh ap­pro­pri­ately. The man is in­trigued, so he shouts “Two thou­sand!”. He is shocked to find ev­ery­one laughs up­roar­i­ously, the loud­est he’s heard that evening. Per­plexed, he turns to the bar­tender and says “They laughed so much more at mine than at any of the oth­ers.” “Well of course,” the bar­tender an­swers mat­ter-of-factly, “they’ve never heard that one be­fore!”

Parents:

• Isomorphism

A mor­phism be­tween two ob­jects which de­scribes how they are “es­sen­tially equiv­a­lent” for the pur­poses of the the­ory un­der con­sid­er­a­tion.

• Mathematics

Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.

• I might try to in­tro­duce these terms one at a time, and a bit more slowly—the para­graph up to this point reads like Sim­ple English (good!), and then in the last two sen­tences I’ve got two terms thrown at me.

I think if a reader doesn’t yet know what an iso­mor­phism is, it would be helpful to spend more time build­ing the in­tu­ition that there’s some­thing the same about both boxes, maybe like this:

If there aren’t any left over, then you know there were the same num­ber of items in each box. So to Count von Count, who only cares about count­ing things, the two boxes are ba­si­cally equiv­a­lent, and might as well be the same box. When­ever two ob­jects are the same from a cer­tain per­spec­tive, we say that they are iso­mor­phic.

In this ex­am­ple, 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 differ­ent num­bers of el­e­ments). When­ever you can match each item in one set with ex­actly one item in an­other set, we say that the sets are bi­jec­tive and the way you paired them is a bi­jec­tion. noteNote that two sets have to have the same num­ber of el­e­ments to be bi­jec­tive, 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 us­ing the or­der in which they were re­moved from their boxes. A bi­jec­tion is a kind of iso­mor­phism.

What do you think?

• Joke stolen shame­lessly from the lat­est post on slat­estar­codex.com

• @5 The post has been up­dated with an iso­mor­phic ver­sion of what you sug­gested. Thanks!

• I think this prob­a­bly wants a di­a­gram of the two graphs, be­ing differ­ently laid out in the plane but iso­mor­phic.

• @267 I agree com­pletely. Along with some other pic­tures. How­ever, due tomy cur­rent cir­cum­stances I can’t make any pic­tures at thr mo­ment.

If some­one else is will­ing to, I would be very grate­ful. Other­wise I could prob­a­bly do it in about a month? Month and a half?

• Why not just count ex­plic­itly?

I think the an­swer is, “be­cause we want to teach what a bi­jec­tion is,” but read­ers might be con­fused why we’re do­ing this. Maybe some of the fla­vor text about the Count should say that he’s not ac­tu­ally good at count­ing? :P (Though if we did that, I’d be wor­ried about start­ing to be too long-winded.)

Or maybe there should just be a par­en­thet­i­cal say­ing there’s a rea­son for not count­ing ex­plic­itly, which we’ll come back later. And then we’d need to come back to that when we in­tro­duce “bi­jec­tion” fur­ther down the page.

• @5 Elmo comes to visit. Does that seem fine you think?

• @5 But… but… poset office was a pun, not a typo.

• Oh, I thought it might be a pun. But noth­ing about the sur­round­ing de­scrip­tion sounded like a poset (weights are to­tally or­dered, right?), so I figured it was a typo :P

• I sup­port the cre­ation of a poset-office, but it’s gotta be about posets!