9.1: Conjuntos finitos

Vista previa de la actividad\(\PageIndex{1}\): Equivalent Sets, Part 1

1. Dejar\(A\) y\(B\) ser conjuntos y dejar\(f\) ser una función de\(A\) a\(B\). (\(f: A \to B\)). Complete cuidadosamente cada uno de los siguientes usando los cuantificadores apropiados: (Si es necesario, revise el material en la Sección 6.3.)
   1. La función\(f\) es una inyección siempre que...
   2. La función no\(f\) es una inyección siempre que...
   3. La función\(f\) es una sobrejección siempre que...
   4. La función no\(f\) es una sobrejección siempre que...
   5. La función\(f\) es una bijección siempre que...

Definiciones: conjuntos equivalentes y correspondencia uno a uno

Dejar\(A\) y\(B\) ser conjuntos.

• El conjunto\(A\) es equivalente al conjunto\(B\) siempre que exista una biyección del conjunto\(A\) al conjunto\(B\). En este caso, escribimos\(A \thickapprox B\).
• Cuando\(A \thickapprox B\), también decimos que el conjunto\(A\) está en correspondencia uno a uno con el conjunto\(B\) y que el conjunto\(A\) tiene la misma cardinalidad que el conjunto\(B\).

Nota: Cuando no\(A\) es equivalente a\(B\), escribimos\(A \not\thickapprox B\).

2. Para cada uno de los siguientes, utilice la definición de conjuntos equivalentes para determinar si el primer conjunto es equivalente al segundo conjunto.
   1. \(A = \{1, 2, 3\}\)y\(B = \{a, b, c\}\)
   2. \(C= \{1, 2\}\)y\(B = \{a, b, c\}\)
   3. \(X = \{1, 2, 3, ..., 10\}\)y\(Y = \{57, 58, 59, ..., 66\}\)
3. Dejar\(D^{+}\) ser el conjunto de todos los números naturales impares. Demostrar que la función\(f: \mathbb{N} \to D^{+}\) definida por\(f(x) = 2x - 1\), para todos\(x \in \mathbb{N}\), es una biyección y de ahí eso\(N \thickapprox D^{+}\).
4. \(\mathbb{R}^{+}\)Sea el conjunto de todos los números reales positivos. Demostrar que la función\(g: \mathbb{R} \to \mathbb{R}^{+}\) definida por\(g(x) = e^{x}\), para todos\(x \in \mathbb{R}\) es una biyección y por lo tanto, eso\(\mathbb{R} \thickapprox \mathbb{R}^{+}\).

Vista previa de la actividad\(\PageIndex{2}\): Equivalent Sets, Part 2

1. Teorema de Revisión 6.20 en la Sección 6.4, Teorema 6.26 en la Sección 6.5, y Ejercicio (9) en la Sección 6.5.
2. Demostrar cada parte del siguiente teorema.

Teorema 9.1.

Dejar\(A\),\(B\), y\(C\) ser conjuntos.

1. Para cada conjunto\(A\),\(A \thickapprox A\).
2. Para todos los conjuntos\(A\) y\(B\), si\(A \thickapprox B\), entonces\(B \thickapprox A\).
3. Para todos los conjuntos\(A\),\(B\) y\(C\), si\(A \thickapprox B\) y\(B \thickapprox C\), entonces\(A \thickapprox C\).

Conjuntos Equivalentes

En Preview Activity\(\PageIndex{1}\), introdujimos el concepto de conjuntos equivalentes. La motivación para esta definición fue contar con un método formal para determinar si dos conjuntos “tienen o no el mismo número de elementos”. Esta idea fue descrita en términos de una correspondencia uno a uno (una biyección) de un conjunto a otro conjunto. Esta idea puede parecer simple para conjuntos finitos, pero como veremos, esta idea tiene consecuencias sorprendentes cuando tratamos con conjuntos infinitos. (Pronto proporcionaremos definiciones precisas para conjuntos finitos e infinitos).

Nota Técnica

