Loading...
Please wait, while we are loading the content...
Similar Documents
LINEAR ORDERS REALIZED BY C.E. EQUIVALENCE RELATIONS
| Content Provider | Scilit |
|---|---|
| Author | Fokina, Ekaterina Khoussainov, Bakhadyr Semukhin, Pavel Turetsky, Daniel |
| Copyright Year | 2016 |
| Description | LetEbe a computably enumerable (c.e.) equivalence relation on the setωof natural numbers. We say that the quotient set $\omega /E$ (or equivalently, the relationE)realizesa linearly ordered set ${\cal L}$ if there exists a c.e. relation ⊴ respectingEsuch that the induced structure ( $\omega /E$ ; ⊴) is isomorphic to ${\cal L}$ . Thus, one can consider the class of all linearly ordered sets that are realized by $\omega /E$ ; formally, ${\cal K}\left( E \right) = \left\{ {{\cal L}\,|\,{\rm{the}}\,{\rm{order}}\, - \,{\rm{type}}\,{\cal L}\,{\rm{is}}\,{\rm{realized}}\,{\rm{by}}\,E} \right\}$ . In this paper we study the relationship between computability-theoretic properties ofEand algebraic properties of linearly ordered sets realized byE. One can also define the following pre-order $ \le _{lo} $ on the class of all c.e. equivalence relations: $E_1 \le _{lo} E_2 $ if every linear order realized $byE_{1}$is also realized $byE_{2}$. Following the tradition of computability theory, thelo-degrees are the classes of equivalence relations induced by the pre-order $ \le _{lo} $ . We study the partially ordered set oflo-degrees. For instance, we construct various chains and anti-chains and show the existence of a maximal element among thelo-degrees. |
| Related Links | http://pdfs.semanticscholar.org/1508/bbab823fcce33b22dcc5d2f1c615646e263a.pdf https://core.ac.uk/download/pdf/80775956.pdf https://www.cambridge.org/core/services/aop-cambridge-core/content/view/340BA6924EC38C5BE0965C0D5B4BE8C3/S0022481215000110a.pdf/div-class-title-linear-orders-realized-by-c-e-equivalence-relations-div.pdf |
| Ending Page | 482 |
| Page Count | 20 |
| Starting Page | 463 |
| ISSN | 00224812 |
| e-ISSN | 19435886 |
| DOI | 10.1017/jsl.2015.11 |
| Journal | The Journal of Symbolic Logic |
| Issue Number | 2 |
| Volume Number | 81 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2016-06-01 |
| Access Restriction | Open |
| Subject Keyword | The Journal of Symbolic Logic Equivalence Relations |
| Content Type | Text |
| Resource Type | Article |
| Subject | Philosophy Logic |
