Introducción

El fundamento más importante para el estudio de los lenguajes y autómatas es la Teoría de Conjuntos. En efecto, siempre que hablemos de “formalizar” una noción, estaremos diciendo en realidad “expresar en términos de la Teoría de Conjuntos”. La idea de un conjunto como una colección de individuos u objetos no es, para un verdadero matemático, suficientemente precisa, y se parece a la noción de clase; sin embargo, para nuestros propósitos es suficiente. Un conjunto que vamos a utilizar con frecuencia es el de los n´umeros naturales, {1, 2, 3, . . .}, denotado por ℕ.

Las dos formas de expresar un conjunto

Los conjuntos pueden expresarse de dos maneras básicamente:

1. En extensión: Lo cual quiere decir que citamos explícitamente cada uno de sus elementos, como el conjunto {1,3,5} que contiene exactamente los números 1, 3 y 5.
2. En intención, dando una descripción 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 ∈ ℕ | impar(i), i < 6}, donde se supone que los números impares cumplen la condición impar(i).

Representación de los conjuntos

Representamos a los conjuntos con letras mayúsculas , como en A = {2,4}. Los conjuntos pueden contener conjuntos como elementos, como en B = { {a}, {b,c} }.

Conjunto vacío ∅

El conjunto sin elementos (vacío) se representa por ∅ o bien por { }.

Pertenece y no pertenece ∈ /∉

La notación a ∈ B significa que a es elemento o está contenido en el conjuntoB; por ejemplo, {2, 3} ∈ {1, {2, 3}, 4}.

Para indicar que a no está en B se escribe a ∉ B

Tamaño de un conjunto |A|

El tamaño de un conjunto es el número de elementos que contiene, y se representa como |A| para un conjunto A.

Ejemplos:

• El tamaño de {a,b,c} es 3, y el tamaño de ∅ es cero.
• El tamaño de {{a}, {b, c}} es 2 y no 3, pues tiene 2 elementos, siendo el primero {a} y el segundo {b, c}. La definición de “tamaño” parece muy clara, pero hay conjuntos que no tienen un número determinado de elementos; estos se llaman “infinitos”.

Igualdad de conjuntos =

Dos conjuntos A y B son iguales, A = B, si y sólo si tienen los mismos elementos, esto es, x ∈ A ssi x ∈ B.