Tema 1: Conceptos Preliminares

Conjuntos, aplicaciones.

Conjunto: colección de objetos. Tiene que estar claro qué elementos pertenecen a él. Un objeto no puede estar repetido (A).

Elemento: cada uno de los objetos del conjunto (x).

Pertenece a: cuando un elemento está en un conjunto se dice que x pertenece a A (xA).

Un conjunto se describe o se define:

• Por extensión: diciendo cuáles son todos y cada uno de sus elementos. Se escriben esos elementos entre llaves y separados por comas.

• Por comprensión: diciendo cuáles son las propiedades que cumplen los elementos de ese conjunto.

Un conjunto A se dice que es subconjunto de otro conjunto U si cada elemento de A pertenece a U. Se escribe A"U y se dice “A contenido en U” ó “A subconjunto de U”.

A"U ! (xA !xU)

Sea U un conjunto consideramos A,B"U:

• Se llama intersección de A y B al conjunto A"B = {xU; xA, xB}

• Se llama unión de A y B al conjunto A"B = {xU; xA ó xB}

• Se llama complementario de A (en U) al conjunto A' = Ac = {xU; x"A}

• Se llama diferencia de A y B o “A menos B” al conjunto A\B = {xA; x"B}= A"Bc

• Se llama diferencia simétrica de A y B al conjunto A"B = (A"B)\(A"B)

Propiedades: suponemos A,B,C"U:

Asociativa: A"(B"C) = (A"B)"C

A"(B"C) = (A"B)"C

Conmutativa: A"B = B"A

A"B = B"A

Elemento neutro: A"" = A

A"U = A

A"U = U

A"" = "

Distributiva: A"(B"C) = (A"B)"(A"C)

A"(B"C) = (A"B)"(A"C)

"c = U

Uc = "

Leyes de Morgan: (A"B)c = Ac"Bc

(A"B)c = Ac"Bc

Nota: Dos conjuntos son iguales cuando tienen exactamente los mismos elementos:

A = B ! A"B y B"A (doble contenido)

Dado un conjunto A se llama conjunto de las partes de A (o booleano de A) al conjunto P(A) = {B; B"A} (los elementos son subconjuntos de A).

Si A tiene n elementos, P(A) tiene 2n elementos.

Si A1, A2, …, An son conjuntos, se llama producto cartesiano de esos conjuntos al conjunto A1xA2x…xAn cuyos elementos son todas las posibles n-tuplas (a1,a2,…,an) con aiAi Vi.

A1xA2x…xAn = {(a1,a2,…,an); a1A1,…,anAn}

El número de elementos del producto cartesiano es igual al producto del número de elementos de cada uno de sus factores.

Dado un conjunto A se llama partición de A a un conjunto de subconjuntos de A, {Ai, iI} = {A1,…, An} de modo que se cumplan las siguientes condiciones:

Ai"Aj = " Vi"j (la intersección de dos de ellos es el vacío).

UiIAi = A (la unión de todos ellos es igual a A).

Dados dos conjuntos, A y B, se llama aplicación de A en B a una ley o un criterio que asigna a cada elemento de A un elemento y sólo uno de B. Esta definición no es correcta desde el punto de vista matemático.

Una aplicación de A en B es un subconjunto f del producto cartesiano AxB del que para cada aA existe un único bB con (a,b)f.

Se escribe:

f: A!B

Propiedades que se tienen que cumplir: f"A tal que

Si aA, existe bB tal que (a,b)f, es decir, cada elemento tiene una imagen.

Si (a,b)f y (a,b')f, entonces b = b', es decir, esa imagen es única.

El conjunto A se llama conjunto de partida.

El conjunto B se llama conjunto de llegada.

Si aA, entonces el elemento bB que se le asigna por la aplicación f se denota f(a) (diríamos f(a) = b) y se llama imagen de a.

Si bB puede ocurrir que:

b sea imagen de algún elemento de A: si b = f(a) se dice que a es una antiimagen de b.

b no sea imagen de ningún elemento de A.

Si A1"A entonces se llama imagen de A1 al conjunto f(A1) = {f(a); aA1}.

Si B1"B entonces se llama antiimagen de B1 al conjunto f!(B1) = {aA1; f(a)B1}. (Puede ser f!(B1) = ").

Dada una aplicación f: A!B se dice que:

• f es inyectiva si se cumple que en A no y dos elementos distintos que tengan la misma imagen:

• si a1,a2A y a1"a2 !f(a1)"f(a2)

• si f(a1) = f(a2) !a1 = a2

• f se dice que es suprayectiva si para cada bB existe algún aA tal que f(a) = b (a todos los elementos de B les llega alguna flecha).

• f se dice biyectiva si es inyectiva y suprayectiva.

(número de elementos de A = número de elementos de B).

Si f: A!B y g: B!C son dos aplicaciones se llama composición de f y g ó g compuesta con f a la aplicación:

g%f: A!C dada por (g%f)(a) = g(f(a))

Proposición: la composición de aplicaciones tiene la propiedad asociativa.

f: A!B g: B!C h: C!D h%(g%f) = (h%g)%f

aplic. de A en D aplic. de A en D

f g h

A!B!C!D

Proposición:

Si f: A!B y g: B!C son aplicaciones inyectivas, entonces g%f es inyectiva.

Si f: A!B y g: B!C son aplicaciones suprayectivas, entonces g%f es suprayectiva.

Si f: A!B y g: B!C son aplicaciones biyectivas, entonces g%f es biyectiva.

Si g%f es inyectiva, entonces f es inyectiva.

Si g%f es suprayectiva, entonces f es suprayectiva.

f: A!B aplicación si B1"B f!(B1) = {aA1; f(a)B1}

f! no es una aplicación de B en A (generalmente)

f! es una aplicación P(B) ! P(A)

Si f es inyectiva, se puede construir la aplicación f-1: B!A dada por f-1(b) es el único elemento de A cuya imagen por f es b.

Es fácil comprobar que f-1%f: A!A f%f-1: B!B

a!a b!b

La aplicación A!A se llama aplicación identidad y se escribe 1A.

a!a

Dados dos conjuntos, A y B, se dice que el cardinal del conjunto A es menor o igual que el cardinal de B si existe alguna aplicación inyectiva f: A!B se denota |A| " |B|.

Se puede demostra que si existe f: A!B inyectiva y existe g: B!A inyectiva, entonces existe h: A!B biyectiva.

Se dice que A y B tienen el mismo cardinal si existe una aplicación biyectiva de A en B.

Un conjunto A se dice que tiene cardinal infinito si existe algún subconjunto A1"A, A1"A, de modo que |A1| = |A|.

Cardinal = número de elementos del conjunto.

Relaciones binarias: Relaciones de equivalencia, relaciones de orden.

Dado un conjunto A se llama relación binaria en A a un subconjunto R de AxA.

Si (a,b)!, escribiremos aR b y leeremos “a relacionado con b”.

Propiedades que puede tener una relación binaria:

Reflexiva: se dice que la relación binaria R en el conjunto A es reflexiva si aR a VaA.

Simétrica: se dice que la relación binaria R en el conjunto A es simétrica si se cumple aR b ! bR a VaA.

Antisimétrica: se dice que la relación binaria R en el conjunto A es antisimétrica si se cumple: aR b y bR a !a = b.

Transitiva: se dice que la relación binaria R en el conjunto A es transitiva si se cumple aR b y bR c ! aR c.

Una relación binaria R en un conjunto A se dice que es relación de equivalencia si es reflexiva, simétrica y transitiva.

Establecer una relación de equivalencia es establecer una partición.

Si (A,R) es un conjunto con una relación de equivalencia para cada xA, se llama clase de equivalencia de x al subconjunto de A[x] = {aA; xR a}.

Las clases de equivalencia son los subconjuntos de A formados por todos los elementos que dan la misma imagen.

Proposición:

Si x e y son dos clases de equivalencia [x] = [y] ó [x]"[y] = ", es decir, dos clases de equivalencia distintas no tienen ningún elemento en común.

"xA[x] = A. La unión de todas las clases de equivalencia es todo el conjunto.

Conclusión: {[x]; xA} es una partición de A.

Si x'[x], entonces [x'] = [x].

Sea {Ai " 0, iI} una partición del conjunto A. Entonces, en A podemos definir una relación de equivalencia cuyas clases de equivalencia sean los trozos Ai (trozos de la partición).

Si R es una relación de equivalencia en A, el conjunto de las clases de equivalencia se denota A/R (A sobre R) y se llama “conjunto cociente” (= conjunto de los “trozos”).

A\R = {[x]; xA}

Los elementos del conjunto cociente son clases de equivalencia de A, luego son subconjuntos de A.

Una relación binaria R, en un conjunto A, se dice que es relación de orden si es (reflexiva) antisimétrica y transitiva.

A la relación de orden se le suele llamar, en general, ".

Sea (A,") un conjunto ordenado y B"A.

• Un elemento aA se dice que es cota superior de B si b"a VbB.

• Un elemento aA se dice que es cota inferior de B si a"b VbB.

• Un elemento aA se dice que es máximo en B si es cota superior de B y además está en B.

• Un elemento aA se dice que es mínimo en B si es cota inferior de B y además está en B.

• Se llama supremo de B al mínimo del conjunto de las cotas superiores de B.

• Se llama ínfimo de B al máximo del conjunto de las cotas inferiores de B.

• Un elemento aA se dice que es maximal en B si: aB y a"b con bB ! b = a (ningún elemento de B “está por encima” de él).

• Un elemento aA se dice que es minimal en B si: aB y no tiene ningún elemento de B que esté “por debajo” de él.

Si existe máximo, ese es el único maximal.

El conjunto ordenado se dice que es totalmente ordenado si para cualesquiera a,bA se cumple a"b ó b"a.

Proposición: Sea un conjunto ordenado (A,"), B subconjunto de A.

Si B tiene algún máximo, es único.

Si B tiene algún mínimo, es único.

Un conjunto ordenado (A,") es “bien ordenado” si cada subconjunto no vacío de A tiene mínimo (primer elemento).

Observación: Si (A,") es bien ordenado, entonces es totalmente ordenado.

Si a1,a2A (a1"a2), consideramos el subconjunto de A {a1,a2}. Como A es bien ordenado, ese subconjunto tiene mínimo a1"a2 ó a2"a1.

Axioma de elección: Dado un conjunto no vacío, A, existe alguna aplicación:

f: P(A)\" ! A

B ! f(B) B

Para cada subconjunto no vacío de A, se puede elegir un elemento del subconjunto.

Principio de buena ordenación: (Axioma) Todo conjunto no vacío admite una buena ordenación, es decir, es bien ordenado.

Nota: El axioma de elección y el principio de buena ordenación son equivalentes.

Dado un conjunto ordenado (A,") se llama cadena en A a cualquier subconjunto B de A tal que (B,") es bien ordenado.

Principio de inducción: (teorema que a veces se toma como axioma).

Si S"! y se verifican:

1S

Si nS, entonces n+1S (supongamos que nS y veamos que entonces n+1S)

Entonces, S = !.

Un conjunto ordenado (A,") se dice que es inductivo si para cada cadena de ese conjunto existe alguna cota superior.

Lema de Zorn (Axioma): Todo conjunto inductivo posee algún elemento maximal. Es equivalente al axioma de elección y al principio de buena ordenación.

Operaciones:

Dado un conjunto no vacío, A, se llama operación binaria interna en A a cualquier aplicación f: AxA ! A se suele denotar f(a,b) = a*b (operación estrella) y se lee a

a,b ! a*b

estrella b.

Si B"A y * es una operación binaria interna en A, se dice que B es estable para la operación *, si b1*b2B Vb1,b2B.

Propiedades que puede tener una operación interna:

• Conmutativa: a*b = b*a Va,bA.

• Asociativa: (a*b)*c = a*(b*c)

• Elemento neutro: un elemento eA tal que a*e = a = e*a. El neutro, si existe, es único.

• Un elemento aA se dice que es inversible si existe otro bA de modo que a*b = b*a = e.

b se dice que es inversa de a.

- en el caso de la suma b = -a y se llama opuesto.

- en el caso del producto b = a-1.

Si * es asociativa, si a tiene inverso, el inverso es único.

(A,*) un conjunto con una operación interna y R una relación de equivalencia en A.

Se dice que * es compatible con R si se cumple:

a R a'

b R b' ! a*b R a'*b'

Si * y R son compatibles, entonces la operación * se hereda en A/R.

[a]*[b] = [a*b]

En general, !n = !/n!

Dados dos conjuntos, A y K se llama operación externa con dominio de operadores en K a cualquier aplicación

KxA ! A

(t,a) ! t·a

ta

KxA ! A una operación externa y R una relación de equivalencia en A.

Se dice que la operación externa es compatible con la relación de equivalencia R si se cumple: aR a' !taR ta' Vt!.

En ese caso, queda definida una relación de equivalencia en el conjunto cociente:

K x A/R ! A/R

(t,[a]) ! [ta]

Para que esté bien definido, siendo [a] = [a'] ! [ta] = [ta']

[a] = [a'] ! a R a' ! ta R ta' ! [ta] = [ta']

Estructuras algebraicas: grupos y anillos.

Un grupo es un conjunto, G, con una operación binaria interna, *, que es asociativa, tiene elemento neutro y cada elemento de G tiene inverso.

Grupo simétrico: Consideramos el conjunto {1,2,…,n} y consideramos todas las aplicaciones biyectivas (permutaciones) de ese conjunto en sí mismo. Lo denotamos Sn.

En Sn consideramos la operación composición (es interna, asociativa y tiene elemento neutro (la identidad), cada elemento tiene inverso).

(Sn,·) es un grupo, |Sn| = n!.

Un grupo se dice que es abeliano cuando la operación es conmutativa.

Un anillo es un conjunto, A, con dos operaciones binarias internas, + y ·, de modo que:

(A,+) es un grupo abeliano. (El neutro de la operación suma se llama cero y se escribe 0). (El inverso respecto de la suma de un elemento se llama opuesto de a y se escribe -a).

La operación · es asociativa.

La operación · es distributiva respecto de la suma:

a·(b+c) = a·b + a·c Va,b,cA

(b+c)·a = b·a + c·a

Si la operación · tiene elemento neutro, se llama identidad y se escribe 1. En tal caso, se dice que es un anillo con identidad.

Si tiene identidad y es conmutativo, se dice que es un anillo conmutativo con identidad.

En un anillo (A,+,·) se dice que un elemento aA, (a"0) es divisor de cero si existe bA tal que a·b = 0 con b"0.

Dominios de integridad; divisibilidad.

Un anillo conmutativo, con identidad y sin divisores de cero, se llama dominio de integridad.

En un anillo con identidad, un elemento se dice que es una unidad si tiene inverso (se dice que bA es inverso de aA si a·b = b·a = 1)

• Si a·b = 1 se dice que b es inverso a derecha de a.

• Si b·a = 1 se dice que b es inverso a izquierda de a.

Un dominio de integridad en el que todos los elementos salvo el 0 son unidades se llama cuerpo.

Si es (K,+,·) cuerpo:

(K,+) es grupo abeliano

· es asociativa y conmutativa

· tiene elemento neutro, 1

Para cada tK, t"0, existe sK tal que t·s = s·t = 1 (se escribe s = t-1)

Un divisor de cero no puede ser unidad.

Propiedades en un anillo: (A,+,·) anillo:

(-a)·b = a·(-b) = -(a·b) Va,bA

(-a)·(-b) = a·b Va,bA

a·0 = 0 = 0·a VaA

Los anillos ! y K[x] (K un cuerpo)

Algoritmo de la división: Dados n,m!, existen q,r! tales que n = q·m + r de modo que |r| < |m|

Dados f(x),g(x)K[x] existen q[x] y r[x]  K[x] tales que f(x) = g(x)·q(x) + r(x), siendo gr(r(x)) < gr(g(x)).

Esos polinomios q(x) y r(x) son únicos.

A es un dominio de integridad (!,K[x])

Dados a,bA se dice que a divide a b, a es divisor de b o que b es múltiplo de a si existe cA tal que a·c = b. Se escribe a|b.

Dados a1,…,arA, se llama máximo común divisor de a1,…,ar a cualquier elemento de A que cumpla

d|a: Vi = 1,…,r si d'|ai Vi = 1,…,r ha de ser d'|d

Se escribe d = m.c.d.(a1,…,ar)

Se llama mínimo común múltiplo de a1,…,ar a cualquier mA tal que

ai|m Vi = 1,…,r y si ai|m' Vi entonces m|m'

Se escribe m = m.c.m.(a1,…,ar).

¿Cómo se hallan el mc.d. y el m.c.m.?

Dado un dominio de integridad, A, y un subconjunto no vacío de A, J, se dice que J es un ideal de A si se cumple:

a+bJ Va,bJ

r·aJ VaJ VrA

Nota: en ! va a ocurrir que cualquier ideal que tengamos va a ser el conjunto de los múltiplos de un número. Lo mismo va a pasar en K[x].

Un ideal, J, de un dominio de integridad A se dice que es ideal principal si es el conjunto de los múltiplos de un elemento.

J = {r·a; rA} Se escribe J = (a)

Se dice que un conjunto X es un sistema generador de un ideal, J, si X"J y además, para cada aJ y además, para cada aJ existen x1,…,xmX tales que a = r1x1 +…+ rmxm con riA Vi.

A = dominio de integridad J ideal X = {x1,…} J = {r1x1 +…+ rmxm}

Nota: el 0 siempre está en el ideal.

Teorema: En ! o en K[x] todos los ideales son principales.

El m.c.d. y el m.c.m. de {a1,…,ar} no son únicos, en general.

En ! se elige el m.c.d. y el m.c.m. con coeficinet ede mayor grado (coeficiente director) = 1.

Polinomio mónico: es aquel que tiene coeficiente director 1.

En ! y en K[x], todos los ideales son principales. Si J es ideal, existe dJ tal que J = (d) (" el conjunto de los múltiplos de d).

En !, podemos elegir d>0. En K[x] podemos elegir el mónico.

Supongamos que f1,…,fr! ó K[x]. Consideramos el ideal, J, generado por f1,…,fr (el ideal más pequeño que contiene a f1,…,fr).

J = {a1f1 + … + arfr; ai! ó K[x]}

Dado ese J, existirá d! positivo ó K[x] mónico tal que J = (d).

En esa situación: d|fi Vi (porque fiJ).

Además, si d'|fi Vi, entonces fi(d') Vi y por tanto J"(d') y así d(d'), o sea, d'|d.

Teorema (Identidad de Bezout): Si f1,…,fr! ó K[x]y d = m.c.d.(f1,…,fr), entonces existen g1,…,gr! ó K[x] tales que d = g1f1 + … + grfr.

Cómo hallar el m.c.d. de 3548 y 126:

Se divide uno entre el otro: 3548 = 28·126 + 20

Se divide divisor entre el resto

126 = 6·20 + 6

20 = 3·6 + 2

6 = 3·2 + 0

El último resto no nulo es el m.c.d.. Además, “despejando hacia atrás” obtenemos la expresión del m.c.d. en términos de los números iniciales (obtenemos g1, g2 tales que g1f1 + g2f2 = d).

2 = 20 - 3·6 = 20 - 3·(126 - 6·20) = 19·20 - 3·126 = 19·(3548 - 28·126) - 3·126 =

= 19·3548 - 535·126