Las tres propiedades que probamos en el Teorema 9.1 en Actividad Previa\(\PageIndex{2}\) son muy similares a los conceptos de relaciones reflexivas, simétricas y transitivas. Sin embargo, no consideramos que la equivalencia de conjuntos sea una relación de equivalencia sobre un conjunto\(U\) ya que una relación de equivalencia requiere un conjunto subyacente (universal)\(U\). En este caso, nuestros elementos serían los conjuntos\(A\),\(B\)\(C\), y estos tendrían entonces que subconjuntos de algún conjunto universal W (elementos del conjunto de potencia de\(W\)). Para la equivalencia de conjuntos, no estamos requiriendo que los conjuntos\(A\)\(B\),, y\(C\) sean subconjuntos del mismo conjunto universal. Por lo que no utilizamos el término relación en lo que respecta a la equivalencia de conjuntos. No obstante, si\(A\) y\(B\) son conjuntos y\(A \thickapprox B\), entonces a menudo decimos eso\(A\) y\(B\) son conjuntos equivalentes.

Comprobación de progreso 9.2: Ejemplos de conjuntos equivalentes

Utilizaremos la definición de conjuntos equivalentes de en Vista previa de Actividad\(\PageIndex{1}\) en todas las partes de esta comprobación de progreso. Ya no es suficiente decir que dos conjuntos son equivalentes simplemente diciendo que los dos conjuntos tienen el mismo número de elementos.

1. Dejar\(A = \{1, 2, 3, ..., 99, 100\}\) y dejar\(B = \{351, 352, 353, ..., 449, 450\}\). Definir\(f: A \to B\) por\(f(x) = x + 350\), para cada uno\(x\) en\(A\). Demostrar que\(f\) es una bijección del conjunto\(A\) al conjunto\(B\) y por lo tanto,,\(A \thickapprox B\).
2. Dejar\(E\) ser el conjunto de todos los enteros pares y dejar\(D\) ser el conjunto de todos los enteros impares.
   Demostrar eso\(E \thickapprox D\) demostrando que\(F: E \to D\)\(F(x) = x + 1\), donde, para todos\(x \in E\), es una biyección.
3. Sea (0, 1) el intervalo abierto de números reales entre 0 y 1. De igual manera, si\(b \in \mathbb{R}\) con\(b > 0\), deja\(0, b\) ser el intervalo abierto de números reales entre 0 y\(b\).
   Demostrar que la función\(f: (0, 1) \to (0, b)\) por\(f(x) = bx\), para todos\(x \in (0, 1)\), es una biyección y por lo tanto\((0, 1) \thickapprox (0, b)\).

Contestar

Agrega textos aquí. No elimine primero este texto.

En la Parte (3) de la Comprobación de Progreso 9.2, observe que si\(b > 1\), entonces (0, 1) es un subconjunto apropiado de (0,\(b\)) y\((0, 1) \thickapprox (0, b)\). Además, en la Parte (3) de Vista previa de Actividad\(\PageIndex{1}\), probamos que el conjunto\(D\) de todos los números naturales impares es equivalente a\(\mathbb{N}\), y sabemos que\(D\) es un subconjunto propio de\(\mathbb{N}\).

Estos resultados pueden parecer un poco extraños, pero son consecuencias lógicas de la definición de conjuntos equivalentes. Aunque aún no hemos definido los términos, veremos que una cosa que distinguirá un conjunto infinito de un conjunto finito es que un conjunto infinito puede ser equivalente a uno de sus subconjuntos propios, mientras que un conjunto finito no puede ser equivalente a uno de sus subconjuntos propios.

Conjuntos finitos

En la Sección 5.1, definimos la cardinalidad de un conjunto finito\(A\), denotado por card (\(A\)), como el número de elementos en el conjunto\(A\). Ahora que conocemos las funciones y las bijecciones, podemos definir este concepto de manera más formal y más rigurosa. Primero, para cada uno\(k \in \mathbb{N}\),\(\mathbb{N}_k\) definimos como el conjunto de todos los números naturales entre 1 y\(k\), inclusive. Es decir,

\(\mathbb{N}_k = \{1, 2, ..., k\}\).

Utilizaremos el concepto de conjuntos equivalentes introducido en Preview Activity\(\PageIndex{1}\) para definir un conjunto finito.

Definición: conjuntos finitos e infinitos

