Model Theory – Two Notions of Generalized Quotient/Substructure

lo.logicmodel-theoryuniversal-algebra

Given a language $\Sigma$ and a $\Sigma$-algebra (in the sense of universal algebra) $\mathcal{A}=(A;\dotsc)$ and a function $f:A\rightarrow A$, let $\mathcal{A}_f$ be the $\Sigma$-algebra whose underlying set is $\operatorname{im}(f)$ and whose basic operations are given by $$g^{\mathcal{A}_f}(a_1,\dotsc,a_n)=f(g^\mathcal{A}(a_1,\dotsc,a_n))$$ for each $g\in\Sigma$. In general passing from $\mathcal{A}$ to $\mathcal{A}_f$ does not preserve the equational theory; even if we require $f$ to be idempotent only equations where both the left and right side have at most one function symbol (call such equations "basic") are guaranteed to be preserved (e.g. let $\mathcal{A}=(\mathbb{R}; +,\times)$ and $f(x)=x-\lfloor x\rfloor$).

Note that every subalgebra $\mathcal{S}$ of $\mathcal{A}$ is an $\mathcal{A}_f$ (pick any $f$ with $\operatorname{im}(f)=\mathcal{S}$, $ff=f$, and $f\upharpoonright\mathcal{S}=\mathrm{id}_\mathcal{S}$) and every quotient $\mathcal{Q}$ of $\mathcal{A}$ is isomorphic to an $\mathcal{A}_f$ (have $f$ pick out representatives of the equivalence classes). This motivates the following pair of questions. Given a class of algebras $\mathbb{K}$, let $F(\mathbb{K})$ be the smallest class of algebras containing $\mathbb{K}$ and closed under arbitrary products, isomorphic images, and maps $\mathcal{A}\mapsto\mathcal{A}_f$, and let $F_i(\mathbb{K})$ be the same but where we require $f$ to be idempotent in the latter case. By the above, both $F_i(\mathbb{K})$ and $F(\mathbb{K})$ are varieties and we have $\mathbb{K}\subseteq F_i(\mathbb{K})\subseteq F(\mathbb{K})$.

  • Is there a $\mathbb{K}$ such that $F_i(\mathbb{K})\subsetneq F(\mathbb{K})$?

  • Is the equational theory of $F_i(\mathbb{K})$ the (deductive closure of the) set of basic equations true in each element of $\mathbb{K}$?

Best Answer

Let me copy Definition 4.1 of

Libor Barto, Jakub Oprsal, Michael Pinsker
The wonderland of reflections
Israel Journal of Mathematics 223 (2018), 363-398

Defn. 4.1 Let $\mathbf{A}$ be an algebra with signature $\tau$. Let $B$ be a set, and let $h_1\colon B\to A$ and $h_2\colon A\to B$ be functions. We define a $\tau$-algebra $\mathbf{B}$ with domain $B$ as follows: for every operation $f(x_1,\ldots,x_n)$ of $A$, $\mathbf{B}$ has the operation $$(x_1,\ldots,x_n) \mapsto h_2(f(h_1(x_1),\ldots, h_1(x_n))).$$ We call $\mathbf{B}$ a reflection of $\mathbf{A}$. If $h_2 \circ h_1$ is the identity function on $B$, then we say that $\mathbf{B}$ is a retraction of $\mathbf{A}$.

The construction in the problem statement above is the special case of a reflection where $B=\textrm{im}(f)$, $h_2=f$, and $h_1$ = the inclusion of $B$ into $A$. In this case, the algebra $\mathbf{B}$ of Definition 4.1 is what would be called $\mathbf{A}_{h_2}$ in the problem statement.

The idempotent construction in the problem statement is exactly what is meant in Theorem 4.1 by a retraction. (If $f$ is idempotent in the problem statement, let $B=\textrm{im}(f)$, $h_2 = f$, $h_1$ = the inclusion of $B$ into $A$ to see that $\mathbf{A}_f$ is what is called a retraction of $\mathbf{A}$ in the wonderland paper. Conversely, if $\mathbf{B}$ is a retraction of $\mathbf{A}$ in the sense of Definition 4.1, let $f = h_1\circ h_2$ in the problem statement and notice that $h_1\colon \mathbf{B}\to \mathbf{A}_f$ is an isomorphism.)

