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.
[1] Specifying sets by member properties is allowed by the axiom of extensionality.
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.
[2] In this form, set-builder notation has three parts: a variable, a colon or vertical bar separator, and a predicate.
These three parts are contained in curly brackets: or The vertical bar (or colon) is a separator that can be read as "such that", "for which", or "with the property that".
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.
is the set of all values of x that satisfy the formula Φ.
[3] It may be the empty set, if no value of x satisfies the formula.
A domain E can appear on the left of the vertical bar:[4] or by adjoining it to the predicate: The ∈ symbol here denotes set membership, while the
In general, it is not a good idea to consider sets without defining a domain of discourse, as this would represent the subset of all possible things that may exist for which the predicate is true.
For example, Russell's paradox shows that the expression
[5] In cases where the set E is clear from context, it may be not explicitly specified.
It is common in the literature for an author to state the domain ahead of time, and then not specify it in the set-builder notation.
For example, an author may say something such as, "Unless otherwise stated, variables are to be taken to be natural numbers," though in less formal contexts where the domain can be assumed, a written mention is often unnecessary.
The following examples illustrate particular sets defined by set-builder notation via predicates.
An extension of set-builder notation replaces the single variable x with an expression.
which should be read For example: When inverse functions can be explicitly stated, the expression on the left can be eliminated through simple substitution.
That is if and only if 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.
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.
In Python, the set-builder's braces are replaced with square brackets, parentheses, or curly braces, giving list, generator, and set objects, respectively.
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.