# Many-one equivalence of sets that differ finitely

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

https://math.stackexchange.com/questions/4792354/many-one-equivalence-of-sets-that-differ-finitely

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.)

• You are right.  Nov 22, 2023 at 8:24
• What is the definition of many-one equivalent? Nov 23, 2023 at 21:05
• @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$. Nov 24, 2023 at 9:33
• And where is the problem? That $f$ needs to be $\mathbb N\to \mathbb N$? Nov 24, 2023 at 15:19