Notation for carrier vs magma

Stream: Equational

[Stanley Burris]

page 3: M-font in "magma M that obeys E"

On page 3 one finds "A magma ${\mathcal M} = (M, ⋄)$ obeys a law E"

Perhaps the word "obeys" could be italicized to show this is a definition, or perhaps even revised to "obeys or satisfies" since variations of the the word "satisfy" are used on the following pages :

9: "namely magmas satisfying them"
10: "if every magma that satisfies Γ also satisfies E."
33: "find a magma which satisfies (E854)"
33: "E854-satisfying solution also satisfies E."
34: "finding a magma satisfying"
49: "namely magmas that satisfy a candidate law"
53: "an example of its smallest satisfying magma"
54: "which equations a given finite magma satisfies or fails to satisfy"

[Stanley Burris]

A senior colleague once told me that induction proves that every paper requires an infinite sequence of revisions since it always requires one revision, and following every revision one discovers another that needs to be made.

So here is my next set of comments:

Page 3: "that satisfies E, also implies E′"
change implies to satisfies

Page 27: "In the language of first-order logic, a partial magma operation can also be viewed as a ternary relation R(x, y, z)"
Is there any other way for first-order logic to handle partial operations? If not, then perhaps "must be viewed as" ?

page 30: " necessary and sufficient resolve any"
change: "sufficient to resolve"

page 30: a G-font issue ?

page 32: The N - font in “in such a way that N satisfies E but not E′.”

page 33: G-font in “the model G with carrier" ?

page 33: Is undefining an English word, as in "while undefining the remainder"

Perhaps "leaving the remainder undefined" is better?

page 36: "6.3. Canonization. One possible way of obtaining refutations of a given implication E ⇒ E′ between equational laws"

This is the first time ⇒ is used as a relation between two laws.

page 37: "Theorem 6.8. Whenever R weakly collapsing, a weak canonizer, and non-overlapping, then conditions of Definition 6.7 then CR is a canonizer."

Changes: R is weakly collapsing & Definition 6.7 imply CR is a canonizer

page 58: "Two equational laws are equivalent if "
This is not the same definition of equivalent laws as on page 3.
Perhaps something like "weakly equivalent"?

[Terence Tao]

Thanks! I had accidentally deleted a lot of "obeys" intending to replace them with "satisfies" but I think I found all of them now.

Regarding the G on page 30, I have been trying to make a distinction between groups and magmas; technically a group is a magma, but usually we want a magma structure on the group that is distinct from the group operation, so I have avoided trying to give groups the same font as a magma unless there is an operation on it that is explicitly designated as a magma operation. Hopefully this is less confusing than it sounds!

[Stanley Burris]

