Boolean Constructions and Discriminator Varieties

Functionally Complete Algebras

Functional completeness is primality with constants allowed. The relaxation looks small and changes the theory substantially, because polynomial operations respect congruences but not homomorphisms.

Engineering · Mathematics5 min readKV-MATH-0243

Learning objectives

Define functional completeness in terms of polynomial operations.
Distinguish the polynomial clone from the term clone.
State the characterisation of functionally complete algebras.
Explain why functional completeness does not determine the generated variety.
Identify examples among rings and groups.
Relate functional completeness to the centre.

01Polynomial operations again

A polynomial operation of A is one built from the basic operations, variables and elements of A used as constants. The polynomial clone contains the term clone and is generally larger.

Term versus polynomial clone
	Built from	Preserved by	Determines
Term clone	operations, variables	homomorphisms, subalgebras, congruences	the identities of A, hence V(A)
Polynomial clone	the above plus constants from A	congruences only	the congruence structure of A

A is functionally complete ⟺ every finitary operation on A is a polynomial operation

Compare primality, which demands every operation be a TERM operation. Constants are the only difference, and they are a large one.

Because constants are permitted, functional completeness makes no demand that subalgebras be absent — the constants are available regardless. What it does demand is that no congruence obstruct any operation.

02The characterisation

Functional completeness has a clean characterisation in terms of the discriminator, parallel to quasiprimality but at the polynomial level.

Key resultThe criterion

A finite algebra with at least two elements is functionally complete if and only if the ternary discriminator is a polynomial operation of A. Equivalently, A is functionally complete iff the algebra obtained by adjoining all elements of A as nullary operations is quasiprimal.

Adjoin the constants
Form A⁺, the algebra A with every element added as a nullary operation. Term operations of A⁺ are exactly polynomial operations of A.
A⁺ has no proper subalgebras
Every element is a constant, so the only subuniverse containing anything is everything.
A⁺ is rigid
Automorphisms must fix every constant, hence every element.
So quasiprimal and primal coincide for A⁺
With no proper subalgebras and no non-trivial automorphisms, the inner isomorphisms are trivial and Pixley's criterion collapses to primality.

This is why the source treats functional completeness alongside quasiprimality: the two are the same phenomenon viewed with and without constants in the type.

03Functional completeness implies simplicity

ProcedureWhy a functionally complete algebra is simple

in: functionally complete A → out: A is simple

input: functionally complete algebra A, |A| ≥ 2
suppose θ is a congruence with ⟨a, b⟩ ∈ θ and a ≠ b
the discriminator t is a polynomial operation, so θ is compatible with it
compute t(a, b, c) = a (since a ≠ b) and t(a, a, c) = c
⟨a, b⟩ ∈ θ gives ⟨t(a,b,c), t(a,a,c)⟩ ∈ θ, i.e. ⟨a, c⟩ ∈ θ
c was arbitrary, so θ relates a to everything, so θ = ∇
therefore Con A = {Δ, ∇} and A is simple

Correctness: congruences are compatible with polynomial operations, which is exactly the property that distinguishes them from arbitrary equivalence relations. Caveat: the converse fails — simple algebras need not be functionally complete.

Simplicity is necessary and not sufficient. The gap is measured by the centre: a simple algebra fails to be functionally complete precisely when it retains some Abelian structure, which is the connection developed below.

04What functional completeness does not determine

Primality

Determines the variety

V(A) is categorically equivalent to Boolean algebras. The generated variety is completely known.

Functional completeness

Says nothing about V(A)

Because constants are not in the type, the identities of A are unconstrained by the condition. Two functionally complete algebras can generate wildly different varieties.

CautionFunctional completeness is a property of A, not of V(A)

It is tempting to expect a structure theorem for the variety generated by a functionally complete algebra, parallel to Foster's theorem. There is none, because the property involves constants that are invisible to the identities. This is the clearest illustration of why the term/polynomial distinction matters.

05Examples

Functionally complete or not
Algebra	Functionally complete?	Reason
Finite field	Yes	Every function on a finite field is a polynomial function.
Finite simple non-abelian group	Yes	A classical result; the centre is trivial.
Finite abelian group	No	Polynomial operations are affine; most functions are not.
Ring of matrices over a finite field	Yes	Simple with trivial centre.
Finite Boolean algebra with > 2 elements	No	Not simple.
Two-element Boolean algebra	Yes	Also primal.
Finite lattice	Generally no	Term and polynomial operations are monotone.

The finite field case is the classical one: every function from a finite field to itself is given by a polynomial, by Lagrange interpolation. This is exactly functional completeness and predates the general theory by a century.

06The centre as the obstruction

The failure of a simple algebra to be functionally complete is measured by its centre.

Abelian algebras are far from complete
If Z(A) = ∇ the algebra is polynomially equivalent to a module, and module polynomial operations are affine. Almost no function is affine, so completeness fails badly.
Trivial centre is the good case
A finite simple algebra with Z(A) = Δ in a congruence-modular variety is functionally complete. Simplicity plus a trivial centre suffices.
Abelian groups versus non-abelian simple groups
The abelian case has full centre and fails; the non-abelian simple case has trivial centre and succeeds. The dichotomy is exactly the centre.
Connection to the commutator programme
This is one of the results that motivated extending the commutator beyond groups, since it shows the centre controls a purely functional property.

The source uses this connection to link Chapter IV's functional questions with the centre defined in Chapter II §13, which is why the two sit in the same book despite appearing unrelated.

Frequently asked

Is every simple algebra functionally complete?

No. A finite abelian group of prime order is simple, and its polynomial operations are the affine maps, which are a tiny fraction of all operations. Simplicity is necessary; trivial centre is what closes the gap in the congruence-modular case.

Does functional completeness imply quasiprimality?

Not directly, because quasiprimality requires the discriminator as a term operation and functional completeness only as a polynomial operation. An algebra can be functionally complete without being quasiprimal. Adding the constants to the type converts one into the other.

Why does Lagrange interpolation give functional completeness?

Because over a finite field any function can be written as a polynomial by interpolating at every point — there are only finitely many, and the Vandermonde system is solvable. The polynomial obtained uses field elements as coefficients, which is exactly what polynomial operations permit and term operations do not.

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.