0
$\begingroup$

$A=\{1,2,3,4\}$

$B=\{5,6,7,8,9\}$

$K$ is a relation from $A$ to $B$ ($K\subseteq AXB)$

  1. in how many $K$'s - $1 \notin domain(K)$ ?

  2. in how many $K$'s - $\{1,2,3\}\subseteq domain(K)$ (use the Inclusion-exclusion principle).

for example, one option is $K =\{(2,5),(2,6),(3,5),(4,9)\}$

$domain(K)=\{2,3,4\}$


  1. I'm pretty sure it's all the subsets of the set

    $\{(2,5),(2,6),(2,7),(2,8),(2,9),(3,5),(3,6),(3,7),(3,8),(3,9),(4,5),(4,6),(4,7),(4,8),(4,9)\} = 2^{15}=32,768 $

    which is weird because all the subsets of $AXB$ is $2^{20}=1,048,576$ and only $32,768$ of them don't include (1,x) elements?

  2. I need help determining what sets I use for the Inclusion-disclusion principle, is it:

    $A_1=$ the set of $\{1,2\} \subseteq domain(K) $

    $A_2=$ the set of $\{1,3\} \subseteq domain(K) $

    $A_3=$ the set of $\{1,4\} \subseteq domain(K) $

    $A_4=$ the set of $\{2,3\} \subseteq domain(K) $

    $A_5=$ the set of $\{2,4\} \subseteq domain(K) $

    $A_6=$ the set of $\{3,4\} \subseteq domain(K) $

$\endgroup$
  • $\begingroup$ I think I got it wrong for 2, should be $A_1 = $ the set of 1 is not in domain K. $A_2 = $ the set of 2 is not in domain K. and $A_3 = $ the set of 3 is not in domain K. right? $\endgroup$ – Seth Keno May 25 '14 at 1:32
1
$\begingroup$
  1. Looks correct. It's the possible relations from $\{2,3,4\}$ to $\{5,6,7,8,9\}$, of which there are $2^{3 \times 5}$.

  2. I think we're meant to use the idea of part 1. here.

    • Include: There are $2^{4 \times 5}$ relations.
    • Exclude: There are $2^{3 \times 5}$ relations that don't contain $1$ in the domain. There are $2^{3 \times 5}$ relations that don't contain $2$ in the domain. There are $2^{3 \times 5}$ relations that don't contain $3$ in the domain.
    • Include: There are $2^{2 \times 5}$ relations that don't contain $1$ and $2$ in the domain. There are $2^{2 \times 5}$ relations that don't contain $1$ and $3$ in the domain. There are $2^{2 \times 5}$ relations that don't contain $2$ and $3$ in the domain.
    • Exclude: There are $2^{1 \times 5}$ relations that don't contain $1$, $2$ and $3$ in the domain.
$\endgroup$
  • $\begingroup$ I think you are right Rebecca, are you sure it's not (total number of K's) - ($S_1 - S_2+S_3$)? or is it the same thing as your answer?, it's just what I've been told in this thread math.stackexchange.com/questions/805059/…, and I want to understand it ;) $\endgroup$ – Seth Keno May 25 '14 at 2:01
  • $\begingroup$ ok I checked it, it's the same thing ;) $\endgroup$ – Seth Keno May 25 '14 at 2:05

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.