Detecting Properties of Algorithmically Presented Algebraic and Relational Structures

A Markov property, P, for a class of groups, C, is any property such that there is a positive witness, G+ ∈ C, that exhibits the property, and there is a negative witness, G− ∈ C, such that any group in C which contains a copy of G− fails to exhibit property P. We show that detecting a Markov property is Π02-hard in the class of recursively presented groups, which are those groups that have a presentation with computable set of generators and recursively enumerable set of relators. Furthermore, detecting a Markov property is Σ01-hard in the class of computable groups, those with a computable domain and a computable atomic diagram. These results are an extension of the classic result by Adian and Rabin in the class of finitely presented groups.We apply these results to determine the exact computability-theoretic complexity of detecting Markov properties of groups, including being abelian and torsion-free. We then find the exact complexity of detecting properties at higher levels of the arithmetical hierarchy, notably the properties of being torsion, nilpotent, and cyclic. Finally, we redefine the notion of a Markov property for classes of computable relational structures and follow a similar analysis and application of results as in the class of computable groups.

Author

• Bilanovic, Iva Iris

Language

• en

Keyword

• Computable Model Theory
• Groups
• Markov Properties
• Algebra

Date created

• 2020

Type of Work

• Dissertation

License

• All rights reserved

Rights statement

• In Copyright

GW Unit

• Mathematics

Degree

• Ph.D.

Advisor

• Harizanov, Valentina

Committee Member(s)

• Vora, Poorvi
• Chubb, Jennifer
• Przytycki, Jozef
• Wan, Xiang
• Shumakovitch, Alexander
• Alekseyev, Max

Persistent URL

•  https://scholarspace.library.gwu.edu/etd/5x21tg08m