6 ms·

I like your explanation overall. But "point-to-point equivalence" is a little off from the math notion of homomorphism, and I think also the type theory version

by wging 3y ago

I like your explanation overall. But "point-to-point equivalence" is a little off from the math notion of homomorphism, and I think also the type theory version, if I understand correctly how you're using that phrase. It seems to imply that the homomorphism is 1-to-1 (as does the phrase "if you know the mapping you can turn one into the other"), which isn't necessarily required for the mathematical idea of a homomorphism: homomorphisms can map multiple elements of the source space to a single element of the destination space. So there may not be a well-defined way to 'go back' from the result of applying the homomorphism to the original input. (A homomorphism that isn't 'lossy' in this way is called an isomorphism.) An example is reduction mod 5: it's a (ring) homomorphism because the relevant laws of arithmetic work just the same if you do arithmetic in the ordinary integers then reduce the result mod 5, or if you instead reduce all numbers mod 5 first and then apply special 'modulo 5' versions of those arithmetic operations. (E.g. 7 + 19 = 26 = 1 mod 5, but also (7 mod 5 + 19 mod 5) = (2 mod 5) + (4 mod 5) = 1 mod 5, where that last '+' is addition mod 5 instead of integer addition.) But you don't, given just '1 mod 5', know whether the original source integer was 1, 6, 21, -4, or any of infinitely many other choices. Another example: projecting 3d space down to 2d by just dropping the third coordinate: (x, y, z) -> (x, y). That's a vector space homomorphism, but there isn't a way to recover the z-coordinate given just (x, y). An example from the Haskell wiki mentioned above (I think you're referring to https://en.wikibooks.org/wiki/Haskell/Monoids#Homomorphisms https://en.wikibooks.org/wiki/Haskell/Monoids#Homomorphisms) is the `length` function: given only the result of applying the homomorphism, `length(a)`, it's not possible to recover a.

deleted 3y ago
[deleted]
skybrian 3y ago
Is preserving one operation enough to call it a homomorphism? How trivial can that operation be? If we have an is_positive() operation, maybe mapping numbers to either -1 or 1 is enough? Or maybe map to true or false?
- wging 3y ago
  It depends what the fundamental operations are in your context. There are different types of map that we call "X homomorphism" for different types of algebraic structure X (groups, rings, fields, vector spaces, modules, algebras, etc). In an abstract algebra course you'd probably first encounter the definition of a 'group homomorphism' (preserves the group's multiplication operation, whatever that is: f(x*y) = f(x)*f(y)), and then a separate definition of a 'ring homomorphism' (preserves the ring's addition and multiplication, which are the two operations you have on a ring - f(x+y)=f(x)+f(y) and f(xy) = f(x)f(y)), etc. The definitions are similar, but they are distinct: a group homomorphism is between groups, a ring homomorphism is between rings, etc. (There's also a more formal sense in which they're examples of the same thing, you'd look into category theory for more on that.) So what's going on in your example? Well, you could define a simple type of algebraic structure where, for any instances of that structure, you can only ask the question "is x positive" for one of its elements x and get a yes or no answer, and then define 'homomorphisms' between such structures as maps that take 'positive' elements of the source space to 'positive' elements of the destination space (and vice versa). But I'm not sure you'd really be able to use it for much. (On https://en.wikipedia.org/wiki/Homomorphism#Definition https://en.wikipedia.org/wiki/Homomorphism#Definition, that'd correspond to having exactly one unary operation μ(x) = is_positive(x) and no other operations, not even addition.)
holden_nelson 3y ago
> where that last ‘+’ is addition mod 5 It can just be integer addition. 2 + 4 = 6 = 1 mod 5 is a true statement.
- wging 3y ago
  If we're talking homomorphisms, no it can't: the whole point of the homomorphism is that the addition operation works regardless of whether you do it in the source space (2 + 4 = 6, then reduce mod 5) or the target space, where you're dealing with entirely different objects (2 mod 5 added to 4 mod 5, where each of these is an object in the target space and not an ordinary integer).

by wging 3y ago

deleted 3y ago

[deleted]

skybrian 3y ago

Is preserving one operation enough to call it a homomorphism? How trivial can that operation be? If we have an is_positive() operation, maybe mapping numbers to either -1 or 1 is enough? Or maybe map to true or false?

wging 3y ago
It depends what the fundamental operations are in your context. There are different types of map that we call "X homomorphism" for different types of algebraic structure X (groups, rings, fields, vector spaces, modules, algebras, etc). In an abstract algebra course you'd probably first encounter the definition of a 'group homomorphism' (preserves the group's multiplication operation, whatever that is: f(x*y) = f(x)*f(y)), and then a separate definition of a 'ring homomorphism' (preserves the ring's addition and multiplication, which are the two operations you have on a ring - f(x+y)=f(x)+f(y) and f(xy) = f(x)f(y)), etc. The definitions are similar, but they are distinct: a group homomorphism is between groups, a ring homomorphism is between rings, etc. (There's also a more formal sense in which they're examples of the same thing, you'd look into category theory for more on that.) So what's going on in your example? Well, you could define a simple type of algebraic structure where, for any instances of that structure, you can only ask the question "is x positive" for one of its elements x and get a yes or no answer, and then define 'homomorphisms' between such structures as maps that take 'positive' elements of the source space to 'positive' elements of the destination space (and vice versa). But I'm not sure you'd really be able to use it for much. (On https://en.wikipedia.org/wiki/Homomorphism#Definition https://en.wikipedia.org/wiki/Homomorphism#Definition, that'd correspond to having exactly one unary operation μ(x) = is_positive(x) and no other operations, not even addition.)

holden_nelson 3y ago

> where that last ‘+’ is addition mod 5 It can just be integer addition. 2 + 4 = 6 = 1 mod 5 is a true statement.

wging 3y ago
If we're talking homomorphisms, no it can't: the whole point of the homomorphism is that the addition operation works regardless of whether you do it in the source space (2 + 4 = 6, then reduce mod 5) or the target space, where you're dealing with entirely different objects (2 mod 5 added to 4 mod 5, where each of these is an object in the target space and not an ordinary integer).