Undecidability of automorphism groups
The main result gives a uniform approach to proving that many automorphism groups have an undecidable first-order theory. Let \(\Omega=(\Omega, \leq)\) be a linearly ordered set. \(L(\Omega)\) denote the normal subgroup \[ \{g\in\text{Aut}(\Omega): (\exists\alpha\in\Omega)(\exists\beta> \alpha)(\beta g=\beta)\} \] of \(\text{Aut}(\Omega)\). \(R(\Omega)\) denotes \[ \{g\in\text{Aut}(\Omega): (\exists\alpha\in\Omega) (\forall\beta<\alpha)(\beta g=\beta)\}. \] \(B(\Omega)\) denotes \(L(\Omega)\cap R(\Omega)\). The main result immediately implies that the theories of Sym\((\mathbb Q)\), Aut\((\mathbb Q)\), \(B(\mathbb Q)\), \(L(\mathbb Q)\), \(R(\mathbb Q)\), Sym\((\mathbb R)\), Aut\((\mathbb R)\), B\((\mathbb R)\), L\((\mathbb R)\), R\((\mathbb R)\) are undecidable. (Here \(\mathbb Q\) \((\mathbb R)\) is the set of rational (real) numbers with their usual ordering). This result implies in particular the following: Sym\((X)\) for infinite \(X\) has an undecidable theory; the group of all strictly increasing differentiable functions from \(\mathbb R\) onto \(\mathbb R\), the group of all homeomorphisms of \(\mathbb Q\) (with the order topology), the automorphism group of the random graph, the automorphism group of the countable atomless Boolean algebra have undecidable theories.
- Insolubility of the elementary theory of a group of automorphisms in Lebesgue space
- Undecidable word problem in subshift automorphism groups
- scientific article; zbMATH DE number 3110205
- scientific article; zbMATH DE number 1302877
- Unitriangular groups and undecidability
- An automaton group with undecidable order and Engel problems
- scientific article; zbMATH DE number 804141
- Definability and automorphism groups
- Automorphism groups of decidable models
- Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness
- The partial ordering on the automorphism group of the countable generic partial order
- Undecidability of the elementary theory of groups of measure-preserving transformations
- Unitriangular groups and undecidability
- Groups of automatic automorphisms of some automatic structures
- On the decidability boundary of the infinite symmetric group
- UNDECIDABILITY AND THE DEVELOPABILITY OF PERMUTOIDS AND RIGID PSEUDOGROUPS
- Undecidable theories of valuated abelian groups
- The categoricity of the group of all computable automorphisms of the rational numbers
- Definable sets in automorphism groups of rational order
- Automorphism groups of models of first order theories
- The automorphism group of a resplendent model
- scientific article; zbMATH DE number 804141 (Why is no real title available?)
- Insolubility of the elementary theory of a group of automorphisms in Lebesgue space
This page was built for publication: Undecidability of automorphism groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q699745)
