[hackerblues]

For people who aren't up to speed on Abstract Algebra, the analogy to have in mind is:

A: Rectangles and squares are the same things.

B: That isn't correct. All squares are rectangles but the reverse isn't true.

A: I only care about the number of sides the polygon has so for my domain of interest rectangles and squares are equivalent. (Therefore the falsity of the first statement is a minor issue?)

[ionfish]

Diagrams can help too. Here's a bijection f that doesn't preserve the <-ordering.

         a > b > c > d
         ^   ^   ^   ^
    f :  |   |   |   |
         w < x < y < z

Here's an isomorphism g that preserves the <-ordering.

         d < c < b < a
         ^   ^   ^   ^
    g :  |   |   |   |
         w < x < y < z

Note that the domain {w, x, y, z} and range {a, b, c, d} are the same for both f and g, but one of them preserves the ordering while the other doesn't.

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

[6ren]

Thanks! That's certainly a simple one.

[eru]

Always specify the equivalence relation you are interested in, if it's a non-standard one.