1

Question:

We'll define a function between two sets A and B:

$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}$.<\lambda a \in A . f(a),\lambda b \in B.f(b)>$

  1. If H is invertible, what is the cardinality of $A \cap B$?
  2. Present the inverse function of H.

What I did: I figured that from the fact that H is invertible I can figure $2^{|A \cup B|}=2^{|A|} \cdot 2^{|B|}= 2^{|A \times B|}$ I also know that$ |A \cap B| $= |A| +|B| -$|A \cup B |$ but from there I don't really have a clue how to proceed..

Thanks a bunch.

jreing
  • 3,297
  • $2^{|A|}\cdot 2^{|B|} = 2^{|A|+|B|}$. – dtldarek Mar 20 '13 at 06:57
  • A more intuitive approach is as follows: 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)$. – dtldarek Mar 20 '13 at 07:03

1 Answers1

3

HINT: Note that $H$ is always injective (one-to-one); the question is whether it’s surjective (onto). Suppose that $c\in A\cap B$. Define

$$f:A\to\{0,1\}:x\mapsto\begin{cases}1,&\text{if }x=c\\0,&\text{if }x\ne c\end{cases}$$

and

$$g:B\to\{0,1\}:x\mapsto 0\;;$$

is $\langle f,g\rangle$ in the range of $H$?

Brian M. Scott
  • 616,228
  • so from what I understand, because H is invertible (therefore surjective and injective) then |$A \cap B$| = 0 . That is because the function g you defined is not surjective (therefore not in the range of H) – jreing Mar 20 '13 at 12:05
  • @user1685224: It’s true that $g$ is not surjective, but that’s beside the point: the point is that $H$ is not surjective, so it’s not invertible. But yes, what I did can be done whenever $|A\cap B|>0$, so in order for $H$ to be surjective and hence invertible, we must have $|A\cap B|=0$. – Brian M. Scott Mar 20 '13 at 16:59
  • Okay, thanks! So is it a sufficient proof just to say that : $2 ^ {|A \cup B|}$ = $2 ^{|A|} \cdot 2^{|B|} = 2^{|A| + |B|}$

    so: $|A| + |B| = |A \cup B|$

    $|A \cup B| =|A| + |B| - |A \cap B|$ so

    $|A \cap B| =0$ or should I use functions as examples like here?

     – jreing Mar 21 '13 at 08:19
  • @user1685224: Your calculation works when $A$ and $B$ are finite sets, but the result that $H$ is invertible if and only if $A\cap B=\varnothing$ is true in general, not for finite sets. The calculation doesn’t work if at least one of $A$ and $B$ is infinite, so for the general result you do need to use a different argument, and the one that I suggested is probably the simplest. – Brian M. Scott Mar 21 '13 at 12:14
  • Okay. Thanks alot! – jreing Mar 21 '13 at 12:37
  • @user1685224: You’re welcome! – Brian M. Scott Mar 21 '13 at 12:37