The finite validity problem asks whether a sentence holds in every finite structure. Its complement is computably enumerable by searching for a finite countermodel, but Trakhtenbrot theorem says that finite validity itself is not computably enumerable.

Ancestors (8)

  1. Trakhtenbrot theorem
  2. Finite satisfiability problem for first-order logic
  3. First-order logic
  4. Mathematical logic
  5. Foundations of mathematics
  6. Area of mathematics
  7. Mathematics
  8. Home

Incoming links (1)

View article source

Discussion (0)

New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version