Core Universal Algebra

The Irredundant Basis Theorem

Q: Does the theorem hold for infinitely generated algebras?

The clean interval statement is for the finitely generated case. In the infinite setting cardinal arithmetic swamps the combinatorics and the question changes character. The source states and proves the finitely generated version, which is where the content lies.

Q: Do vector spaces satisfy the theorem trivially?

Yes — IrB(V) is a single number, namely the dimension, and a one-element set is trivially an interval. The theorem is only informative where the exchange property fails, which is to say almost everywhere else.

Q: Is there an algorithm to compute IrB(A) for a finite algebra?

For a finite algebra one can in principle enumerate subsets and test generation, so the set is computable, but the search is exponential in |A|. The theorem helps in practice by reducing the problem to finding the extremes: once the minimum and maximum irredundant basis sizes are known, every value between them is realised and need not be searched for separately.

Minimal generating sets in a general algebra need not have equal size. The Irredundant Basis Theorem says the sizes they can take form an interval, with no gaps.

Engineering · Mathematics4 min readKV-MATH-0212

Learning objectives

Define an irredundant basis and give an algebra with bases of different sizes.
State the exchange property and identify where it fails.
State the Irredundant Basis Theorem precisely.
Explain why 'no gaps' is the strongest available conclusion.
Relate the theorem to the closure-operator setting in which it is proved.

01Irredundant bases

A subset X of an algebra A is an irredundant basis when Sg(X) = A and no proper subset of X generates A. Equivalently, X generates and every element of X is needed.

CautionIrredundant is weaker than independent

Irredundance says no element is superfluous. Independence, in the vector space sense, says no element lies in the closure of the others — which for closure operators is the same thing — but crucially neither implies that all irredundant bases have the same size. That further conclusion needs the exchange property, which general algebras lack.

The vector space case is anomalous, not typical. There, the exchange property forces every basis to have the same cardinality, and dimension is well defined. Remove the exchange property and dimension simply does not exist as an invariant.

02The exchange property and its failure

Exchange: a ∈ Sg(X ∪ {b}) and a ∉ Sg(X) ⟹ b ∈ Sg(X ∪ {a})

Holds for linear span, for algebraic closure in field theory, and for very little else in general algebra.

A closure operator with the exchange property is called a matroid or a pregeometry, and for those the cardinality of an irredundant basis is an invariant. Subuniverse generation in an arbitrary algebra is not a matroid, and irredundant bases of different sizes coexist routinely.

Take a semilattice or a groupoid
Small finite examples with two irredundant generating sets of different cardinality are easy to construct once the exchange property is abandoned.
Observe there is no dimension
The size of a minimal generating set is not an invariant of the algebra, so no notion of rank survives.
Ask what does survive
The set of achievable sizes. That set turns out to be constrained, and the constraint is the theorem.

03The theorem

Let IrB(A) denote the set of cardinalities of irredundant bases of A. The theorem asserts that for a finitely generated algebra this set contains no gaps.

Key resultThe Irredundant Basis Theorem

If A is a finitely generated algebra and IrB(A) is the set of sizes of its irredundant bases, then IrB(A) is a set of consecutive integers — an interval. If bases of size m and size n exist with m < n, then bases of every intermediate size exist too.

The result is stated and proved in the source at the level of closure operators rather than algebras, which is the right generality: nothing about the algebraic structure is used beyond the fact that generation is a finitary closure operator. That abstraction is characteristic of the subject's method.

04Why 'no gaps' is the right conclusion

Strongest false claim

All bases equal size

Refuted by explicit small examples. The exchange property fails, so nothing forces uniqueness of cardinality.

Strongest true claim

The sizes form an interval

Cannot be improved: for any prescribed interval one can construct an algebra realising exactly that set of basis sizes.

That the bound is attained is what makes the theorem sharp rather than merely true. It also illustrates a recurring pattern: when a classical invariant fails to generalise, the correct replacement is often a constraint on the set of possible values rather than a single value.

05Proof strategy

ProcedureFilling a gap between two irredundant basis sizes

in: two irredundant bases of different size → out: bases of all intermediate sizes

input: finitely generated A with irredundant bases X, Z, |X| = m < n = |Z|
goal: produce an irredundant basis of size k for each m < k < n
start from X and adjoin elements of Z one at a time
after each adjunction, prune to an irredundant subset that still generates
each step changes the size by at most one
so every intermediate cardinality is realised along the way
output: irredundant basis of size k

Correctness: the pruning step preserves generation, and adjunction increases size by exactly one, so the size sequence cannot jump. Caveat: finiteness of the generating set is essential — the argument uses that the process terminates.

Frequently asked

Does the theorem hold for infinitely generated algebras?

The clean interval statement is for the finitely generated case. In the infinite setting cardinal arithmetic swamps the combinatorics and the question changes character. The source states and proves the finitely generated version, which is where the content lies.

Do vector spaces satisfy the theorem trivially?

Yes — IrB(V) is a single number, namely the dimension, and a one-element set is trivially an interval. The theorem is only informative where the exchange property fails, which is to say almost everywhere else.

Is there an algorithm to compute IrB(A) for a finite algebra?

For a finite algebra one can in principle enumerate subsets and test generation, so the set is computable, but the search is exponential in |A|. The theorem helps in practice by reducing the problem to finding the extremes: once the minimum and maximum irredundant basis sizes are known, every value between them is realised and need not be searched for separately.

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.