• Un conjunto\(A\) es un conjunto finito siempre que\(A = \emptyset\) o exista un número natural\(k\) tal que\(A \thickapprox \mathbb{N}_k\).
• Un conjunto es un conjunto infinito siempre que no sea un conjunto finito.
• Si\(A \thickapprox \mathbb{N}_k\), decimos que el conjunto\(A\) tiene cardinalidad\(k\) (o número cardinal\(k\)), y escribimos card (\(A\))\(= k\).

Además, decimos que el conjunto vacío tiene cardinalidad 0 (o número cardinal 0), y escribimos\(\text{card}(\emptyset) = 0\).

Observe que por esta definición, el conjunto vacío es un conjunto finito. Además, para cada uno\(k \in \mathbb{N}\), la función de identidad on\(\mathbb{N}_k\) es una biyección y por lo tanto, por definición, el conjunto\(\mathbb{N}_k\) es un conjunto finito con cardinalidad\(k\).

Teorema 9.3

Cualquier conjunto equivalente a un conjunto finito no vacío\(A\) es un conjunto finito y tiene la misma cardinalidad que\(A\).

Prueba

Supongamos que\(A\) es un conjunto finito no vacío,\(B\) es un conjunto, y\(A \thickapprox B\). Ya que\(A\) es un conjunto finito, existe\(k \in \mathbb{N}\) tal que\(A \thickapprox \mathbb{N}_k\). También hemos asumido que\(A \thickapprox B\) y así por la parte (b) del Teorema 9.1 (en Actividad Previa\(\PageIndex{2}\)), podemos concluir que\(B \thickapprox A\). Ya que\(A \thickapprox \mathbb{N}_k\), podemos usar la parte (c) del Teorema 9.1 para concluir que\(B \thickapprox \mathbb{N}_k\). Así,\(B\) es finito y tiene la misma cardinalidad que\(A\).

Puede parecer que hemos hecho mucho trabajo para demostrar un resultado “obvio” en el Teorema 9.3. Lo mismo puede ser cierto de los resultados restantes en esta sección, que dan más resultados sobre conjuntos finitos. Uno de los objetivos es asegurar que el concepto de cardinalidad para un conjunto finito corresponda a nuestra noción intuitiva del número de elementos en el conjunto. Otro objetivo importante es sentar las bases para un tratamiento más riguroso y matemático de conjuntos infinitos que el que hemos encontrado antes. En el camino, veremos la distinción matemática entre conjuntos finitos e infinitos.

Los siguientes dos lemas serán utilizados para probar el teorema que establece que cada subconjunto de un conjunto finito es finito.

Lema 9.4

Si\(A\) es un conjunto finito y\(x \notin A\), entonces\(A \cup \{x\}\) es un conjunto finito y\(\text{card}(A \cup \{x\}) = \text{card}(A) + 1\).

Prueba

Vamos\(A\) es un conjunto finito y asumir que\(\text{card}(A) = k\), donde\(k = 0\) o\(k \in \mathbb{N}\). Asumir\(x \notin A\).

Si\(A = \emptyset\), entonces\(\text{card}(A) = 0\) y\(A \cup \{x\} = \{x\}\), que equivale a\(\mathbb{N}_1\). Así,\(A \cup \{x\}\) es un conjunto finito con cardinalidad 1, que equivale a carta (\(A\)) + 1.

Si\(A \ne \emptyset\), entonces\(A \thickapprox \mathbb{N}_k\), para algunos\(k \in \mathbb{N}\). Esto significa que\(\text{card}(A) = k\), y existe una biyección\(f: A \to \mathbb{N}_k\). Ahora usaremos esta bijección para definir una función\(g: A \cup \{x\} \to \mathbb{N}_{k + 1}\) y luego demostrar que la función\(g\) es una biyección. Definimos de\(g: A \cup \{x\} \to \mathbb{N}_{k + 1}\) la siguiente manera: Para cada uno\(t \in A \cup \{x\}\),

\(g(t) = \begin{cases} f(t) & \text{ if \(t \in A\)}\\ k + 1 &\ texto {si\(t = x\).} \ end {casos}\)

