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.

UDC: 510.5

Received: 28.04.2010

 English version: Algebra and Logic, 2012, 51:4, 281–284

Bibliographic databases:

• 
• 
• 
•