Set-builder notation

Specifying sets by member properties is allowed by the axiom schema of specification. This is also known as set comprehension and set abstraction.

Sets defined by a predicate

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. In this form, set-builder notation has three parts: a variable, a colon or vertical 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 the rule or the predicate. 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 ${\displaystyle \{x\mid \mathrm{\Phi }(x)\}}$ is the set of all values of x that satisfy the formula Φ. It may be the empty set, if no value of x satisfies the formula.

Specifying the domain

A domain E—that is a set to which the notation defines a subset—can appear on the left of the vertical bar:

${\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 ⁠${\displaystyle \in }$⁠ denotes set membership, and the symbol ${\displaystyle \wedge }$ denotes the logical and operator). This notation represents the set of all values of x that belong to the set E and for which the predicate is true. The subset axiom insures that if E is a set and ⁠${\displaystyle \mathrm{\Phi }}$⁠ is a predicate, the notation defines always a set, which is a subset of E. If ${\displaystyle \mathrm{\Phi }(x)}$ has the form ${\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 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.

In the cases where the domain E is not defined (implicitly or explicitly), it may occur that the notation does not define a set, but a proper class. For example, Russell's paradox shows that the expression ${\displaystyle \{x\mid x\notin x\},}$ although seemingly well formed as a set builder expression, cannot define a set without producing a contradiction.

In some cases, the notation may define a set that is not a subset of a previously defined set. This is the case of the power set of a set E, which is defined as $${\displaystyle \mathcal{P}(E)=\{x\mid x\subset E\}=\{x\mid y\in x⟹y\in E\}.}$$ The fact that this defines a set is an axiom of set theory, called the axiom of power set.

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.

• ${\displaystyle \{x\in \mathbb{R}\mid x>0\}}$ is the set of all strictly positive real numbers, which can be written in interval 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\}}$; see equivalent predicates yield equal sets below.
• For each integer m, 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 \}}$.
• ${\displaystyle \{(x,y)\in \mathbb{R}\times \mathbb{R}\mid 0<y<f(x)\}}$ is the set of pairs of real numbers such that y is greater than 0 and less than f(x), for a given function f. Here the cartesian 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 all even natural numbers. The ${\displaystyle \wedge }$ sign stands for "and", which is known as logical conjunction. The ∃ sign stands for "there exists", which is known as existential quantification. So for example, ${\displaystyle (\mathrm{\exists }x)P(x)}$ is read as "there exists an x such that P(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 that n 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 of rational numbers; that is, real numbers that can be written as the ratio of two integers.