A~pseudo-rundamental sequence not equivalent to any monotone sequence

G. S. Tseitin

Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part IV, Tome 20 (1971), pp. 263-271

Résumé

An algorithmic sequence $\varphi$ of rational numbers is called pseudo-fundamental if $$ \forall m\rceil\rceil\exists n\forall kl(k>n\ l>n\supset|\varphi_k-\varphi_l|2^{-m}). $$ Two sequences $\varphi$ and $\psi$ are called equivalent if $$ \forall m\rceil\rceil\exists n\forall l(l>n\supset|\varphi_l-\psi_l|2^{-m}). $$ A pseudo-fundamental sequence is constructed that is not equivalent to any monotonous sequence (it is the difference of two bounded increasing sequences). The construction is based on two recursively enumerable sets with incomparable degrees of unsolvability or on a weaker result proved independently.