Re:Classes of functions (partial, total, bijective, injectiv...
by drbaskin on Monday April 18, 2011 @01:14PM
(#2459807)
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.
Re:Classes of functions (partial, total, bijective, injectiv...
by eru on Monday April 18, 2011 @04:08PM
(#2460425)
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.
Re:Classes of functions (partial, total, bijective, injectiv...
by drbaskin on Tuesday April 19, 2011 @12:40PM
(#2463146)
I don't follow -- what is the structure being preserved in this example?
Re:Classes of functions (partial, total, bijective, injectiv...
by eru on Tuesday April 19, 2011 @12:53PM
(#2463203)
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.
Re:Classes of functions (partial, total, bijective, injectiv...
by drbaskin on Tuesday April 19, 2011 @05:35PM
(#2464326)
Oh, fair enough! That's a fun example.
Re:Classes of functions (partial, total, bijective, injectiv...
by eru on Wednesday April 20, 2011 @03:46PM
(#2468077)
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.
Re:Classes of functions (partial, total, bijective, injectiv...
by drbaskin on Wednesday April 20, 2011 @10:58PM
(#2469289)
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!
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.