A note on distance increasing reducibility
A new type of reducibility between sets of natural numbers (the distance increasing reducibility) is introduced in the paper. The author tries to analyze properties of distance increasing reducibility and its relationship to many-one and one-one reducibility. Let N be the set of natural numbers. A function \(f: N\to N\) is called distance increasing function (dif) iff f is recursive and, for every \(n\in N\), \(f(n)>n\). Let A, B be subsets of N. If \(f: N\to N\), then \(A\leq_{di}B\) via f iff f is dif and \(\forall n\in N:\) \(n\in A\) iff f(n)\(\in B\). A is distance reducible to B \((A\leq_{di}B)\) iff either \(A=B\), or there is a dif f such that \(A\leq_{di}B\) via f. For \(\emptyset \neq X\subseteq N\), min X denotes the smallest number in X. Obviously, if \(\emptyset \neq A\) and \(A\leq_{di}B\) via f then min A\(<\min B\). Hence, if \(\emptyset \neq A\) then \(A\leq_{di}A\) via f does not hold for any dif f. Therefore, Lemma 1 of reviewed paper: ``If A is a recursive set and both A and \(N\setminus A\) are infinite, then there is a dif f such that \(A\leq_{di}A\) via f does not hold. The only theorem of the paper: ``There exists a nonrecursive enumerable set A such that for any dif f, \(A\leq_{di}A\) via f does not hold, too. The complicated proof of this theorem is based on Lemma 1.
This page was built for publication: A note on distance increasing reducibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1102276)
