¿Por qué $\#(X\cup Y)=\#(X)+\#(Y)-\#(X\cup Y)$ ?

Question

Me encontré con la siguiente afirmación en un artículo wiki :

Dejemos que $X$ y $Y$ sean conjuntos finitos. Entonces, si $\# X$ denota la cardinalidad de $X$ , $$\#(X\cup Y)=\#(X)+\#(Y)-\#(X\cap Y),$$ para que si $X$ y $Y$ son disjuntos, entonces $$\#(X\cup Y)= \#(X)+\#(Y).$$

Al buscar en varias preguntas de este sitio, apareció varias veces, pero sólo una vez se probó (por ejemplo, sólo se dijo aquí , aquí y aquí ; se demostró que aquí pero de manera similar a $(\star)$ . Mi objetivo es construir una biyección $j:X\cup Y\to \Bbb N_{m+n-k}$ (véase más adelante, y no para demostrar la afirmación de esta manera). Geométricamente, si consideráramos un diagrama de conjuntos como el siguiente: La afirmación tiene mucho sentido, teniendo en cuenta que $$\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)$$ pero he inferido geométricamente estas igualdades; no las he demostrado rigurosamente. Además, suponiendo que $f:X\to\Bbb N_n$ y $g:Y\to\Bbb N_m$ son biyectivas, por lo que $\#(X)=n$ y $\#(Y)=m$ , si $X$ y $Y$ son disjuntos, entonces el mapa $h:X\cup Y\to\Bbb N_{n+m}$ que definimos como $$h(a):=\begin{cases}f(a) &\text{if} \ a\in X \\ g(a)+n &\text{if} \ a\in\{x\}\end{cases},$$ es una biyección. En efecto, $h\vert_X=f$ se hipotetizó como biyectiva. En cuanto a $h\vert_Y=g(a)+n$ a priori tenemos que $$\forall y\in\Bbb N_m\exists !x\in Y[y=g(x)],$$ y por lo tanto $$\forall y\in\Bbb N_{m+n}\exists ! x\in Y[y=f(x)].$$ Mi problema es el caso que $X\cap Y\neq\emptyset$ - cómo puedo construir una biyección $j:X\cup Y\to\Bbb N_{m+n-k}$ , donde $k=\#(X\cap Y)$ ?

Answer 1

Sólo hay que demostrar la aditividad; que la cardinalidad de la unión de dos conjuntos finitos disjuntos es la suma de la cardinalidad de cada conjunto.

Sean conjuntos finitos $A,B$ sean disjuntos.   Mostrar $\#(A\cup B)=\#(A)+\#(B)$ .

Una vez que haya aceptado que se deduce que si conjunto finito $X\cup Y$ puede dividirse en una unión contable finita de subconjuntos disjuntos, entonces puede sumar sus cardinalidades.

Desde $\{X,(Y\smallsetminus X)\}$ es una partición de $X\cup Y$ y $\{(Y\smallsetminus X),(X\cap Y)\}$ particiones $Y$ (¿lo hacen?) entonces hemos terminado:

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

Answer 2

Si realmente quieres una biyección puedes construirla de esta manera.

Comience con una biyección de $X$ a $N_m$ . Ahora ya has mapeado el $k$ elementos de $X \cap Y$ Así que tienes que lidiar con el otro $n-k$ de esos. Elija una biyección para $N_{n-k}$ . A continuación, añada $m$ a todos los valores del rango y se tiene una biyección a $N_{m+n-k}$ .

Ahora tienes una respuesta. Deberías olvidarlo. Sólo sirve para conjuntos finitos aunque el hecho subyacente es mucho más general. No toda demostración de un teorema sobre la cardinalidad debe depender de una biyección explícita. Una vez que tengas herramientas probadas de esa manera, úsalas.

Answer 3

En el momento en que se suma el cardinal de los elementos en $X$ con el cardinal de los elementos en $Y$ estarías contando dos veces los elementos comunes por eso tienes que restar una vez los elementos que has contado dos veces.