I still haven’t heard of any operators other than product or coproduct used in reductions

I’m still not sure what you mean by ‘reduction’ here; but comparing your links to your comment #11, I guess that you must mean `fold`

.

Mathematicians certainly apply `fold`

(although not under that name) to operations other than products and coproducts. Your comment #11 seems to me to be the usual recursive definition of how to apply a monoid operation (as normally defined) to a finite list. I have seen this used to define the sum and product of a list of numbers, for example; in fact, I’m pretty sure that I’ve written it down for sums when teaching undergraduate discrete mathematics. (Once we knew what the sum of a list of numbers was, then I introducted $\sum_{i = a}^b x_i$ as fancy notation for that simple concept.)

Mathematics is often more concerned with minimal definitions - from which subsets of facts can all the others be derived.

You might be interested in bias and unbiased definitions using operads and the like.

In the case of monoids, the usual definition is a set equipped with two operations: one $2$-ary and one $0$-ary. Then some axioms are posulated of these. But instead one could equip the set with an $n$-ary operation for every integer $n \geq 0$, although this also requires several more axioms. There are even more operations than these, such as $(x,y) \mapsto y x$ and $x \mapsto x^2$. By describing all possible operations and stating all true equational laws between them, you give an *unbiased* definition of what a monoid is.

To consider all of these at once, you pack them together into a single operad (or PROP, or PRO, or Lawvere theory, or whatever depending on exactly what you count as an ’operation’). A description in terms of a few basic operations and axioms then amounts to a *presentation* of an operad (or whatever) by generators and relations.

I was so blinded by my impressive reasoning from a bogus example that I didn’t realize it was bogus until a few moments after I posted.

Well, I think we all know that feeling… :)

]]>Finn, you were too quick. I was so blinded by my impressive reasoning from a bogus example that I didn’t realize it was bogus until a few moments after I posted. I thought no one had a chance to see it.

]]>I’m not following this debate, but

the category of pointed sets … has … no initial object

is not true – the one-point set (with its unique point) is both initial and terminal in $Set_\ast$.

]]>Toby, I was purposefully vague about ordering - the only example I gave was using **first** to extract the only element of a one element set. We appear to be in agreement on what matters.

I still haven’t heard of any operators other than product or coproduct used in reductions - which might motivate further discussion.

This discussion also brings up the huge terminological mess that can result when different fields interact. In English “reduce” basically means “to make smaller”. In math it often means “to break into small pieces” (e.g. “factor”, like English “reduce to rubble”), while in computer work it often means “make the number of pieces smaller or turn them into just one” which can be the opposite of the mathematical meaning. And in logic, reduction can mean “simplify”. Hoo boy.

I find my current perspective different than most mathematicians. I am concerned with mathematical structures, what is true in them, and where these facts live - e.g. did they emerge in the structure or were they inherited? Mathematics is often more concerned with minimal definitions - from which subsets of facts can all the others be derived.

My current ontological stumbling block involves “universal property” - a property that may not exist but if it does it has a unique existence. Conceptually I want “product” to live in the general structure “category” rather than in some generalization of the more specific categories where products actually exist.

[edit: quickly removed some stuff which may be badly wrong]

]]>I was taking it for granted that you were using an ordered index set, since you used $first$ and $last$ as if they were functions. Also, that is what I had been thinking of.

If op is associative then no matter what choices are made the reduction is the same.

No, in this case it is also has to be commutative. Already when applied to a $2$-element family $(a,b)$, I’ll get different results if I choose $x \coloneqq a$ than if I choose $x \coloneqq b$, since $x$ comes first.

But in the ordered case, it only has to be associative.

Edit: In my comment #8, I didn’t say that the index set was ordered in any way; I just said that it was finite. Yet I said only that the operation had to be associative. So actually the mistake was mine all along! (But nobody will ever know this, since I have just edited that comment.)

]]>@toby, only when the index set is ordered is there any difference between first(X) and last(X). Otherwise they are equivalent to choose(X) and the function should be written so that what was rest(X) has to become X without what was chosen. In more bastard notation:

reduce(op, X) = op(x := choose(X), reduce(op, X-{x}))

If op is associative then no matter what choices are made the reduction is the same.

So if op is associative then the index set can be given any total ordering and first(X) or last(X) can be used. But assigning an arbitrary order is the same as making a bunch of choices so all three versions turn out to be the same for the unordered case.

]]>There we go, that’s substantially better.

]]>@ Harry

You could certainly add that, not only to empty function but also to empty set, initial object, or Set.

I’ve rephrased the sentence so that it looks less like it’s trying to be some kind of proof.

]]>@ Rod

If the family contains just one member, then you don’t even need to have any operation at all! (^_^) The result must simply be that one member.

Anyway, I agree with your recursive definition, although there is also this definition:

reduce(op, {}) = unit(op)

