2
$\begingroup$

$\newcommand{\card}{\operatorname{card}}$Let $X$, $Y$ be finite sets. If $X$ and $Y$ are disjoint, i've proven that $\card(X\cup Y) + \card(X\cap Y) = \card(X)+\card(Y).$

I'm actually trying to prove this result for $X$ and $Y$ not disjoint. Here's my attempt:

Notation: $I_n = \{x\in N: 1\leq x \leq n \}$.

Suppose that $X$ and $Y$ has $k$ elements in common. Ie, $\card(X\cap Y)=k$. Since $X$ and $Y$ are finite, there exists $f:I_n \rightarrow X$ and $g:I_m \rightarrow Y$ bijections. Hence, $\card(X)=n$ and $\card(Y)=m$. Let $\varphi: I_{n+m-k} \rightarrow X\cup Y$ such that $\varphi(x)=f(x)$ if $1\leq x \leq m$ and $\varphi(x+m)=g(x)$ if $m<x\leq n$, $x\in Y-X$. This define $\varphi$ such that it is a bijection. Hence $\card(X\cup Y) + \card(X\cap Y) = (n+m-k) +k = n+m =\card(X)+\card(Y).$

Is it correct?

$\endgroup$
2
  • 1
    $\begingroup$ Looks good to me. $\endgroup$ Jan 10, 2017 at 1:17
  • $\begingroup$ To me as well ;) $\endgroup$
    – RGS
    Jan 10, 2017 at 1:20

1 Answer 1

1
$\begingroup$

Here is another way, by reducing to the disjoint case. $$|X\cup (Y-X)|+|X\cap(Y-X)|=|X|+|Y-X|$$ (disjoint case) is the same as $$|X\cup Y|=|X|+|Y-X|$$

And $$|(X\cap Y)\cup (Y-X)|+|(X\cap Y)\cap(Y-X)|=|X\cap Y|+|Y-X|$$ (disjoint case) is the same as $$|Y|=|X\cap Y|+|Y-X|$$
Putting the two together gives the result.

$\endgroup$
1
  • $\begingroup$ In fact the disjoint case says $|X\cup Y|=|X|+|Y|$ and this is just the definition of $+$. $\endgroup$ Jan 10, 2017 at 1:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .