Using a result of Gurevich and Lewis on the word problem for finite semigroups, we give short proofs that the following theories are hereditarily undecidable: (1) finite graphs of vertex-degree at most 3; (2) finite nonvoid sets with two distinguished permutations; (3) finite-dimensional vector spaces over a finite field with two distinguished endomorphisms.
Publié le : 1994-12-14
Classification:
Undecidable theory,
interpretable,
finite graphs,
word problem,
03D35,
03C13
@article{1183744623,
author = {Willard, Ross},
title = {Hereditary Undecidability of Some Theories of Finite Structures},
journal = {J. Symbolic Logic},
volume = {59},
number = {1},
year = {1994},
pages = { 1254-1262},
language = {en},
url = {http://dml.mathdoc.fr/item/1183744623}
}
Willard, Ross. Hereditary Undecidability of Some Theories of Finite Structures. J. Symbolic Logic, Tome 59 (1994) no. 1, pp. 1254-1262. http://gdmltest.u-ga.fr/item/1183744623/