1

Given:

$$H:((A \cup B) \to \{ 0,1\} ) \to ((A \to \{ 0,1\} ) \times (B \to \{ 0,1\} ))$$

$$H = \lambda f \in (A \cup B) \to \{ 0,1\} .\left\langle {\lambda a \in A.f(a),\lambda b \in B.f(b)} \right\rangle$$

Based on @Brian M. Scott answer we know that $H$ is injective, but not surjective, and therefore, $H$ isn't invertible.

How does it tell us that $A\cap B = \emptyset$?

Community
  • 1
AnnieOK
  • 2,920

2 Answers2

2

See the comment on the original question :

if $H$ is invertible and the arguments of $H^{-1}$ are $f_A$ and $f_B$, then for $f$ to exists we need $f_A$ and $f_B$ to agree at $A \cap B$, that is $\forall x \in A \cap B$, $f_A(x) = f_B(x)$.

But the definition of Brian Scott couple $<f,g>$ gives you , for $c \in A \cap B$ that :

$f(c) = 1$ and $g(c) = 0$.

Mauro ALLEGRANZA
  • 94,169
  • Why is it a problem that $f(c)=1$ and $g(c)=0$? they are two different functions. – AnnieOK Mar 06 '14 at 13:46
  • 1
    @AnnieOK - what does it mean that a function $f$ is invertible ? That must exists a function $f^{-1}$ such that, for all $x$, $f^{-1}(f(x))=x$, i.e. $f^{-1}$ must bring you back to the starting point. In the case proposed by Brian, the purported inverse function $H^{-1}$ must associate to every couple of function $<f_A,f_B>$ a unique function from $A \cup B$ to ... But with $f$ as $f_A$ and $g$ as $f_B$ this do not work, because the function $A \cup B$ to ... is not a function, because it must give for input $c \in A \cap B$ two different values : $1$ and $0$. – Mauro ALLEGRANZA Mar 06 '14 at 13:56
1

Assume for a contradiction that $k \in A \cap B$ and that $H$ is surjective. Then $H(K) = \langle \{k\}_A,\emptyset_B\rangle$ for some $K : A \cup B \rightarrow 2.$ Fix any such $K$.

Case 1. Assume $k \in K$. Then $k \in [H(K)]_0$ and $k \in [H(K)]_1$, thus $H(K) \neq \langle \{k\}_A,\emptyset_B\rangle,$ a contradiction.

Case 2. Assume $k \notin K$. Then $k \notin [H(K)]_0$ and $k \notin [H(K)]_1$, thus $H(K) \neq \langle \{k\}_A,\emptyset_B\rangle,$ a contradiction.

In conclusion: if $H$ is surjective, then $A \cap B$ must be empty.

goblin GONE
  • 67,744