Undecidability of automorphism groups (Q699745): Difference between revisions

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.