Indeed I see your point, and it goes back to a shortcoming of the notation that Sanka and I adopted for our book. We were very happy to use $\mathbf{A} = (A,+)$ since it was easy to remember the notation for the algebra and for the carrier if one knew either. Unfortunately it is not a good notation if one wants to discuss different algebras on the same carrier $A$---we must have largely simply avoided that conflict in our book. When discussing clone theory (which we didn't) something better is needed because one is interested in comparing the term-definable functions on two different algebras on the same carrier. I rarely worked with clone theory, so I didn't try to find a better notation. In some cases, like 2-element algebras, by choosing the carrier to be $2$, that is, $\{0,1\}$, we were free to use any letter for the algebra, or in well known cases of a variety with a unique 2-element model we would subscript it as in $\mathbf {2}_L$ for the 2-element lattice, and $\mathbf {2}_{BA}$ for the 2-element Boolean algebra. When you have two magmas on the same carrier, say $(M,\diamond_1)$ and $(M,\diamond_2)$, with the notation for the binary operations differing only in the subscript, one can simply use $\mathcal{M}_1$ and $\mathcal{M}_2$. For two operations with distinct symbols, like $\diamond$ and $\square$, one could try
$\mathcal{M}_\diamond = (M,\diamond)$ and $\mathcal{M}_\square = (M,\square)$.
For group notation I would be tempted to try $\mathcal{G}_\bullet = (G,\bullet)$, using \bullet instead of \cdot.
I would really try to avoid notation like "G = (G, +) and G′ = (G′, +) " on page 31.

[Terence Tao]

Well, outside of algebra it is extremely common to "abuse notation" and use the same symbol for both an algebraic structure and its carrier. For instance the ring of integers is usually denoted by the same symbol ${\mathbb Z}$ as its carrier, even though strictly speaking one should use $({\mathbb Z}, +, \times, -, 0, 1)$ or some other symbol than ${\mathbb Z}$. Since groups are introduced fairly infrequently in the paper, we can avoid this issue by referring to $(G,+,-,0)$ or $(G,\cdot, \cdot^{-1},1)$ the few times such groups are introduced.

[Stanley Burris]

Indeed the simplest acceptable, easy to remember notation has everything going for it.

One more comment: On page 10 the alphabet X and words w are introduced. In universal algebra, and I think in logic, X is called a set of variables and words are called terms. The set $W$ of words has a precise definition by recursion:
(1) all $x$ in X are words
(2) if $w_1$ and $w_2$ are words so is $w_1 \diamond w_2$.

This is understood to mean that the set of words over X is the smallest set $W$ closed under (1) and (2). This set exists because some set is closed under the two, namely the set of all strings over $X \cup \{\diamond, (, )\}$, so just take the intersection of all subsets of this set that are closed under (1) and (2) to obtain the smallest such set.

The essence of equational logic is that $\Gamma \vdash E$ means there is a finite list of equations $E_1,\ldots,E_n$, called a derivation of $E$ from $\Gamma$, such that each $E_i$ comes from $\Gamma$ or is the result of applying one of Birkhoff's 5 Rules of Inference to previous $E_j$, and $E_n$ is $E$. Such a derivation is called a formal proof of $E$ from $\Gamma$. Such a proof is clearly a good candidate for Automated Proof Verification.

If one drops the requirement that $E_n$ is $E$ then one simply has a derivation from $\Gamma$, which of course is a derivation of $E_n$ from $\Gamma$. Indeed each initial portion $E_1,\ldots,E_j$ of the derivation is a derivation of $E_j$ from $\Gamma$, so every step of the derivation gives a theorem, $\Gamma \vdash E_j$.

By contrast, a proof that $\Gamma \models E$ is based on naive set theory unless one invokes the completeness theorem that says $\Gamma \models E$ iff $\Gamma \vdash E$ and gives a derivation of $E$ from $\Gamma$. (The completeness theorem is usually proved using naive set theory.) Proving $\Gamma \models E$ based on naive set theory has no simple set of clear rules on what a valid proof has to look like, it just needs to be accepted by the scholarly community.

Strict rules for creating derivations give the look of a game, namely given $\Gamma$ and $E$, find a derivation to show $\Gamma \vdash E$. This made formal proof theory look like a good candidate for computer theorem proving.

For $\Gamma$ finite there is a simple algorithm to search for a derivation of $E$, namely start creating a list of all derivations of length 1, and then start this for length 2, etc. If $\Gamma \vdash E$ then a proof (i.e., a desired derivation) will appear. This of course is miserably inefficient, so programs have been written that offer the user the chance to search for a proof in a much narrower space by setting various parameters, using term rewriting, etc. The amazing thing is that such ATPs have been so successful with equations.

It seems the biggest impact of computers on mathematics in the years to come will be developments in automated proof verification. Maybe this will become a standard part of mathematics in about a decade.

[Stanley Burris]

Notation for algebras with the same carrier.

I asked ChatGPT:

One usually refers to a group $(G,\cdot)$ simply as the group $G$.
Is there an abbreviated notation for two groups on the same set $G$?

REPLY:

When you have two (or more) group structures on the same underlying set $G$, it’s common to abbreviate the notation in several systematic ways, depending on the context and how much emphasis you need to give to the operations.

---

:one: The fully explicit form

You start from the full data:

$$(G, \cdot) \quad \text{and} \quad (G, *)$$

two groups with the same underlying set $G$, but possibly different operations.

That’s perfectly clear and always correct.
Now we look at standard abbreviations.

:two: Abbreviated notations

(a) Subscripts or decorations on the operation

You can keep $G$ as the set, and distinguish the operations with subscripts or adornments:

$$(G, \cdot_1) \quad\text{and}\quad (G, \cdot_2),$$

or equivalently,

$$(G, *_1) \quad\text{and}\quad (G, *_2).$$

Then, for readability, people often write

$$G_1 := (G, \cdot_1), \quad G_2 := (G, \cdot_2).$$

So you just refer to “the group $G_1$” and “the group $G_2$” — both living on the same underlying set.

:check: This is by far the most common practice.

---

(b) Different symbols for the operation itself

Sometimes, to emphasize the operations rather than the structures, one writes:

$$(G, \cdot) \quad\text{and}\quad (G, \circ),$$

or

$$(G, +) \quad\text{and}\quad (G, \cdot),$$

when one is additive and the other multiplicative.
Then you simply refer informally to “the $\cdot$-group on $G$” and “the $\circ$-group on $G$”.

[Bruno Le Floch]

I've taken the liberty to move the messages about fonts and notations for groups/magmas/the underlying set to a new discussion, this way Terry's questions about the status of section 7.3, and about which journal to choose, remain visible in the "Writing the paper" thread.

[Jose Brox]

Terence Tao ha dicho:

Well, outside of algebra it is extremely common to "abuse notation" and use the same symbol for both an algebraic structure and its carrier

I'd say this is in fact the case inside algebra too!