Notación de constructor de conjuntos - Set-builder notation

En la teoría de conjuntos y sus aplicaciones a la lógica , las matemáticas y la informática , la notación del constructor de conjuntos es una notación matemática para describir un conjunto enumerando sus elementos o indicando las propiedades que sus miembros deben satisfacer.

La definición de conjuntos por propiedades también se conoce como comprensión de conjuntos , abstracción de conjuntos o definición de la intensión de un conjunto .

Conjuntos definidos por enumeración

Un conjunto se puede describir directamente enumerando todos sus elementos entre llaves, como en los dos ejemplos siguientes:

• ${\ Displaystyle \ {7,3,15,31 \}}$ es el conjunto que contiene los cuatro números 3, 7, 15 y 31, y nada más.
• ${\ Displaystyle \ {a, c, b \} = \ {a, b, c \}}$es el conjunto que contiene una , b , y c , y nada más (no hay orden entre los elementos de un conjunto).

Esto a veces se denomina "método de lista" para especificar un conjunto.

Cuando se desea denotar un conjunto que contiene elementos de una secuencia regular, se puede emplear una notación de elipses , como se muestra en los siguientes ejemplos:

• ${\ Displaystyle \ {1,2,3, \ ldots, 100 \}}$ es el conjunto de números enteros entre 1 y 100 inclusive.
• ${\ Displaystyle \ {1,2,3, \ ldots \}}$es el conjunto de números naturales .
• ${\ Displaystyle \ {\ ldots, -2, -1,0,1,2, \ ldots \} = \ {0,1, -1,2, -2, \ ldots \}}$ es el conjunto de todos los números enteros.

No hay orden entre los elementos de un conjunto (esto explica y valida la igualdad del último ejemplo), pero con la notación de elipses, usamos una secuencia ordenada antes (o después) de la elipsis como un vehículo de notación conveniente para explicar qué elementos están en un set. Se muestran los primeros elementos de la secuencia, luego las elipses indican que se debe aplicar la interpretación más simple para continuar la secuencia. Si no aparece ningún valor de terminación a la derecha de las elipses, entonces la secuencia se considera ilimitada.

En general, denota el conjunto de todos los números naturales tales que . Otra notación para es la notación de corchetes . Un caso especial sutil es , en el que es igual al conjunto vacío . De manera similar, denota el conjunto de todos para . ${\ Displaystyle \ {1, \ dots, n \}}$${\ Displaystyle i}$${\ Displaystyle 1 \ leq i \ leq n}$${\ Displaystyle \ {1, \ dots, n \}}$${\ Displaystyle [n]}$${\ Displaystyle n = 0}$${\ Displaystyle [0] = \ {1, \ dots, 0 \}}$ ${\ Displaystyle \ emptyset}$${\ Displaystyle \ {a_ {1}, \ dots, a_ {n} \}}$${\ Displaystyle a_ {i}}$${\ Displaystyle 1 \ leq i \ leq n}$

En cada ejemplo anterior, cada conjunto se describe enumerando sus elementos. No todos los conjuntos pueden describirse de esta manera o, si es posible, su enumeración puede ser demasiado larga o complicada para resultar útil. Por tanto, muchos conjuntos están definidos por una propiedad que caracteriza a sus elementos. Esta caracterización se puede hacer de manera informal utilizando prosa general, como en el siguiente ejemplo.

• ${\ Displaystyle \ {}$direcciones en Pine Street es el conjunto de todas las direcciones en Pine Street.${\ Displaystyle \}}$

Sin embargo, el enfoque en prosa puede carecer de precisión o ser ambiguo. Por lo tanto, la notación del constructor de conjuntos se usa a menudo con un predicado que caracteriza los elementos del conjunto que se está definiendo, como se describe en la siguiente sección.

Conjuntos definidos por un predicado

La notación del generador de conjuntos se puede utilizar para describir un conjunto definido por un predicado , es decir, una fórmula lógica que se evalúa como verdadera para un elemento del conjunto y falsa en caso contrario. En esta forma, la notación del generador de conjuntos tiene tres partes: una variable, un separador de dos puntos o barra vertical y un predicado. Por lo tanto, hay una variable a la izquierda del separador y una regla a la derecha. Estas tres partes están contenidas entre corchetes:

