<p>[This is a duplicate of my question from Mathematics Stack Exchange:</p>
<p><a href="https://math.stackexchange.com/questions/4792354/many-one-equivalence-of-sets-that-differ-finitely">https://math.stackexchange.com/questions/4792354/many-one-equivalence-of-sets-that-differ-finitely</a></p>
<p>I am posting it here since it didn't get an answer there.]</p>
<p>Consider two sets of natural numbers, <span class="math-container">$A$</span> and <span class="math-container">$B$</span>. Suppose that they differ finitely, i.e., their symmetric difference <span class="math-container">$(A-B)\cup (B-A)$</span> is a finite set. Is it true that <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are many-one equivalent?</p>
<p>According to Odifreddi (Exercise III.2.2. f) in his &quot;Classical recursion theory Vol. 1&quot;) and Rogers (Exercise 7-4 in his &quot;Theory of recursive functions and effective computability&quot;, under additional assumption that <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are infinite) the sets <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are many-one equivalent.</p>
<p>However, taking <span class="math-container">$A=\mathbb{N}-\{0\}$</span> and <span class="math-container">$B=\mathbb{N}$</span>, <span class="math-container">$A$</span> and <span class="math-container">$B$</span> clearly differ finitely, but are not many-one equivalent.</p>
<p>Am I not seeing something important, or both Odifreddi and Rogers gave false statements as exercises?</p>
<p>(It seems that if <span class="math-container">$A$</span> and <span class="math-container">$B$</span> 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.)</p>

CC BY-SA 4.0
2023-11-22T08:24:17.630Z
You are right. $ $
Emil Jeřábek
CC BY-SA 4.0
2023-11-23T21:05:37.857Z
What is the definition of many-one equivalent?
domotorp
CC BY-SA 4.0
2023-11-24T09:33:18.900Z
@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$.
Jean Abou Samra
CC BY-SA 4.0
2023-11-24T15:19:32.950Z
And where is the problem? That $f$ needs to be $\mathbb N\to \mathbb N$?
domotorp
<computability>
Many-one equivalence of sets that differ finitely
ijon
# Many-one equivalence of sets that differ finitely

(Asked by: username_0 on 2023-11-21)

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

**Tags:** computability
> **Comments:**
> **username_1**: You are right. $ $  
> **username_2**: What is the definition of many-one equivalent?  
> **username_3**: @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$.  
> **username_2**: And where is the problem? That $f$ needs to be $\mathbb N\to \mathbb N$?  

---

## 0 answers

