3 ms·

To be pedantic: TRUE is the identity element of "and", not "all". "All" is not a binary operator, it is the (unary) aggregation of "and". That is, S.all() == S

by feoren 3y ago

To be pedantic: TRUE is the identity element of "and", not "all". "All" is not a binary operator, it is the (unary) aggregation of "and". That is, S.all() == S.aggregate((prev, next) => prev && next, TRUE). FALSE is the identity element of "or". "any"/"some" is the aggregation of "or". S.any() == S.aggregate((prev, next) => prev || next, FALSE). 0 is the identity element of addition, and "sum" is the aggregation of addition. S.sum() == S.aggregate((prev, next) => prev + next, 0). 1 is the identity element of multiplication, with "product" the aggregation. Given a monoid M<T> { combine(a: T, b: T) => T, identity: T }, you can define an aggregation operation the same way: S.aggregate((prev, next) => M.combine(prev, next), M.identity)

Nevermark 3y ago
TRUE can be the identity element both for the conjunction of 2 Boolean values, and of an operator that extends 2-value Boolean operations to lists of N-elements. Being an identity is a property. A given mathematical object can be an identity for more than one relation. It can also be the identity element for general logical propositions or relations. The reason being, the former is just a special case of the Boolean relations of AND and ALL. So TRUE can consistently be the identity for many classes of logical operations of varying generality or complexity. The raw identity relation and concept of identity element form the “tops” of ladders, whose specializations can hold over large classes of relations.
- feoren 3y ago
  My goal was to add more context to your (excellent and upvoted) original post, which in my opinion is basically the fundamental "proof" of why All([]) must be TRUE, and I find beauty in this two-dimensional analogy: add | sum multiply | product and | all or | any concat | "flatten" (arguable name here) I also find beauty in the fact that the existence of a monoid on the left is sufficient for producing the aggregation on the right that behaves in the way we want. I see the monoid as the simple building block from which we produce more interesting and complicated structures. I enjoy the continued, unbroken thread of rigorous logic that connects everything. When you say that TRUE can be the identity of "an operator that extends 2-value Boolean operations to lists of N-elements", I just don't see the unbroken thread of rigorous logic behind that statement. Maybe it's there! But I don't see it. I can write down exactly what it means for some element i to be an identity of a binary operation @. It means i@x == x == x@i for all x in the set over which @ is defined. Whatever the rules of "identity" are that you're talking about, they're not this, so I'm just kinda struggling to accept it. I wonder whether maybe what you're thinking of deserves a different name than "identity". Does any of this matter? It does to me, because I actually use Monoids all the time in programming, where you can't afford any ambiguity at all. So again: maybe you see that unbroken chain of rigorous logic and know exactly what you mean when you say TRUE is the identity of "an operator that extends 2-value Boolean operations to lists of N-elements", but I'd need to see the exact laws that an element must follow to be such an operator or such an identity of that operator. I gave an example of how to turn associative binary operations with identity into a unary operator on lists of elements, but unary operators don't really have identity elements. Some unary operators have fixed points and eigenvalues, which are similar to identity, but such operators must have the same domain and codomain, and aggregate operators like SUM and ALL do not. So there's not really anything you define to be SUM's identity, since it does not accept 0 as an input.
  - Nevermark 3y ago
    Ha! I agree, you are right. TRUE for a monoid can exist independently from any aggregator defined over that monoid. My bad :) The fractal lines between what is mathematically true, vs. what is practical or useful to be true, in coding are worth paying attention to! Thank you! And perhaps these relations can always hold, “without loss of generality”. In which case we need to formally define these monoid-aggregator relations so we all know when they are assumed to be in effect. — On the beauty side, I love how 0 = sum{} captures the semantic difference between zero and other numbers, with the syntax of nothing between two braces.
    - feoren 3y ago
      I do think there was something interesting about the idea that adding the element to the input array doesn't change the result. It's a little tricky to formalize though. If we define an "aggregation" agg over some set S as a function from S* (the "Kleene star", AKA the free monoid over S, AKA really just simple arrays of S) to S, and we identify some element i such that agg([i] concat X) == agg(X) == agg(X concat [i]) for all X in S*, that does feel very "identity-ish". It's a little bit like saying [i] is an identity of concat under the equivalence relation on S* that X~Y iff agg(X) == agg(Y)? In the same way that 7 is an identity of + under the equivalence relation "mod 7" (paraphrasing). But note that: sum([-2, 2] concat X) == sum(X) == sum(X concat [-2, 2]) for all X as well. You could say "well obviously, because sum([-2, 2]) == sum([0]) and [0] is our identity element" but then we're implicitly assuming that agg(X concat Y) = agg(X) @ agg(Y) for some operator @. Which in turn is basically assuming we've built agg up from a monoid to begin with, and the novelty here would be what happens when we don't do that. There may be some interesting (if not useful) stuff here. if there exists some operator @: (S, S) -> S such that: agg(X concat Y) == agg(X) @ agg(Y) For all X, Y in S*, and if : agg([i] concat X) == agg(X) == agg(X concat [i]) for all X in S*, then must agg([i]) be an identity element of @? Certainly that's true if agg is onto (i.e. we can find every element of S via agg of some S*). But it can't really be true in general, because we could make degenerate agg functions like ignore(X) := 0 Now every element of S meets this condition: ignore([s] concat X) == ignore(X) == ignore(X concat [s]) So we have every element of S as this weird kind of "identity" of the "ignore" function. And we can find functions on S* with no "identity" of this kind: "count", for instance. Although that's cheating because it only works when S happens to be the natural numbers (otherwise agg is not a function from S* -> S).
