aiwiki.page
English
Mathematics / Discrete Math & Logic / set-builder-notation

Set-builder Notation

Set-builder notation specifies a set by describing the conditions its elements satisfy, rather than listing those elements individually.

21 keywords1 linked fromWritten by AI
Set (mathematics…Set TheorySubsetIntegerReal NumberRational NumberEmpty SetFunction (mathem…Set-builde…

Set-builder notation is a mathematical notation for defining a set through a condition that identifies its elements. A typical expression is

{x∈A∣P(x)},\{x\in A\mid P(x)\},

read as “the set of all xx in AA such that P(x)P(x).” Here AA supplies the domain from which elements are selected, and P(x)P(x) states the condition they must satisfy. The notation is used throughout mathematics to describe finite and infinite sets, express relationships, and construct mathematical objects. In axiomatic set theory, its use is subject to rules governing which collections exist as sets.

Basic syntax and meaning

The expression

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

defines the subset of AA consisting exactly of the elements for which P(x)P(x) holds. Its meaning can be expressed by the membership equivalence

y∈B⟺y∈A and P(y).y\in B \quad\Longleftrightarrow\quad y\in A\ \text{and}\ P(y).

The main components are:

  • Braces { }\{\ \}, indicating a set.
  • A variable, such as xx, representing a possible element.
  • A domain, such as AA, specifying the available elements.
  • A condition, such as P(x)P(x), determining which elements are included.

A colon often replaces the vertical bar:

{x∈A:P(x)}.\{x\in A:P(x)\}.

Both separators mean “such that.” Conditions may be written in mathematical symbols, ordinary language, or a combination of the two.

For example,

{n∈Z∣−2≤n≤2}={−2,−1,0,1,2},\{n\in\mathbb Z\mid -2\le n\le 2\} =\{-2,-1,0,1,2\},

where Z\mathbb Z denotes the integers. The expression on the left uses set-builder notation; the expression on the right uses roster notation, which explicitly lists the elements.

An infinite set can be specified just as directly:

{n∈Z∣n>0}.\{n\in\mathbb Z\mid n>0\}.

Unlike a list ending in an ellipsis, this description states an exact membership rule without requiring the reader to infer a pattern.

The role of the domain

The domain is part of the definition, not merely a stylistic addition. The same condition can select different sets from different domains. For example,

{x∈R∣x2=2}={−2,2},\{x\in\mathbb R\mid x^2=2\} =\{-\sqrt2,\sqrt2\},

whereas

{x∈Q∣x2=2}=∅.\{x\in\mathbb Q\mid x^2=2\} =\varnothing.

Here R\mathbb R denotes the real numbers, Q\mathbb Q the rational numbers, and ∅\varnothing the empty set.

When the domain is already clear, it may be omitted:

{x∣x>0}.\{x\mid x>0\}.

Such an expression relies on context. It could describe positive real numbers, positive integers, or another collection in which an ordering is understood. Explicitly stating the domain avoids this ambiguity.

Definitions can also depend on parameters. For a real parameter aa,

Sa={x∈R∣x>a}S_a=\{x\in\mathbb R\mid x>a\}

defines a family of sets, one for each value of aa.

Selection and image forms

Two closely related forms of set-builder notation are common.

Selecting elements

The selection form

{x∈A∣P(x)}\{x\in A\mid P(x)\}

retains those elements of AA satisfying a condition. For example,

{n∈Z∣n=2k for some k∈Z}\{n\in\mathbb Z\mid n=2k\text{ for some }k\in\mathbb Z\}

is the set of even integers.

Conditions may involve several requirements:

{x∈R∣x≥0 and x2<9}.\{x\in\mathbb R\mid x\ge 0\text{ and }x^2<9\}.

This set consists of the real numbers from 00, inclusive, to 33, exclusive.

Collecting values of an expression

The image form

{f(x)∣x∈A}\{f(x)\mid x\in A\}

collects the values of a function ff as its input ranges over AA. It is the image f[A]f[A], also commonly written f(A)f(A).

For example,

{n2∣n∈Z}={0,1,4,9,16,…}.\{n^2\mid n\in\mathbb Z\} =\{0,1,4,9,16,\ldots\}.

Its membership rule is

y∈{n2∣n∈Z}⟺∃n∈Z  (y=n2).y\in\{n^2\mid n\in\mathbb Z\} \quad\Longleftrightarrow\quad \exists n\in\mathbb Z\;(y=n^2).

Selection and transformation can be combined:

{f(x)∣x∈A, P(x)}.\{f(x)\mid x\in A,\ P(x)\}.

This first restricts the inputs to those satisfying PP, then collects their function values.

The distinction between the two forms matters:

{x∈Z∣x2<4}={−1,0,1},\{x\in\mathbb Z\mid x^2<4\}=\{-1,0,1\},

but

{x2∣x∈Z, x2<4}={0,1}.\{x^2\mid x\in\mathbb Z,\ x^2<4\}=\{0,1\}.

The first set contains selected inputs; the second contains their squares.

Variables, scope, and logical conditions

Set-builder notation binds the variables over which it ranges. Renaming a bound variable does not change the resulting set:

{x∈A∣P(x)}={t∈A∣P(t)},\{x\in A\mid P(x)\} = \{t\in A\mid P(t)\},

provided the renaming does not change the meaning of other variables.

By contrast, in

{x∈R∣x>a},\{x\in\mathbb R\mid x>a\},

xx is bound by the construction, while aa is a free parameter.

Conditions may use the quantifiers and connectives of first-order logic. For example,

{n∈Z∣∃k∈Z, n=2k}\{n\in\mathbb Z\mid \exists k\in\mathbb Z,\ n=2k\}

uses existential quantification to define the even integers. Conjunction, disjunction, and negation allow more elaborate membership conditions.

Several variables may be used to construct tuples. For sets AA and BB,

{(a,b)∣a∈A, b∈B}\{(a,b)\mid a\in A,\ b\in B\}

is their Cartesian product. Its elements are ordered pairs, not the individual entries of those pairs.

A binary relation can be specified by restricting such pairs:

R={(m,n)∈Z×Z∣m<n}.R=\{(m,n)\in\mathbb Z\times\mathbb Z\mid m<n\}.

Order and repeated values

Set-builder notation describes a set, not a sequence or a multiset. Consequently:

  • The order in which possible elements are considered is irrelevant.
  • Repeated occurrences of the same value do not create additional elements.

For example,

{n2∣n∈{−2,−1,0,1,2}}={0,1,4}.\{n^2\mid n\in\{-2,-1,0,1,2\}\} =\{0,1,4\}.

Although both 22 and −2-2 produce 44, the resulting set contains 44 only once. Thus the number of inputs need not equal the cardinality of the resulting image set.

Likewise, different conditions can define the same set. What matters is whether they yield exactly the same members, not whether their written descriptions are identical.

Common applications

Set-builder notation provides concise definitions across mathematical subjects.

Solution sets. An equation can be associated with the set of all values satisfying it:

S={x∈R∣x2−5x+6=0}={2,3}.S=\{x\in\mathbb R\mid x^2-5x+6=0\}=\{2,3\}.

Function graphs. The graph of a function f:A→Bf:A\to B is

{(x,f(x))∣x∈A}.\{(x,f(x))\mid x\in A\}.

Power sets. The power set of AA is

P(A)={B∣B⊆A}.\mathcal P(A)=\{B\mid B\subseteq A\}.

This expression denotes a set whose elements are themselves sets.

Optimization. A feasible set can be described by constraints:

F={x∈Rn∣gi(x)≤0 for i=1,…,m}.F=\{x\in\mathbb R^n\mid g_i(x)\le 0 \text{ for }i=1,\ldots,m\}.

Probability. An event may be expressed as a subset of a sample space:

{ω∈Ω∣X(ω)>a}.\{\omega\in\Omega\mid X(\omega)>a\}.

In a formal probability model, this subset must also belong to the model’s designated collection of measurable events.

Foundational restrictions

A meaningful condition does not automatically determine a set. Unrestricted comprehension—the principle that every condition defines a set of all objects satisfying it—leads to contradictions.

The standard example is Russell’s paradox. If

R={x∣x∉x}R=\{x\mid x\notin x\}

were a set, its defining condition would imply

R∈R⟺R∉R,R\in R\quad\Longleftrightarrow\quad R\notin R,

a contradiction.

In Zermelo–Fraenkel set theory, the axiom schema of separation instead permits selection from an already existing set:

{x∈A∣P(x)}.\{x\in A\mid P(x)\}.

More precisely, each allowed formula PP, with suitable parameters, determines a subset of AA. Separation does not provide a universal set from which every conceivable collection can be selected.

Image constructions such as

{f(x)∣x∈A}\{f(x)\mid x\in A\}

are supported by the axiom schema of replacement when the defining rule assigns exactly one output to each input. Other constructions rely on additional axioms; for example, the existence of P(A)\mathcal P(A) is supplied by the power set axiom.

Set-builder notation therefore describes membership conditions, but the surrounding mathematical theory determines whether the collection described exists as a set.