Set-builder notation

$\{n\mid \exists k\in \mathbb {Z},n=2k\}$

The set of alleven integers,
expressed in set-builder notation.

Inset theoryand its applications tologic,mathematics,andcomputer science,set-builder notationis amathematical notationfor describing asetby enumerating itselements,or stating the properties that its members must satisfy.^[1]

Defining sets by properties is also known asset comprehension,set abstractionor as defining a set'sintension.

Sets defined by enumeration

Asetcan be described directly by enumerating all of its elements between curly brackets, as in the following two examples:

$\{7,3,15,31\}$ is the set containing the four numbers 3, 7, 15, and 31, and nothing else.
$\{a,c,b\}=\{a,b,c\}$ is the set containing $a$ , $b$ ,and $c$ ,and nothing else (there is no order among the elements of a set).

This is sometimes called the "roster method" for specifying a set.^[2]

When it is desired to denote a set that contains elements from a regular sequence, anellipsisnotation may be employed, as shown in the next examples:

$\{1,2,3,\ldots,100\}$ is the set of integers between 1 and 100 inclusive.
$\{1,2,3,\ldots \}$ is the set ofnatural numbers.
$\{\ldots,-2,-1,0,1,2,\ldots \}=\{0,1,-1,2,-2,\ldots \}$ is the set of all integers.

There is no order among the elements of a set (this explains and validates the equality of the last example), but with the ellipses notation, we use an ordered sequence before (or after) the ellipsis as a convenient notational vehicle for explaining which elements are in a set. The first few elements of the sequence are shown, then the ellipses indicate that the simplest interpretation should be applied for continuing the sequence. Should no terminating value appear to the right of the ellipses, then the sequence is considered to be unbounded.

In general, $\{1,\dots,n\}$ denotes the set of all natural numbers $i$ such that $1\leq i\leq n$ .Another notation for $\{1,\dots,n\}$ is the bracket notation $[n]$ .A subtle special case is $n=0$ ,in which $[0]=\{1,\dots,0\}$ is equal to theempty set $\emptyset$ .Similarly, $\{a_{1},\dots,a_{n}\}$ denotes the set of all $a_{i}$ for $1\leq i\leq n$ .

In each preceding example, each set is described by enumerating its elements. Not all sets can be described in this way, or if they can, their enumeration may be too long or too complicated to be useful. Therefore, many sets are defined by a property that characterizes their elements. This characterization may be done informally using general prose, as in the following example.

$\{$ addresses on Pine Street $\}$ is the set of all addresses on Pine Street.

However, the prose approach may lack accuracy or be ambiguous. Thus, set-builder notation is often used with a predicate characterizing the elements of the set being defined, as described in the following section.

Sets defined by a predicate

Set-builder notation can be used to describe a set that is defined by apredicate,that is, a logical formula that evaluates totruefor an element of the set, andfalseotherwise.^[3]In this form, set-builder notation has three parts: a variable, acolonorvertical barseparator, 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:

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

or

