Undecidability in Some Structures Related to Computation Theory
We show that many of the so called discrete weak semilattices considered earlier in a series of author's publications have hereditary undecidable first-order theories. Since such structures appear naturally in some parts of computation theory, we obtain several new undecidability results. This applies e. g. to the structures of complete numberings, of m-degrees of index sets and of the Wadge degrees of k-partitions in the Baire space and omega-algebraic domains. Whenever possible, we try to determine also the exact degrees of undecidability of the theories under discussion.
undecidability theory discrete weak semilattice semilattice partition reducibility