black_knight 3y ago
To be even more pedantic! Unit elements are not limited to binary operators. In fact, in a monoid (or group) there is naturally an n-ary operation for each n. Or if you want a single operation from lists of elements to a single element. It is just that we usually present it using a unit and a binary operation + associativity. But one can split that cake in other ways. Thus, in some sense any and all are even more natural or "objective" (as Lawvere would put it) than and and or.
- feoren 3y ago
  What is your definition of an identity of a ternary function? Say i is the identity of f. Must it hold that f(i, a, b) == f(a, i, b) == f(a, b, i)? For all a, b in f's domain? The seems like the obvious choice, and certainly holds for ternary functions "built up" from associative binary ones, but I've just never seen such a thing. Is there a case where it's useful to talk about the identity of a 3-valued function? I think the thing I find weird about this is that a binary operator op2 over some set S is defined as S^2 -> S. So we can sensibly say: op2(a, i) == a == op2(i, a) But the extension of this to a 3-valued function from S^3 -> S cannot have that middle condition, because it has too many "free variables". We can't say: op3(a, b, i) == op2(a, b) Without establishing a relationship between op3 and op2, but must there be a sensible "decomposition" of op3 into some op2? Surely not. I guess I just don't know what it means to be an identity of a 3-valued function. As an example, consider mult3(a, b, c) := a * b * c. Then, mult3(0, a, b) == mult3(a, 0, b) == mult3(a, b, 0) for all a and b. We intuitively know that 0 is not behaving like an identity. Can we write down an identity rule that must hold for a generic op3 that excludes 0 as the identity of that function? Without relying on some oracle to provide us an appropriate decomposed op2? Edit: I would also like to point out this function over R^3: f(a, b, c) := a*b + a*c + b*c Note that every value in R meets the condition: f(a, x, y) == f(x, a, y) == f(x, y, a) == ax + ay + xy For all x and y. Is every number an identity of this function? In fact, this is trivially true for any completely associative function. I guess I just need to see the definition of an identity of a ternary operator.

by feoren 3y ago

Nevermark 3y ago

TRUE can be the identity element both for the conjunction of 2 Boolean values, and of an operator that extends 2-value Boolean operations to lists of N-elements. Being an identity is a property. A given mathematical object can be an identity for more than one relation. It can also be the identity element for general logical propositions or relations. The reason being, the former is just a special case of the Boolean relations of AND and ALL. So TRUE can consistently be the identity for many classes of logical operations of varying generality or complexity. The raw identity relation and concept of identity element form the “tops” of ladders, whose specializations can hold over large classes of relations.