Para probar que\(g\) es una inyección, dejamos\(x_1, x_2 \in A \cup \{x\}\) y asumimos\(x_1 \ne x_2\).

• Si\(x_1, x_2 \in A\), entonces ya\(f\) es una bijección,\(f(x_1) \ne f(x_2)\), y esto implica que\(g(x_1) \ne g(x_2)\).
• Si\(x_1 = x\), entonces desde entonces\(x_2 \ne x_1\), concluimos eso\(x_2 \ne x\) y por lo tanto\(x_2 \in A\). Entonces\(g(x_1) = k + 1\), y desde\(f(x_2) \in \mathbb{N}_k\) y\(g(x_2) = f(x_2)\), podemos concluir eso\(g(x_1) \ne g(x_2)\).

Esto demuestra que la función\(g\) es una inyección. La prueba de que g es una sobreyección es Ejercicio (1). Dado que g es una biyección, concluimos que\(A \cup \{x\} \thickapprox \mathbb{N}_{k + 1}\), y

\(\text{card}(A \cup \{x\}) = k + 1\).

Desde entonces\(\text{card}(A) = k\), lo hemos demostrado\(\text{card}(A \cup \{x\}) = \text{card}(A) + 1\).

Lema 9.5

Para cada número natural\(m\), si\(A \subseteq \mathbb{N}_{m}\), entonces\(A\) es un conjunto finito y\(\text{card}(A) \le m\).

Prueba

Usaremos una prueba usando inducción en\(m\). Para cada uno\(m \in \mathbb{N}\), deja\(P(m)\) ser, “Si\(A \subseteq \mathbb{N}_{m}\), entonces\(A\) es finito y\(\text{card}(A) \le m\)”.

Primero probamos que eso\(P(1)\) es cierto. Si\(A \subseteq \mathbb{N}_1\), entonces\(A = \emptyset\) o\(A = \{1\}\), ambos son finitos y tienen cardinalidad menor o igual a la cardinalidad de\(\mathbb{N}_1\). Esto prueba que eso\(P(1)\) es cierto.

Para el paso inductivo, vamos\(k \in \mathbb{N}\) y asumamos que eso\(P(k)\) es cierto. Es decir, supongamos que si\(B \subseteq \mathbb{N}_k\), entonces\(B\) es un conjunto finito y\(\text{card}(B) \le k\). Tenemos que demostrar que eso\(P(k + 1)\) es cierto.

Entonces supongamos que\(A\) es un subconjunto de\(\mathbb{N}_{k + 1}\). Entonces\(A - \{k + 1\}\) es un subconjunto de\(\mathbb{N}_{k}\). Ya que\(P(k)\) es cierto,\(A - \{k + 1\}\) es un conjunto finito y

\(\text{card}(A - \{k + 1\}) \le k\).

Hay dos casos a considerar: Cualquiera\(k + 1 \in A\) o\(k + 1 \notin A\).

Si\(k + 1 \notin A\), entonces\(A = A - \{k + 1\}\). Por lo tanto,\(A\) es finito y

\(\text{card}(A) \le k < k + 1\).

Si\(k + 1 \in A\), entonces\(A = (A - \{k + 1\}) \cup \{k + 1\}\). Por lo tanto, por Lemma 9.4,\(A\) es un conjunto finito y

\(\text{card}(A) = \text{card}(A - \{k + 1\}\)+ 1\).

Ya que\(\text{card}(A - \{k + 1\}) \le k\), podemos concluir que\(\text{card}(A) \le k + 1\).

Esto quiere decir que hemos demostrado el paso inductivo. De ahí que por inducción matemática, para cada uno\(m \in \mathbb{N}\)\(A \subset \mathbb{N}_{m}\), si, entonces\(A\) es finito y\(\text{card}(A) \le m\).

Se demostró que los dos lemas precedentes ayudan en la prueba del siguiente teorema.

Teorema 9.6.

Si\(S\) es un conjunto finito y\(A\) es un subconjunto de\(S\), entonces\(A\) es un conjunto finito y\(\text{card}(A) \le \text{card}(S)\).

Prueba

