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

  • $\begingroup$ I might have found the answer: it is not necessary/implied that $B = f(A)$: if $b \in B$ is not in the range of $f$, it is irrelevant to the $\Leftarrow$ condition. $\endgroup$ – Tobia Tesan Aug 19 '16 at 15:11
  • 1
    $\begingroup$ Yes, you don't have to cover all of $B$. You can for example send all the elements of $A$ to the same element of $B$, so cases 1 and 2 are fine. $\endgroup$ – Ariel Aug 19 '16 at 15:12

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.

  • $\begingroup$ Thank you. Obvious in hindsight, I don't know where I got that from. $\endgroup$ – Tobia Tesan Aug 19 '16 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.