4 ms·

The sum of no numbers is 0. The product of no numbers is 1. The union of no areas (sets, …) is the empty area. The intersection of no areas (sets, …) is the

The sum of no numbers is 0. The product of no numbers is 1. The union of no areas (sets, …) is the empty area. The intersection of no areas (sets, …) is the universal area. The commonality here, is what element z can you add or remove from a list which won’t change the result? We call the element that makes no change to the result, the “identity element”. For y = sum of {x1,x2, … Xn, z}, We know z must be 0, if it has no impact on y. So the identity element for sum is 0. So if y = sum of {}, we know we can insert the identity element without changing the result, and we know the sum of {0} is 0. The identity element itself. So operations applied across lists return that operation’s identity element for an empty list. —- Ergo: the identity element of “all” is “true”. The identity element of “any” is “false”. —— More fun: The identity element for the resistance sum across parallel resistors, is the infinite ohm resister. The identity element for the vector distance sum of a child making a sequence of jumps is the in-place jump. —- Getting meta with, oh hell, monads: The identity element for C, the concatenation operator over lists, is the empty list {}. Since all lists are concatenations of lists (down to empty & unitary lists), we can view any operation Q over lists also as an operation over the concatenation of lists. So any Q acts like a monad over list concatenation operations. If Q = sum, then it is the monad that transforms concatenations of lists of numbers into the sum of those numbers. If Q = all, then it is the monad that transforms concatenations of lists of truth values to the conjunction of the truth values in those lists. With that view in place, we can see another reason why the identity of any operation Q is Q on an empty list Q{} Because as a monad, Q applies over C, the concatenation of lists. The identity of C is {}, so the identity of Q must be Q{}. Voila! So we really shouldn’t define sum{} as 0, but define 0 as sum{}. “0” is just a symbol. Sum{} is what it is. 0 is the sum of nothing. So “True” IS the conjunction of nothing. It’s meaning IS all{}. It is the truth of “no requirements”.

layer8 3y ago
One corollary is that a zero-dimensional array has exactly one element, whereas a 1-dimensional array can have zero elements (can have length zero). It took me a while to wrap my head around this.
- Nevermark 3y ago
  Yes! Dimensions are multipliers on each other. The cross points, over multiple points on segments in different dimensions is a product. And the product across an empty list is 1. The number of ways you can roll a dice “no” times is also 1. Cross combinations of all kinds are products.
  - itishappy 3y ago
    Whoah... Does this imply there's a sixth of a way to unroll a dice?
- rain1 3y ago
  I don't understand this. Please can you point me to information about it?
  - layer8 3y ago
    I haven’t seen this discussed anywhere else in terms of arrays, so I’ll elaborate here: The number of elements in an n-dimensional array is the product of its n dimension sizes. For example, the number of elements in a two-dimensional 2x3 array is 6, because 2 x 3 = 6. Consequently, the number of elements in a zero-dimensional array would be the empty product, which is 1 (as the root comment mentions). Naively, one might think that removing a dimension from an array cannot increase the number of elements. For example, dropping a dimension from a 2x3 array reduces the number of elements from 6 to 2 (or 3, depending in which dimension you drop). But in the case of a zero-length 1-dimensional array (i.e. an empty list or empty vector), dropping the one dimension causes an element to be added, because a zero-dimensional array always has 1 element. (This effect is not restricted to 1- and 0- dimensional arrays, by the way. If you admit zero-length dimensions, then you can also think of a 2x0 two-dimensional array, which would have zero elements, but dropping the zero-length dimension would result in a 1-dimensional array of length 2, increasing the element count by 2.) The other maybe surprising part is that for all n > 0, you can have an n-dimensional array with zero elements by having at least one of the dimensions have length zero. But for a zero-dimensional array, it’s not possible for it to be empty, because it has no dimension whose length could be zero. This is somewhat counterintuitive at first, because one might have thought that a zero-dimensional array would be the canonical empty array, like how a point in space (whis is a zero-dimensional object) has no length/area/volume. By the way, one could think of non-array values in a programming language to really be zero-dimensional array values, with their value being the singular element of the zero-dimensional array.