\{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 theruleor thepredicate.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 $\{x\mid \Phi (x)\}$ is the set of all values of $x$ that satisfy the formula $Φ$ .^[4]It may be theempty set,if no value of $x$ satisfies the formula.

Specifying the domain

A domain $E$ can appear on the left of the vertical bar:^[5]

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

or by adjoining it to the predicate:

\{x\mid x\in E{\text{ and }}\Phi (x)\}\quad {\text{or}}\quad \{x\mid x\in E\land \Phi (x)\}.

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

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

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.

Examples

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.

$\{x\in \mathbb {R} \mid x>0\}$ is the set of all strictlypositive real numbers,which can be written ininterval notationas $(0,\infty )$ .
$\{x\in \mathbb {R} \mid |x|=1\}$ is the set $\{-1,1\}$ .This set can also be defined as $\{x\in \mathbb {R} \mid x^{2}=1\}$ ;seeequivalent predicates yield equal setsbelow.
For each integer $m$ ,we can define $G_{m}=\{x\in \mathbb {Z} \mid x\geq m\}=\{m,m+1,m+2,\ldots \}$ .As an example, $G_{3}=\{x\in \mathbb {Z} \mid x\geq 3\}=\{3,4,5,\ldots \}$ and $G_{-2}=\{-2,-1,0,\ldots \}$ .
$\{(x,y)\in \mathbb {R} \times \mathbb {R} \mid 0<y<f(x)\}$ is the set of pairs of real numbers such thatyis greater than 0 and less than $f (x)$ ,for a givenfunction $f$ .Here thecartesian product $\mathbb {R} \times \mathbb {R}$ denotes the set of ordered pairs of real numbers.
$\{n\in \mathbb {N} \mid (\exists k)[k\in \mathbb {N} \land n=2k]\}$ is the set of alleven natural numbers.The $\land$ sign stands for "and", which is known aslogical conjunction.The ∃ sign stands for "there exists", which is known asexistential quantification.So for example, $(\exists x)P(x)$ is read as "there exists an $x$ such that $P (x)$ ".
$\{n\mid (\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 that $n$ is a natural number, as this is implied by the formula on the right.
$\{a\in \mathbb {R} \mid (\exists p\in \mathbb {Z} )(\exists q\in \mathbb {Z} )[q\not =0\land aq=p]\}$ is the set ofrational numbers;that is, real numbers that can be written as the ratio of twointegers.

More complex expressions on the left side of the notation

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

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

.

For example:

$\{2n\mid n\in \mathbb {N} \}$ ,where $\mathbb {N}$ is the set of all natural numbers, is the set of all even natural numbers.
$\{p/q\mid p,q\in \mathbb {Z},q\not =0\}$ ,where $\mathbb {Z}$ is the set of all integers, is $\mathbb {Q},$ the set of all rational numbers.
$\{2t+1\mid t\in \mathbb {Z} \}$ is the set of odd integers.
$\{(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 $\{2t+1\mid t\in \mathbb {Z} \}$ .Make the substitution $u=2t+1$ ,which is to say $t=(u-1)/2$ ,then replacetin the set builder notation to find

\{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

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

if and only if

(\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,

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

because the two rule predicates are logically equivalent:

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

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

Set existence axiom

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 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 $Φ$ :

(\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 $\{x\in E\mid \Phi (x)\}$ .

In programming languages

A similar notation available in a number ofprogramming languages(notablyPythonandHaskell) is thelist comprehension,which combinesmapandfilteroperations over one or morelists.

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 inScalausing Sequence Comprehensions, where the "for" keyword returns a list of the yielded variables using the "yield" keyword.^[7]

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

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

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 anymonadwith azero element.

Notes

^Rosen, Kenneth (2007).Discrete Mathematics and its Applications(6th ed.). New York, NY: McGraw-Hill. pp. 111–112.ISBN 978-0-07-288008-3.
^ Richard Aufmann, Vernon C. Barker, and Joanne Lockwood, 2007,Intermediate Algebra with Applications,Brooks Cole, p. 6.
^Michael J Cullinan, 2012,A Transition to Mathematics with Proofs,Jones & Bartlett, pp. 44ff.
^Weisstein, Eric W."Set".mathworld.wolfram.com.Retrieved20 August2020.
^"Set-Builder Notation".mathsisfun.com.Retrieved20 August2020.
^Irvine, Andrew David; Deutsch, Harry (9 October 2016) [1995]."Russell's Paradox".Stanford Encyclopedia of Philosophy.Retrieved6 August2017.
^"Sequence Comprehensions".Scala.Retrieved6 August2017.

[1] Rosen, Kenneth (2007).Discrete Mathematics and its Applications(6th ed.). New York, NY: McGraw-Hill. pp. 111–112.ISBN 978-0-07-288008-3.

[2] Richard Aufmann, Vernon C. Barker, and Joanne Lockwood, 2007,Intermediate Algebra with Applications,Brooks Cole, p. 6.

[3] Michael J Cullinan, 2012,A Transition to Mathematics with Proofs,Jones & Bartlett, pp. 44ff.

[4] Weisstein, Eric W."Set".mathworld.wolfram.com.Retrieved20 August2020.

[5] "Set-Builder Notation".mathsisfun.com.Retrieved20 August2020.

[6] Irvine, Andrew David; Deutsch, Harry (9 October 2016) [1995]."Russell's Paradox".Stanford Encyclopedia of Philosophy.Retrieved6 August2017.

[7] "Sequence Comprehensions".Scala.Retrieved6 August2017.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

v t e Set theory
Overview	Set (mathematics)
Axioms	Adjunction Choice countable dependent global Constructibility (V=L) Determinacy Extensionality Infinity Limitation of size Pairing Power set Regularity Union Martin's axiom Axiom schema replacement specification
Operations	Cartesian product Complement(i.e. set difference) De Morgan's laws Disjoint union Identities Intersection Power set Symmetric difference Union
Concepts Methods	Almost Cardinality Cardinal number(large) Class Constructible universe Continuum hypothesis Diagonal argument Element ordered pair tuple Family Forcing One-to-one correspondence Ordinal number Set-builder notation Transfinite induction Venn diagram
Settypes	Amorphous Countable Empty Finite(hereditarily) Filter base subbase Ultrafilter Fuzzy Infinite(Dedekind-infinite) Recursive Singleton Subset·Superset Transitive Uncountable Universal
Theories	Alternative Axiomatic Naive Cantor's theorem Zermelo General Principia Mathematica New Foundations Zermelo–Fraenkel von Neumann–Bernays–Gödel Morse–Kelley Kripke–Platek Tarski–Grothendieck
Paradoxes Problems	Russell's paradox Suslin's problem Burali-Forti paradox
Set theorists	Paul Bernays Georg Cantor Paul Cohen Richard Dedekind Abraham Fraenkel Kurt Gödel Thomas Jech John von Neumann Willard Quine Bertrand Russell Thoralf Skolem Ernst Zermelo