Math 2.0

General algebraic systems Terms, identities and equational logic Problem

Tarski's finite basis problem

Builds on Finitely based algebraEquational basisIdentityComputable functionOates–Powell theoremBaker's finite basis theorem

Problem

A finite algebra AA of finite signature is given by the finite tables of its operations. It is finitely based if it has a finite equational basis. That is, some finite set of identities true in AA implies every identity true in AA. Tarski's finite basis problem asks for an algorithm, that is, a computable function, with the following task. Given a finite algebra of finite signature, it decides whether the algebra is finitely based.

Remarks

The problem was solved negatively by Ralph McKenzie in 1996: no such algorithm exists. Earlier work showed that the answer to "is every finite algebra finitely based?" is no. Lyndon showed that every two-element algebra of finite signature is finitely based, and he also gave a seven-element algebra that is not. Many classes of finite algebras are known to consist of finitely based algebras, among them finite groups, by the Oates–Powell theorem, and finite lattices. Baker's finite basis theorem covers all finite algebras of finite signature that generate a congruence-distributive variety. The decision problem restricted to finite semigroups is still open.

Reading path

To understand this page from the ground up, read these 10 pages in order. The foundations come first.

Show the path as a graph
Computable function, concept, no evidence levelComputable functionconceptCongruence-distributive variety, concept, no evidence levelCongruence-distributi…conceptEquational basis, concept, no evidence levelEquational basisconceptFinitely based algebra, concept, no evidence levelFinitely based algebraconceptGroup, concept, no evidence levelGroupconceptIdentity, concept, no evidence levelIdentityconceptVariety of algebras, concept, no evidence levelVariety of algebrasconceptBaker's finite basis theorem, statement, no evidence levelBaker's finite basis …statementOates–Powell theorem, statement, no evidence levelOates–Powell theoremstatementTarski's finite basis problem, problem, no evidence levelTarski's finite basis…problem
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Computable function concept
  2. Congruence-distributive variety concept
  3. Equational basis concept
  4. Finitely based algebra concept
  5. Group concept
  6. Identity concept
  7. Variety of algebras concept
  8. Baker's finite basis theorem statement
  9. Oates–Powell theorem statement
  10. Tarski's finite basis problem problem

Where this leads

1 page builds on this one.

Further reading

  1. Web https://doi.org/10.1142/S0218196796000040
  2. Web https://en.wikipedia.org/wiki/Variety_(universal_algebra)
About this page
TagAB22FWBQ0M
URIm2://AB22FWBQ0M
Kindproblem
WritingW0 stub
MSC08B05, 03B25, 03C05
StatusThis copy of the site has no build data. Run m2 status AB22FWBQ0M.
AboutFinitely based algebra
UsesFinitely based algebra, Equational basis, Identity, Computable function, Oates–Powell theorem, Baker's finite basis theorem

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Results about this

Used by