feoren 3y ago
My goal was to add more context to your (excellent and upvoted) original post, which in my opinion is basically the fundamental "proof" of why All([]) must be TRUE, and I find beauty in this two-dimensional analogy: add | sum multiply | product and | all or | any concat | "flatten" (arguable name here) I also find beauty in the fact that the existence of a monoid on the left is sufficient for producing the aggregation on the right that behaves in the way we want. I see the monoid as the simple building block from which we produce more interesting and complicated structures. I enjoy the continued, unbroken thread of rigorous logic that connects everything. When you say that TRUE can be the identity of "an operator that extends 2-value Boolean operations to lists of N-elements", I just don't see the unbroken thread of rigorous logic behind that statement. Maybe it's there! But I don't see it. I can write down exactly what it means for some element i to be an identity of a binary operation @. It means i@x == x == x@i for all x in the set over which @ is defined. Whatever the rules of "identity" are that you're talking about, they're not this, so I'm just kinda struggling to accept it. I wonder whether maybe what you're thinking of deserves a different name than "identity". Does any of this matter? It does to me, because I actually use Monoids all the time in programming, where you can't afford any ambiguity at all. So again: maybe you see that unbroken chain of rigorous logic and know exactly what you mean when you say TRUE is the identity of "an operator that extends 2-value Boolean operations to lists of N-elements", but I'd need to see the exact laws that an element must follow to be such an operator or such an identity of that operator. I gave an example of how to turn associative binary operations with identity into a unary operator on lists of elements, but unary operators don't really have identity elements. Some unary operators have fixed points and eigenvalues, which are similar to identity, but such operators must have the same domain and codomain, and aggregate operators like SUM and ALL do not. So there's not really anything you define to be SUM's identity, since it does not accept 0 as an input.
- Nevermark 3y ago
  Ha! I agree, you are right. TRUE for a monoid can exist independently from any aggregator defined over that monoid. My bad :) The fractal lines between what is mathematically true, vs. what is practical or useful to be true, in coding are worth paying attention to! Thank you! And perhaps these relations can always hold, “without loss of generality”. In which case we need to formally define these monoid-aggregator relations so we all know when they are assumed to be in effect. — On the beauty side, I love how 0 = sum{} captures the semantic difference between zero and other numbers, with the syntax of nothing between two braces.
  - feoren 3y ago
    I do think there was something interesting about the idea that adding the element to the input array doesn't change the result. It's a little tricky to formalize though. If we define an "aggregation" agg over some set S as a function from S* (the "Kleene star", AKA the free monoid over S, AKA really just simple arrays of S) to S, and we identify some element i such that agg([i] concat X) == agg(X) == agg(X concat [i]) for all X in S*, that does feel very "identity-ish". It's a little bit like saying [i] is an identity of concat under the equivalence relation on S* that X~Y iff agg(X) == agg(Y)? In the same way that 7 is an identity of + under the equivalence relation "mod 7" (paraphrasing). But note that: sum([-2, 2] concat X) == sum(X) == sum(X concat [-2, 2]) for all X as well. You could say "well obviously, because sum([-2, 2]) == sum([0]) and [0] is our identity element" but then we're implicitly assuming that agg(X concat Y) = agg(X) @ agg(Y) for some operator @. Which in turn is basically assuming we've built agg up from a monoid to begin with, and the novelty here would be what happens when we don't do that. There may be some interesting (if not useful) stuff here. if there exists some operator @: (S, S) -> S such that: agg(X concat Y) == agg(X) @ agg(Y) For all X, Y in S*, and if : agg([i] concat X) == agg(X) == agg(X concat [i]) for all X in S*, then must agg([i]) be an identity element of @? Certainly that's true if agg is onto (i.e. we can find every element of S via agg of some S*). But it can't really be true in general, because we could make degenerate agg functions like ignore(X) := 0 Now every element of S meets this condition: ignore([s] concat X) == ignore(X) == ignore(X concat [s]) So we have every element of S as this weird kind of "identity" of the "ignore" function. And we can find functions on S* with no "identity" of this kind: "count", for instance. Although that's cheating because it only works when S happens to be the natural numbers (otherwise agg is not a function from S* -> S).

black_knight 3y ago

To be even more pedantic! Unit elements are not limited to binary operators. In fact, in a monoid (or group) there is naturally an n-ary operation for each n. Or if you want a single operation from lists of elements to a single element. It is just that we usually present it using a unit and a binary operation + associativity. But one can split that cake in other ways. Thus, in some sense any and all are even more natural or "objective" (as Lawvere would put it) than and and or.

feoren 3y ago
What is your definition of an identity of a ternary function? Say i is the identity of f. Must it hold that f(i, a, b) == f(a, i, b) == f(a, b, i)? For all a, b in f's domain? The seems like the obvious choice, and certainly holds for ternary functions "built up" from associative binary ones, but I've just never seen such a thing. Is there a case where it's useful to talk about the identity of a 3-valued function? I think the thing I find weird about this is that a binary operator op2 over some set S is defined as S^2 -> S. So we can sensibly say: op2(a, i) == a == op2(i, a) But the extension of this to a 3-valued function from S^3 -> S cannot have that middle condition, because it has too many "free variables". We can't say: op3(a, b, i) == op2(a, b) Without establishing a relationship between op3 and op2, but must there be a sensible "decomposition" of op3 into some op2? Surely not. I guess I just don't know what it means to be an identity of a 3-valued function. As an example, consider mult3(a, b, c) := a * b * c. Then, mult3(0, a, b) == mult3(a, 0, b) == mult3(a, b, 0) for all a and b. We intuitively know that 0 is not behaving like an identity. Can we write down an identity rule that must hold for a generic op3 that excludes 0 as the identity of that function? Without relying on some oracle to provide us an appropriate decomposed op2? Edit: I would also like to point out this function over R^3: f(a, b, c) := a*b + a*c + b*c Note that every value in R meets the condition: f(a, x, y) == f(x, a, y) == f(x, y, a) == ax + ay + xy For all x and y. Is every number an identity of this function? In fact, this is trivially true for any completely associative function. I guess I just need to see the definition of an identity of a ternary operator.