9.1: Definición y Propiedades Básicas

De manera informal, la cardinalidad de un conjunto es el número de elementos que contiene. (Esto fue mencionado en Notación\(3.2.14\).)

Ejercicio\(9.1.1\).

¿Cuál es la cardinalidad de cada uno de estos conjuntos? (No necesitas mostrar tu trabajo ni justificar tus respuestas.)

1. \(\#\{1,2,3,4\}=\)
2. \(\#\{\mathrm{a}, \mathrm{e}, \mathrm{i}, \mathrm{o}, \mathrm{u}\}=\)
3. \(\#\{\mathrm{a}, \mathrm{l}, \mathrm{b}, \mathrm{e}, \mathrm{r}, \mathrm{t}, \mathrm{a}\}=\)
4. \(\text { 4) } \# \varnothing=\)
5. \(\#\{\varnothing\}=\)
6. \(\#\{k \in\{1,2, \ldots, 10\} \mid k \neq 7\}=\)

Una comprensión informal de la cardinalidad no es suficiente en los cursos avanzados de matemáticas, por lo que necesitamos estudiar esta idea más a fondo.

Ejemplo\(9.1.2\).

La cardinalidad de\(\{a, b, c\}\) es 3. Los niños aprenden a verificar esto contando:\[1(\text { for } \mathrm{a}), \quad 2(\text { for } \mathrm{b}), \quad 3(\text { for } \mathrm{c}) .\]

Se les enseña a asignar exactamente un número a cada elemento del conjunto (y a no omitir ningún número a medida que cuentan). Los matemáticos expresan esta idea de una manera más sofisticada: si definimos una función\(f:\{\mathrm{a}, \mathrm{b}, \mathrm{c}\} \rightarrow\{1,2,3\}\)\[f(\mathrm{a})=1, f(\mathrm{~b})=2, f(\mathrm{c})=3,\]

entonces\(f\) es una biyección.

En general, si un conjunto\(A\) tiene\(n\) elementos, entonces contar los elementos uno por uno define una biyección de\(A\) a\(\{1,2,3, \ldots, n\}\). Esta observación lleva a la siguiente definición oficial.

Definición\(9.1.3\).

1. Dejar\(A\) ser un conjunto y\(n\) ser un número natural. Decimos que la cardinalidad de\(A\) es\(n\) (y escribir\(\# A = n\)) si hay una biyección de\(A\) a\(\{1,2,3, \ldots, n\}\).
2. Un conjunto\(A\) es finito si hay algunos\(n \in \mathbb{N}\), tal que\(\# A = n\).
3. Un conjunto\(A\) es infinito si no es finito.

Observaciones\(9.1.4\).

1. No todos los conjuntos son finitos. Por ejemplo,\(\mathbb{N}\) es infinito (ver Ejercicio\(9.2.8(5)\)).
2. Veremos en Teorema\(9.1.20\) que cada subconjunto de un conjunto finito es finito.

Dado que la definición de\(\# A\) se basa en bijecciones, toda prueba sobre la cardinalidad se basará en hechos sobre bijecciones.

Ejemplo\(9.1.5\).

Espectáculo\(\#\{1,2,3, \ldots, n\}=n\), para cada\(n \in \mathbb{N}\).

Scratchwork. La definición de cardinalidad nos dice que si\(A\) es algún conjunto, y necesitamos mostrar\(\# A = n\), entonces necesitamos encontrar una bijección de\(A\) a\(\{1,2,3, \ldots, n\}\). En este problema, tenemos\(A=\{1,2,3, \ldots, n\}\). Por lo tanto, necesitamos encontrar una bijección de\(\{1,2,3, \ldots, n\}\) a\(\{1,2,3, \ldots, n\}\). Por lo tanto, necesitamos encontrar una bijección de un conjunto a sí mismo. El ejercicio nos\(6.6.9\) dice que el mapa de identidad es tal función.

Solución

PRUEBA.

Desde Ejercicio\(6.6.9\), sabemos que el mapa de identidad\(I_{\{1,2, \ldots, n\}}\) es una biyección de\(\{1,2, \ldots, n\}\) a\(\{1,2, \ldots, n\}\), entonces\(\#\{1,2, \ldots, n\}=n\).

COMPROBANTE ALTERNO.

Definir\(f:\{1,2,3, \ldots, n\} \rightarrow\{1,2,3, \ldots, n\}\) por\(f(k) = k\).

Afirmamos que\(f\) es una bijección. En otras palabras, afirmamos que\(f\) es uno a uno y hacia.

(uno-a-uno) Dado\(i_{1}, i_{2} \in\{1,2,3, \ldots, n\}\), tal que\(f(i_{1}) = f(i_{2})\), tenemos\(i_{1} = i_{2}\). Así\(f\) es uno a uno.

(onto) Dado\(j \in\{1,2,3, \ldots, n\}\), vamos\(i = j\). Entonces\(f(i) = i = j\). Así\(f\) es sobre.

Dado que\(f\) es tanto uno a uno como a uno, es una bijección. Esto completa el comprobante de la demanda.

Por lo tanto, hay una bijección (es decir,\(f\)) de\(\{1,2,3, \ldots, n\}\) a\(\{1,2,3, \ldots, n\}\). De ahí,\(\#\{1,2,3, \ldots, n\}=n\).

OBSERVACIÓN\(9.1.6\).

Dado que el conjunto vacío no tiene elementos, su cardinalidad debería ser 0. Si bien puede no ser obvio, Definición\(9.1.3\) sí está de acuerdo con esta observación. Para verificar esto, es importante darse cuenta de que, para cualquier\(n \in \mathbb{N}\), la notación\(\{1,2, \ldots, n\}\) es sólo otro nombre para el conjunto\(\{i \in \mathbb{N} \mid 1 \leq i \leq n\}\). En particular, si\(n = 0\), entonces\[\{1,2, \ldots, n\}=\{i \in \mathbb{N} \mid 1 \leq i \leq n\}=\{i \in \mathbb{N} \mid 1 \leq i \leq 0\}=\varnothing .\]

Por lo tanto, dejar\(n = 0\) entrar Ejemplo nos\(9.1.5\) dice eso\(\# \varnothing=0\), como se esperaba.

La definición de\(\# A\) especifica que hay una bijección de\(A\) a\(\{1,2,3, \ldots, n\}\). El siguiente ejercicio muestra que no hay daño si eliges que la biyección vaya por otro lado.

Ejercicio\(9.1.7\).

\(A\)Déjese ser un conjunto. Para\(n \in \mathbb{N}\), show\(\# A = n\) iff hay una bijección de\(\{1,2,3, \ldots, n\}\) a\(A\). [Pista: Usar ejercicio\(6.7.13(1)\).]

Las bijecciones se pueden utilizar para demostrar que dos conjuntos tienen la misma cardinalidad, sin saber cuántos elementos tienen.

Ejemplo\(9.1.8\).

En la sociedad Casado de Ejemplo\(6.6.2\) (donde cada hombre está casado con una mujer, y viceversa), está claro que debe haber exactamente el mismo número de hombres y mujeres. (Si hubiera más mujeres que hombres, entonces o alguna mujer estaría soltera, o más de una mujer tendría que estar casada con el mismo hombre. De igual manera, si hubiera más hombres que mujeres.) Esto es cierto, aunque no tenemos idea de cuántas mujeres u hombres hay en la sociedad. Todo lo que sabemos es que por muchas mujeres que haya es exactamente lo mismo que el número de hombres.

Esta observación se formaliza en la siguiente proposición.

Proposición\(9.1.9\).

Supongamos\(A\) y\(B\) son conjuntos finitos. Entonces\(\# A = \# B\) si y sólo si hay una bijección de\(A\) a\(B\).

Prueba

\((\Rightarrow)\)\(n\)Sea la cardinalidad de\(A\). Por definición, esto significa\[\text { there is a bijection } f: A \rightarrow\{1,2, \ldots, n\} \text {. }\]

Por supuesto,\(n\) es también la cardinalidad de\(B\), por lo\[\text { there is also a bijection } g: B \rightarrow\{1,2, \ldots, n\} \text {. }\]

El inverso de una bijección es una biyección (ver Ejercicio\(6.7.13(1)\)), y la composición de las bijecciones es una bijección (ver Ejercicio\(6.8.12(1)\)), así\(g^{-1} \circ f\) es una bijección de\(A\) a\(B\).

\((\Leftarrow)\)Dejamos esto como ejercicio.

Ejercicio\(9.1.10\).

Demostrar Proposición\(9.1.9(\Leftarrow)\). [Pista: Usar ejercicio\(6.8.12(1)\).]

Ejercicio\(9.1.11\).

1. Demuéstralo si\(\# A_{1} = \# A_{2}\), entonces\(\# (A_{1} \times B) = \# (A_{2} \times B)\). [Pista: Si\(f : A_{1} \rightarrow A_{2}\) es una biyección, defina\(g : A_{1} \times B \rightarrow A_{2} \times B\) por\(g\left(a_{1}, b\right)=\left(f\left(a_{1}\right), b\right)\).]
2. Mostrar que si\(\{a_{0}\}\) hay algún conjunto con un solo elemento, entonces\(\#\left(\left\{a_{0}\right\} \times B\right)=\# B\). [Pista: Definir\(f: B \rightarrow\left\{a_{0}\right\} \times B\) por\(f(b)=\left(a_{0}, b\right)\).]
3. Supongamos que\(f : A \rightarrow B\) es uno a uno, y\(X \subset A\). Espectáculo\(\# f(X) = \# X\).

Ejemplo\(9.1.12\).

En la primaria, aprendemos que si Alice tiene\(m\) manzanas y Bob tiene\(n\) manzanas, entonces la suma\(m+n\) es el número total de manzanas que tienen las dos. No obstante, este sencillo ejemplo supone que Alice y Bob no están compartiendo ninguna de las manzanas; el conjunto de manzanas de Alice debe ser disgregado del conjunto de manzanas de Bob.

El siguiente resultado generaliza este ejemplo.

Teorema\(9.1.13\).

Si\(A\) y\(B\) son conjuntos finitos disjuntos, entonces\ [\ # (A\ copa B) =\ # A +\ # B.

Prueba

Dejar\(m = \# A\) y\(n = \# B\). Entonces existen bijecciones\[f:\{1,2, \ldots, m\} \rightarrow A \quad \text { and } \quad g:\{1,2, \ldots, n\} \rightarrow B .\]

Define una función\ (h:\ {1,2,\ ldots, m+n\}\ fila derecha (A\ copa B)) por\ [h (k) =\ left\ {\ begin {array} {cl}
f (k) &\ text {if} k\ leq m\\
g (k-m) &\ text {if} k>m
\ end {array}\ right.\]

(Observe que si\(k \in\{1,2, \ldots, m+n\}\), y\(k > m\), entonces\(m + 1 \leq k \leq m + n\), así\(1 \leq k − m \leq n\); por lo tanto,\(k − m\) está en el dominio de\(g\), entonces la expresión tiene\(g(k − m)\) sentido.)

Para completar la prueba, basta con mostrar que\(h\) es una biyección; así, solo necesitamos mostrar que\(h\) es uno-a-uno y sobre.

(onto) Dado\(y \in A \cup B\), tenemos cualquiera\(y \in A \text { or } y \in B\), y consideramos estas dos posibilidades como casos separados.

1. Supongamos\(y \in A\). Ya que\(f\) está en, hay algunos\(k \in\{1,2, \ldots, m\}\) con\(f(k) = y\). Entonces, porque\(k \leq m\), tenemos\[h(k)=f(k)=y .\]
2. Supongamos\(y \in B\). Ya que\(g\) está en, hay algunos\(k \in\{1,2, \ldots, n\}\) con\(g(k) = y\). Entonces\(k+m \in\{1,2, \ldots, m+n\}\) y\(k + m > m\), entonces\[h(k+m)=g((k+m)-m)=\eta(k)=y .\]

Dado que\(y\) es un elemento arbitrario de\(A \cup B\), concluimos que\(h\) es sobre.

(uno-a-uno) Dejamos esto como un ejercicio.

Ejercicio\(9.1.14\).

Mostrar que la función\(h\) definida en la prueba de Proposición\(9.1.13\) es uno a uno.

Ejercicio\(9.1.15\).

Supongamos que\(B\) es un conjunto finito.

1. Para todos\(b \in B\), demuéstralo\(\#(B \backslash\{b\})=\# B-1\).
2. \(A \subset B\)Demuéstralo si, entonces\(\# A \leq \# B. [Hint: \(\# B=\# A+\#(B \backslash A) \geq \# A\).]
3. Mostrar que si\(A_{1}\) y\(A_{2}\) son subconjuntos disjuntos de\(B\), entonces\(\# A_{1}+\# A_{2} \leq \# B\).
4. (más difícil) Asumir\(B \neq \varnothing\). Demostrar que si\(S \subset \mathcal{P}(B)\), y no hay dos elementos de\(S\) son disjuntos, entonces\(\# S \leq \frac{1}{2} \# \mathcal{P}(B)\).
   [Pista: Puede asumir (sin pruebas) que\(\mathcal{P}(B)\) es finito. Si\(X \in S\), entonces\(\bar{X} \notin S\).]
5. Mostrar\(\# B = 0\) si y solo si\(B=\varnothing\).

La siguiente generalización de Proposición\(9.1.13\) se aplica a la unión de cualquier número de conjuntos, no sólo dos.

Ejercicio\(9.1.16\).

Si\(A_{1}, A_{2}, \ldots, A_{n}\) son conjuntos finitos disjuntos por pares, entonces\[\#\left(A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right)=\# A_{1}+\# A_{2}+\cdots+\# A_{n} .\]

[Pista: Induce\(n\), usando Proposición\(9.1.13\) y Ejercicio\(4.5.7\).]

Se señaló en Observación\(6.1.7\) que si\(A\) y\(B\) son conjuntos finitos, entonces\(\#(A \times B)=\# A \cdot \# B\). Ahora podemos probar esto, después de usar Ejercicio\(9.1.16\) para resolver el siguiente ejercicio:

Ejercicio\(9.1.17\).

Supongamos que\(A_{1}, A_{2}, \ldots, A_{m}\) son conjuntos finitos desarticulados por pares. Demostrar que si\(A=A_{1} \cup \cdots \cup A_{m}\), entonces\[\#(A \times B)=\#\left(A_{1} \times B\right)+\#\left(A_{2} \times B\right)+\cdots+\#\left(A_{m} \times B\right) .\]

[Pista: Los conjuntos\(A_{i} \times B\) son par-disjuntos, y su unión es\(A \times B\).]

Teorema\(9.1.18\).

Para cualquier conjunto finito\(A\) y\(B\), tenemos\[\#(A \times B)=\# A \cdot \# B.\]

Prueba

Vamos\(m = \# A\). Entonces no hay daño en asumir\(A=\{1,2, \ldots, m\}\) (ver Ejercicio\(9.1.11(1)\)). Por lo tanto\[A=\{1\} \cup\{2\} \cup \cdots \cup\{m\},\]

y los conjuntos\(\{1\},\{2\}, \cdots,\{m\}\) son par-disjuntos, así que\ [\ begin {aligned}
\ # (\ Lambda\ times B) &=\ # (\ {1\}\ times B)\ text { }\ # (\ {2\}\ veces B) +\ cdots\ texto { }\ # (\ {m\}\ veces B)\\
&=\ # B+\ # B+\ cdots+\ # B\ quad (m\ text {summands})\\
&=m\ cdot\ # B\
&=\ # A\ cdot\ # B.
\ end {alineado}\]

(Primera Línea: Ejercicio\(9.1.17\) Segunda Línea: Ejercicio\(9.1.11(2)\))

Ejercicio\(9.1.19\).

Supongamos\(A\) y\(B\) son conjuntos finitos, y\(m, n \in \mathbb{N}\). Demostrar:

1. Si\(m \leq n\), entonces existe una función uno a uno\(f:\{1,2, \ldots, m\} \rightarrow\{1,2, \ldots, n\}\).
2. Si\(\# A \leq \# B\), entonces existe una función uno a uno\(f: A \rightarrow B\). [Pista: Utilice el ejercicio anterior.]
3. Si\(m \geq n > 0\), entonces existe una función onto\(f:\{1,2, \ldots, m\} \rightarrow\{1,2, \ldots, n\}\).
4. Si\(A\) y no\(B\) están vacíos, y\(\# A \geq \# B\), entonces existe una función onto\(f : A \rightarrow B\). [Pista: Utilice el ejercicio anterior.]

Las conversas de los ejercicios en\((9.1.19)\) son verdaderas, e importantes. Serán discutidos en la Sección\(9.2\).

Terminamos la sección con un dato básico que puede parecer obvio (y fue mencionado en Observación\(9.1.4(2)\)), pero que sería difícil o imposible de probar sin usar inducción.

Teorema\(9.1.20\).

Cada subconjunto de cualquier conjunto finito es finito.

Prueba

Definir\(P(n)\) para ser la aserción\[\text { If } A \text { is any set with } \# A=n \text {, then every subset of } A \text { is finite. }\]

1. Estuche base. Asumir\(n = 0\), y dejar\(B\) ser cualquier subconjunto de\(A\). Ahora\(\# A = n = 0\), entonces\(A=\varnothing\). Como el único subconjunto del conjunto vacío es el conjunto vacío, tenemos\(B = \varnothing\). De ahí\(\# B = 0\) que así\(B\) sea finito.
2. Paso de inducción. Asumir\(n \geq 1\), y eso\(P(n − 1)\) es cierto, y dejar que\(B\) sea cualquier subconjunto de\(A\). Podemos suponer que\(B\) es un subconjunto apropiado de\(A\). (De lo contrario, tenemos\(B = A\), así\(\# B = \# A = n\), lo que significa que\(B\) es finito.) Así, existe\(a \in A\), tal que\(a \notin B\). Vamos\(A^{\prime}=A \backslash\{a\}\). Entonces\(\# A^{\prime} = n − 1\), entonces la hipótesis de inducción nos dice que cada subconjunto de\(A^{\prime}\) es finito. Ya que\(B \subset A^{\prime}\), concluimos que\(B\) es finito.