Variant of universal algebra where equations are constrained to have a single variable on the right.

105 Views Asked by At

This question by user107952 asks for equational theories with only infinite models and the trivial model on the set with one element.

There are a few answers such as the ordered-pair theory mentioned in Alex Kruckman's answer:

$$ \pi_1(p(x, y)) \approx x \\ \pi_2(p(x, y)) \approx y \\ p(\pi_1(z), \pi_2(z)) \approx z $$

And the theory of an injective function $s$ mentioned in Noah Schweber's answer, among others.

$$ p(s(x)) \approx x \\ t(0, y, z) \approx y \\ t(s(x), y, z) \approx z $$

And the single theory $(x'y)z \approx y$ .

One thing all of these equations have in common is that the term on the RHS of all of the equations listed is a simple variable.

Let me define the boring algebra on $(\sigma, \lambda)$ where $\sigma$ is a signature and $\lambda$ is an ordinal. Let the domain of the boring $(\sigma, \lambda)$-algebra be $\lambda$. Additionally, let the interpretation of every constant in $\sigma$ be $0$ and let the interpretation of every function in $\lambda$ be the constantly $0$ function.

Let me define a type I equation as having both sides headed by functions or constants, e.g. $1 \approx 0$, $x+1 \approx 0$, etc. A type II equation has one term headed by a function and one term headed by a variable like the examples above. A type III equation has two variables, it is equivalent to $x \approx x$ or $x \approx y$ neither of which are interesting.

Some axioms like associativity are type I $(a + b) + c \approx a + (b + c)$. However, any theory in $\sigma$ with only type I axioms will have every boring algebra in $\sigma$ as a model.

My question is: do we get an interesting subset of universal algebra if we restrict our attention to type II equations?

1

There are 1 best solutions below

1
On BEST ANSWER

Let me say something about Type II identities. These are the identities of the form $w\approx x$ where $x$ is a variable and $w=s(t_1,\ldots,t_n)$ where $s$ is a function symbol and each $t_i$ is a term in a set $V$ of variables. I will call the function symbol $s$ the outermost function symbol on the LHS.

I take the question to be: Let $L$ be an algebraic language. What can be said about an equational theory $\Sigma$ in the language $L$ if $\Sigma$ has a set of axioms consisting of Type II identities?

I don't know the full answer, but I will make a few comments.

Observation. An equational theory $\Sigma$ contains a Type II identity $s(t_1,\ldots,t_n)\approx x$, for a particular choice of the outermost function symbol $s$, if and only if $s$ interprets as a surjective function in every model of $\Sigma$.

Only if. Assume that $\Sigma$ contains $s(t_1,\ldots,t_n)\approx x$ and $M$ is a model of $\Sigma$. We must show that $s^M\colon M^n\to M$ is a surjective function. Choose $m\in M$ arbitrarily, let $v$ be any valuation $v\colon V\to M$ such that $v(x)=m$. Since $M\models s(t_1,\ldots,t_n)\approx x$, we have $s^M(t_1[v],\ldots,t_n[v]) = x[v] = v(x) =m$, so $m$ is in the image of $s^M$. $\Box$

If. Assume $s$ is surjective on all models of $\Sigma$. Let $F = F_{\Sigma}(x)$ be the free $\Sigma$-algebra over the set $\{x\}$. Since $s^F\colon F^n\to F$ is surjective, there is an $n$-tuple $(t_1,\ldots,t_n)\in F^n$ such that $s^F(t_1,\ldots,t_n)=x\in F$. This relation satisfied by the free generator $x\in F$ must hold universally in all models of $\Sigma$ by the universal mapping property for free algebras, so all models of $\Sigma$ satisfy $s(t_1,\ldots,t_n)\approx x$. $\Box$

The above observation makes it clear that if ${\bf A}$ is an algebra that has no surjective fundamental operations, then ${\bf A}$ does not satisfy any Type II identities. This is enough to conclude that some equational theories do not have axioms consisting of Type II identities.

Groups have surjective multiplication $\ast\colon G\times G\to G$ and surjective inverse ${}^{-1}\colon G\to G$, raising the question of whether the theory of groups can be axiomatized by Type II identities. The answer is Yes. An old result about this is in

A. Tarski.
Ein Beitrag zur Axiomatik der Abelschen Gruppen.
Fundamenta Mathematicae, 30:253-256, 1938.

Tarski proves that the class of abelian groups can be axiomatized in the language of division $x/y: = x-y$ by the Type II identity $$ x / (y / (z / (x / y))) \approx z. $$

Higman and Neumann proved in

G. Higman and B. H. Neumann.
Groups as groupoids with one law.
Publicationes Mathematicae Debrecen, 2:215-227, 1952.

that the class of all (not necessarily abelian) groups can also be axiomatized in the language of division by the Type II identity $$ x / ((((x / x) / y) / z) / (((x / x) / x) / z)) \approx y. $$

Kunen proved in

K. Kunen.
Single axioms for groups.
J. Automated Reasoning, 9(3):291-308, 1992.

that the class of all groups can be axiomatized in the language of multiplication and inverse by the Type II identity $$ ((z * (x * y)')' * (z * y')) * (y' * y)' \approx x. $$

McCune proved in

W. McCune
Single axioms for Boolean algebra
Mathematics and Computer Science Division
Technical Memorandum No. 243, June 2000

that the class of Boolean algebras expressed in the language of NOR (Sheffer stroke) is axiomatized by the Type II identity

$$(((((x|(((y |z )|(y |(u|z )))|y ))|y )|(((y |z )|(y |(u|z )))|(x|(y | y ))))|((((v |(v |w ))|w )|(v |(v |(w |w ))))|y ))|y )|((((v |(v |w ))| w )|(v |(v |(w |w ))))|((((x|(((y |z )|(y |(u|z )))|y ))|y )|(((y | z )|(y |(u|z )))|(x|(y |y ))))|(y |y ))) \approx w.$$

All of the above results seem to focus on theories axiomatized by a single Type II identity. There is an interesting result that connects theories axiomatized by finitely many Type II identities with theories axiomatized by a single Type II identity in

R. McKenzie
Equational bases for lattice theories.
Mathematica Scandinavica, Vol. 27, No. 1 (1970), pp. 24-38.

Theorem 1.2. (paraphrased) If $\Sigma$ is an equational theory that can be axiomatized by finitely many Type II identities, and $\Sigma$ contains the near unanimity identities for some term $m(x_1,\ldots,x_k)$, then $\Sigma$ can be axiomatized by a single Type II identity.

(The near unanimity identities for $m$ are $m(y,x,x,\ldots,x)$ = $m(x,y,x,\ldots,x)$ = $\cdots$ = $m(x,x,x,\ldots,y)$ = $x$.)