Dejar\(S\) ser un conjunto finito y asumir que\(A\) es un subconjunto de\(S\). Si\(A = \emptyset\), entonces\(A\) es un conjunto finito y\(\text{card}(A) \le \text{card}(S)\). Entonces asumimos eso\(A \ne \emptyset\).

Dado que S es finito, existe una biyección\(f : S \to \mathbb{N}_k\) para algunos\(k \in \mathbb{N}\). En este caso,\(\text{card}(S) = k\). Tenemos que demostrar que\(A\) es equivalente a un conjunto finito. Para ello, definimos\(g : A \to f(A)\) por

\(g(x) = f(x)\)para cada uno\(x \in A\).

Dado que\(f\) es una inyección, concluimos que\(g\) es una inyección. Ahora vamos\(y \in f(A)\). Entonces existe\(a \in A\) tal que\(f(a) = y\). Pero por la definición de\(g\), esto significa eso\(g(a) = y\), y por lo tanto\(g\) es una suryección. Esto demuestra que\(g\) es una bijección.

De ahí que lo hayamos demostrado\(A \thickapprox f(A)\). Dado que\(f(A)\) es un subconjunto de\(\mathbb{N}_k\), usamos Lemma 9.5 para concluir que\(f(A)\) es finito y\(\text{card}(f(A)) \le k\). Además, por el Teorema 9.3,\(A\) es un conjunto finito y\(\text{card}(A) = \text{card}(f(A))\). Esto demuestra que\(A\) es un conjunto finito y\(\text{card}(A) \le \text{card}(S)\).

Lema 9.4 implica que agregar un elemento a un conjunto finito aumenta su cardinalidad en 1. También es cierto que eliminar un elemento de un conjunto finito no vacío reduce la cardinalidad en 1. El comprobante de Corolario 9.7 es Ejercicio (4).

corolario 9.7

Si\(A\) es un conjunto finito y\(x \in A\), entonces\(A - \{x\}\) es un conjunto finito y\(\text{card}(A - \{x\}) = \text{card} (A) - 1\)

El siguiente corolario se utilizará en la siguiente sección para proporcionar una distinción matemática entre conjuntos finitos e infinitos.

Corolario 9.8

Un conjunto finito no es equivalente a ninguno de sus subconjuntos adecuados.

Prueba

Dejar\(B\) ser un conjunto finito y asumir que\(A\) es un subconjunto adecuado de\(B\). Dado que\(A\) es un subconjunto apropiado de\(B\), existe un elemento\(x\) en\(B - A\). Esto significa que\(A\) es un subconjunto de\(B - \{x\}\). De ahí que, por el Teorema 9.6

\(\text{card}(A) \le \text{card}(B - \{x\}).\)

Además, por Corolario 9.7

\(\text{card}(B - \{x\}) = \text{card}(B) - 1.\)

De ahí que podamos concluir que\(\text{card}(A) \le \text{card}(B) - 1\) y que

\(\text{card}(A) < \text{card}(B).\)

El teorema 9.3 implica eso\(B \not\thickapprox A\). Esto demuestra que un conjunto finito no es equivalente a ninguno de sus subconjuntos propios.

El principio del encasillamiento

La última propiedad de los conjuntos finitos que consideraremos en esta sección se suele llamar el Principio de Pigeonhole. La versión “casillero” de esta propiedad dice: “Si\(m\) las\(r\) palomas se meten en los\(m > r\) casilleros y, entonces al menos un casillero tiene más de una paloma”.

En esta situación, podemos pensar en el conjunto de palomas como equivalente a un conjunto\(P\) con cardinalidad m y el conjunto de casilleros como equivalente a un conjunto\(H\) con cardinalidad\(r\). Luego podemos definir una función\(f : P \to H\) que mapee cada paloma a su casillero. El Principio Pigeonhole establece que esta función no es una inyección. (No es uno a uno ya que hay al menos dos palomas “mapeadas” al mismo casillero).

Teorema 9.9: El principio del encasillamiento

Dejar\(A\) y\(B\) ser conjuntos finitos. Si\(\text{card}(A) > \text{card}(B)\), entonces cualquier función no\(f : A \to B\) es una inyección.

Prueba

