prueba

Cap´
ıtulo 1
Preliminares
En esta parte repasaremos brevemente algunas nociones y notaciones que ser´n necesarias
a
para comprender adecuadamente el resto del material de este libro. Debe, sin embargo,
quedar claro que este repaso queda fuera del ´rea de aut´matas y lenguajes formales. Por otra
a
o
parte, no es nuestra intenci´n hacer una introducci´n para un lector que no tenga ningunao
o
base en matem´tica, especialmente en teor´ de conjuntos, sino que unicamente haremos
a
ıa
´
un repaso, ayudando al lector a detectar sus puntos d´biles, adem´s de recordar nociones
e
a
que pueden no estar frescas. Un objetivo adicional del presente cap´
ıtulo es uniformizar la
notaci´n, que var´ bastante de libro a libro. Para los lectores que requieran una introducci´n
o
ıa
om´s exhaustiva a la teor´ de conjuntos y temas afines, recomendamos textos como [19].
a
ıa

1.1.

Conjuntos

El fundamento m´s importante para el estudio de los lenguajes y aut´matas es la Teor´a
a
o
ı
de Conjuntos. En efecto, siempre que hablemos de “formalizar” una noci´n, estaremos dio
ciendo en realidad “expresar en t´rminos de la Teor´ de Conjuntos”. Es por esto que en este
e
ıacap´
ıtulo presentamos los conceptos m´s b´sicos de dicha Teor´ de Conjuntos.
a a
ıa
La idea de un conjunto como una colecci´n de individuos u objetos no es, para un
o
verdadero matem´tico, suficientemente precisa, y se parece a la noci´n de clase; sin embargo,
a
o
para nuestros prop´sitos es suficiente.
o
Un conjunto que vamos a utilizar con frecuencia es el de los n´meros naturales,{1, 2, 3, . . .},
u
denotado por N.
Los conjuntos pueden expresarse de dos maneras b´sicamente:
a

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

CAP´
ITULO 1. PRELIMINARES

4

como en el conjunto {1, 3, 5} que contiene exactamente los n´meros 1, 3 y 5.
u
En intenci´n, dando una descripci´n precisa de los elementos que forman partedel
o
o
conjunto, en vez de citarlos expl´
ıcitamente. Por ejemplo, el conjunto del punto anterior
u
puede ser visto como {i ∈ N|impar(i), i < 6}, donde se supone que los n´meros impares
cumplen la condici´n impar(i).
o
Representamos a los conjuntos con letras may´sculas, como en A = {2, 4}. Los conjuntos
u
pueden contener conjuntos como elementos, como en B = {{a}, {b, c}}. Elconjunto sin
elementos (vac´ se representa por ∅ o bien por {}.
ıo)
La notaci´n a ∈ B significa que a es elemento o est´ contenido en el conjunto B; por
o
a
ejemplo, {2, 3} ∈ {1, {2, 3}, 4}. Para indicar que a no est´ en B se escribe a ∈ B.
a
El tama˜o de un conjunto es el n´mero de elementos que contiene, y se representa como
n
u
|A| para un conjunto A. Por ejemplo, el tama˜o de {a, b, c} es3, y el tama˜o de ∅ es cero. Por
n
n
ejemplo, el tama˜o de {{a}, {b, c}} es 2 y no 3, pues tiene 2 elementos, siendo el primero {a}
n
y el segundo {b, c}. La definici´n de “tama˜o” parece muy clara, pero hay conjuntos que no
o
n
tienen un n´mero determinado de elementos; estos se llaman “infinitos” y ser´n discutidos
u
a
m´s adelante.
a
Dos conjuntos A y B son iguales, A = B, si y s´losi tienen los mismos elementos, esto
o
es, x ∈ A ssi x ∈ 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 ∈ A,
j ∈ A, no estamos suponiendo que i seadistinto 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´n i, j ∈ A, i = j.
o
La notaci´n A ⊆ B significa que el conjunto A est´ “contenido” en el conjunto B, o m´s
o
a
a
t´cnicamente, que A es subconjunto de B. Por ejemplo, el conjunto {a, c} es subconjunto
e
de {a, b, c}, indicado como...