Now let me summarize some definitions from the wonderland paper. A term has height 0 if it is a variable and has height 1 if it is a fundamental operation applied to variables. A term has height at most 1 if its height is 0 or 1. An identity $s\approx t$ has height 1 if both $s$ and $t$ have height 1, and has height at most 1 if both $s$ and $t$ have height at most 1.

The wonderland result that is relevant to this problem is:

Corollary 5.4: Let $K$ be a nonempty class of algebras of the same signature $\tau$.
(i) $K$ is closed under reflections and products if and only if $K$ is the class of models of some set of $\tau$-identities of height 1.
(ii) $K$ is closed under retractions and products if and only if $K$ is the class of models of some set of $\tau$-identities of height at most 1.

With this background, let me address the questions in the problem.

  • Is there a $\mathbb{K}$ such that $F_i(\mathbb{K})\subsetneq F(\mathbb{K})$?

  • Yes, let $\mathbb{K}$ be the class of semilattices. It can be shown that the associative law is not a consequence of height 1 identities, so $\mathbb{K}\subsetneq F_i(\mathbb{K})$. Also, the idempotent law $x\wedge x\approx x$ has height at most 1, so it will be satisfied in $F_i(\mathbb{K})$. (This fact is easy to prove from the definitions, you don't need to cite the wonderland paper.) The class $F(\mathbb{K})$ does not satisfy $x\wedge x\approx x$, because this class contains nontrivial algebras of size $>1$ that have constant multiplication. To see this, choose a semilattice $\mathbf{A}$ and a nonconstant function $f\colon A\to A$ such that $\textrm{im}(f)$ is a proper subsemilattice of $\mathbf{A}$ and $f\circ f$ is constant. In this situation $\mathbf{A}_f$ will have size $>1$ and have constant multiplication, so it will not satisfy the idempotent law, so it will lie in $F(\mathbb{K})-F_i(\mathbb{K})$.

  • Is the equational theory of $F_i(\mathbb{K})$ the (deductive closure of the) set of basic equations true in each element of $\mathbb{K}$?

  • Yes, as indicated by Corollary 5.4 of the wonderland paper.

    Related remarks.

    Remark 1. The phrase 'basic equations' goes back to

    Kelly, David
    Basic equations: word problems and Mal’cev conditions.
    Abstract 701-08-04, AMS Notices 20 (1972) A-54.

    For Kelly, a term is basic if it is a variable, a constant, or a fundamental operation symbol applied to variables and constants. An identity is a basic equation if both sides are basic. This is close to but different from what is meant in the problem on this page.

    Remark 2. The part of Corollary 5.4 that concerns retractions was observed earlier in

    Taylor, Walter
    Simple equations on real intervals.
    Algebra Universalis 61 (2009), no. 2, 213-226.

    I summarize Taylor's Theorem 2.1 as follows:

    Theorem 2.1. Let $V$ be a variety Then $V$ is closed under set-retractions iff $V$ is definable by simple equations.

    Taylor's terminology is a little different than that of the wonderland paper, but the result is the same in the case of retractions. (Simple = height at most 1.)

    You can find a extended discussion of Theorem 2.1 in Volume 2, Section 6.7, of the encyclopedia

    Ralph S. Freese, Ralph N. McKenzie, George F. McNulty, Walter F. Taylor
    Algebras, Lattices, Varieties
    Mathematical Surveys and Monographs, American Mathematical Society, v. 268, 2022.

    [In particular, FMMT show in their Theorem 6.61 that if $\mathbb{K}$ is the class of semilattices, then $\mathbb{K}\subsetneq F_i(\mathbb{K})$, because the latter does not satisfy the associative law.]

    Remark 3. The wonderland paper was written primarily to develop tools to study the Constraint Satisfaction Problem for $\aleph_0$-categorical structures.