antisubalgebra

In constructive mathematics, we often do algebra by equipping an algebra with a tight apartness (and requiring the algebraic operations to be strongly extensional). In this context, it is convenient to replace subalgebras with *anti*-subalgebras, which classically are simply the complements of subalgebras.

Let us work in the context of universal algebra, so an **algebra** is a set $X$ equipped with a family of functions $f_i\colon X^{n_i} \to X$ (where each arity? $n_i$ is a cardinal number) that satisfy certain equational identities (which are irrelevant here). As usual, a **subalgebra** of $X$ is a subset $S$ such that $f_i(p_1,\ldots,p_{n_i}) \in S$ whenever each $p_k \in S$.

Now we require $S$ to have a tight apartness $\ne$, which induces a tight apartness on each $X^{n_i}$ (via existential quantification), and we require the operations $f_i$ to be strongly extensional. (There is no need, in general, to require that any arity $n_i$ be finite or that there be finitely many $f_i$.)

A subset $A$ of $X$ is **open** (or $\ne$-open) if, whenever $p \in A$, $q \in A$ or $p \ne q$. An **antisubalgebra** of $X$ is an open subset $A$ such that $p_j \in A$ for some $j$ whenever $f_i(p_1,\ldots,p_{n_i}) \in A$ for any $i$. By taking the contrapositive, we see that the complement of $A$ is a subalgebra $S$; then $A$ may be recovered as the $\ne$-complement of $S$ (the set of those $p$ such that $p \ne q$ whenever $q \in S$). However, we cannot start with an arbitrary subalgebra $S$ and get an antisubalgebra $A$ in this way, as we cannot (in general) prove openness. (Impredicatively, we can take the antisubalgebra generated by the $\ne$-complement of $S$, as described below, but its complement will generally only be a superset of $S$.)

Unless otherwise noted, all of the constructions in these examples should be predicative.

The empty subset of any algebra is an antisubalgebra, the **empty antisubalgebra** or **improper antisubalgebra**, whose complement is the improper subalgebra (which is all of $X$). An antisubalgebra is **proper** if it is inhabited; the ability to have a positive definition of when an antisubalgebra is proper is a significant motivation for the concept.

If $A$ is an antisubalgebra and $c$ is a constant (given by an operation $X^0 \to X$ or a composite of same with other operations), then $p \ne c$ whenever $p \in A$. If there are only Kuratowski-finitely many constants (which is needed to prove openness), we define the **trivial antisubalgebra** to be the subset of those elements $p$ such that $p \ne c$ for each constant $c$ (the $\ne$-complement of the trivial subalgebra). In general, we may also take the **trivial antisubalgebra** to be the union of all antisubalgebras (but this is not predicative).

Instead of subgroups, use antisubgroups. In detail, a subset $A$ of $X$ is an **antisubgroup** if $p \ne 1$ whenever $p \in A$, $p \in A$ or $q \in A$ whenever $p q \in A$, and $p \in A$ whenever $p^{-1} \in A$. (We need not assume that $A$ is open; this can be proved.) An antisubgroup $A$ is **normal** if $p q \in A$ whenever $q p \in A$. The **trivial antisubgroup** is the $\ne$-complement of $\{1\}$.

Instead of ideals (of rings), use antiideals. (Technically, these are antisubalgebras of the ring as a module over itself.) In detail, a subset $A$ of $X$ is a **two-sided antiideal** (or simply an **antiideal** in the commutative case) if $p \ne 0$ whenever $p \in A$, $p \in A$ or $q \in A$ whenever $p + q \in A$, and $p \in A$ and $q \in A$ whenever $p q \in A$. $A$ is a **left antiideal** if instead the last condition requires only that $p \in A$, and $A$ is a **right antiideal** if instead the last condition requires only that $q \in A$. It follows that an antiideal $A$ is proper iff $1 \in A$. $A$ is **prime** if it is proper and $p q \in A$ whenever $p \in A$ and $q \in A$; $A$ is **minimal** if it is proper and, for each $p \in A$, for some $q$, for each $r \in A$, $p q + r \ne 1$ and $q p + r \ne 1$ (which is constructively stronger than being prime and minimal among proper ideals). The **trivial antiideal** is the $\ne$-complement of $\{0\}$.

Note that a union of antisubalgebras is again an antisubalgebra. Given any subset $B$ of $X$, the antisubalgebra **generated** by $B$ is the union of all antisubalgebras contained in $B$. (This construction is not predicative, although it may still be true predicatively that the generated subalgebra exists in some situations.)

To form a quotient group or a quotient ring, it's enough to have a normal subgroup or a two-sided ideal. However, if we want the quotient algebra to inherit an apartness from the original algebra, then we need antisubgroups and antiideals.

In general, instead of congruence relations, use anticongruence relations. An **anticongruence relation** $K$ on $X$ is an apartness relation on $X$ that is also an antisubalgebra of $K \times K$. Given this, let $R$ be the negation of $K$; then $R$ is a congruence relation, giving a quotient algebra $X/R$. Furthermore, $K$ becomes a tight apartness on $X/R$, relative to which the algebra operations on $X/R$ are strongly extensional. We denote the resulting algebra-with-apartness by $X/K$. (This notation should cause no confusion; if an apartness relation on a set $X$ is also an equivalence relation, then $X$ must be the empty set, which has a unique apartness and at most one algebra structure, and the only quotient set of the empty set is itself.) The quotient map $X \twoheadrightarrow X/K$ is also strongly extensional.

Conversely, any strongly extensional map $f\colon X \to Y$ between algebras with apartness gives rise to an anticongruence $\aker f$ on $X$ (the **antikernel** of $f$), where $(p, q) \in \aker f$ iff $f(p) \ne f(q)$. The complement of the antikernel is the kernel in the usual sense of universal algebra, so the quotient algebra $X/(\aker f)$ is naturally isomorphic to a subalgebra $im f$ of $Y$; the maps $X \twoheadrightarrow X/(\aker f) \cong \im f \hookrightarrow Y$ are strongly extensional. Similarly, a sequence $X \overset{f}\to Y \overset{g} \to Z$ is exact iff $\im f$ is the complement of $\aker g$.

(We would like to say that there is an antisubalgebra $\aim f$ of $Y$ whose complement is $\im f$; then we could, for example, define a stronger notion of exactness requiring that $\aker g$ equal the antiimage of $f$. In principle, $a$ should belong to $\aim f$ iff $a \ne f(p)$ for every $p$ in $X$. If $X$ is Kuratowski-finite, then this works, but in general, we can prove neither that this is open nor that its complement is all of $\im f$.)

Given a group-with-apartness and a normal antisubgroup $A$, we define an anticongruence $K$, where $(p, q) \in K$ iff $p q^{-1} \in A$. Similarly, given a ring-with-apartness and a two-sided antiideal $A$, we define an anticongruence $K$, where $(p, q) \in K$ iff $p - q \in A$. This allows us to form quotient groups or quotient rings by modding out by normal antisubgroups or two-sided antiideals. Conversely, we can interpret the antikernel as a normal antisubgroup or two-sided antiideal: $p \in \aker f$ iff $f(p) \ne 1$, $p \in \aker f$ iff $f(p) \ne 0$, etc. In general, this works for any Omega-group structure.

These concepts play a large role in

- Ray Mines?, Fred Richman, Wim Ruitenburg?.
*A Course in Constructive Algebra*. Springer, 1987.

But I can't be sure that everything above appears in this reference.

Revised on January 17, 2017 12:56:52
by Toby Bartels
(108.167.41.14)