[This is a duplicate of my question from Mathematics Stack Exchange:


I am posting it here since it didn't get an answer there.]

Consider two sets of natural numbers, $A$ and $B$. Suppose that they differ finitely, i.e., their symmetric difference $(A-B)\cup (B-A)$ is a finite set. Is it true that $A$ and $B$ are many-one equivalent?

According to Odifreddi (Exercise III.2.2. f) in his "Classical recursion theory Vol. 1") and Rogers (Exercise 7-4 in his "Theory of recursive functions and effective computability", under additional assumption that $A$ and $B$ are infinite) the sets $A$ and $B$ are many-one equivalent.

However, taking $A=\mathbb{N}-\{0\}$ and $B=\mathbb{N}$, $A$ and $B$ clearly differ finitely, but are not many-one equivalent.

Am I not seeing something important, or both Odifreddi and Rogers gave false statements as exercises?

(It seems that if $A$ and $B$ are nonempty and not equal to the whole set of natural numbers then indeed they are many-one equivalent if they differ finitely. However, the question still stands since I don't see why both Odifreddi and Rogers would give false statements, so I presume that I am missing something here.)

  • 3
    $\begingroup$ You are right. $ $ $\endgroup$ Nov 22, 2023 at 8:24
  • $\begingroup$ What is the definition of many-one equivalent? $\endgroup$
    – domotorp
    Nov 23, 2023 at 21:05
  • $\begingroup$ @domotorp I think it's: $A$ many-to-one reducible to $B$ iff there is a many-to-one reduction from $A$ to $B$, i.e., a computable function $f$ such that $∀ x, x ∈ A ⟺ f(x) ∈ B$; and $A$ many-to-one equivalent to $B$ iff $A$ many-to-one reducible to $B$ and $B$ many-to-one reducible to $A$. $\endgroup$ Nov 24, 2023 at 9:33
  • $\begingroup$ And where is the problem? That $f$ needs to be $\mathbb N\to \mathbb N$? $\endgroup$
    – domotorp
    Nov 24, 2023 at 15:19


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.