3

Let B be many-one reducible to A i.e. $B \leq_m A$ if there is a computable function $f$ s.t. for all $x\in \mathbb{N}$:

$$ x \in B \iff f(x) \in A $$

If the function $f$ is one-one (injective) then B is said to be one-one reducible to A i.e. $B \leq_1 A$.

As far as most of the papers I have read, these two measures of reducibility coincide completely. However I keep reading mentions of the fact that one-one and many-one reducibility are actually two different metrics.

Can anyone point me to an example of c.e sets A and B s.t. $B \leq_m A$ but $ B \not \leq_1 A$? In particular with $B$ not being computable?

gowrath
  • 3,573
  • 13
  • 31

1 Answers1

5

Many-one and one-one reducibility are very different.

Here's one way to see this: for a function $g:\omega\rightarrow\omega$ and a sequence $S\in2^\omega$, let the $g$-spread of $S$ be the sequence $Spread_g(S)$ gotten by "stretching" the $n$th bit of $S$ by a factor of $g(n)$. So e.g. if $g: x\mapsto x$ and $S=(0,1,0,1,0,1,...)$, then $Spread_g(S)$ is $$(0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0,0,0,0,0,1,1,1,1,1,1,...).$$

Note that we always have $Spread_g(S)\le_m S$ whenever $g$ is computable - just map each number in the $n$th "$g$-block" to $n$. However, this is very noninjective. The point is in general that there is no way to fix this - if $g$ is computable and infinitely often greater than $1$, then we can find an $S$ such that $Spread_g(S)\not\le_1 S$.

The intuition behind this is the following. Take $g: x\mapsto 2$, and $S$ some complicated set. If $f$ is to be a $1$-reduction of $Spread_g(S)$ to $S$, what should $f(3)$ be? We know that $3\in Spread_g(S)\iff 2\in Spread_g(S)$, so $f$ needs to send $3$ to something in the $k$th $g$-block (that is, an element of $\{2k-1, 2k\}$) such that $S(k)=S(2)$ (remember, $3$ is in the second $g$-block - hence the $2$).

But the next such block could be very far away! In particular, let $S$ be any sequence whose principle function (= take $n$ to place in $S$ where we see $n$th $1$) is not computably dominated; then no computable $f$ can always "look far enough" to find an un-mapped to $g$-block, so either isn't even an $m$-reduction or isn't injective.

Basically, $1$-reductions are very sensitive to "padding out" the sets involved, whereas many-one reductions aren't.

Noah Schweber
  • 245,398
  • But $Spread_g(S)$ is also a computable set I think? I can think of a fair few examples of $B$ and $A$ that answer my question, but not ones where $B$ is not computable. – gowrath May 10 '17 at 19:44
  • @gowrath The point is, $S$ needn't be computable. – Wojowu May 10 '17 at 19:46
  • @gowrath Neither $S$ nor $Spread_g(S)$ is computable. First of all, note the definition of $S$: "let $S$ be any sequence whose principle function is not computably dominated" - such an $S$ is never computable. But they do exist, in fact computably in $0'$, and this is a nice exercise if you haven't seen it before. Second, note that $S$ and $Spread_g(S)$ have the same Turing (indeed many-one) degree, so if one is computable the other is too. Neither set is computable. – Noah Schweber May 10 '17 at 19:47
  • @NoahSchweber Yes you're right; I missed that line. Great answer! – gowrath May 10 '17 at 19:48
  • @NoahSchweber I suppose my lack of closure with this answer is that I was looking for two sets $A,B$ in $\mathbb{N}$ that could demonstrate the difference. Your answer is absolutely correct, but uses sequences. Are you aware of examples that could demonstrate this as sets alone instead of sequences? – gowrath May 10 '17 at 19:58
  • @NoahSchweber The entire issue I've had with solving this problem is being unable to use this cardinality type of padding argument because if $A$ and $B$ are subsets of $\mathbb{N}$ then they must be countable. I hope that makes sense? – gowrath May 10 '17 at 19:58
  • @gowrath A sequence of zeroes and ones is a subset of $\mathbb{N}$ - or rather, it's the characteristic function of such a set. Switching between the two is often useful for intuition. I just talked about sequences since then describing $Spread_g$ is simpler. BTW, this is a cardinality argument essentially, but not as direct as comparing the cardinalities of two specific sets - rather, the point is that $Spread_g(S)$ gives us a sequence of finite cardinalities, and assuming we choose $S$ appropriately this sequence is eventually greater than any computable sequence of finite cardinalities. – Noah Schweber May 10 '17 at 20:03
  • Explicitly, here's how to translate everything I've written above into the language of sets (although really you should be comfortable with the conflation binary sequences / subsets of $\mathbb{N}$). For a function $g:\mathbb{N}\rightarrow\mathbb{N}$, we say that $n$ is in the $k$th $g$-block if $\sum_{i<k}g(i)<n$ but $\sum_{i\le k}g(i)\ge n$. Note that for each $n$ there is exactly one $k$ such that $n$ is in the $k$th $g$-block; denote this $block_g(n)$. Now $Spread_g(S)={n: block_g(n)\in S}$. (cont'd) – Noah Schweber May 11 '17 at 18:46
  • We can now argue identically as above. But note how much work it took to define $Spread_g(S)$ as compared with the perfectly clear informal definition when we spoke of $S$ as a sequence. This is what the sequence/set conflation is good for: often, our language is better suited to one than the other. As a useful tool for the future, there are two sequences associated to any set: its characteristic function (= an infinite binary sequence), and its principle function which sends $n$ to the sets $n$th element (= a sequence of natural numbers which is possibly finite). – Noah Schweber May 11 '17 at 18:49