Set-builder notation

In set theory and its applications to logic, mathematics, and computer science, set-builder notation (sometimes simply set notation) is a mathematical notation for describing a set by stating the properties that its members must satisfy. Forming sets in this manner is also known as set comprehension, set abstraction or as defining a set's intension.

Building sets

Let Φ(x) be a formula in which x appears free. Set builder notation has the form {x : Φ(x)} (or {x | Φ(x)} according to the international standard ISO 31-11 using the vertical bar instead of the colon), denoting the set of all individuals in the universe of discourse satisfying the formula Φ(x), that is, the set whose members are every individual x such that Φ(x) is true: formally, the extension of the predicate. Sometimes the universe of discourse is established within the notation; writing {x ∈ U : Φ(x)} establishes that the universe of discourse is U, for purposes of the set being built. Set builder notation binds the variable x and must be used with the same care applied to variables bound by quantifiers.

Examples (the universe of discourse can be taken to be the set of real numbers, where not specified inside the notation):

• $\{x \in \mathbf R: x = x^2 \} \,\!$ is the set {0,1},
• $\{x \in \mathbf R: x > 0\}$ is the set of all positive real numbers.
• $\{k : (\exists n \in \mathbf{N}) (k = 2n)\}$ is the set of all even natural numbers,
• $\{a : \exists \ p, q \in \mathbf{Z} (q \not = 0 \land aq=p) \}$ is the set of rational numbers; that is, numbers that can be written as the ratio of two integers.
• $\mathbf{N}_m = \{x \in \mathbf{Z} : x \ge m \} = \{ m, m + 1, m + 2, ...\}.$ Thus, e.g., $x_1 = m,\ x_2 = m + 1$, etc. (n.b.: in the case of sets, the order is not important; x₁ = m + 2 could be used). As an example, $\mathbf{N}_3 = \{x \in \mathbf{Z} : x \ge 3 \} = \{ 3, 4, 5, ...\}.$

The $\and$ sign stands for and, requiring both conditions be fulfilled simultaneously. It is often replaced by a comma (,) semicolon (;) or written out as and. The $\in$ sign denotes set membership, and can be read as "in".

Logical equivalence

Logical equivalence is an important concept in set-builder notation:

$\Big[ \{ x \in U  : P(x) \} = \{ x \in U : Q(x) \} \Big] \equiv \Big[ ( \forall x \in U ) \big[ P(x) \Leftrightarrow Q(x) \big] \Big]$.

This means that two sets are equal if and only if their "membership requirements" are logically equivalent.

For example, $\{ x \in \mathbf{R} : x^2 = 1 \} = \{ x \in \mathbf{R} : |x| = 1 \}$ because, for any real number x, x² = 1 if and only if |x| = 1; and, therefore, both constructions produce the same set {-1,1}.

Russell's paradox

Let $R = \{S : S \notin S\}$ denote the set R of all sets S that do not belong to themselves. The inconsistency of the existence of this set is known as Russell's paradox.

Solutions to the paradox restrict the notion of set construction in some way. To illustrate this in terms of our notation, let X = {x ∈ A : P(x)} denote the set of every element of A satisfying the predicate P(x). The canonical restriction on set builder notation asserts that X is a set only if A is already known to be a set. This restriction is codified in the axiom schema of separation present in standard axiomatic set theory. Note that this axiom schema excludes R from sethood.

Other problems

The notation can be complicated, especially as in the previous example, and abbreviations are often employed when context indicates the nature of a variable. For example:

• {x : x > 0}, in a context where the variable x is used only for real numbers, indicates the set of all positive real numbers;
• {p/q : q ≠ 0}, in a context where the variables p and q are used only for integers, indicates the set of all rational numbers; and
• {S : S does not belong to S}, in a context where the variable S is used only for sets, indicates the set of all sets that don't belong to themselves.

As the last example shows, such an abbreviated notation again might not denote an actual nonparadoxical set, unless there is in fact a set of all objects that might be described by the variable in question.

Variations

Terms more complicated than a single variable

Another variation on set-builder notation replaces the single variable x with a term T which may include one or more variables, combined with functions acting on them. So instead of {x : Φ(x)}, we would have {T : Φ(x₁ ... x_n)}, where T is a term involving variables x₁ through x_n. For example:

• {2n : n ∈ N}, where N is the set of all natural numbers, is the set of all even natural numbers.
• {p/q : p,q ∈ Z, q≠0}, where Z is the set of all integers, is the set of all rational numbers (Q).

Z notation

Main article: Z notation

In Z notation, the set of all x (in a universe of discourse A) satisfying the condition P(x) would be written $\{x : A \ |\ P(x)\}$. In Z, an element x's set membership is written as (x:A) instead of $(x \in A)$, the vertical bar is used to indicate a predicate. Versions of set builder notation are also available in Z which allow for terms more complicated than a single variable, using a bullet to indicate the form of members of the set. So $\{x : A \ |\ P(x) \bullet F(x)\}$ denotes the set of all values F(x), where x is in A and P(x) holds.

Parallels in programming languages

Main article: List comprehension

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.

Python replaces set-builder's braces with square brackets and uses a language-based syntax. Haskell replaces set-builder's braces with square brackets and uses symbolic constructs, including the standard set-builder vertical bar. Consider these examples given in set-builder notation, Python, and Haskell:

	Example 1	Example 2
Set-builder	$\{l\ |\ l \in L\}$	$\{(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]

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.