[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.

[drbaskin]

I was aware of the group structure of the Rubik's cube (it is, after all, a subgroup of the permutation group on 54 elements), but apparently I had never given it much thought beyond that. Thanks!

[6ren]

Thanks! That's certainly a simple one.