Conjuntos, Aplicaciones, Relaciones:

Conceptos primarios (sin definición): Conjuntos, elemento, pertenece

Teoría de conjuntos

Las reglas del juego (sin demostrar) se llaman axiomas.

Otros conceptos primarios: Objetos, flechas, composición Teoría de categorías

Notación:

a es un elemento de A a " A

a no es un elemento de A a " A

Definiciones:

A está contenido en (o es un subconjunto de ) un conjunto B si todos los elementos de A son elementos de B A " B

A no está contenido en (o no es un subconjunto de ) un conjunto B si hay algún elemento de A que no está en B A " B

Axioma (del vacío) :

Existe un conjunto que no tiene elementos, lo llamamos conjunto vacío Ø

Teorema:

Si A y B son conjuntos que no tienen elementos, entonces A = B

- D -

A " B

Si demostramos que A " B es falso, entonces A " B es cierto.

Como A no tiene elementos, no hay ningún elemento de A que no esté en B A " B

B " A

Si demostramos que B " A es falso, entonces B " A es cierto.

Como B no tiene elementos, no hay ningún elemento de B que no esté en A B " A

Conclusión A=B

Pregunta: ¿Es el vacío un elemento de todo conjunto?

NO, porque Ø " Ø ya que Ø no tiene elementos.

Teorema:

El vacío está contenido en todo conjunto. Si A es cualquier conjunto entonces Ø " A

- D -

Reducción al absurdo

Suponemos que " un conjunto A tq. Ø no es subconjunto suyo "x " Ø tq. x " A "x " Ø (Absurdo)

Axioma (del par):

Si A y B son conjuntos, " un conjunto que tiene como elementos a A y a B, a este nuevo conjunto lo denotaremos {A,B}. Si cogemos A=B escribimos {A}

Ejemplillo :

A= Ø , hacemos un nuevo conjunto {Ø}, a su vez {{Ø}}, {Ø,{Ø}}

Ø " {Ø,{Ø}}

Ø " {{Ø}}

Ø " {{Ø}}

{a,b} " (a,b) porque (a,b) = {a,{a,b}} y b " (a,b)

nota: y a su vez (b,a) = {b,{b,a}}

Axioma: (de la unión)

Si A es un conjunto (cuyos elementos son conjuntos) " un conjunto U cuyos elementos están caracterizados por la siguiente propiedad: x " U si " a " A tq. x " a.

Ejercicio:

A = { Ø, {Ø} }

U= { Ø }

U= Ua Unión de los elementos de A

a"A

Si A tiene dos elementos x,y U = x U y

Ejercicio:

Dar un conjunto con tres elementos.

A= { Ø , { Ø }} B={A}

AUB = { Ø , { Ø }, A}

Ø notación = 0

{Ø} = 1

{Ø,{Ø}} = 2 = {Ø,1} A estos conjuntos se les llama nºs naturales

{Ø,1,2} = 3 = 2 U {2}

{Ø,1,2,3} = 4 = 3 U {3}

Podemos dar un conjunto listando todos sus elementos (por extensión).

Axioma: (del infinito)

Existe un conjunto N cuyos elementos son los nºs naturales.

Axioma: (de comprensión)

Si A es un conjunto y P es una propiedad referida a los elementos de A entonces " un conjunto cuyos elementos son los elementos de A que cumplen la propiedad P.

{x " A tq. x cumple P} y si P´ = ø P formamos otro {x " A tq. x cumple P´ } Así podemos dar un conjunto por comprensión.

Axioma: (de las partes)

Si A es un conjunto " un conjunto P(A) cuyos elementos son los subconjuntos de A. Si A tiene n elementos P(A) tiene 2 elementos.

Ejemplo:

A= {ø,{ø},{{ø}} }

P(A)= {ø, {ø} , {{ø}} , {{{ø}}} , {ø,{ø}} , {ø,{{ø}}} , {{ø},{{ø}}} , A}

Operaciones con conjuntos:

Unión:

x " A U B si x " A o x " B o x pertenece a A y a B

Intersección:

x " A " B si x " A y x " B

A " B = { x " A U B tq. x " A y x " B} = { x " A tq. x " B}ç

Diferencia conjuntista:

A \ B = { x " A tq. x " B}

2 \ 5 = 0

5 \ 2 = {2,3,4}

Producto cartesiano:

A x B es un conjunto con elementos los pares (a,b) tales que a " A y b " B

2 x 2 ={(0,0),(0,1),(1,0),(1,1)} " 4

2 x 1 ={(0,0),(1,0)} " 2 1 x 2 = {(0,0),(0,1)} " 2

Aplicaciones:

Una aplicación f consiste de:

Un conjunto ha llamado dominio de f.

Un conjunto B llamado codominio de f.

Un conjunto Gf llamado gráfica de f que cumple que es un subconjunto de A x B, es decir Gf " A x B, " elemento x " A " un único elemento y " B tq. (x,y) " Gf.

Notación:

f

A ! B

f : A ! B

y = f(x) se llama imagen por la aplicación f de x

Igualdad de aplicaciones:

Mismo dominio, codominio y gráfica.

N ! N no es lo mismo que N ! Z

x ! x² x ! x²

Composición de aplicaciones:

f g

A ! B ! C

gof

El dominio de gof es el dominio de f (es decir A)

El codominio de gof es el codominio de g (es decir C)

(gof)(x)=g(f(x)) para cualquier x " A

Ejemplo:

f g

1

g(f(1))= l =(gof)(1)

g(f(2))= l =(gof)(2)

g(f(3))= n =(gof)(3)

Propiedades:

Es asociativa:

f g h f g h

A ! B ! C ! D A ! B ! C ! D

gof hog

ho(gof) (hog)of

Si tenemos tres aplicaciones que se puedan componer se da esta igualdad

ho(gof) = (hog)of Son las mismas porque tienen los mismos dominios y codominios, ahora hay que preguntarse si tienen la misma gráfica.

Para cualquier x " A ¿ (ho(gof))(x) = ((hog)of)(x)?

((hog)of)(x)=(hog)(f(x))=h(g(f(x)))

(ho(gof))(x)=((hog)of)(x)=h(g(f(x)))

Existencia de Identidades:

Cada conjunto X determina una aplicación especial llamada identidad 1dx. Su dominio es X, su codominio es X también.

1dx: X ! X

x ! x

Hay también identidades como conjuntos. Dada una aplicación cualquiera f : AB si componemos 1dB o f = f y si componemos f o 1dA = f

Inclusiones:

Son aplicaciones especiales. Si X " A podemos definir la inclusión de X en A cuyo dominio es X y su codominio es A y cuya gráfica es la misma que la de la identidad.

i

X ! A

x ! x El concepto análogo al de igualdad es Isomorfos

Isomorfismo:

Es una aplicación f: A ! B tq. " otra aplicación g: B ! A con las propiedades gof = 1dA y fog = 1dB

Proposición:

Si f: A ! B es un isomorfismo y g,h: B ! A son tales que

gof = hof = 1dA

Entonces h = g

fog = foh = 1dB

- D -

fog = 1dB

ho(fog) = ho1dB = h

asociativa h = g

(hof)og = go1dA = g

Inversa:

Si f: A!B y

fof-¹ = 1dB

f-¹:B!A

f-¹of = 1dA

Propiedad:

Si f:A!B y g:B!C son isomorfismos gof es un isomorfismo

Quiero encontrar la inversa de gof que es (gof)-¹: C ! A = f-¹ o g-¹

Propiedad:

Si f es un isomorfismo entonces si dos elementos del dominio tienen la misma imagen son iguales. Si f: A!B es un isomorfismo entonces " u, v " A f(u)=f(v) se tiene u = v. Las aplicaciones que cumplen esta propiedad son aplicaciones inyectivas.

- D -

Sabemos que existe f-¹ : B!A tq f f-¹=1dA y f-¹ f=1dB

Supongamos u,v " A tq. f(u) = f(v)

f-¹ (f(u))=( f-¹ of)(u) = 1dx(u) = u

f-¹ (f(u))=( f-¹ of)(v) = 1dx(v) = v

Si f: A!B es un isomorfismo entonces " elemento  " B " un u " A tq. f(u) = . Estas aplicaciones son sobreyectivas (cuando todo elemento del codominio es imagen de alguien del dominio)

