3 ms·
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. A
by hackerblues 15y ago
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 15y agoDiagrams 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 15y agoNice 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_discussion 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 15y agoI'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.
- 6ren 15y agoThanks! That's certainly a simple one.
- eru 15y agoOr 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 15y agoI don't follow -- what is the structure being preserved in this example?
- eru 15y agoIf 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 15y agoOh, fair enough! That's a fun example.
- eru 15y agoTo 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.
- eru 15y agoAlways specify the equivalence relation you are interested in, if it's a non-standard one.