Boolean Constructions and Discriminator Varieties

Discriminator Varieties

The ternary discriminator is a single term that encodes if-then-else. A variety generated by algebras carrying it is arithmetical, semisimple, congruence-permutable, has the congruence extension property and decomposes into Boolean products of simples.

Engineering · Mathematics5 min readKV-MATH-0241

Learning objectives

Define the ternary discriminator and verify it encodes a conditional.
Define a discriminator variety.
State the Boolean product representation theorem.
List the structural properties that follow automatically.
Show the discriminator is a Pixley term, hence arithmeticity.
Recognise standard examples of discriminator varieties.

01The ternary discriminator

On a set A, the ternary discriminator is the function that returns its third argument unless the first two agree, in which case it returns the second.

t(x, y, z) = z if x = y, x if x ≠ y

Equivalently: an if-then-else with equality as the test. Written t or the discriminator term throughout.

Key resultThe discriminator encodes case analysis

Because the discriminator tests equality and branches, a term algebra containing it can express conditional definitions. This single operation is what gives discriminator varieties their exceptional behaviour: arguments that would need case analysis in the metatheory can be carried out inside the algebra.

An algebra on which the discriminator is a term operation is called quasiprimal, treated in detail on the next page. A discriminator variety is one generated by a class of algebras on which a common term realises the discriminator.

02The discriminator is a Pixley term

ProcedureChecking the Pixley identities for the discriminator

in: the discriminator t → out: verification that t is a Pixley term

required: p(x,y,y) ≈ x, p(x,y,x) ≈ x, p(y,y,x) ≈ x
take p := t, the ternary discriminator
t(x,y,y): if x = y the value is y = x; if x ≠ y the value is x. So t(x,y,y) = x ✓
t(x,y,x): if x = y the value is x; if x ≠ y the value is x. So t(x,y,x) = x ✓
t(y,y,x): first two arguments agree, so the value is x ✓
all three identities hold, so t is a Pixley term

Consequence: every discriminator variety is arithmetical — congruence-permutable and congruence-distributive. Caveat: the converse fails; arithmetical varieties need not be discriminator varieties.

Arithmeticity comes for free, and with it congruence distributivity, hence Jónsson's lemma. That combination is what makes the structure theory possible.

03The representation theorem

Key resultBulman-Fleming, Keimel and Werner

Every algebra in a discriminator variety is isomorphic to a Boolean product of simple algebras. Conversely, a variety in which every member is such a Boolean product, with the simples suitably related, is a discriminator variety.

Simplicity of the stalks
In a discriminator variety the subdirectly irreducible members are exactly the simple members, and every algebra on which the discriminator is a term operation is simple.
Boolean product structure
The factor congruences of a member contain a Boolean algebra, and the corresponding Stone space indexes the stalks.
Patching from the discriminator
The discriminator term is precisely what supplies the patching condition — it performs the clopen case split algebraically.
Result
A complete structural description: the variety is determined by its simple members and the Boolean algebras used to glue them.

The source describes discriminator varieties as remarkably well behaved yet fascinating, and observes that probably no other class of varieties combines both qualities to the same degree. The representation theorem is why.

04The structural package

Properties that follow automatically
Property	Holds?	Source
Arithmetical	Yes	discriminator is a Pixley term
Congruence-permutable	Yes	from arithmeticity
Congruence-distributive	Yes	from arithmeticity
Congruence extension property	Yes	direct from the discriminator
Semisimple	Yes	SI members are simple
Every member a Boolean product of simples	Yes	BFKW theorem
Finitely generated ⟹ finitely based	Yes	Baker, via congruence distributivity
Finitely generated of finite type ⟹ decidable	Yes	Burris and Werner 1979
Model companion exists	Yes	Burris and Werner

Very few hypotheses in universal algebra deliver this much. Assuming a variety is a discriminator variety settles almost every structural question about it at once, which is why the class attracted so much attention in the period the source describes.

05Examples

Boolean algebras

The archetype

The Pixley term given in the Boolean stream is a discriminator term on 2. Boolean algebras are the simplest discriminator variety.

Post algebras

n-valued logic

Generated by a chain of n elements with the right operations; discriminator varieties for each n.

Cylindric algebras of finite dimension

Algebraic logic

Comer's work on these motivated much of the sheaf theory that became Boolean products.

Monadic algebras

Modal logic

Discriminator varieties, which is why their model companions are well behaved.

Varieties generated by quasiprimal algebras

The general source

Any finite algebra with a discriminator term generates a discriminator variety. This is the standard way examples arise.

Rings satisfying x^n ≈ x

For fixed n

Generate discriminator varieties, connecting the theory to classical ring conditions.

06Decidability

The decidability result for discriminator varieties is one of the strongest positive results in the area, and it is proved through the Boolean product representation.

ProcedureBurris and Werner's decidability argument

in: finitely generated discriminator variety of finite type → out: decidability

input: finitely generated discriminator variety V of finite type
every member is a Boolean product of simple algebras (BFKW)
convert the Boolean product to a filtered Boolean power
(a better-behaved construction, Arens–Kaplansky)
semantically embed the countable members of V into
countable Boolean algebras with finitely many distinguished filters
apply Rabin's decidability result for that theory
conclude: the first-order theory of V is decidable

The semantic embedding technique is developed in the Model-Theoretic stream, where it is used in the opposite direction to prove undecidability. Caveat: both hypotheses matter — finite generation and finite type.

Frequently asked

Is every arithmetical variety a discriminator variety?

No. Arithmeticity is necessary but not sufficient. Heyting algebras are arithmetical and do not form a discriminator variety, since they have subdirectly irreducible members that are not simple. Semisimplicity is the additional ingredient.

Must the discriminator term be the same across the generating class?

Yes — a discriminator variety requires a single term that realises the discriminator on every member of the generating class. Different terms on different algebras would not give a common term operation on the variety, and the representation theorem would fail.

Why are discriminator varieties semisimple?

Because any algebra on which the discriminator is a term operation is simple: given a non-trivial congruence relating a ≠ b, the discriminator term applied appropriately forces the congruence to relate everything. Since the subdirectly irreducibles of the variety are among such algebras, they are all simple.

Sources and further reading

S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Millennium Edition (a corrected re-typesetting of Springer GTM 78, 1981).
G. Grätzer, Universal Algebra, 2nd edition, Springer.
R. McKenzie, G. McNulty and W. Taylor, Algebras, Lattices, Varieties, Volume I.

Original KEVOS® explanatory article. Written from the topic map of the cited works; no text is reproduced from them.