Inmathematics and more specifically inset theory,set-builder notation is anotation for specifying aset by a property that characterizes its members.^[1]

Specifying sets by member properties is allowed by theaxiom schema of specification. This is also known asset comprehension andset abstraction.

Set-builder notation can be used to describe a set that is defined by apredicate, that is, a logical formula that evaluates totrue for an element of the set, andfalse otherwise.^[2] In this form, set-builder notation has three parts: a variable, acolon orvertical 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 \mathrm{\Phi }(x)\}}$

or

${\displaystyle \{x:\mathrm{\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 therule or thepredicate. All values ofx for which the predicate holds (is true) belong to the set being defined. All values ofx for which the predicate does not hold do not belong to the set. Thus${\displaystyle \{x\mid \mathrm{\Phi }(x)\}}$ is the set of all values ofx that satisfy the formulaΦ.^[3] It may be theempty set, if no value ofx satisfies the formula.

A domainE can appear on the left of the vertical bar:^[4]

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

or by adjoining it to the predicate:

${\displaystyle \{x\mid x\in E\text{ and }\mathrm{\Phi }(x)\}\text{or}\{x\mid x\in E\wedge \mathrm{\Phi }(x)\}.}$

The ∈ symbol here denotesset membership, while the${\displaystyle \wedge }$ symbol denotes the logical "and" operator, known aslogical conjunction. This notation represents the set of all values ofx that belong to some given setE for which the predicate is true (see "Set existence axiom" below). If${\displaystyle \mathrm{\Phi }(x)}$ is a conjunction${\displaystyle {\mathrm{\Phi }}_1(x)\wedge {\mathrm{\Phi }}_2(x)}$, then${\displaystyle \{x\in E\mid \mathrm{\Phi }(x)\}}$ is sometimes written${\displaystyle \{x\in E\mid {\mathrm{\Phi }}_1(x),{\mathrm{\Phi }}_2(x)\}}$, using a comma instead of the symbol${\displaystyle \wedge }$.

In general, it is not a good idea to consider sets without defining adomain of discourse, as this would represent thesubset ofall possible things that may exist for which the predicate is true. This can easily lead to contradictions and paradoxes. For example,Russell's paradox shows that the expression${\displaystyle \{x|x\notin x\},}$ although seemingly well formed as a set builder expression, cannot define a set without producing a contradiction.^[5]

In cases where the setE 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. In each case, the domain is specified on the left side of the vertical bar, while the rule is specified on the right side.

• ${\displaystyle \{x\in \mathbb{R}\mid x>0\}}$ is the set of all strictlypositivereal numbers, which can be written ininterval notation as${\displaystyle (0,\mathrm{\infty })}$.
• ${\displaystyle \{x\in \mathbb{R}\mid |x|=1\}}$ is the set${\displaystyle \{-1,1\}}$. This set can also be defined as${\displaystyle \{x\in \mathbb{R}\mid x^2=1\}}$; seeequivalent predicates yield equal sets below.
• For each integerm, we can define${\displaystyle G_m=\{x\in \mathbb{Z}\mid x\ge m\}=\{m,m+1,m+2,\dots \}}$. As an example,${\displaystyle G_3=\{x\in \mathbb{Z}\mid x\ge 3\}=\{3,4,5,\dots \}}$ and${\displaystyle G_{-2}=\{-2,-1,0,\dots \}}$.
• is the set of pairs of real numbers such thaty is greater than 0 and less thanf(x), for a givenfunctionf. Here thecartesian product${\displaystyle \mathbb{R}\times \mathbb{R}}$ denotes the set of ordered pairs of real numbers.
• ${\displaystyle \{n\in \mathbb{N}\mid (\mathrm{\exists }k)[k\in \mathbb{N}\wedge n=2k]\}}$ is the set of allevennatural numbers. The${\displaystyle \wedge }$ sign stands for "and", which is known aslogical conjunction. The ∃ sign stands for "there exists", which is known asexistential quantification. So for example,${\displaystyle (\mathrm{\exists }x)P(x)}$ is read as "there exists anx such thatP(x)".
• ${\displaystyle \{n\mid (\mathrm{\exists }k\in \mathbb{N})[n=2k]\}}$ is a notational variant for the same set of even natural numbers. It is not necessary to specify thatn is a natural number, as this is implied by the formula on the right.
• ${\displaystyle \{a\in \mathbb{R}\mid (\mathrm{\exists }p\in \mathbb{Z})(\mathrm{\exists }q\in \mathbb{Z})[q\ne 0\wedge aq=p]\}}$ is the set ofrational numbers; that is, real numbers that can be written as the ratio of twointegers.

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

${\displaystyle \{f(x)\mid \mathrm{\Phi }(x)\}=\{y\mid \mathrm{\exists }x(y=f(x)\wedge \mathrm{\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\ne 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 replacet in the set builder notation to find

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

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 (\mathrm{\forall }t)[(t\in A\wedge P(t))\iff (t\in B\wedge 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}\wedge x^2=1)\iff (x\in \mathbb{Q}\wedge |x|=1).}$

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

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

${\displaystyle (\mathrm{\forall }E)(\mathrm{\exists }Y)(\mathrm{\forall }x)[x\in Y\iff x\in E\wedge \mathrm{\Phi }(x)].}$

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

A similar notation available in a number ofprogramming languages (notablyPython andHaskell) is thelist comprehension, which combinesmap andfilter operations over one or morelists.

It has been suggested that parts of this page bemoved intoList 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 inScala using Sequence Comprehensions, where the "for" keyword returns a list of the yielded variables using the "yield" keyword.^[6]

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	{lforlinL}	{(k,x)forkinKforxinXifP(x)}
Haskell	[l|l<-ls]	[(k,x)|k<-ks,x<-xs,px]
Scala	for(l<-L)yieldl	for(k<-K;x<-XifP(x))yield(k,x)
C#	fromlinLselectl	fromkinKfromxinXwhereP(x)select(k,x)
SQL	SELECTlFROML_set	SELECTk,xFROMK_set,X_setWHEREP(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	[lforl∈L]	[(k,x)fork∈Kforx∈XifP(x)]
Mathematica	(l|->l)/@L	Cases[Tuples[{K,X}],{k_,x_}/;P[x]]

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

• Glossary of set theory

• Set theory
• Mathematical notation

• Articles with short description
• Short description is different from Wikidata
• Use dmy dates from December 2020
• Articles proposed for splitting from December 2023
• All articles proposed for splitting
• Articles proposed for section moving from December 2023
• All articles proposed for section moving
• Articles with example Haskell code
• Articles with example Python (programming language) code