No Access

Orders on magmas and computability theory

Trang Ha

Department of Mathematics, George Washington University, Washington, DC, USA

E-mail Address: trangtha@gwmail.gwu.edu

Corresponding author.

Search for more papers by this author

and

Valentina Harizanov

Department of Mathematics, George Washington University, Washington, DC, USA

E-mail Address: harizanv@email.gwu.edu

Search for more papers by this author

https://doi.org/10.1142/S0218216518410018Cited by:2 (Source: Crossref)

This article is part of the issue:

Special Issue — AMS Special Session on Inverse Problems; Guest Editors: Hanna E. Makaruk and Robert M.Owczarek

Abstract

We investigate algebraic and computability-theoretic properties of orderable magmas. A magma is an algebraic structure with a single binary operation. A right order on a magma is a linear ordering of its domain, which is right-invariant with respect to the magma operation. We use tools of computability theory to investigate Turing complexity of orders on computable orderable magmas. A magma is computable if it is finite, or if its domain can be identified with the set of natural numbers and the magma operation is computable. Interesting orderable magmas that are not even associative come from knot theory.

Keywords:

AMSC: 03D45, 03C57, 54D30

References

1. C. J. Ash and J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy (Elsevier, Amsterdam, 2000). Google Scholar
2. R. N. Buttsworth, A family of groups with a countable infinity of full orders, Bull. Austral. Math. Soc. 4 (1971) 97–104. Crossref, Google Scholar
3. J. Carson, V. Harizanov, J. Knight, K. Lange, C. Maher, C. McCoy, A. Morozov, S. Quinn and J. Wallbaum, Describing free groups, Trans. Amer. Math. Soc. 364 (2012) 5715–5728. Crossref, Web of Science, Google Scholar
4. J. Chubb, Ordered structures and computability, PhD dissertation, George Washington University (2009). Google Scholar
5. J. Chubb, M. Dabkowski and V. Harizanov, Groups with orderings of arbitrary algorithmic complexity, in Sets and Computations, Lecture Note Series, IMS, NUS, eds. R. Dilip, S. D. Friedman and Y. Yang (World Scientific, Singapore, 2017), pp. 221–251. Link, Google Scholar
6. M. A. Dabkowska, Turing degree spectra of groups and their spaces of orders, PhD dissertation, George Washington University (2006). Google Scholar
7. M. A. Dabkowska, M. K. Dabkowski, V. S. Harizanov, J. H. Przytycki and M. A. Veve, Compactness of the space of left orders, J. Knot Theory Ramifications 16 (2007) 257–266. Link, Web of Science, Google Scholar
8. M. A. Dabkowska, M. K. Dabkowski, V. S. Harizanov and A. Togha, Spaces of orders and their Turing degree spectra, Annals Pure Appl. Logic 161 (2010) 1134–1143. Crossref, Web of Science, Google Scholar
9. V. P. Dobritsa, Some constructivizations of abelian groups, Siber. Math. J. 24 (1983) 167–173 (English translation). Crossref, Web of Science, Google Scholar
10. R. G. Downey and S. A. Kurtz, Recursion theory and ordered groups, Ann. Pure Appl. Logic 32 (1986) 137–151. Crossref, Web of Science, Google Scholar
11. E. Fokina, V. Harizanov and A. Melnikov, Computable model theory, in Turing’s Legacy: Developments from Turing Ideas in Logic, ed. R. Downey (Cambridge University Press/ASL, 2014), pp. 124–194. Crossref, Google Scholar
12. A. M. W. Glass, Partially Ordered Groups (World Scientific, Singapore, 1999). Link, Google Scholar
13. V. Harizanov, Pure computable model theory, in Handbook of Recursive Mathematics, Vol. 1, eds. Yu. L. Ershov, S. S. Goncharov, A. Nerode and J. B. Remmel (North-Holland, Amsterdam, 1998), pp. 3–114. Google Scholar
14. M. Harrison-Trainor, Left-orderable computable groups, to appear in J. Symbol. Logic. Google Scholar
15. C. G. Jockusch and R. I. Soare, $Π_{1}^{0}$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972) 33–56. Web of Science, Google Scholar
16. C. G. Jockusch and R. I. Soare, Degrees of members of $Π_{1}^{0}$ classes, Pacific J. Math. 40 (1972) 605–616. Crossref, Web of Science, Google Scholar
17. D. Joyce, A classifying invariant of knots: The knot quandle, J. Pure Appl. Algebra 23 (1982) 37–65. Crossref, Web of Science, Google Scholar
18. A. I. Kokorin and V. M. Kopytov, Fully Ordered Groups (Halsted Press, New York, 1974). Google Scholar
19. V. M. Kopytov and N. Ya. Medvedev, Right-Ordered Groups, Siberian School of Algebra and Logic (Consultants Bureau, New York, 1996). Google Scholar
20. P. A. Linnell, The space of left orders of a group is either finite or uncountable, Bull. London Math. Soc. 43 (2011) 200–202. Crossref, Web of Science, Google Scholar
21. S. V. Matveev, Distributive groupoids in knot theory, Math. USSR-Sb 47 (1982) 73–83. Crossref, Google Scholar
22. S. H. McCleary, Free lattice-ordered groups represented as $o$ - $2$ transitive l-permutation groups, Trans. Amer. Math. Soc. 290 (1985) 69–79. Web of Science, Google Scholar
23. C. McCoy and J. Wallbaum, Describing free groups, part II: $Π_{4}^{0}$ hardness and no $Σ_{2}^{0}$ basis, Trans. Amer. Math. Soc. 364 (2012) 5729–5734. Crossref, Web of Science, Google Scholar
24. G. Metakides and A. Nerode, Effective content of field theory, Ann. Math. Logic 17 (1979) 289–320. Crossref, Google Scholar
25. R. B. Mura and A. Rhemtulla, Orderable Groups, Lecture Notes in Pure and Applied Mathematics (Marcel Dekker, New York, 1977). Google Scholar
26. A. Navas, On the dynamics of (left) orderable groups, Ann. Inst. Fourier 60 (2008) 1685–1740. Crossref, Web of Science, Google Scholar
27. D. Rolfsen and B. Wiest, Free group automorphisms, invariant orderings, and topological applications, Algebraic Geom. Topol. 1 (2001) 311–320. Crossref, Google Scholar
28. A. S. Sikora, Topology on the spaces of orderings of groups, Bull. London Math. Soc. 36 (2004) 519–526. Crossref, Web of Science, Google Scholar
29. R. I. Soare, Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets (Springer, Berlin, 1987). Google Scholar
30. R. I. Soare, Turing Computability, Theory and Applications (Springer, Berlin, 2016). Google Scholar
31. D. R. Solomon, Reverse mathematics and ordered groups, PhD dissertation, Cornell University (1998). Google Scholar
32. D. R. Solomon, $Π_{1}^{0}$ classes and orderable groups, Ann. Pure Appl. Logic 115 (2002) 279–302. Crossref, Web of Science, Google Scholar