Why does $\#(X\cup Y)=\#(X)+\#(Y)-\#(X\cup Y)$?

Question

I came across the following claim in a wiki article:

Let $X$ and $Y$ be finite sets. Then, if $\# X$ denotes the cardinality of $X$, $$\#(X\cup Y)=\#(X)+\#(Y)-\#(X\cap Y),$$ so that if $X$ and $Y$ are disjoint, then $$\#(X\cup Y)= \#(X)+\#(Y).$$

Upon searching several questions on this site, it appeared multiple times, but only once proved (for example, it was merely stated here, here, and here; it was proved here, but in a similar manner as $(\star)$. My goal is to construct a bijection $j:X\cup Y\to \Bbb N_{m+n-k}$, see below, and not to prove the claim in this way). Geometrically, if we were to consider a set diagram like the following: The claim makes perfect sense, considering that $$\left. \begin{align} \#(X \cup Y) &= \#((X \Delta Y) + \#(X \cap Y)) \\ &=\#(X \Delta Y)+\#(X \cap Y) \\ &=\#(X)-\#(X \cap Y)+\#(Y)-\#(X \cap Y)+\#(X\cap Y) \\ &= \#(X)+\#(Y)-\#(X\cap Y) \end{align} \right\}(\star)$$ but I have geometrically inferred these equalites; I have not rigorously proven them. Moreover, assuming that $f:X\to\Bbb N_n$ and $g:Y\to\Bbb N_m$ are bijective, so that $\#(X)=n$ and $\#(Y)=m$, if $X$ and $Y$ are disjoint, then the map $h:X\cup Y\to\Bbb N_{n+m}$, which we define as $$h(a):=\begin{cases}f(a) &\text{if} \ a\in X \\ g(a)+n &\text{if} \ a\in\{x\}\end{cases},$$ is a bijection. Indeed, $h\vert_X=f$ was hypothesized as bijective. As for $h\vert_Y=g(a)+n$, a priori we have that $$\forall y\in\Bbb N_m\exists !x\in Y[y=g(x)],$$ and thus $$\forall y\in\Bbb N_{m+n}\exists ! x\in Y[y=f(x)].$$ My problem is the case that $X\cap Y\neq\emptyset$ — how can I construct a bijection $j:X\cup Y\to\Bbb N_{m+n-k}$, where $k=\#(X\cap Y)$?

Answer 1

If you really want a bijection you can construct it this way.

Start with a bijection from $X$ to $N_m$. Now you've mapped the $k$ elements of $X \cap Y$, so you need to deal with the other $n-k$ of those. Choose a bijection to $N_{n-k}$. Then add $m$ to all the values in the range and you have a bijection to $N_{m+n-k}$.

Now you have an answer. You should forget it. It's only good for finite sets although the the underlying fact is much more general. Not every proof of a theorem about cardinality should depend on an explicit bijection. Once you have tools proved that way, use them.

Answer 2

At the moment that you sum the cardinal of the elements in $X$ with the cardinal of the elements in $Y$ you would be counting twice the common elements that is why you got to subtract once the elements you counted twice.

Answer 3

You merely have to prove additivity; that the cardinality for a union of two disjoint finite sets is the sum of the cardinality for each set.

Let finite sets $A,B$ be disjoint.   Show $\#(A\cup B)=\#(A)+\#(B)$.

Once you have accepted that, it follows that if finite set $X\cup Y$ can be partitioned into a finite countable union of disjoint subsets, then you may sum their cardinalities.

Since $\{X,(Y\smallsetminus X)\}$ is a partition of $X\cup Y$, and $\{(Y\smallsetminus X),(X\cap Y)\}$ partitions $Y$, (do they?) then we are done:

$$\#(X\cup Y) ~{= \#(X\cup(Y\smallsetminus X)) \\= \#(X)+\#(Y\smallsetminus X)\\=\#(X)+\#(Y)-\#(X\cap Y)}$$