[6ren]

Nice example, I hadn't thought of using ordering (hmmm, it's just the binary less-than relation... most technical examples I've seen use a trinary relation, like a + b = c). I find it helpful to separate an isomorphism into two: bijection and homomorphism. http://en.wikipedia.org/wiki/Homomorphism#Informal_discussio... (the formal discussion is in terms of groups - above my reading level).

What's a simple example of a homomorphism that isn't bijective? All the ones I can think of are more complex than I'd like, using two functions, one for the structural property that is preserved and one for the mapping. It's hard to explain because there's three relations to keep track of; it's not as much of a problem if you visualize it, but ordinary english makes it hard distinguish whether you're talking about relations between values of the first set (i.e. the structure before the mapping), relations between values of the second set (i.e. the structure after the mapping), or relations between a value of the first set and a value of the second set (i.e. the mapping). It's even confusing to write that, let alone read it.

e.g. structural property of squaring and the mapping of taking the absolute value. Before mapping: 5^2 = 25, -5^2 = 25. After mapping: abs(5)^2 = abs(25) and abs(-5)^2 = abs(25). The mapping of taking the absolute value is not bijective, as both abs(5) and abs(-5) map to the same value, 5, but is it is homomorphic with respect to the absolute value, because the the pairs of values that have this relation before the mapping also have it after (and pairs that aren't related in this way aren't related after).

It's even harder to think of a simple example that is obviously useful.

[drbaskin]

I'm assuming you want non-trivial examples of non-bijective homomorphisms, but you can create a trivial one using the <= relation: Consider the two element set {0, 1} and the function f from {0,1} to {0,1} so that f(0) = f(1) = 0. f preserves the <= relationship but is not a bijection.

[eru]

Or to make it less abstract: Look at a rubics cube. Taking out all edges, just leaving the corners, is a homomorphisms that isn't an isomorphism.

[drbaskin]

I don't follow -- what is the structure being preserved in this example?

[eru]

If you have an algorithm that solves a normal Rubik's cube, you also have an algorithm that solves a corners-only Rubik's cube.

[drbaskin]

Oh, fair enough! That's a fun example.

[eru]

To bore you with more formal terms: All manipulations of a Rubik's cube form a group. And so do all the manipulations possible on a 2x2x2 Rubik's cube. And the 2x2x2 cube's group is a subgroup of the 3x3x3 cube's group, and there's a trivial homomorphism from the 3's group to the 2's group. That homomorphism is not an isomorphism.

[6ren]

Thanks! That's certainly a simple one.