Dejar\(A\) y\(B\) ser conjuntos finitos. Vamos a probar lo contrapositivo o el teorema, que es, si existe una función\(f : A \to B\) que es una inyección, entonces\(\text{card}(A) \le \text{card}(B)\).

Entonces supongamos que\(f : A \to B\) es una inyección. Como en el Teorema 9.6, definimos una función\(g: A \to f(A)\) por

\(g(x) = f(x)\)para cada uno\(x \in A\).

Como vimos en el Teorema 9.6, la función\(g\) es una biyección. Pero entonces\(A \thickapprox f(A)\) y\(f(A) \subseteq B\). Por lo tanto,

\(\text{card}(A) = \text{card}(f(x))\)y\(\text{card}f((A)) \le \text{card}(B)\).

De ahí\(\text{card}f((A)) \le \text{card}(B)\),, y esto prueba lo contrapositivo. De ahí que si\(\text{card}(A) > \text{card}(B)\), entonces cualquier función no\(f : A \to B\) es una inyección.

El Principio Pigeonhole tiene muchas aplicaciones en la rama de las matemáticas llamadas “combinatorias”. Algunos de estos serán explorados en los ejercicios.

Ejercicios 9.1

1. Demostrar que la función\(g : A \cup \{x\} \to \mathbb{N}_{k + 1}\) en Lemma 9.4 es una sobreyección.
2. Dejar\(A\) ser un subconjunto de algún conjunto universal\(U\). Demostrar que si\(x \in U\), entonces\(A \times \{x\} \thickapprox A\).
3. \(E^{+}\)Sea el conjunto de todos los números parejos naturales. \(\mathbb{N} \thickapprox E^{+}\)Demuéstralo.
4. Demostrar Corolario 9.7.
   Si\(A\) es un conjunto finito y\(x \in A\), entonces\(A - \{x\}\) es un conjunto finito y\(\text{card}(A - \{x\}) = \text{card} (A) - 1\)
   Pista: Una aproximación es usar el hecho de que\(A = (A - \{x\}) \cup \{x\}\).
5. Dejar\(A\) y\(B\) ser conjuntos. Demostrar que
   
   (a) Si\(A\) es un conjunto finito, entonces\(A \cap B\) es un conjunto finito.
   (b) Si\(A \cup B\) es un conjunto finito, entonces\(A\) y\(B\) son conjuntos finitos.
   (c) Si\(A \cap B\) es un conjunto infinito, entonces\(A\) es un conjunto infinito.
   (d) Si\(A\) es un conjunto infinito o\(B\) es un conjunto infinito, entonces\(A \cup B\) es un conjunto infinito.
6. Hay más de 7 millones de personas viviendo en la ciudad de Nueva York. También se sabe que el número máximo de pelos en una cabeza humana es menor a 200,000. Usa el Principio de Pigeonhole para demostrar que hay al menos dos personas en la ciudad de Nueva York con el mismo número de pelos en la cabeza.
7. Demostrar las siguientes proposiitones:
   
   (a) Si\(A\)\(B\),\(C\),, y\(D\) son conjuntos con\(A \thickapprox B\) y\(C \thickapprox D\), entonces\(A \times C \thickapprox B \times D\).
   b) Si\(A\),,\(B\)\(C\), y\(D\) son conjuntos con\(A \thickapprox B\) y\(C \thickapprox D\) y si\(A\) y\(C\) son disjuntos y\(B\) y\(D\) son disjuntos, entonces\(A \cup C \thickapprox B \cup D\).
   
   Pista: Desde\(A \thickapprox B\) y\(C \thickapprox D\), existen bijecciones\(f: A \to B\) y\(g: C \to D\). Para probarlo\(A \times C \thickapprox B \times D\), probar que\(h: A \times C \to B \times D\) es una biyección, donde\(h(a, c) = (f(a), g(c))\), para todos\((a, c) \in A \times C\).
   Si\(A \cap C = \emptyset\) y\(B \cap D = \emptyset\), entonces para probarlo\(A \cup C \thickapprox B \cup D\), demostrar que la siguiente función es una biyección:\(k: A \cup C \to B \cup D\), donde
   \[k(x) = \begin{cases} f(x) & \text{ if \(t \in A\)} \\ g(x) & \text{ if \(x \in C\).} \end{cases}\]