reduce(op, X) = op(reduce(op, corest(X)), last(X))

And they agree iff the operation is associative, which is why that matters. (Probably you already noticed this.)

]]>@toby, for a reduction you also have to consider the case where the family contains just one member. The best way I know how to do this (in some bastard notation) is:

reduce(op, {}) = unit(op)

reduce(op, X) = op(first(X), reduce(op, rest(X)))

assuming that first and rest are defined so that first({a}) = a and rest({a}) = {}.

]]>I am not sure what you mean by “property of operators” here.

@Todd, my strange perspective is not about mathematics directly but about structures to encode mathematics and its terminology. I am using “property” in the data structure sense which is basically a function that maps a data structure to an internal data structure sub part.

From this perspective one wants to be able to define “Family reduced by Y” in a way that uses “the unit of Y” without having to use Y to construct a monoidial category to figure out what its unit is (and I don’t see how one can make a monodial category from Y without knowing what its unit is). That is in part why I asked about Yreduction where Y is not a (co)product, where if such cases exist one needs some other way to determine the unit if one cannot find it directly as a property of Y.

Essentially I am trying to discuss this in terms of a generalization of product, coproduct, and any other operators that have a unit. Category theory in general seems to just like to talk about opposites and when if something and its opposite have things in common it is because the commonality had no arrows to be reversed - however the commonality is not explicitly recognized..

My perspective is why in a different discussion I didn’t like the term “indecomposable” and wanted it changed to +indecomposable and ×indecomposable - to essentially allow them to be instances of a parameterized “Yindecomposable”.

If one says that Yproduct is the generalization/parametrization of product and coproduct then we could say that →product = product and ←product = coproduct where the parameter indicates the direction of internal arrows. One fact that lives in Yproduct is that the Yunit is “an” and “the” left and right identities of the operation. In terms of properties, I would say that Yunit lives in the “unit” property of Yproduct, and this property value is automatically inherited by →product as →unit (terminal object) and by ←product as ←unit (initial object). [1]

I am not suggesting the imposition of such a radical terminological renaming for now, Just the recognition that the unit of a (co)product is a fact that needs to be directly and explicitly noted rather than being handled as as two distinct though analogous cases everywhere.

[1] Terminology and notation subject to change as I figure out what I am trying to talk about.

]]>@Toby: Sure, it’s easy enough to prove. A slight change that would make the stub non-circular would be to say something like:

]]>In many set theories (mainly of the structural variety), it is an axiom that the category of sets has an initial object, which is called the empty set, and when it is not, it is often very easy to prove.

@ Rod

If you have a binary operation, then it only makes sense (a priori) to apply that operation to a $2$-indexed family. However, if the operation is associative, then it makes sense to apply it to any family whose index set is finite, inhabited, and linearly ordered. Also, if the operation is associative and commutative, then it makes sense to apply it to any family whose index set is finite and inhabited. On the other hand, if the operation has an identity, then it makes sense to apply it to the empty family. So in a commutative monoid, the operation may be applied to any finitely indexed family.

In a strong symmetric monoidal category, we have associativity, commutativity, and an identity up to coherent isomorphism, so we can still apply the operation to any finitely indexed family of objects to get a result up to coherent isomorphism, and we get the monoidal unit when we apply the operation to the empty family. In the case of a (co)product operation, this monoidal unit is a (co)terminal object. (Of course, if a category has every small (co)product, then we can take the (co)product of any small family of objects, not just a finitely indexed family.)

]]>@ Harry

You are correct.

I’m not trying to give a sound proof in any particular foundation; I’m just stating facts and the relationships between them. I thought that the facts were clear enough that they needed no proof, but I can prove them in any foundation you like if you wish. (At least, if I’m familiar enough with that foundation to use it.)

]]>Harry, I’m not sure what you are driving at (what or whose foundations, exactly?), but in structural set theories it is either an axiom or it is provable that an initial set exists. An empty function is then any function whose domain is initial. (In material set theories, there is a strong tendency for there to be a unique initial object.)

]]>Rod, “the” terminal object is always the unit (in the sense of monoidal category) for cartesian product, and the initial object is, dually, always the unit for coproduct. I am not sure what you mean by “property of operators” here.

]]>Is there some property of operators, say called “unit” or “identity”, where the terminal object is the unit of the product and the initial object is the unit of the coproduct?

It is needed to make the general statement for the reduction (right term here?) of an family by an operator - that the value for an empty family is the operator’s unit. Otherwise one has to describe things on a case by case basis.

Also are there any examples of family reductions that people use where the operator is not a product or coproduct?

[ if “co” and “” prefixes were not arbitrary then one might use their meaning to deduce that the “unit” of the “coproduct” is the “coterminal” object]

]]>@Toby: The assertion that the empty function is unique because $\emptyset$ is the initial object of the category of sets is circular in some foundations.

]]>I guess that I need family itself too.

]]>