1
$\begingroup$

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

$\endgroup$
2
  • $\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$ Commented Aug 19, 2016 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
    Commented Aug 19, 2016 at 15:12

1 Answer 1

2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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