# Cardinal arithmetic for not disjoint sets

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

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

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|$$
• In fact the disjoint case says $|X\cup Y|=|X|+|Y|$ and this is just the definition of $+$. Jan 10, 2017 at 1:44