On positive preorders

The main object of our research is computably enumerable (positive) preorders with respect to computable reducibility. We say that a preorder $P$ is computably reducible to a preorder $Q$ iff there is a computable function $f$ such that $xPy$ iff $f(x)Qf(y)$ for all $x,y\in\omega$. We investigate definable objects in the structure of positive preorders with respect to computable reducibility. We also investigate and classify the arithmetical complexity of some index sets of positive preorders and positive linear preorders. We refer to some fixed universal computable numbering $\{P_i\colon i\in\omega\}$ of all positive preorders, where “computable” means that the set $\{\langle i,x,y\rangle\colon xP_iy\}$ is c.e., and “universal” means that for every such computable numbering $\{R_i\colon i\in\omega\}$ of all positive preorders, there exists a computable function $f$ such that $R_i=P_{f(i)}$ for all $i\in\omega$. Unfortunately, the family of all positive linear preorders does not have a computable numbering, so we will refer to the universal computable numbering of some superfamily of all positive linear preorders.
Papers [1–4] established the complexities of the index sets of such classes of c.e. equivalence relations (ceers) as the following: universal ceers, dark ceers, light ceers, self-full ceers, precomplete ceers, weakly precomplete ceers, and $e$-complete ceers. In addition, they consider the $c$-degree of a given ceer $E$, its upper cone and lower cone (under computable reducibility). In the talk we will discuss complexity of index sets of analogous classes of positive preorders and linear preorders.

Список литературы

1. U. Andrews, S. Lempp, J. S. Miller, K. M. Ng, L. S. Mauro, A. Sorbi, “Universal computably enumerable equivalence relations”, The Journal of Symbolic Logic, 79:1 (2013), 60–88
2. U. Andrews, A. Sorbi, “The Complexity of index sets of classes of computably enumerable equivalence relations”, The Journal of Symbolic Logic, 81:4 (2016), 1375–1395
3. U. Andrews, A. Sorbi, “Joins and meets in the structure of ceers”, Computability, 8:3-4 (2019), 193–241
4. S. Badaev, A. Sorbi, “Weakly precomplete computably enumerable equivalence relations”, Mathematical Logic Quarterly, 62:1-2 (2016), 111–127