Teorema:

Una aplicación f es un isomorfismo si y solo si es inyectiva y sobreyectiva. Si f es inyectiva y sobreyectiva entonces es un isomorfismo (biyectiva).

- D -

Sabemos que a, b " A y f(a)=f(b) a = b

"x " B "! a " A tq. f(a) = x (Biyectiva)

Sabemos que "x " B " a " A tq. f(a) = x

Cardinal:

El cardinal de un conjunto es el nº de elementos del conjunto.

Aplicación imágenes directa e inversa:

f" : P(X) ! P(Y)

f* : P(Y) ! P(X)

f"(A) = {y " Y; "a " A con f(a) = y} Imagen directa de A por f

f*(B) = { x " X; f(x) " B} Imagen inversa de B

f"(Ø) = Ø

f*(Ø) = Ø

f"(X) " Y

f*(Y) = X

Ejemplo:

X f Y

a 0

b 1 2

P(X)={Ø,X,{a},{b}}

P(Y)={Ø,Y,{0},{1},{2},{0,1},{0,2},{1,2}}

f"(Ø) = Ø f"(X) = {Ø}

f"({a}) ={ Ø} f"({b}) = {Ø}

f*(Ø) = Ø f*(Y) = X

f*({Ø}) = X f*({1}) = Ø

f*({2}) = Ø f*({0,1}) = X

f*({0,2}) = X f*({1,2}) = Ø

Construcción de cocientes:

Partición

Sea X un conjunto, una partición de X es un conjunto P " P(X) tq.

1) Si A,B " P, A " B entonces A " B = Ø

2) U A = X

a " P

Ø " P

Proy: X ! P

x ! el único elemento A " P tq. x " A

Relación de equivalencia:

Una relación de equivalencia R en un conjunto X es un subconjunto R " XxX con las siguientes propiedades:

1) "x " X (x,x) " R reflexiva "x " X x R x

2) Si (x,y) " R entonces (y,x) " R simétrica x R y y R x

3) Si (x,y),(y,z) " R (x,z) " R transitiva x R y, y R z x R z

Teorema:

Dar una partición en un conjunto X es equivalente a dar una relación de equivalencia en X.

Definición:

Sea R una relación de equivalencia en X. La clase de equivalencia respecto de la relación R va a ser un subconjunto formado por los elementos que tienen la propiedad de estar relacionados con él.

x " X [x]R = {y " X; xRy}

Los elementos de PR son las clases de equivalencia de los elementos de x (respecto a R)

Terminología:

Si R es una relación de equivalencia en x, PR = conjunto cociente de x por R y se suele denotar X/R. Proy (x) = [x]R

Ejemplo:

n ~5 m si n-m es múltiplo de 5

3 ~5 18 3 -18= -15 es múltiplo de 5, luego sí están relacionados. Y es una relación de equivalencia. Hay que probar la propiedad reflexiva, simétrica y transitiva.

Probamos la reflexiva: (n-n)=0 = 5*0 luego es múltiplo de 5.

• Calcular la partición asociada a la relación de equivalencia (calcular el conjunto cociente asociado a la relación de equivalencia).

Z/~5 = {[0]~ 5,[1]~ 5,[2]~ 5, [3]~ 5,[4]~ 5} los elementos de aquí son subconjuntos de Z

Clase del 0 [0]~ 5 = { n " Z; n es un múltiplo de 5}={0,5,10,15,....,-5,-10,-15....}

Clase del -1 [-1]~ 5 = { n " Z; n~ -1}={-1,4,9,....,-6,-11,-16....}

Notación: Z/~5 = Z5 (los elementos de Z 5 son partes de Z)

[4]~5=[-1]~5

Propiedad universal de proyección:

Sea X un conjunto y R una relación de equivalencia en X. La propiedad universal dice que dar una aplicación en un cociente en un conjunto cualquiera a dar una aplicación desde X en Y con la propiedad tal que f(a) = f(b) si a ~r b

Dar f´ : X/R y a dar f: X y tq. f(a) = f(b) si a ~r b

X proyección X/R

f f´

y 2 elementos relacionados tengan la misma imagen

1

2

3

a

b

c

l

m

n