deleted 3y ago
[deleted]
evertedsphere 3y ago
monoid, not monad --- a monoid is a set A with an associative binary operator @ on it: that is, for any a, b, c a @ (b @ c) = (a @ b) @ c and it also has an "identity" element I, that is, for any a: a @ I = I @ a = a common monoids: integers under addition (i.e. @ is addition, the identity is 0), nonzero real numbers under multiplication, lists under concatenation, booleans under AND (identity is True), booleans under OR (what's the identity?), ... now, when you have a mathematical structure, you often want to study functions between two of them. so you might ask what a reasonable notion of functions between monoids is one nice way is if, given two monoids, M with operation @ and unit I, and N with operation ^ and unit J, we had a function f for which: f(I) = J f(a @ b) = f(a) ^ f(b) this is loosely described as the function "respecting the structure" of the monoids, and such functions are called monoid homomorphisms or just homomorphisms if the context is clear -- with that background, we see that `all` should really be be a homomorphism from the monoid of lists (under concatenation, with the empty list as the identity element) to the monoid of booleans under AND (with True as the identity) this means that all(concat(list1, list2)) = and(all(list1), all(list2)) or, in python, all(a + b) = all(a) and all(b) and, of course, all([]) = True! the value here is that now you can reason about the all() of two lists by thinking about the all() of sublists, and the conditions required for a homomorphism guarantee that the empty list is not an edge case: all([T, F]) = all([]) and all([T, F]) = all([T]) and all([F]) = ... and that it doesn't matter how you cut up a list into sublists and what order you apply the concatenations in to reconstruct it
- Nevermark 3y ago
  I was referring to monad, as used in programming, as a transform that can be applied to the elements of a structure. For instance, a transform that wraps each joining operator, in an expression tree, with a new operator that applies the original operator if all its inputs are defined, but returns a null if any input is null. The expression tree structure hasn’t changed, but it now consistently (anvoiding error) responds to null values by propagating them. In my example, a monad converts the list combining operation of concatenation into other list combining operations. The result was that the identity of concatenation (the empty list) formed the basis for the new list operator’s identity. — Both concepts are indeed relevant. A “monoid-to-aggregator” monad could convert 2-element operations into recursively applied list operations (which also return the single element for unitary lists, and the identity element for empty lists). Then a structure of monoids processing pairs of values could be transformed into a structure that processes lists.
slaymaker1907 3y ago
You could also argue that any({}) is really not defined because first order logic generally excludes empty sets. The reason for said exclusion is because weird stuff starts to happen when you allow an empty domain when talking about if a formula is true in all domains. For example, "exists x, P(x) or !P(x)" is true for every domain unless you allow an empty domain since "exists x ..." is always false. The same is true of all({}) because you have an equivalent weirdness in the form of "!(forall x, P(x) and !P(x))". These seem innocuous, but there are many rules of inference that are excluded once you allow the empty domain.
- deleted 3y ago
  [deleted]
- schoen 3y ago
  Maybe I'm too used to Coq's higher-order theory now, but I think it's not really that bad to say that we have to be careful about whether statements have existential import. https://en.wikipedia.org/wiki/Syllogism#Existential_import https://en.wikipedia.org/wiki/Syllogism#Existential_import
- Nevermark 3y ago
  If we are defining ANY as an n-element LIST operator, in a programming language, which recursively applies the 2-operand AND taking literal Boolean values, there are no ambiguities. Note that this is inherently a constructible relation, which avoids many pratfalls of more general mathematics. But if ANY & ALL are being defined as general mathematical relations over all EXISTING members of a class (whose members’ construction, consistency or completeness, may be unknown or even unattainable), then there are other issues.
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.
klysm 3y ago
> The identity element for the resistance sum across parallel resistors, is the infinite ohm resister. I really like this example, because it has an intuitive physical analog and is more tangible than than the example I typically reach for: lists.
bjourne 3y ago
Continuing the same line or reasoning, for integers, max([]) should be -inf and min([]) should be +inf. For positive numbers max([]) should be 0 and min([]) should be +inf. But that's not how these operations are defined in most languages.
- edflsafoiewq 3y ago
  It's certainly how they're defined in math. In fact all is just min and any is just max over the poset {True, False} with True > False. I think the reason we don't usually use those definitions is we like to maintain the fiction we're working with actual integers or reals, which don't have a min/max.
- xigoi 3y ago
  min and max are in fact defined this way in JavaScript.

layer8 3y ago

One corollary is that a zero-dimensional array has exactly one element, whereas a 1-dimensional array can have zero elements (can have length zero). It took me a while to wrap my head around this.

Nevermark 3y ago
Yes! Dimensions are multipliers on each other. The cross points, over multiple points on segments in different dimensions is a product. And the product across an empty list is 1. The number of ways you can roll a dice “no” times is also 1. Cross combinations of all kinds are products.
- itishappy 3y ago
  Whoah... Does this imply there's a sixth of a way to unroll a dice?
rain1 3y ago
I don't understand this. Please can you point me to information about it?
- layer8 3y ago
  I haven’t seen this discussed anywhere else in terms of arrays, so I’ll elaborate here: The number of elements in an n-dimensional array is the product of its n dimension sizes. For example, the number of elements in a two-dimensional 2x3 array is 6, because 2 x 3 = 6. Consequently, the number of elements in a zero-dimensional array would be the empty product, which is 1 (as the root comment mentions). Naively, one might think that removing a dimension from an array cannot increase the number of elements. For example, dropping a dimension from a 2x3 array reduces the number of elements from 6 to 2 (or 3, depending in which dimension you drop). But in the case of a zero-length 1-dimensional array (i.e. an empty list or empty vector), dropping the one dimension causes an element to be added, because a zero-dimensional array always has 1 element. (This effect is not restricted to 1- and 0- dimensional arrays, by the way. If you admit zero-length dimensions, then you can also think of a 2x0 two-dimensional array, which would have zero elements, but dropping the zero-length dimension would result in a 1-dimensional array of length 2, increasing the element count by 2.) The other maybe surprising part is that for all n > 0, you can have an n-dimensional array with zero elements by having at least one of the dimensions have length zero. But for a zero-dimensional array, it’s not possible for it to be empty, because it has no dimension whose length could be zero. This is somewhat counterintuitive at first, because one might have thought that a zero-dimensional array would be the canonical empty array, like how a point in space (whis is a zero-dimensional object) has no length/area/volume. By the way, one could think of non-array values in a programming language to really be zero-dimensional array values, with their value being the singular element of the zero-dimensional array.

deleted 3y ago

[deleted]

evertedsphere 3y ago

monoid, not monad --- a monoid is a set A with an associative binary operator @ on it: that is, for any a, b, c a @ (b @ c) = (a @ b) @ c and it also has an "identity" element I, that is, for any a: a @ I = I @ a = a common monoids: integers under addition (i.e. @ is addition, the identity is 0), nonzero real numbers under multiplication, lists under concatenation, booleans under AND (identity is True), booleans under OR (what's the identity?), ... now, when you have a mathematical structure, you often want to study functions between two of them. so you might ask what a reasonable notion of functions between monoids is one nice way is if, given two monoids, M with operation @ and unit I, and N with operation ^ and unit J, we had a function f for which: f(I) = J f(a @ b) = f(a) ^ f(b) this is loosely described as the function "respecting the structure" of the monoids, and such functions are called monoid homomorphisms or just homomorphisms if the context is clear -- with that background, we see that `all` should really be be a homomorphism from the monoid of lists (under concatenation, with the empty list as the identity element) to the monoid of booleans under AND (with True as the identity) this means that all(concat(list1, list2)) = and(all(list1), all(list2)) or, in python, all(a + b) = all(a) and all(b) and, of course, all([]) = True! the value here is that now you can reason about the all() of two lists by thinking about the all() of sublists, and the conditions required for a homomorphism guarantee that the empty list is not an edge case: all([T, F]) = all([]) and all([T, F]) = all([T]) and all([F]) = ... and that it doesn't matter how you cut up a list into sublists and what order you apply the concatenations in to reconstruct it

Nevermark 3y ago
I was referring to monad, as used in programming, as a transform that can be applied to the elements of a structure. For instance, a transform that wraps each joining operator, in an expression tree, with a new operator that applies the original operator if all its inputs are defined, but returns a null if any input is null. The expression tree structure hasn’t changed, but it now consistently (anvoiding error) responds to null values by propagating them. In my example, a monad converts the list combining operation of concatenation into other list combining operations. The result was that the identity of concatenation (the empty list) formed the basis for the new list operator’s identity. — Both concepts are indeed relevant. A “monoid-to-aggregator” monad could convert 2-element operations into recursively applied list operations (which also return the single element for unitary lists, and the identity element for empty lists). Then a structure of monoids processing pairs of values could be transformed into a structure that processes lists.

slaymaker1907 3y ago

You could also argue that any({}) is really not defined because first order logic generally excludes empty sets. The reason for said exclusion is because weird stuff starts to happen when you allow an empty domain when talking about if a formula is true in all domains. For example, "exists x, P(x) or !P(x)" is true for every domain unless you allow an empty domain since "exists x ..." is always false. The same is true of all({}) because you have an equivalent weirdness in the form of "!(forall x, P(x) and !P(x))". These seem innocuous, but there are many rules of inference that are excluded once you allow the empty domain.

deleted 3y ago
[deleted]
schoen 3y ago
Maybe I'm too used to Coq's higher-order theory now, but I think it's not really that bad to say that we have to be careful about whether statements have existential import. https://en.wikipedia.org/wiki/Syllogism#Existential_import https://en.wikipedia.org/wiki/Syllogism#Existential_import
Nevermark 3y ago
If we are defining ANY as an n-element LIST operator, in a programming language, which recursively applies the 2-operand AND taking literal Boolean values, there are no ambiguities. Note that this is inherently a constructible relation, which avoids many pratfalls of more general mathematics. But if ANY & ALL are being defined as general mathematical relations over all EXISTING members of a class (whose members’ construction, consistency or completeness, may be unknown or even unattainable), then there are other issues.

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.

klysm 3y ago

> The identity element for the resistance sum across parallel resistors, is the infinite ohm resister. I really like this example, because it has an intuitive physical analog and is more tangible than than the example I typically reach for: lists.

bjourne 3y ago

Continuing the same line or reasoning, for integers, max([]) should be -inf and min([]) should be +inf. For positive numbers max([]) should be 0 and min([]) should be +inf. But that's not how these operations are defined in most languages.

edflsafoiewq 3y ago
It's certainly how they're defined in math. In fact all is just min and any is just max over the poset {True, False} with True > False. I think the reason we don't usually use those definitions is we like to maintain the fiction we're working with actual integers or reals, which don't have a min/max.
xigoi 3y ago
min and max are in fact defined this way in JavaScript.