|
A $\Delta^0_2$-poset with no positive presentation
J. Wallbaum
Abstract:
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.
Received: 28.04.2010
Citation:
J. Wallbaum, “A $\Delta^0_2$-poset with no positive presentation”, Algebra Logika, 51:4 (2012), 423–428; Algebra and Logic, 51:4 (2012), 281–284
Linking options:
https://www.mathnet.ru/eng/al544 https://www.mathnet.ru/eng/al/v51/i4/p423
|
| Statistics & downloads: |
| Abstract page: | 267 | | Full-text PDF : | 89 | | References: | 62 | | First page: | 6 |
|