a un conjunto con dos elementos. c. Sugerencia: La respuesta es 6. d. Considere funciones de un conjunto con cuatro elementos a un conjunto de dos...

a un conjunto con dos elementos.

c. Sugerencia: La respuesta es 6.
d. Considere funciones de un conjunto con cuatro elementos a un conjunto de dos elementos. Denote el conjunto de cuatro elementos por X {a, b, c, d} y al conjunto de dos elementos por Y {u, }. Divida el conjunto de todas las funciones sobre de X a Y en dos categorías. La primera categoría consiste de todas aquellas que envían a los tres elementos en {a, b, c} a {u, } y que mapean a d en u o . Las funciones en esta categoría pueden definirse mediante un proceso de dos pasos. 9.5 Soluciones y sugerencias para los ejercicios seleccionados A-85 A-86 Apéndice B Soluciones y sugerencias para los ejercicios seleccionados Paso 1: Construir una función sobreyectiva de {a, b, c} a {u, }. Paso 2: Elegir si d se envía a u o a . Por el inciso a), hay seis maneras de efectuar el paso 1 y, como existen dos formas de enviar a d, entonces se tienen dos opciones para realizar el paso 2. Así, por la regla de multiplicación, hay 6 2 12 maneras de definir las funciones en la primera categoría. La segunda categoría consiste de todas aquellas funciones sobreyectivas de X a Y que envían a los tres elementos en {a, b, c} a u o y que mandan a d al u o que no haya sido imagen de los otros. Sólo hay dos maneras hacia dónde mandar los elementos en {a, b, c} y como d es simplemente enviada a donde los otros no hayan ido, entonces existen justamente dos funciones en la segunda categoría. Cada función sobreyectiva de X a Y, envía o no, al menos dos elementos de X a f (d ). Si manda al menos dos elementos de X a f (d ) entonces está en la segunda categoría. Si no lo hace, Por tanto la imagen de {a, b, c} es {u, } y así la “restricción” de la función a {a, b, c} es sobreyectiva. En consecuencia, la función es una de aquellas incluidas en la primera categoría. Así todas las funciones sobreyectivas de A a Y están en una de las dos categorías y ninguna función está en ambas categorías, entonces el número total de funciones sobreyectivas es 12 2 14. Sugerencias: a. (i) g es inyectiva (ii) g no es sobreyectiva b. G es sobreyectiva. Demostración: Suponga que y es cualquier elemento de R. [Debemos demostrar que existe un elemento x en R tal que G(x) y. Trabajo desde el principio para determinar qué sería x si existiera y muestre que tendría que ser igual a (y 5) 4. La demostración debe establecer que x tiene las propiedades necesarias.] Sea x (y 5) 4. Entonces (1) x R y (2) G(x) G((y 5) 4) 4[(y 5) 4] ฀ 5 (y 5) ฀ 5 y [que era lo que se quería demostrar]. 27. a. Una relación sobre A es cualquier subconjunto de A A y A A tiene 82 64 elementos. Así hay 264 relaciones binarias sobre A. c. Forme una relación simétrica mediante un proceso de dos pasos: 1) tome un conjunto de elementos de la forma (a, a) (hay ocho de tales elementos, así 28 conjuntos); 2) seleccione un conjunto de pares de elementos de la forma (a, b) y (b, a) en donde a = b (existen (64 ฀ 8) 2 28 de tales pares, así 228 de esos conjuntos). Por tanto, la respuesta es 28 228 236. 28. Sugerencia: Use la regla de diferencia y la generalización de la regla de inclusión/exclusión para 4 conjuntos. (Vea el ejercicio 48 de la sección 9.3.) 31. Al conjunto lo llamamos X y suponemos que X {x1, x2, …,xn}. Para cada entero i 0, 1, 2,…, n ฀ 1, podemos considerar al conjunto de todas las particiones de X (llamémoslas particiones de tipo i) en donde uno de los subconjuntos de la partición es un (i 1) elemento que contiene a xn e i elementos elegidos de {x1, …, xn฀1}. Los restantes subconjuntos de la partición será una partición de los restantes (n ฀ 1) ฀i elementos de {x1,…, xn฀1}. Por ejemplo, si X {x1, x2, x3}, hay cinco particiones de los diversos tipos, a saber, Tipo 0: dos particiones en donde un conjunto es un conjunto que contiene sólo a x3: [{x3},{x1},{x2}], [{x3},{x1,x2}] Tipo 1: dos particiones en donde un conjunto es un conjunto de dos elementos que contiene a x3: [{x1, x3},{x2}], [{x2, x3},{x1}] Tipo 2: una partición en donde un conjunto es un conjunto de tres elementos que contiene a x3: {x1, x2, x3}. En general, podemos imaginar que la construcción de una partición del tipo i es un proceso de dos pasos: Paso 1: Seleccione i elementos de {x1,…, xn฀1} para colocarlos junto con xn. Paso 2: Elija cualquier partición de los restantes (n ฀ 1) ฀ i elementos de {x1,…, xn฀1} para ponerlos con el conjunto formado en el paso 1. Existen (n−1 i) maneras de ejecutar el paso 1 y P(n฀1)฀i opciones para realizar el paso 2. Por tanto, por la regla de multiplicación, hay (n−1 i)· P(n−1)−i particiones del tipo i. Cualquier partición de X es del tipo i para algún i 0, 1, 2,…, n ฀ 1, entonces de la regla de adición se tiene que el número total de particiones es (n − 1 0)Pn−1 + (n − 1 1)Pn−2 + (n − 1 2)Pn−3 + · · · + (n − 1 n − 1)P0. 33. S5,2 = S4,1 + 2S4,2 = 1 + 2 ·7 = 15 36. Demostración (por inducción matemática): Aceptemos que la propiedad P(n) sea la ecuación Sn,2 2n฀1 ฀1. Demostración de que P(2) es verdadero: Debemos demostrar que S2,2 22฀1 ฀ 1. Por el ejemplo 9.5.13, S2,2 1 y 22฀1 ฀ 1 2 ฀ 1 1. Entonces P(2) es verdadero. Demostración de que para todos los enteros k 2, si P(k) es verdadero, entonces P(k 1) también es verdadero: Sea k cualquier entero con k 2 y suponga que Sk,2 2k฀1 ฀ 1. [Hipótesis inductiva.] Debemos demostrar que Sk 1,2 2(k 1)฀1 ฀ 1 2k ฀ 1. Pero de acuerdo con el ejemplo 9.5.13, Sk 1,2 Sk,1 2 Sk,2 y Sk,1 1. Así, sustituyendo y la hipótesis inductiva, Sk 1,2 1 2Sk,2 1 2(2k฀1 ฀ 1) 1 2k ฀ 2 2k ฀ 1 [que era lo que se quería demostrar]. 38. Sugerencia: Observe que el número de funciones sobreyectivas de X {x1, x2, x3, x4} a Y {y1, y2, y3} es S4,3 3! porque la construcción de una función sobreyectiva puede pensarse como un proceso de dos pasos en donde el paso 1 es elegir una partición de X en tres subconjuntos y el paso 2 es seleccionar, para cada subconjunto de la partición, un elemento de Y para los elementos del conjunto a ser enviado. Sección 9.6 1. a. (5+3−1 5 ) = (7 5 ) = 7 ·6 2 = 21. a. Los tres elementos del conjunto son 1, 2 y 3. Las 5-combinaciones son [1, 1, 1, 1, 1], [1, 1, 1, 1, 2], [1, 1, 1, 1, 3], [1, 1, 1, 2, 2], [1, 1, 1, 2, 3],