1 El principio del Palomar
2 Capítulo 4 Funciones 4.4 Principio del palomarEn matemáticas se descubre a menudo que una idea casi obvia, aplicada de manera apropiada, es la clave necesaria para resolver un problema complejo. Sin duda, muchos pondrían en la lista de tales ideas la siguiente regla, conocida como principio del palomar.
3 Capítulo 4 Funciones 4.4 Principio del palomarEl principio del palomar: Si m palomas ocupan n nidos, y si m n, entonces hay al menos un nido con dos o más palomas. Ahora, qué tiene que ver con matemáticas discretas o de otro tipo, las palomas del palomar?
4 Capítulo 4 Funciones 4.4 Principio del palomarEJEMPLO En una oficina hay 13 empleados, de forma que al menos dos de ellos deben celebrar su cumpleaños en el mismo mes. Aquí se tienen 13 palomas (los empleados) y 12 nidos (los meses del año).
5 Capítulo 4 Funciones 4.4 Principio del palomarEJEMPLO Cualquier subconjunto de tamaño seis del conjunto S={1,2,3,...,9} debe contener dos elementos que sumen 10. Aquí los números 1,2,3,...,9 son las palomas mientras que los nidos son los subconjuntos {1,9}, {2,8}, {3,7}, {4,6}, {5}. Cuando seis palomas van a sus respectivos nidos, deben ocupar al menos un subconjunto de dos elementos, cuyos miembros sumen diez.
6 Capítulo 4 Funciones 4.4 Principio del palomarEJEMPLO El triangulo ACE es equilátero, con AC = 1. Si se eligen cinco puntos de su interior hay como mínimo dos que distan menos de 1/2. A C E
7 R1: el interior del triángulo BCD, junto con los puntos sobre el segmento BD; excluyendo B y D.R2: el interior del triángulo ABF. R3: el interior del triángulo BDF, junto con los puntos sobre los segmentos BF, DF; excluyendo B, D y F. R4: el interior del triángulo FDE. region 1 region 2 region 3 region 4 4 nidos 5 palomas D B C A F E
8 Capítulo 4 Funciones 4.4 Principio del palomarAhora aplicando el principio del palomar, cinco puntos del interior del triángulo ACE deben cumplir que al menos dos de ellos estén en una de las cuatro regiones Ri, 1i4, donde dos puntos cualesquiera distan menos de 1/2.
9 Capítulo 4 Funciones 4.4 Principio del palomarEJEMPLO Sea C un conjunto de seis enteros positivos cuyo máximo es, a lo sumo, 14. Muéstrese que la suma de los elementos de todos los subconjuntos no vacíos de C no pueden ser distintos. Para cualquier subconjunto no vacío A de C, la suma de los elementos de A, definida por SA, cumple 1 SA = 69 y hay 26 – 1 =63 subconjuntos no vacíos de C. Se desea obtener el resultado, tomando las sumas posibles, de 1 a 69, como los nidos y los 63 subconjuntos no vacíos de C como las palomas, pero habría muy pocas palomas.
10 Capítulo 4 Funciones 4.4 Principio del palomarAsí, consideraremos todos los subconjuntos A A C donde 5. Entonces, 1 SA = 60. Como hay 62 subconjuntos no vacíos de C con 5, los elementos de al menos dos de ellos deben generar la misma suma.
11 Capítulo 4 Funciones 4.4 Principio del palomarEJEMPLO Durante sus cuatro semanas de vacaciones, Heriberto jugará al tenis, disputando un set como mínimo cada día, pero no jugará más de 40 sets en ese tiempo. Pruébese que, independientemente de cómo distribuya sus sets durante las cuatro semanas, hay una serie de días consecutivos durante los cuales jugará exactamente 15 sets.
12 Capítulo 4 Funciones 4.4 Principio del palomarPara 1 i 28, sea xi el número total de sets jugados desde el inicio de las vacaciones hasta el final del i-ésimo día. Entonces 1 x1 x2... x28 40, y x1+15,...,x28+1555. Tenemos 28 números distintos x1, x2,..., x28 y los 28 números distintos x1+15,..., x Estos 56 números sólo pueden tomar 55 valores distintos, de modo que al menos dos de ellos deben ser iguales, así que existe 1 j i 28 con xi = xj Por tanto, desde el principio del día j al final del día i, Heriberto juega exactamente 15 sets de tenis.
13 Funciones Especiales
14 Capítulo 4 Funciones 4.5 Funciones especialesDefinición Para cualquier conjunto A, cualquier función f: A A A se llama operación binaria en A. EJEMPLO La función f: Z Z Z, definida por f(a, b)= a – b, es una operación binaria en Z. EJEMPLO Sea U = {1, 2, 3, 4}. Para los conjuntos arbitrarios A, B U, g: P(U) P(U) P(U), definida por g(A, B) = A B, es una operación binaria en P(U).
15 Capítulo 4 Funciones 4.5 Funciones especialesDefinición Sea f: A A A. Se dice que f es conmutativa si f(a, b) = f(b, a) para toda (a, b) A A. b) Se dice que f es asociativa si para a, b, c A, f(f(a, b), c) = f(a, f(b, c)).
16 Capítulo 4 Funciones 4.5 Funciones especialesDefinición Para conjuntos A, B, si D A B, entonces A: DA definida por A(a, b)=a se denomina proyección sobre la primera coordenada. La función B se define de manera análoga, y se observa que si D = A B, entonces A y B son suprayectivas.
17 Capítulo 4 Funciones 4.5 Funciones especialesAhora se ampliará el concepto de proyección de la siguiente forma: si A1, A2, ... , An son conjuntos e {i1, i2, ... , im} {1, 2, ... , n}, con i1 i2 ,.., im, m n, para D A1 A2 , ..., An = , la función : D Ai1 Ai2 , ..., Aim definida por (a1,....,an) = (ai1, ai2,...,aim) es una proyección de D sobre las i1-ésima, i2-ésima, ..., im-ésima coordenadas. Los elementos de D se denominan n-uplas, mientras que un elemento en (D) es una m-uplas. Estas proyecciones aparecen de manera natural en el estudio de las bases de datos relacionales
18 A1= conjunto de número de cursos ofrecidos en matemáticas. EJEMPLO En determinada universidad se relacionan los siguientes conjuntos para hacer distintos registros: A1= conjunto de número de cursos ofrecidos en matemáticas. A2= conjunto de nombres de cursos ofrecidos en matemáticas. A3= conjunto de los profesores de matemáticas. A4= el conjunto de las letras del alfabeto. Considere la tabla, o relación D A1 A2 A3 A4 Número del curso Nombre del curso Profesor Letra MA 111 Cálculo I G. Sosa A V. Lara B MA 112 Cálculo II J. Quintana A. Suárez R. Martínez C MA 113 Cálculo III
19 Los conjuntos A1, A2, A3, A4 se denominan campos de la base de datos relacional, y se dice que la tabla D tiene grado 4. A cada elemento de D se le suele denominar registro. En la tabla a) se muestra la proyección de D sobre A1 A3 A4 . La tabla b) indica el resultado de la proyección de D sobre A1 A2. Número del curso Profesor Letra Nombre del curso MA 111 G. Sosa A V. Lara B MA 112 J.Quintana MA 113 A. Suárez R.Martínez C J. Quintana Cálculo I Cálculo II Cálculo III a) b)
20 Capítulo 4 Funciones 4.5 Funciones especialesDefinición Si f: A B, se dice que f es biyectiva o que tiene correspondencia uno a uno si f es al mismo tiempo uno a uno y suprayectiva. EJEMPLO Si A = {1, 2, 3, 4}, B = {w, x, y, z}, entonces f = {(1, w), (2, x), (3, y), (4, z)} es una correspondencia biyectiva de A a (en) B.
21 Capítulo 4 Funciones 4.5 Funciones especialesPara cualquier conjunto A, siempre hay una correspondencia biyectiva simple, pero importante, como se observa a continuación. Definición La función 1A: A A, definida por 1A(a)=a, para toda aA, se denomina función identidad para A. Si f: A A es biyectiva, se obtiene f(A) = A y se puede pensar que f = es una permutación de A.
22 Capítulo 4 Funciones 4.5 Funciones especialesDefinición Si f, g: A B, se dice que f y g son iguales, y se escribe f = g si f(a) = g(a) para toda a A. Un fallo común al tratar la igualdad de funciones tiene lugar cuando f, g son funciones con un dominio común A y f(a) = g(a) para toda aA. Puede darse el caso que no sea f = g. El error se origina por no prestar atención a los codominios de las funciones.
23 Capítulo 4 Funciones 4.5 Funciones especialesEJEMPLO Sea f: Z Z, g: Z Q, donde f(x) = x = g(x) para toda x Z. Por tanto f, g comparten el mismo dominio Z, tienen la misma imagen Z y actúan igual sobre cada elemento de Z. Pero f g, pues f es una correspondencia uno a uno, mientras que g es uno a uno, pero no suprayectiva, pues los codominios las diferencian.
24 Capítulo 4 Funciones 4.5 Funciones especialesAhora una vez analizadas las operaciones que combinan enteros y otras que operan en conjuntos, se introduce una que combina dos funciones apropiadas. Definición Si f: A B , g: B C, se define la función compuesta, denotada :A C, por ( )(a) = g(f(a)), para cada aA.
25 Capítulo 4 Funciones 4.5 Funciones especialesEJEMPLO Sean A={1, 2, 3, 4}, B={a, b, c}, C={w, x, y, z}, con f: A B , g: B C, dadas por: f={(1,a), (2,a), (3,b), (4,c)} y g={(a,x), (b,y), (c,z)}. Para cada elemento de A resulta: ( )(1)=g(f(1))=g(a)=x ( )(3)=g(f(3))=g(b)= y ( )(2)=g(f(2))=g(a)=x ( )(4) =g(f(4))=g(c)=z De modo que ={(1, x), (2, x), (3, y), (4, z)}.
26 EJEMPLO Sean f: RR, g: RR definidas por f(x)= x2, g(x)= x + 5EJEMPLO Sean f: RR, g: RR definidas por f(x)= x2, g(x)= x + 5. Por tanto, ( )(x)= g(f(x))=g(x2) = x2 + 5, mientras que ( )(x) = f(g(x))=f(x + 5) = (x + 5)2 = x2 + 10x + 25. Aquí, :R R, y g: R R, pero ( )(1) = 6 36 = ( )(1); así, aunque puedan formarse las composiciones y , no resulta = En consecuencia, la composición de funciones no es, en general, una operación conmutativa.
27 Capítulo 4 Funciones 4.5 Funciones especialesEn la definición y ejemplos para funciones compuestas se requería que el codominio de f = dominio de g. En realidad, es suficiente para generar la función compuesta : AC si la imagen de f del domino de g. Se observa también que para cualquier f: A B, = f =
28 Capítulo 4 Funciones 4.5 Funciones especialesUna idea importante que se repite en matemáticas es la investigación de si la combinación de dos entidades con una propiedad común proporciona un resultado con esta propiedad. Por ejemplo, si A y B son conjuntos finitos, entonces AB, AB también son finitos. Sin embargo, para los conjuntos infinitos A, B, AB es infinito, pero AB podría ser finito. (Dése un ejemplo).
29 Capítulo 4 Funciones 4.5 Funciones especialesPara la composición de funciones, se tiene el siguiente resultado. Teorema Sean f: A B , g: B C. a) Si f, g son uno a uno, entonces es uno a uno. b) Si f, g son suprayectivas, entonces es suprayectiva.
30 Capítulo 4 Funciones 4.5 Funciones especiales Demostracióna) Probar que : A C es uno a uno, sea a1, a2 A con ( )(a1) = ( )(a2). Entonces, ( )(a1) = ( )(a2) g(f(a1)) = g(f(a2)) f(a1) = f(a2), pues g es uno a uno. Además, f(a1) = f(a2) a1 = a2 ya que f es uno a uno. Por tanto, es uno a uno.
31 Capítulo 4 Funciones 4.5 Funciones especialesDemostración (Continuación...) b) Para : A C, sea z C. Como g es suprayectiva, existe yB, con g(y) = z. Si f es suprayectiva, existe xA, con f(x) = y. De ahí que z = g(y) = g(f(x))= ( )(x), pues la imagen de ( ) =C= codominio de ( ) y es suprayectiva.
32 Capítulo 4 Funciones 4.5 Funciones especialesAunque la composición de funciones no sea conmutativa, si f: A B, g: B C, h: C D ¿Qué se puede afirmar sobre las funciones y ? ¿Por ejemplo, es asociativa la composición de funciones ?
33 Teorema Dadas f: A B, g: B C, h: C D, entonces=
34 Capítulo 4 Funciones 4.5 Funciones especialesDemostración Como las dos funciones tienen el mismo dominio, A, y codominio, D, el resultado se obtendrá mostrando que para cada xA, (x) = (x). Véase el diagrama de Venn de la figura Mediante la definición de función compuesta , resulta que mientras que Por tanto, la composición de funciones es una operación asociativa.
35 Capítulo 4 Funciones 4.5 Funciones especialesEn virtud de la propiedad asociativa de la composición de funciones, es posible escribir sin problema de ambigüedad , o Definición Para los conjuntos A, B U, si R es una relación de A a B, la conversa de R, denotada por Rc, es una relación de B a A definida por Rc =
36 Capítulo 4 Funciones 4.5 Funciones especialesPara obtener Rc de R, no hay más que intercambiar las componentes de cada par ordenado en R, de modo que si A ={1,2,3,4}, B={w,x,y} y R={(1, x), (2,w), (3,x)}, entonces Rc = {(x, 1), (w, 2), (x, 3)}, es una relación de B a A.
37 Capítulo 4 Funciones 4.5 Funciones especialesPara los conjuntos A ={1,2,3,4}, B={w,x,y}, sea f: A B, donde f ={(1, w), (2, x), (3, y), (4, x)}. Entonces, f c = {(w, 1), (x, 2), (y, 3), (x, 4)} es una relación, pero no una función, de B a A. Se pretende investigar en qué condiciones la conversa de una función genera una función, pero antes de entrar en abstracciones, se considerará el siguiente ejemplo.
38 Capítulo 4 Funciones 4.5 Funciones especialesEJEMPLO Para A={1,2,3}, B={w,x,y}, Sea f:AB dada por f={(1,w),(2,x),(3,y)}. Entonces f c={(w,1),(x,2), (y,3)} es una función de B a A. La función f c se llama función inversa para f , y se halla que y
39 Capítulo 4 Funciones 4.5 Funciones especialesDefinición Si f: A B, se dice que f es invertible si existe una función g: B A tal que y EJEMPLO Sea f, g : R R definidas por f(x)=2x+5, g(x)=(1/2)(x–5). Entonces, ( )(x)= g(f(x))= g(2x+5) = (1/2)[(2x+5)–5]= x, ( )(x)= f(g(x))= f((1/2)(x–5))= 2[(1/2)(x–5)]+5= x De modo que =1R y =1R. En consecuencia, f y g son funciones invertibles.
40 Capítulo 4 Funciones 4.5 Funciones especialesTeorema Si una función f: AB es invertible, entonces su función inversa g: BA es única. Demostración Si g es una inversa de f, se tiene =1A, =1B. Si g no es única, existe otra función h: BA con =1A, =1B. En consecuencia, = = = g.
41 Capítulo 4 Funciones 4.5 Funciones especialesComo resultado de este teorema, se puede denotar la inversa de una función invertible f por f -1; ¿pero cuándo es invertible una función?
42 Capítulo 4 Funciones 4.5 Funciones especialesTeorema Una función f: A B es invertible si, y sólo si, es uno a uno y suprayectiva. Demostración Al suponer que f: A B es invertible, se tiene una función única g: B A, con =1A, =1B. Si a1, a2 A, con f(a1) = f(a2), entonces g(f(a1)) = g(f(a2)) o ( )(a1) = ( )(a2). Como =1A, resulta que a1 = a2 , de modo que f es uno a uno. Para la propiedad de suprayectividad, sea bB. Entonces, g(b)A de manera que es posible hablar de f(g(b)). Como = 1B, resulta b = 1B(b)= ( )(b) = f(g(b)), por lo que f es suprayectiva.
43 Capítulo 4 Funciones 4.5 Funciones especialesDemostración. Continuación... A la reciproca, supóngase que f: A B es biyectiva. Como f es suprayectiva, para cada b B existe alguna a A con f(a) = b. En consecuencia, se define una función g: B A por g(b) = a, donde f(a) = b. Esta definición produce una función única. El único problema que se puede presentar, es si g(b) = a1 a2 = g(b) debido a que f(a1) = b = f(a2). Sin embargo, no puede darse esta situación, pues f es uno a uno. Como la definición de g es tal que =1A, = 1B, se tiene que f es invertible, con g = f -1.
44 Capítulo 4 Funciones 4.5 Funciones especialesEJEMPLO Por el teorema anterior, la función f1: R R definida por f1(x) = x2 no es invertible (pues no es uno a uno), pero f2:[0, +) [0, +), definida por f2(x) = x2 es invertible con (x) =
45 Teorema Si f: A B, g: B C son funciones invertibles, entonces : A C es invertible y( )-1 = Vistos algunos ejemplos de funciones y sus inversas, cabe pensar si existe un método algebraico para determinar la inversa de una función invertible. Si la función es finita, no hay más que intercambiar las componentes de los pares ordenados dados pero, ¿y si la función está definida por una fórmula? Por fortuna, las manipulaciones algebraicas son poco más que un análisis cuidadoso del intercambio de las componentes de los pares ordenados. Esto se demuestra en los siguientes ejemplos.
46 Capítulo 4 Funciones 4.5 Funciones especialesEJEMPLO Para m, b R, m 0, f: R R, definida por f = , es una función invertible. Para obtener f -1, se observa que Así que f: R R está definida por f(x) = mx + b, mientras que f -1: R R se define por f -1(x) = (1/m)(x – b).
47 EJEMPLO Sea f: R R+ definida por f(x) = ex, dondee = , es la base para el logaritmo natural. En la gráfica de la figura se observa que f es uno a uno y suprayectiva, de modo que existe f -1: R+ R. Entonces, f -1 = = = , así que f -1(x) = ln x.
48 Capítulo 4 Funciones 4.5 Funciones especiales El ejemplo anterior da lugar a la siguiente fórmula: x = 1R(x) = ( )(x) = ln (ex) para toda x R, x = 1R+(x) = ( )(x) = eln x, para toda x 0.
49 Capítulo 4 Funciones 4.5 Funciones especiales El resultado x = eln x para x 0 es muy útil. En la aplicación estándar de Pascal no hay exponenciación. Para determinar 23, se puede recurrir a la repetición de la multiplicación, pero esto es inútil cuando se trata de evaluar un número como (5.73)4.32. Como exp y ln son funciones definidas en Pascal, se puede determinar (5.73)4.32 expresándolo de nuevo como e4.32 ln (5.73), pues por la fórmula anterior, 5.73 = e ln(5.73). En Pascal, esto se transforma en exp(4.32 ln(5.73)).
50 Capítulo 4 Funciones Definición Si f: A B y B1 B, entonces4.5 Funciones especiales Definición Si f: A B y B1 B, entonces f-1(B1) = . A f -1(B1) se le llama imagen inversa de B1 bajo f. Aquí es necesario tener cuidado. Aunque, se cuente con el concepto de imagen inversa para cualquier función, no toda función tiene inversa. En consecuencia, no se puede suponer la existencia de una inversa de una función f sólo porque se emplee el símbolo f -1. Se necesita prestar un poco de atención.
51 Capítulo 4 Funciones 4.5 Funciones especiales EJEMPLO Si f: Z R definida por f(x) = x La siguiente tabla enumera f -1(B) para varios subconjuntos B del codominio R. B f -1(B) B f -1(B) {6} {-1,1} [-4,5) [6,7] [-4,5] {0} [6,10] {-2, -1, 1, 2} [5,+) Z
52 Capítulo 4 Funciones Teorema Si f: A B y B1, B2 B, entonces:4.5 Funciones especiales Teorema Si f: A B y B1, B2 B, entonces: a) f-1(B1 B2) = f-1(B1) f-1(B2), b) f-1(B1 B2) = f-1(B1) f-1(B2), y c) f-1( ) =
53 Capítulo 4 Funciones 4.5 Funciones especiales Demostración Se demuestra el apartado b), y se deja a) y el c) como ejercicio. Para aA, a f -1(B1 B2) f(a) B1 B2 f(a) B1 o f(a) B2 a f -1(B1) o a f -1(B2) a f -1(B1) a f -1(B2).