A $\Delta^0_2$-poset with no positive presentation
Algebra i logika, Tome 51 (2012) no. 4, pp. 423-428
Cet article a éte moissonné depuis la source Math-Net.Ru
S. Yu. Podzorov in [Mat. Trudy, 9, No. 2, 109–132 (2006)] proved the validity of the following THEOREM. If $\langle L,\le_L\rangle$ is a local lattice and $v$ a numbering of $L$ such that the relation $v(x)\le_L v(y)$ is $\Delta^0_2$-computable, then there is a numbering $\mu$ of $L$ such that the relation $\mu(x)\le_L\mu(y)$ is computably enumerable. Podzorov also asked whether the hypothesis that $\langle L,\le_L\rangle$ is a local lattice is needed or the theorem is true of any partially ordered set (poset). We answer his question by constructing a poset for which the theorem fails.
Keywords:
partially ordered set, local lattice, computably enumerable set.
@article{AL_2012_51_4_a0,
author = {J. Wallbaum},
title = {A~$\Delta^0_2$-poset with no positive presentation},
journal = {Algebra i logika},
pages = {423--428},
year = {2012},
volume = {51},
number = {4},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/AL_2012_51_4_a0/}
}
J. Wallbaum. A $\Delta^0_2$-poset with no positive presentation. Algebra i logika, Tome 51 (2012) no. 4, pp. 423-428. http://geodesic.mathdoc.fr/item/AL_2012_51_4_a0/
[1] S. Yu. Podzorov, “Numerovannye distributivnye polureshetki”, Matem. trudy, 9:2 (2006), 109–132 | MR | Zbl
[2] D. R. Hirschfeldt, B. Khoussainov, R. A. Shore, A. M. Slinko, “Degree spectra and computable dimensions in algebraic structures”, Ann. Pure Appl. Logic, 115:1–3 (2002), 71–113 | DOI | MR | Zbl