${\ Displaystyle \ {x \ mid \ Phi (x) \}}$

o

${\ Displaystyle \ {x: \ Phi (x) \}.}$

La barra vertical (o dos puntos) es un separador que se puede leer como " tal que ", "para cuál" o "con la propiedad que". Se dice que la fórmula Φ ( x ) es la regla o el predicado . Todos los valores de x para los que el predicado es válido (es verdadero) pertenecen al conjunto que se está definiendo. Todos los valores de x para los que no se cumple el predicado no pertenecen al conjunto. Así es el conjunto de todos los valores de x que satisfacen la fórmula Φ . Puede ser el conjunto vacío , si ningún valor de x satisface la fórmula. ${\ Displaystyle \ {x \ mid \ Phi (x) \}}$

Especificando el dominio

Un dominio E puede aparecer a la izquierda de la barra vertical:

${\ Displaystyle \ {x \ in E \ mid \ Phi (x) \},}$

o adjuntándolo al predicado:

${\ Displaystyle \ {x \ mid x \ in E {\ text {y}} \ Phi (x) \} \ quad {\ text {o}} \ quad \ {x \ mid x \ in E \ land \ Phi (X)\}.}$

El símbolo ∈ aquí denota pertenencia al conjunto , mientras que el símbolo denota el operador lógico "y", conocido como conjunción lógica . Esta notación representa el conjunto de todos los valores de x que pertenecen a algún conjunto dado E para el que el predicado es verdadero (ver " Establecer axioma de existencia " a continuación). Si es una conjunción , a veces se escribe con una coma en lugar del símbolo . ${\ Displaystyle \ land}$${\ Displaystyle \ Phi (x)}$${\ Displaystyle \ Phi _ {1} (x) \ land \ Phi _ {2} (x)}$${\ Displaystyle \ {x \ in E \ mid \ Phi (x) \}}$${\ Displaystyle \ {x \ en Mi \ mid \ Phi _ {1} (x), \ Phi _ {2} (x) \}}$${\ Displaystyle \ land}$

En general, no es una buena idea considerar conjuntos sin definir un dominio, ya que esto representaría el subconjunto de todas las cosas posibles que pueden existir para las que el predicado es verdadero. Esto puede conducir fácilmente a contradicciones y paradojas. Por ejemplo, la paradoja de Russell muestra que la expresión, aunque aparentemente bien formada como una expresión de constructor de conjuntos, no puede definir un conjunto sin producir una contradicción. ${\ Displaystyle \ {x ~ | ~ x \ not \ in x \},}$

En los casos en los que el conjunto E se desprende del contexto, es posible que no se especifique explícitamente. Es común en la literatura que un autor indique el dominio con anticipación y luego no lo especifique en la notación del constructor de conjuntos. Por ejemplo, un autor puede decir algo como, "A menos que se indique lo contrario, las variables deben tomarse como números naturales". Aunque en contextos menos formales en los que se puede asumir el dominio, una mención escrita a menudo es innecesaria.

Ejemplos de

Los siguientes ejemplos ilustran conjuntos particulares definidos por la notación del constructor de conjuntos a través de predicados. En cada caso, el dominio se especifica en el lado izquierdo de la barra vertical, mientras que la regla se especifica en el lado derecho.

