Many-one reducibility: why $A = \{1\}$ is not a counterexample to $\forall A : A \leq_m A \cup \{0\}$?

Question

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$:

1. If $0 \in A$, $id$ is good enough

2. 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. $(1,0) \in f$, therefore $f(A) = \{0\} \neq A \cup \{0\} = \{0,1\}$
2. $(1,1) \in f$, therefore $f(A) = \{1\} \neq A \cup \{0\} = \{0,1\}$
3. $(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$?

Answer 1

The property that, for all $x$, $x\in A$ iff $f(x)\in B$ means that $f(A)\subseteq B$ and $f(\overline{A})\subseteq \overline{B}$. Your proof attempt uses the condition $f(A)=B$, which is neither necessary nor sufficient.