Repaso Conjuntos

Cap´ıtulo 1

Preliminares

En esta parte repasaremos brevemente algunas nociones y notaciones que ser´an necesarias

para comprender adecuadamente el resto del material de este libro. Debe, sin embargo,

quedar claro que este repaso queda fuera del ´area de aut´omatas y lenguajes formales. Por otra

parte, no es nuestra intenci´on hacer una introducci´on para un lector que no tenga ninguna

base en matem´atica, especialmente en teor´ıa de conjuntos, sino que ´unicamente haremos

un repaso, ayudando al lector a detectar sus puntos d´ebiles, adem´as de recordar nociones

que pueden no estar frescas. Un objetivo adicional del presente cap´ıtulo es uniformizar la

notaci´on, que var´ıa bastante de libro a libro. Para los lectores que requieran una introducci´on

m´as exhaustiva a la teor´ıa de conjuntos y temas afines, recomendamos textos como [19].

1.1. Conjuntos

El fundamento m´as importante para el estudio de los lenguajes y aut´omatas es la Teor´ıa

de Conjuntos. En efecto, siempre que hablemos de “formalizar” una noci´on, estaremos diciendo

en realidad “expresar en t´erminos de la Teor´ıa de Conjuntos”. Es por esto que en este

cap´ıtulo presentamos los conceptos m´as b´asicos de dicha Teor´ıa de Conjuntos.

La idea de un conjunto como una colecci´on de individuos u objetos no es, para un

verdadero matem´atico, suficientemente precisa, y se parece a la noci´on de clase; sin embargo,

para nuestros prop´ositos es suficiente.

Un conjunto que vamos a utilizar con frecuencia es el de los n´umeros naturales, {1, 2, 3, . . .},

denotado por N.

Los conjuntos pueden expresarse de dos maneras b´asicamente:

En extensi´on, lo cual quiere decir que citamos expl´ıcitamente cada uno de sus elementos,

3

4 CAP´ITULO 1. PRELIMINARES

como en el conjunto {1, 3, 5} que contiene exactamente los n´umeros 1, 3 y 5.

En intenci´on, dando una descripci´on precisa de los elementos que forman parte del

conjunto, en vez de citarlos expl´ıcitamente. Por ejemplo, el conjunto del punto anterior

puede ser visto como {i 2 N|impar(i), i < 6}, donde se supone que los n´umeros impares

cumplen la condici´on impar(i).

Representamos a los conjuntos con letras may´usculas, como en A = {2, 4}. Los conjuntos

pueden contener conjuntos como elementos, como en B = {{a}, {b, c}}. El conjunto sin

elementos (vac´ıo) se representa por ; o bien por {}.

La notaci´on a 2 B significa que a es elemento o est´a contenido en el conjunto B; por

ejemplo, {2, 3} 2 {1, {2, 3}, 4}. Para indicar que a no est´a en B se escribe a 62 B.

El tama˜no de un conjunto es el n´umero de elementos que contiene, y se representa como

|A| para un conjunto A. Por ejemplo, el tama˜no de {a, b, c} es 3, y el tama˜no de ; es cero. Por

ejemplo, el tama˜no de {{a}, {b, c}} es 2 y no 3, pues tiene 2 elementos, siendo el primero {a}

y el segundo {b, c}. La definici´on de “tama˜no” parece muy clara, pero hay conjuntos que no

tienen un n´umero determinado de elementos; estos se llaman “infinitos” y ser´an discutidos

m´as adelante.

Dos conjuntos A y B son iguales, A = B, si y s´olo si tienen los mismos elementos, esto

es, x 2 A ssi x 2 B. 1 Por ejemplo, {1, {2, 3}} = {{3, 2}, 1}; vemos que en los conjuntos el

orden de los elementos es irrelevante.

Se supone que en los conjuntos no hay repeticiones de elementos, y que cada elemento del

conjunto es distinto de todos los otros elementos. Sin embargo, si decimos, por ejemplo, i 2 A,

j 2 A, no estamos suponiendo que i sea distinto de j, pues tanto i como j son elementos

cualquiera de A. Si necesitamos que sean distintos, hay que indicarlo expl´ıcitamente, como

en la expresi´on i, j 2 A, i 6= j.

La notaci´on A  B significa que el conjunto A est´a “contenido” en el conjunto B, o m´as

t´ecnicamente, que A es subconjunto de B. Por ejemplo, el conjunto {a, c} es subconjunto

de {a, b, c}, indicado como {a, c}  {a, b, c}. En otras palabras, A  B cuando siempre que

x 2 A, tenemos tambi´en x 2 B. Obs´ervese que de acuerdo con esta definici´on, A  A para

cualquier conjunto A: todo conjunto es subconjunto de s´ı mismo. Un caso extremo es el

conjunto vac´ıo, que es subconjunto de cualquier conjunto.

Para indicar que un subconjunto contiene menos elementos que otro, es decir, que es un

subconjunto propio de ´este, se escribe A  B. Por ejemplo, {a, c}  {a, b, c}. Claramente,

A = B ssi A  B y B  A. Obs´erverse tambi´en que si A  B, entonces |A|  |B|, y si

A  B, entonces |A| < |B|.

Las relaciones de inclusi´on entre conjuntos se acostumbran representar gr´aficamente mediante

los llamados “diagramas de Venn”, que denotan mediante ´areas cerradas (por ejemplo

1“A ssi B” se lee “A si y s´olo siB”, y significa que A implica B y tambi´en B implica A.

1.1. CONJUNTOS 5

C A B

Figura 1.1: Diagrama de Venn

elipses) los conjuntos. Por ejemplo, en la figura 1.1 se ilustra la situaci´on donde un conjunto

A es subconjunto de B, y B es subconjunto de C.

En los diagramas de Venn es f´acil visualizar relaciones que de otra forma pueden parecer

complejas; por ejemplo, si un conjunto A es subconjunto de B y ´este es subconjunto de C,

se espera que A  C, como se aprecia intuitivamente en la figura 1.1, pues el ´area de A

est´a obviamente contenida dentro de la de C.

1.1.1. Operaciones

Llamamos operaciones a formas est´andar de combinar o transformar objetos matem´aticos.

Por ejemplo, una operaci´on habitual es la suma, que en la expresi´on “3 + 7” combina los

objetos 3 y 7 dando como resultado el objeto 10. El 3 y el 7, que son los objetos que se

combinan, son los operandos, el “+” es la operaci´on, y el 10 es el resultado. Una operaci´on

es binaria cuando tiene dos operandos. Es unaria si tiene un s´olo operando, como en la

operaci´on de la ra´ız cuadrada.

Una operaci´on “

” es conmutativa si x

y = y

x, como es el caso de la suma o la

multiplicaci´on de n´umeros. Se dice que es asociativa si x

(y

z) = (x

y)

z; por ejemplo,

la suma es asociativa, pero no la resta, pues podemos ver que 8 − (4 − 3) 6= (8 − 4) − 3.

1.1.2. Operaciones con conjuntos

Sean A y B conjuntos. Se definen las siguientes

...