8. Vamos\(A = \{a, b, c\}\).
   
   (a) Construir una función\(f: \mathbb{N}_5 \to A\) tal que\(f\) sea una sobreyección.
   (b) Utilizar la función\(f\) para construir una función de\(g: A \to \mathbb{N}_5\) manera que\(f \circ g = I_A\), donde\(I_A\) está la función de identidad en el conjunto\(A\). ¿La función es\(g\) una inyección? Explique.
9. Este ejercicio es una generalización de Ejercicio (8). Sea m un número natural,\(A\) sea un conjunto, y supongamos que\(f : \mathbb{N}_m \to A\) es una suryección. \(g: A \to \mathbb{N}_m\)Defina de la siguiente manera:
   Para cada uno\(x \in A\)\(g(x) = j\),, donde\(j\) es el número menos natural en\(f^{-1}(\{x\})\).
   Demostrar eso\(f \circ g = I_A\), dónde\(I_A\) está la función de identidad en el set\(A\) y probar que\(g\) es una inyección.
10. \(B\)Sea un conjunto finito, no vacío y supongamos que\(f: B \to A\) es una sobreyección. Demostrar que existe una función\(h: A \to B\) tal que\(f \circ h = I_A\) y\(h\) es una inyección.
    Pista: Como\(B\) es finito, existe un número natural\(m\) tal que\(\mathbb{N}_m \thickapprox B\). Esto significa que existe una biyección\(k: \mathbb{N}_m \to B\). Ahora vamos\(h = k \circ g\), donde\(g\) se construye la función en Ejercicio (9).
    
    Exploraciones y actividades
11. Usando el Principio de Pigeonhole. Para esta actividad, consideraremos subconjuntos de los\(\mathbb{N}_30\) que contienen ocho elementos.
    
    (a) Uno de esos conjuntos es\(A = \{3, 5, 11, 17, 21, 24, 26, 29\}\). Observe que
    \[\begin{array} {rcr} {\{3, 21, 24, 26\} \subseteq A} &\text{and} & {3 + 21 + 24 + 26 = 74} \\ {\{3, 5, 11, 26, 29\} \subseteq A} &\text{and} & {3 + 5 + 11 + 26 + 29 = 74} \end{array}\]
    Use esta información para encontrar dos subconjuntos disjuntos de\(A\) cuyos elementos tengan la misma suma.
    b) Dejar\(B = \{3, 5, 9, 12, 15, 18, 21, 24\}\). Encuentra dos subconjuntos disjuntos de\(B\) cuyos elementos tengan la misma suma. Nota: Por convención, si\(T = \{a\}\), donde\(a \in \mathbb{N}\), entonces la suma de los elementos en\(T\) es igual a\(a\).
    (c) Ahora vamos a\(C\) ser cualquier subconjunto de\(\mathbb{N}_{30}\) que contenga ocho elementos.
    i. ¿Cuántos subconjuntos\(C\) tiene?
    ii. La suma de los elementos del conjunto vacío es 0. ¿Cuál es la suma máxima para cualquier subconjunto\(\mathbb{N}_{30}\) que contenga ocho elementos.? \(M\)Sea esta suma máxima.
    iii. Ahora definimos una función para\(f: \mathcal{P}(C) \to \mathbb{N}_M\) que para cada uno\(X \in \mathcal{P}\),\(f(X)\) sea igual a la suma de los elementos en\(X\).
    Usa el Principio de Pigeonhole para probar que existen dos subconjuntos de C cuyos elementos tienen la misma suma.
    d) Si los dos subconjuntos de la parte (11 c) iii) no son disjuntos, utilizar la idea presentada en la parte (11a) para probar que existen dos subconjuntos disjuntos de\(C\) cuyos elementos tienen la misma suma.
    (e)\(S\) Sea un subconjunto de\(\mathbb{N}_{99}\) que contenga 10 elementos. Usa el Principio de Agujas para probar que existen dos subconjuntos disjuntos de\(S\) cuyos elementos tienen la misma suma.

Contestar

Agrega textos aquí. No elimine primero este texto.