Boolean Constructions and Discriminator Varieties
Quasiprimal Algebras and Pixley's Theorem
Quasiprimality relaxes primality to a single requirement: the discriminator must be a term operation. Pixley's theorem characterises exactly which finite algebras qualify.
- Define quasiprimality and relate it to the discriminator.
- State Pixley's theorem characterising quasiprimal algebras.
- Explain the role of inner isomorphisms.
- Compare quasiprimal with primal and identify what is relaxed.
- Determine the subalgebras and congruences of a quasiprimal algebra.
- Recognise how quasiprimal algebras generate discriminator varieties.
01Quasiprimality
A finite algebra A with at least two elements is quasiprimal when the ternary discriminator on A is a term operation of A.
If the discriminator is a term operation and θ is a congruence relating distinct a and b, then applying the discriminator gives t(a, b, c) = a related to t(a, a, c) = c for arbitrary c. So every element is θ-related to a, and θ is everything. A quasiprimal algebra is therefore simple.
Simplicity is forced, but the other two consequences of primality are not. A quasiprimal algebra may have proper subalgebras and may have non-trivial automorphisms — and Pixley's theorem says exactly how these must interact.
02Pixley's theorem
The characterisation is in terms of inner isomorphisms — isomorphisms between subalgebras of A.
A finite algebra A is quasiprimal if and only if every operation on A that preserves all inner isomorphisms of A is a term operation. Equivalently: the term operations of A are exactly the operations commuting with every isomorphism between subalgebras of A.
- input: finite algebra A
- compute Sub(A), the subuniverses of A
- compute Iso(A), the set of isomorphisms between members of Sub(A)
- (this includes automorphisms and identity maps on subalgebras)
- for a candidate operation g on A:
- g preserves an inner isomorphism φ : C → D when applying g
- inside C and then φ agrees with applying φ then g inside D
- A is quasiprimal iff every operation preserving ALL inner isomorphisms
- is already a term operation
- output: quasiprimality decision
The theorem is a clone-theoretic statement: it identifies the clone of term operations with the clone of operations preserving a specified relational structure. This operation–relation Galois connection is the standard framework for clone theory and reappears in the algebraic approach to constraint satisfaction.
03What primality adds
Primal is quasiprimal plus the vanishing of all inner structure.
| Feature | Primal | Quasiprimal |
|---|---|---|
| Discriminator is a term operation | Yes | Yes |
| Simple | Yes | Yes |
| Proper subalgebras | None | Permitted |
| Non-trivial automorphisms | None | Permitted |
| Inner isomorphisms | only identities | may be rich |
| Every operation a term operation | Yes | Only those preserving inner isomorphisms |
| Generated variety | equivalent to Boolean algebras | a discriminator variety |
So primality is the case where the only inner isomorphisms are the identity maps, which makes the preservation condition vacuous and every operation a term operation. Pixley's theorem contains Foster's as the degenerate case.
04Generated varieties
A quasiprimal algebra generates a discriminator variety, and Jónsson's lemma pins down its subdirectly irreducibles precisely.
- The discriminator is a term operationSo V(A) is a discriminator variety by definition, and inherits the whole structural package: arithmetical, semisimple, CEP, Boolean product representation.
- Jónsson's lemma appliesV(A) is congruence-distributive and A is finite, so the subdirectly irreducibles lie in HS({A}).
- Quotients are trivialA is simple, so H({A}) contributes only A and the trivial algebra. The subdirectly irreducibles are therefore among the subalgebras of A.
- ConclusionThe subdirectly irreducible members of V(A) are exactly the subalgebras of A on which the discriminator term still acts as the discriminator — a finite, computable list bounded by |A|.
Every member of V(A) is then a Boolean product of algebras from that finite list. The variety is completely described by a finite amount of data, which is as good as structure theory gets.
05Deciding quasiprimality in practice
The practical route is not Pixley's criterion but a direct search for a discriminator term.
- input: finite algebra A of finite type
- target: a ternary term t with t(a,b,c) = c when a = b, and = a when a ≠ b
- enumerate term operations of increasing depth:
- depth 0: projections
- depth k+1: apply each basic operation to depth-k term operations
- at each stage check whether any ternary term operation matches the target table
- the clone of a finite algebra is finite, so the search terminates
- output: a discriminator term, or a proof that none exists
Quoting |A|^(|A|³) as the search space makes the procedure sound feasible for small algebras and it is not — for |A| = 4 that is already 4^64. Use a purpose-built tool. The sourcing policy page routes to the current ones.
06Where quasiprimality sits
| Condition | Clone requirement | Consequence |
|---|---|---|
| Primal | clone = all operations | V(A) ≃ Boolean algebras |
| Quasiprimal | clone contains the discriminator | V(A) a discriminator variety |
| Functionally complete | polynomial clone = all operations | A is simple with no proper subalgebras up to constants |
| Demi-semi-primal and variants | weaker conditions | studied in the older literature |
| Arbitrary finite algebra | no condition | no general structure theory |
The older literature contains a proliferation of primality variants — semiprimal, demi-semi-primal, hemiprimal and others — most of which were absorbed once quasiprimality and the discriminator were identified as the right notions. The source treats quasiprimality as the central case and the earlier taxonomy as largely superseded.
Frequently asked
Can a quasiprimal algebra have non-trivial automorphisms?
Yes — that is precisely what distinguishes it from primality. The automorphisms are inner isomorphisms from A to itself, and Pixley's theorem says term operations must commute with them. A primal algebra is rigid; a quasiprimal one need not be.
Are all quasiprimal algebras finite?
The definition as usually stated is for finite algebras, and Pixley's theorem uses finiteness essentially. Infinite algebras with a discriminator term operation exist and generate discriminator varieties, but the characterisation via inner isomorphisms does not extend unchanged.
Is quasiprimality preserved by subalgebras?
A subalgebra of a quasiprimal algebra inherits the discriminator term, so the term still acts as the discriminator on it, making the subalgebra quasiprimal too. This is why the subdirectly irreducibles of the generated variety are exactly the subalgebras.
- 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.