Set-builder notation

In mathematics and more specifically in set theory, set-builder notation is a notation for specifying a set by a property that characterizes its members. Roster notation is a similar notation used for specifying a set by enumerating its elements.

Specifying sets by member properties is allowed by the axiom schema of specification. This is also known as set comprehension and set abstraction.

Sets defined by a predicate

Set-builder notation can be used to describe a set that is defined by a predicate, that is, a logical formula that evaluates to true for an element of the set, and false otherwise. In this form, set-builder notation has three parts: a variable, a colon or vertical bar separator, and a predicate. Thus there is a variable on the left of the separator, and a rule on the right of it. These three parts are contained in curly brackets:

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

or

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

The vertical bar (or colon) is a separator that can be read as "such that", "for which", or "with the property that". The formula Φ(x) is said to be the rule or the predicate. All values of x for which the predicate holds (is true) belong to the set being defined. All values of x for which the predicate does not hold do not belong to the set. Thus ${\displaystyle \{x\mid \Phi (x)\}}$ is the set of all values of x that satisfy the formula Φ. It may be the empty set, if no value of x satisfies the formula.

More complex expressions on the left side of the notation

An extension of set-builder notation replaces the single variable x with an expression. So instead of ${\displaystyle \{x\mid \Phi (x)\}}$, we may have ${\displaystyle \{f(x)\mid \Phi (x)\},}$ which should be read

${\displaystyle \{f(x)\mid \Phi (x)\}=\{y\mid \exists x(y=f(x)\wedge \Phi (x))\}}$.

For example:

• ${\displaystyle \{2n\mid n\in \mathbb {N} \}}$, where ${\displaystyle \mathbb {N} }$ is the set of all natural numbers, is the set of all even natural numbers.
• ${\displaystyle \{p/q\mid p,q\in \mathbb {Z} ,q\not =0\}}$, where ${\displaystyle \mathbb {Z} }$ is the set of all integers, is ${\displaystyle \mathbb {Q} ,}$ the set of all rational numbers.
• ${\displaystyle \{2t+1\mid t\in \mathbb {Z} \}}$ is the set of odd integers.
• ${\displaystyle \{(t,2t+1)\mid t\in \mathbb {Z} \}}$ creates a set of pairs, where each pair puts an integer into correspondence with an odd integer.

When inverse functions can be explicitly stated, the expression on the left can be eliminated through simple substitution. Consider the example set ${\displaystyle \{2t+1\mid t\in \mathbb {Z} \}}$. Make the substitution ${\displaystyle u=2t+1}$, which is to say ${\displaystyle t=(u-1)/2}$, then replace t in the set builder notation to find

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

Equivalent predicates yield equal sets

Two sets are equal if and only if they have the same elements. Sets defined by set builder notation are equal if and only if their set builder rules, including the domain specifiers, are equivalent. That is

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

if and only if

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

Therefore, in order to prove the equality of two sets defined by set builder notation, it suffices to prove the equivalence of their predicates, including the domain qualifiers.

For example,

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

because the two rule predicates are logically equivalent:

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

This equivalence holds because, for any real number x, we have ${\displaystyle x^{2}=1}$ if and only if x is a rational number with ${\displaystyle |x|=1}$. In particular, both sets are equal to the set ${\displaystyle \{-1,1\}}$.

Set existence axiom

In many formal set theories, such as Zermelo–Fraenkel set theory, set builder notation is not part of the formal syntax of the theory. Instead, there is a set existence axiom scheme, which states that if E is a set and Φ(x) is a formula in the language of set theory, then there is a set Y whose members are exactly the elements of E that satisfy Φ:

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

The set Y obtained from this axiom is exactly the set described in set builder notation as ${\displaystyle \{x\in E\mid \Phi (x)\}}$.

In programming languages

A similar notation available in a number of programming languages (notably Python and Haskell) is the list comprehension, which combines map and filter operations over one or more lists.

It has been suggested that parts of this page be moved into List comprehension. (Discuss) (December 2023)

In Python, the set-builder's braces are replaced with square brackets, parentheses, or curly braces, giving list, generator, and set objects, respectively. Python uses an English-based syntax. Haskell replaces the set-builder's braces with square brackets and uses symbols, including the standard set-builder vertical bar.

The same can be achieved in Scala using Sequence Comprehensions, where the "for" keyword returns a list of the yielded variables using the "yield" keyword.

Consider these set-builder notation examples in some programming languages:

	Example 1	Example 2
Set-builder	${\displaystyle \{l\ |\ l\in L\}}$	${\displaystyle \{(k,x)\ |\ k\in K\wedge x\in X\wedge P(x)\}}$
Python	{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)
Prolog	setof(L,member(L,Ls),Result)	setof((K,X),(member(K,Ks),member(X,Xs),call(P,X)),Result)
Erlang	[L || L <- Ls]	[{K,X} || K <- Ks, X <- Xs, p(X)]
Julia	[l for l ∈ L]	[(k, x) for k ∈ K for x ∈ X if P(x)]
Mathematica	(l |-> l) /@ L	Cases[Tuples[{K, X}], {k_, x_} /; P[x]] Tuples[{K, Select[X, P]}]

The set builder notation and list comprehension notation are both instances of a more general notation known as monad comprehensions, which permits map/filter-like operations over any monad with a zero element.

See also

• Glossary of set theory

Notes