• ${\ Displaystyle \ {x \ in \ mathbb {R} \ mid x> 0 \}}$es el conjunto de todos los números reales estrictamente positivos , que se puede escribir en notación de intervalo como .${\ displaystyle (0, \ infty)}$
• ${\ Displaystyle \ {x \ in \ mathbb {R} \ mid | x | = 1 \}}$es el conjunto . Este conjunto también se puede definir como ; vea los predicados equivalentes producen conjuntos iguales a continuación.${\ Displaystyle \ {- 1,1 \}}$${\ Displaystyle \ {x \ in \ mathbb {R} \ mid x ^ {2} = 1 \}}$
• Para cada entero m , podemos definir . Como ejemplo, y .${\ Displaystyle G_ {m} = \ {x \ in \ mathbb {Z} \ mid x \ geq m \} = \ {m, m + 1, m + 2, \ ldots \}}$${\ Displaystyle G_ {3} = \ {x \ in \ mathbb {Z} \ mid x \ geq 3 \} = \ {3,4,5, \ ldots \}}$${\ Displaystyle G _ {- 2} = \ {- 2, -1,0, \ ldots \}}$
• ${\ Displaystyle \ {(x, y) \ in \ mathbb {R} \ times \ mathbb {R} \ mid 0 <y <f (x) \}}$ es el conjunto de pares de números reales tal que y es mayor que 0 y menor que f ( x ), para una función dada f . Aquí el producto cartesiano denota el conjunto de pares ordenados de números reales.${\ Displaystyle \ mathbb {R} \ times \ mathbb {R}}$
• ${\ Displaystyle \ {n \ in \ mathbb {N} \ mid (\ existe k) [k \ in \ mathbb {N} \ land n = 2k] \}}$es el conjunto de todos los números naturales pares . El signo significa "y", que se conoce como conjunción lógica . El signo ∃ significa "existe", lo que se conoce como cuantificación existencial . Entonces, por ejemplo, se lee como "existe una x tal que P ( x )".${\ Displaystyle \ land}$${\ Displaystyle (\ existe x) P (x)}$
• ${\ Displaystyle \ {n \ mid (\ existe k \ in \ mathbb {N}) [n = 2k] \}}$es una variante de notación para el mismo conjunto de números naturales pares. No es necesario especificar que n es un número natural, ya que esto está implícito en la fórmula de la derecha.
• ${\ Displaystyle \ {a \ in \ mathbb {R} \ mid (\ existe p \ in \ mathbb {Z}) (\ existe q \ in \ mathbb {Z}) [q \ not = 0 \ land aq = p ] \}}$es el conjunto de números racionales ; es decir, números reales que se pueden escribir como la razón de dos enteros .

Expresiones más complejas en el lado izquierdo de la notación

Una extensión de la notación del generador de conjuntos reemplaza la variable única x con una expresión . Entonces, en lugar de , podemos tener lo que debería leerse ${\ Displaystyle \ {x \ mid \ Phi (x) \}}$${\ Displaystyle \ {\ Psi (x) \ mid \ Phi (x) \},}$

${\ Displaystyle \ {\ Psi (x) \ mid \ Phi (x) \} = \ {y \ mid \ existe (x), y = \ Psi (x) {\ text {y}} \ Phi (x) \}}$.

Por ejemplo:

• ${\ Displaystyle \ {2n \ mid n \ in \ mathbb {N} \}}$, donde es el conjunto de todos los números naturales, es el conjunto de todos los números naturales pares.${\ Displaystyle \ mathbb {N}}$
• ${\ Displaystyle \ {p / q \ mid p, q \ in \ mathbb {Z}, q \ not = 0 \}}$, donde es el conjunto de todos los números enteros, es el conjunto de todos los números racionales.${\ Displaystyle \ mathbb {Z}}$${\ Displaystyle \ mathbb {Q},}$
• ${\ Displaystyle \ {2t + 1 \ mid t \ in \ mathbb {Z} \}}$ es el conjunto de números enteros impares.
• ${\ Displaystyle \ {(t, 2t + 1) \ mid t \ in \ mathbb {Z} \}}$ crea un conjunto de pares, donde cada par pone un número entero en correspondencia con un número entero impar.

Cuando las funciones inversas se pueden establecer explícitamente, la expresión de la izquierda se puede eliminar mediante una simple sustitución. Considere el conjunto de ejemplos . Haga la sustitución , es decir , luego reemplace t en la notación del constructor de conjuntos para encontrar ${\ Displaystyle \ {2t + 1 \ mid t \ in \ mathbb {Z} \}}$${\ Displaystyle u = 2t + 1}$${\ Displaystyle t = (u-1) / 2}$

${\ Displaystyle \ {2t + 1 \ mid t \ in \ mathbb {Z} \} = \ {u \ mid (u-1) / 2 \ in \ mathbb {Z} \}.}$

Los predicados equivalentes producen conjuntos iguales

