Induccion MatematicaConjuntosFunciones

Matematica Discreta

Agustın G. Bonifacio

UNSL

Repaso de Induccion, Conjuntos y Funciones

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Induccion Matematica (Seccion 1.7 del libro)

Supongamos que queremos demostrar enunciados del siguientetipo:P (n) : “La suma de los primeros n numeros naturales es n(n+1)

2 ”,Q(n) : “La suma de los primeros n numeros naturales impares esn2”.

P (1) es verdadero ya que 1 = 1·22 ,

P (2) es verdadero ya que 1 + 2 = 3 = 2·32

P (3) es verdadero ya que 1 + 2 + 3 = 6 = 3·42

. . .

¿Como probamos esto para todo numero natural? A traves delPrincipio de Induccion.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Recordemos que N = {1, 2, 3, . . .} denota al conjunto de numerosnaturales. Sea N0 = N ∪ {0} = {0, 1, 2, 3, . . .}

Principio de Induccion

Sea P (n) una funcion proposicional, con n ∈ N. Supongamos que:

1 P (1) es verdadera (paso base),

2 Para todo k ≥ 1, P (k) =⇒ P (k + 1) (paso inductivo),

Entonces, P (n) es verdadera para todo n ∈ N.

Para probarlo vamos a hacer uso del siguiente principio:

Principio de Buena Ordenacion

Todo subconjunto no vacıo de N tiene primer elemento.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Teorema

Si S ⊆ N satisface:

1 1 ∈ S,

2 h ∈ S =⇒ h+ 1 ∈ S,

Entonces S = N.

Demostracion: Evidentemente S ⊆ N. Resta ver que N ⊆ S. Definamosel conjunto:

S′ = {n ∈ N | n /∈ S}.

Supongamos que N * S, lo que implica que S′ 6= ∅. Por el Principio de

Buena Ordenacion, S′ tiene primer elemento. Llamemoslo m. Por la

Propiedad (1) de S, m 6= 1. Entonces m > 1 y m− 1 ∈ S. Pero por la

propiedad (2), m− 1 ∈ S =⇒ (m− 1) + 1 ∈ S, o sea, m ∈ S. Esto es un

absurdo ya que m ∈ S′. Se deduce que S′ = ∅ y N ⊆ S. En consecuencia

S = N. �

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Principio de Induccion (P. I.)

Sea P (n) una funcion proposicional, con n ∈ N. Supongamos que:

1 P (1) es verdadera (paso base),

2 Para todo k ≥ 1, P (k) =⇒ P (k + 1) (paso inductivo),

Entonces, P (n) es verdadera para todo n ∈ N.

Demostracion del Principio de Induccion: Definamos elconjunto:

S = {n ∈ N | P (n) es verdadera}.

Por la Parte (1) del P. I., 1 ∈ S.Por la Parte (2) del P. I., k ∈ S =⇒ k + 1 ∈ S.Entonces, por el Teorema anterior, S = N. Esto significa que P (n)es verdadero para todo n ∈ N. �

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Observaciones

El Principio tambien vale cambiando N por N0.

El Principio puede entenderse como un “efecto domino”.

Ejemplo

Probar, usando induccion, que

P (n) : 1 + 2 + 3 + ...+ n =n(n+ 1)

2

para todo n ∈ N.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Definicion

El factorial de n es el numero dado por:

n! ≡

