Universal magmas

Stream: Equational

[Daniel Weber]

We can say that $M$ is a universal magma for a law if the set of laws it satisfies is exactly the consequences of the law.
For example, the quotient of the free magma on $\mathbb{N}$ by a law is always a universal magma for it. I think that's also the case for the quotient of the free magma on $\{0, 1\}$, but I don't have a proof. The law $x = x \diamond y$ has as a universal magma the set $\{0, 1\}$ with $x \diamond y = x$. The law $x = y$ has the trivial magma. The law $x = x$ has the free magma on $\mathbb{N}$, and I think also $\mathbb{N}$ with exponentiation. Associativity has strings with the operation of concatenation.

What are some other examples of interesting universal magmas? Which laws admit finite universal magmas? Is every finite magma a universal magma for some law?

[Anand Rao Tadipatri]

Multisets over the natural numbers are also universal magmas satisfying the commutativity and associativity axioms.

[Daniel Weber]

For both of them together. Are they a universal magma for a single law?

[Anand Rao Tadipatri]

I'm sorry, I misread the definition. I don't think this example works any longer under the constraint of having a single law.

[Daniel Weber]

It's still interesting if it's a universal magma for any singular law, as for that purpose it's also equivalent to $\mathbb{N}$ with either addition or multiplication

[Terence Tao]

I would call these magmas "generic magmas" rather than "universal magmas", as they do not obey a https://en.wikipedia.org/wiki/Universal_property.

I believe you are correct that a free magma on two elements modulo the law will be generic, because a free magma on two elements 0, 1 contains the free magma on countably many elements as a submagma (e.g., take the submagma generated by 10, 1(00), 1(0(00)), 1(0(0(00))), etc.).

[Daniel Weber]

That's not enough, because the quotient may make these equal (a quotient of the free magma on one element isn't general, for instance, as in it $x \diamond y = x$ implies $x = y$)

[Terence Tao]

Hmm, good point. Then I don't see a cheap "abstract nonsense" way to resolve your question.

[Terence Tao]

A simple remark: we have Austin pairs: laws X, Y such that X implies Y for finite magmas, but not for infinite magmas. For instance, Asterix and Oberlix form an Austin pair. In such cases, generic models of X must be infinite (as they are not permitted to obey Y).

The question of whether the free magma on two generators, modulo laws, is generic, seems to be subtle. Take for instance the Sheffer stroke law models Boolean algebras (the Sheffer stroke can be used to recover all the other Boolean operations). The universal magma here is then the free Boolean algebra on countably many generators, whereas the magma generated by two elements becomes the free Boolean algebra on two generators, which has only 16 elements. So in particular, from a first-order logic point of view it is not generic (the assertion "there are seventeen distinct elements" does not hold in this model, but holds in the universal model). On the other hand, it appears that every equational law obeyed by the sixteen-element algebra holds for the universal Boolean algebra (and hence all Boolean algebras), because one can view the latter as the direct sum (or direct product?) of infinitely many copies of the former.

In the case of natural central groupoids the free magma of two generators is a four-element magma (the base set S has two elements). It's not clear to me right now whether there are laws on this magma that are not obeyed by the universal magma (in which case the base set is countably infinite).

[Mario Carneiro]

Terence Tao said:

I would call these magmas "generic magmas" rather than "universal magmas", as they do not obey a https://en.wikipedia.org/wiki/Universal_property.

Huh? Isn't this precisely an initial object in the category of magmas satisfying the law in question?

[Terence Tao]

I don't think there is necessarily a magma homomorphism from a generic magma (a magma that obeys only the laws that are entailed by a given law X) to an arbitrary magma obeying X.

[Mario Carneiro]

maybe this hinges on what it means to "satisfy only the laws entailed by X"

[Mario Carneiro]

is this a quantification over MagmaLaw?

[Terence Tao]

That's how I understood it

[Mario Carneiro]

in which case you are right, that's not quite the same as a free object, although I don't have a counterexample

[Terence Tao]

A random magma on Nat will almost surely be generic for x=x (for any reasonable notion of "random"), but one can plant some entries to ensure that it is not free.

[Mario Carneiro]

it's not clear to me that you can do that without spoiling genericity at the same time

[Mario Carneiro]

is there a cardinality argument for this?

[Terence Tao]

Well, equational laws have to hold universally. If you mess up only a finite number of values of the multiplication table, there are still an infinite number of remaining constants on which one is selecting the table randomly, and so the probability of a non-trivial law holding can be easily seen to be zero (lots of independent events of probability less than one have to simultaneously hold).

[Terence Tao]

There's probably also a Baire category argument, if one prefers to interpret "generic" as "outside of a countable union of nowhere dense sets".

[Mario Carneiro]

so I guess you can construct a magma on Nat which spoils every law by enumerating and popping them all with a new element

[Mario Carneiro]

but how do I know that didn't accidentally make a free magma?

[Terence Tao]

In the free magma for the trivial law x=x, no two different words can ever be equal, for instance 0 * 1 can never equal 1 * 0. But one can start the multiplication table with say 0 * 1 = 1 * 0 = 2 and fill in the rest randomly.

[Mario Carneiro]

Daniel Weber said:

For both of them together. Are they a universal magma for a single law?

This seems like a kind of PID property. Is every pair of laws expressible as a single law? If so, I think this is true, assuming that the theory of a finite magma is finitely generated (which I believe to be true although I don't know how to prove that either)

[Cody Roux]

Not sure where to mention this, but I have a candidate for the "free" magma over a set of equations (which are called Ctx in Completeness.lean and a somewhat awkward statement of the universal property, trying to stick to what's in FreeMagma.lean.

It's here: https://github.com/teorth/equational_theories/pull/563 feel free to (gently) critique.