Dos conjuntos son iguales si y solo si tienen los mismos elementos. Los conjuntos definidos por la notación del constructor de conjuntos son iguales si y solo si sus reglas del constructor de conjuntos, incluidos los especificadores de dominio, son equivalentes. Es decir

${\ Displaystyle \ {x \ en A \ mid P (x) \} = \ {x \ in B \ mid Q (x) \}}$

si y solo si

${\ Displaystyle (\ forall t) [(t \ in A \ land P (t)) \ Leftrightarrow (t \ in B \ land Q (t))]}$.

Por lo tanto, para probar la igualdad de dos conjuntos definidos por la notación del constructor de conjuntos, basta con probar la equivalencia de sus predicados, incluidos los calificadores de dominio.

Por ejemplo,

${\ Displaystyle \ {x \ in \ mathbb {R} \ mid x ^ {2} = 1 \} = \ {x \ in \ mathbb {Q} \ mid | x | = 1 \}}$

porque los dos predicados de la regla son lógicamente equivalentes:

${\ Displaystyle (x \ in \ mathbb {R} \ land x ^ {2} = 1) \ Leftrightarrow (x \ in \ mathbb {Q} \ land | x | = 1).}$

Esta equivalencia es válida porque, para cualquier número real x , tenemos si y solo si x es un número racional con . En particular, ambos conjuntos son iguales al conjunto . ${\ Displaystyle x ^ {2} = 1}$${\ Displaystyle | x | = 1}$${\ Displaystyle \ {- 1,1 \}}$

Establecer axioma de existencia

En muchas teorías formales de conjuntos, como la teoría de conjuntos de Zermelo-Fraenkel , la notación del constructor de conjuntos no es parte de la sintaxis formal de la teoría. En cambio, hay un esquema de axiomas de existencia de conjuntos , que establece que si E es un conjunto y Φ ( x ) es una fórmula en el lenguaje de la teoría de conjuntos, entonces hay un conjunto Y cuyos miembros son exactamente los elementos de E que satisfacen Φ :

${\ Displaystyle (\ forall E) (\ existe Y) (\ forall x) [x \ in Y \ Leftrightarrow x \ in E \ land \ Phi (x)].}$

El conjunto Y obtenido de este axioma es exactamente el conjunto descrito en la notación del constructor de conjuntos como . ${\ Displaystyle \ {x \ in E \ mid \ Phi (x) \}}$

Paralelos en lenguajes de programación

Una notación similar disponible en varios lenguajes de programación (especialmente Python y Haskell ) es la comprensión de listas , que combina operaciones de mapa y filtro en una o más listas .

En Python, las llaves del constructor de conjuntos se reemplazan por corchetes, paréntesis o llaves, dando lista, generador y objetos de conjunto, respectivamente. Python usa una sintaxis basada en inglés. Haskell reemplaza las llaves del constructor de conjuntos con corchetes y usa símbolos, incluida la barra vertical estándar del constructor de conjuntos.

Lo mismo se puede lograr en Scala usando Sequence Comprehensions, donde la palabra clave "for" devuelve una lista de las variables obtenidas usando la palabra clave "yield".

Considere estos ejemplos de notación de constructores de conjuntos en algunos lenguajes de programación:

	Ejemplo 1	Ejemplo 2
Constructor de escenarios	${\ Displaystyle \ {l \ | \ l \ in L \}}$	${\ Displaystyle \ {(k, x) \ | \ k \ in K \ wedge x \ in X \ wedge P (x) \}}$
Pitón	{l for l in L}	{(k, x) for k in K for x in X if P(x)}
Haskell	[l | l <- ls]	[(k, x) | k <- ks, x <- xs, p x]
Scala	for (l <- L) yield l	for (k <- K; x <- X if P(x)) yield (k,x)
C#	from l in L select l	from k in K from x in X where P(x) select (k,x)
SQL	SELECT l FROM L_set	SELECT k, x FROM K_set, X_set WHERE P(x)

La notación del constructor de conjuntos y la notación de comprensión de listas son instancias de una notación más general conocida como comprensión de mónadas , que permite operaciones tipo mapa / filtro sobre cualquier mónada con un elemento cero .

Ver también

• Glosario de teoría de conjuntos

Notas