{

1 si n = 0n . (n− 1) . . . 2 . 1 si n ≥ 1

Ejemplos

0! = 1, 3! = 3 · 2 · 1 = 6, 6! = 6 · 5 · 4 · 3! = 720

Observacion

n! = n . (n− 1)!

Ejemplo

Probar, usando induccion, que

P (n) : n! ≥ 2n−1

para todo n ∈ N.Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Forma Fuerte del P.I. (Seccion 1.8 del libro)

Forma Fuerte del P. I.

Sea P (n) una funcion proposicional, con n ∈ N y n ≥ n0, para uncierto n0 ∈ N. Suponga que:

1 P (n0) es verdadera.

2 Para todo k > n0, si P (k′) es verdadero para todo k′ tal quen0 ≤ k′ < k, entonces P (k) es verdadero.

Entonces P (n) es verdadero para todo n ≥ n0.

Observacion

Esta forma fuerte del principio es logicamente equivalente a la quevimos anteriormente.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Conjuntos (Seccion 2.1 del libro)

Definicion

Un conjunto es una coleccion de objetos, que llamamos elementos.

Si el conjunto es finito y no muy grande, es posible describirlo por lalista de sus elementos. Por ejemplo:

A = {1, 2, 3, 4}.

Un conjunto se determina por sus elementos y no por el orden en elque estos se enumeren. El conjunto A puede tambien describirsecomo sigue:

A = {1, 3, 4, 2}.

Se supone que los elementos que forman un conjunto son distintos,por lo que duplicados en la lista no cambian al conjunto:

A = {1, 2, 2, 3, 4}.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Si un conjunto es grande o infinito, se describe mediante unapropiedad de sus elementos, por ejemplo:

B = {x | x es par}

B = {x | x = 2n, con n ∈ N}

B = {2, 4, 6, 8, . . .}

Si X es un conjunto finito, denotamos por |X| la cantidad deelementos de X. Por ejemplo, |A| = 4.

Si el elemento x se encuentra en el conjunto X, escribimosx ∈ X; si no, x /∈ X. Por ejemplo: si x = 1, entonces x ∈ Apero x /∈ B.

El conjunto que no tiene elementos se llama vacıo y se denotapor ∅.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Sean X e Y dos conjuntos. Si todo elemento de X estambien elemento de Y, se dice que X es subconjunto de Y yse escribe X ⊆ Y.

X ⊆ Y ⇐⇒ (∀x : x ∈ X =⇒ x ∈ Y ).

Por ejemplo: si C = {1, 3}, entonces C ⊆ A.

Sean X e Y dos conjuntos. Si X e Y tienen los mismoselementos se dice que X e Y son iguales y se escribe X = Y.

X = Y ⇐⇒ (X ⊆ Y ∧ Y ⊆ X).

Ejemplo: Sean A = {x | x2 + x− 6 = 0} y B = {2,−3}.Queremos ver que A = B.

Todo conjunto es subconjunto de sı mismo, esto es, X ⊆ X.

El conjunto vacıo es subconjunto de cualquier conjunto, estoes, ∅ ⊆ X.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Si X ⊆ Y y X 6= Y, entonces X es un subconjunto propio deY y se escribe X ⊂ Y .

El conjunto de todos los subconjuntos de un conjunto X, quese denota P(X), se llama conjunto de partes de X. Porejemplo: si A = {a, b, c}, entonces

P(A) = {∅, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, A}.

Notemos que |A| = 3 y que |P(A)| = 23 = 8. Este es unhecho general.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Teorema

Si |X| = n, entonces |P(X)| = 2n para todo n ≥ 0.

Demostracion: por induccion sobre n.

Paso base: si |X| = 0, tenemos X = ∅ y, en consecuencia, P(X) = {∅} y

|P(X)| = 1 = 20.

Afirmacion: Elijamos un x ∈ X. Exactamente la mitad de los subconjuntos de X

contiene al elemento x.

Paso Inductivo:

Hipotesis inductiva P (k) : |X| = k =⇒ |P(X)| = 2k .

Queremos ver que |X| = k + 1 =⇒ |P(X)| = 2k+1. Para ello elijamos un x ∈ X y

consideremos el conjunto Y obtenido de X al eliminar el elemento x. Entonces

|Y | = k y por hipotesis inductiva |P(Y )| = 2k . Ademas, por la Afirmacion,

|P(Y )| = |P(X)|2

,

por lo que |P(X)| = 2|P(Y )| = 2 2k = 2k+1. Se concluye, por el P.I., que el teorema

es verdadero para todo n ≥ 0. �

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Dados dos conjuntos X e Y,X ∪ Y ≡ {x | x ∈ X ∨ x ∈ Y } es el conjunto union de X eY,X ∩ Y ≡ {x | x ∈ X ∧ x ∈ Y } es el conjunto interseccionde X e Y,X − Y ≡ {x | x ∈ X ∧ x /∈ Y } es el conjunto diferenciaentre X e Y.Ejemplo: sean A = {1, 3, 5} y B = {4, 5, 6}. EntoncesA ∪B = {1, 3, 4, 5, 6}, A ∩B = {5}, A−B = {1, 3} yB −A = {4, 6}. Notemos que A−B 6= B −A.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Los conjuntos X e Y son disjuntos si X ∩ Y = ∅. Unacoleccion de conjuntos S es disjunta de a pares si todo par deconjuntos X e Y diferentes en S son disjuntos.

En general, implıcita o explıcitamente, todos los conjuntosque tratamos son subconjuntos de un conjunto U , que sellama universal. Dado un universal U y y un conjunto X de U ,el conjunto U −X se llama complemento de X y se escribe X(o Xc).Ejemplos:

Sean A = {1, 3, 5} y U = {1, 2, 3, 4, 5}; entonces A = {2, 4}Si U = N y A = {pares}, ¿cual es A?

Diagramas de Venn.

Leyes de conjuntos: asociativas, conmutativas, distributivas,de De Morgan, etc.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Una coleccion S de subconjuntos no vacıos de un conjunto Xes una particion (del conjunto X) si todo elemento de Xpertenece exactamente a un miembro de S. (Observese que launion de los elementos de S es X y que S es disjunta de apares.)Ejemplo: S = {{1, 4, 5}, {2, 6}, {3}, {7, 8}} es una particionde X = {1, 2, 3, 4, 5, 6, 7, 8}.

Sean X e Y dos conjuntos. El producto cartesiano de X e Y,que se escribe X × Y, es el conjunto de todos los paresordenados (x, y) donde x ∈ X y y ∈ Y,

X × Y ≡ {(x, y) | x ∈ X ∧ y ∈ Y }.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Ejemplo: sean X = {1, 2, 3} y Y = {a, b}. ¿Como son X × Y,Y ×X, X ×X y Y × Y ?

En general, X × Y 6= Y ×X.

|X1 ×X2 × . . .×Xn| = |X1|.|X2| . . . |Xn| (la prueba sale porinduccion).

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Funciones (Seccion 2.2 del libro)

Definicion

Sean X e Y dos conjuntos. Una funcion f de X a Y es unsubconjunto del producto cartesiano X × Y con la propiedad deque, para cada x ∈ X, existe exactamente un y ∈ Y tal que(x, y) ∈ f.

En ocasiones, denotamos una funcion f de X a Y comof : X → Y.

El conjunto X se llama dominio de f.

El conjunto {y | (x, y) ∈ f} es la imagen de f.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Ejemplo: f = {(1, a), (2, b), (3, a)} es una funcion deX = {1, 2, 3} a Y = {a, b, c}.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Ejemplo: El conjunto f = {(1, a), (2, a), (3, b)} NO es unafuncion de X = {1, 2, 3, 4} a Y = {a, b, c} porque 4 noesta asignado a un elemento de Y. Sin embargo SI es unafuncion de X ′ = {1, 2, 3} a Y.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Ejemplo: El conjunto f = {(1, a), (2, b), (3, c), (1, b)} NO esuna funcion de X = {1, 2, 3} a Y = {a, b, c} porque 1 noesta asignado a un unico elemento de Y.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Dada una funcion f : X → Y, para cada x ∈ X existe ununico y ∈ Y tal que (x, y) ∈ f. Este valor unico y se denotapor f(x). En otras palabras, f(x) = y es otra forma deescribir (x, y) ∈ f.

Sea f definida por f(x) = x2. Esta definicion esta incompleta,hay que decir tambien que f : R → R. La imagen de f es R+.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

La grafica de una funcion f cuyo dominio e imagen sonsubconjuntos de los reales se obtiene trazando puntos en elplano que corresponden a los elementos de f.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

La funcion f de X a Y es uno a uno (o inyectiva), si paracada y ∈ Y existe a lo sumo un x ∈ X con f(x) = y.Equivalentemente, f : X → Y es inyectiva si para todo parax1, x2 ∈ X se cumple que

f(x1) = f(x2) =⇒ x1 = x2.

Ejemplo: f = {(1, b), (3, a), (2, c)} de X = {1, 2, 3} aY = {a, b, c, d} es uno a uno.

Ejemplo: f = {(1, a), (2, b), (3, a)} NO es uno a uno, ya quef(1) = a = f(3) y 1 6= 3.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Ejemplo: Probemos que f : N → N definida por f(n) = 2n+1es uno a uno. Supongamos f(n1) = f(n2). Entonces:

2n1 + 1 = 2n2 + 1

2n1 = 2n2

n1 = n2.

Si f es una funcion de X a Y y la imagen de f es todo elconjunto Y, se dice que f es sobre Y (o suryectiva).Equivalentemente, f : X → Y es sobre Y si para todo y ∈ Yexiste un x ∈ X tal que f(x) = y.

Ejemplo: la funcion f = {(1, b), (3, a), (2, c)} de X = {1, 2, 3}a Y = {a, b, c, d} NO es sobre, pero definida de X = {1, 2, 3}a Y ′ = {a, b, c} SI lo es.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Ejemplo: probar que f(x) = 1x2 de X = R−{0} a Y = R+ es

sobre Y. Debemos probar que: ∀y ∈ Y ∃x ∈ X tal quef(x) = y. Sustituyendo tenemos y = 1

x2 y despejandox = ± 1√

y. Entonces tomamos x = 1√

y(o x = − 1√

y).

Una funcion que es uno a uno y sobre se llama biyeccion.Ejemplo: la funcion f = {(1, b), (2, a), (3, c)} de X = {1, 2, 3}a Y = {a, b, c} es biyectiva.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Supongamos que f es una biyeccion de X a Y. Se puedeprobar que

{(y, x) | (x, y) ∈ f}

es una funcion biyectiva de Y a X. esta nueva funcion, que sedenota f−1, se llama inversa de f.

Sean g : X → Y y f : Y → Z. la composicion de f con g,denotada f ◦ g, es la funcion de X a Z definida por

(f ◦ g)(x) = f(g(x)).

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Ejemplo: si g = {(1, a), (2, a), (3, c)} de X = {1, 2, 3} a Y = {a, b, c} yf = {(a, y), (b, x), (c, z)} de Y = {a, b, c} a Z = {(x, y, z)}, entoncesf ◦ g = {(1, y), (2, y), (3, z)}.

Agustın G. Bonifacio Matematica Discreta

Induccion MatematicaConjuntosFunciones

Un operador binario sobre X es una funcion de X ×X a X.Ejemplo: sea X = N, entonces la funcion “suma”f(x, y) = x+ y es un operador binario.

Un operador unitario sobre X es una funcion de X a X.Ejemplo: sea U un conjunto universal. Si definimos f(X) = Xpara cada X ∈ P(U), entonces f es un operador unitariosobre P(U).

Agustın G. Bonifacio Matematica Discreta