I'm looking at a textbook exercise that asks to prove or give a counterexample that $\forall A : A \leq_m A \cup \{0\}$.
$A \leq_m B$ is defined as:
$\exists f$ total, computable s.t. $\forall x \in A : x \in A \Leftrightarrow f(x) \in B$,
It then says in the answer sheet something to the effect of:
The only counterexample is $A = \mathbb{N} \setminus \{ 0 \}$.
Otherwise there is always an appropriate $f$:
- If $0 \in A$, $id$ is good enough
If $0 \not\in A$, one such $f$ is
$f'(x) = \begin{cases} x_0 & x = 0\\ x & otherwise\end{cases} $ for some $x_0 \not\in A \cup \{0\}$.
However, before checking the answer sheet I was persuaded there were multiple such counterexamples.
In fact, I still don't understand what's wrong in my "proof" that $A = \{ 1\}$ is a counterexample.
It goes like this:
Let $A = \{1\}$. Then $A \cup \{0\} = \{0,1\}$. Suppose such an $f$ as required by the definition exists.
There are three cases, mutually exclusive by definition of function:
- $(1,0) \in f$, therefore $f(A) = \{0\} \neq A \cup \{0\} = \{0,1\}$
- $(1,1) \in f$, therefore $f(A) = \{1\} \neq A \cup \{0\} = \{0,1\}$
- $(1,c) \in f$ for some other $c$, therefore $f(A) = \{c\} \neq A \cup \{0\} = \{0,1\}$
Therefore $f$ such that $f(A) = A \cup \{0\}$ cannot exist for $A = \{ 1 \}$. QED.
In particular, I don't see how, for the given
$f'(x) = \begin{cases} x_0 & x = 0\\ x & otherwise\end{cases} $
it holds that $f'(\{1\}) = \{1,0\}$
It seems to me that $f'(\{1\}) = \{1\} \neq \{0,1\}$.
What am I misunderstanding about either basic set theory or the definition of $\leq_m$?