Set-builder Notation - Domain Notation

In set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a set by enumerating its elements or stating the properties that its members must satisfy.

Defining sets by properties is also known as set comprehension, set abstraction or as defining a set's intension.

Set-builder notation is sometimes simply referred to as set notation, although this phrase may be better reserved for the broader class of means of denoting sets.

Sets defined by enumeration

Introduction to Set-Builder Notation 127-1.16 - How to define sets with both the roster (or list) method and using set-builder notation. This video is provided by the Learning Assistance Center of Howard Community College. For more math...

A set is an unordered collection of elements. (An element may also be referred to as a member.) An element may be any mathematical entity.

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

• ${\displaystyle \{7,3,15,31\}}$ is a set holding the four numbers 3, 7, 15, and 31.
• ${\displaystyle \{a,c,b\}}$ is the set containing 'a','b', and 'c'.

This is sometimes called the "roster method" for specifying a set.

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

• ${\displaystyle \{1,2,3,\ldots ,100\}}$ is the set of integers between 1 and 100 inclusive.
• ${\displaystyle \{0,1,2,\ldots \}}$ is the set of natural numbers.
• ${\displaystyle \{\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 show an ordered sequence before (or after) the ellipsis as a convenient notational vehicle for explaining to a reader 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 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.

• ${\displaystyle \{}$ addresses on Pine Street ${\displaystyle \}}$ 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

ShowMe - Set-builder notation inequality. Source : www.showme.com

Set builder notation can be used to describe sets that are defined by a predicate, rather than explicitly enumerated. In this form, set builder notation has three parts: a variable, a colon or vertical bar separator, and a logical 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 \Phi (x)\}}$

or

${\displaystyle \{x:\Phi (x)\}.}$

The vertical bar, which can also be written as a 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 \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

This kind of set builder notation does not necessarily define a set. Russell's paradox shows that the expression ${\displaystyle \{x~|~x\not \in x\},}$ although seemingly well formed as a set builder expression, does not define a set. To avoid this issue, one generally considers only values of x that belong to some given set E, known as the "domain" (see "Set existence axiom" below). The set being defined can be explicitly denoted in set builder notation either by writing the domain on the left of the vertical bar:

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

or by adjoining it to the predicate:

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

The ∈ symbol here denotes set membership, while the ${\displaystyle \land }$ symbol denotes the logical "and" operator, known as logical conjunction.

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."

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,\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\geq m\}=\{m,m+1,m+2,\ldots \},}$. As an example, ${\displaystyle G_{3}=\{x\in \mathbb {Z} \mid x\geq 3\}=\{3,4,5,\ldots \}}$ and ${\displaystyle G_{-2}=\{-2,-1,0,\ldots \}}$.
• ${\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 (\exists k)[k\in \mathbb {N} \land n=2k]\}}$ is the set of all even natural numbers. The ${\displaystyle \land }$ 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 (\exists x)P(x)}$ is read as 'there exists an x such that P(x)".
• ${\displaystyle \{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.
• ${\displaystyle \{a\in \mathbb {R} \mid (\exists p\in \mathbb {Z} )(\exists q\in \mathbb {Z} )[q\not =0\land aq=p]\}}$ is the set of rational numbers; that is, real numbers that can be written as the ratio of two integers.

More complex expressions on the left side of the notation

ShowMe - Set-builder notation inequality. Source : www.showme.com

An extension of set-builder notation replaces the single variable x with a term that may include one or more variables, combined with functions acting on them. So instead of ${\displaystyle \{x\mid \Phi (x)\}}$, we may have ${\displaystyle \{\Psi (x_{1},\ldots ,x_{n})\mid \Phi (x_{1},\ldots ,x_{n})\},}$ which should be read

${\displaystyle \{\Psi (x_{1},\ldots ,x_{n})\mid \Phi (x_{1},\ldots ,x_{n})\}=\{y\mid \exists (x_{1},\ldots ,x_{n}),y=\Psi (x_{1},\ldots ,x_{n}){\text{ and }}\Phi (x_{1},\ldots ,x_{n})\}}$

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\not =0\}}$, where ${\displaystyle \mathbb {Z} }$ is the set of all integers, is the set of all rational numbers (Q).
• ${\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 replace t in the set builder notation to find

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

Equivalent predicates yield equal sets

Domain and Range · Algebra and Trigonometry. Source : philschatz.com

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

${\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} \land x^{2}=1)\Leftrightarrow (x\in \mathbb {Q} \land |x|=1).}$

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

Set existence axiom

ShowMe - Set and interval notations. Source : www.showme.com

In many formal set theories, such as Zermeloâ€"Fraenkel set theory, set builder notation is not part of the formal syntax of the theory. Instead, there is a set 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 Φ:

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

Z notation

In Z notation, the set of all x in a universe of discourse A that satisfy the condition P(x) is written

${\displaystyle \{x:A\mid P(x)\}}$.

In Z, the set membership of an element x in set A is written as ${\displaystyle (x:A)}$ instead of ${\displaystyle (x\in A)}$. Versions of set builder notation are also available in Z which allow for terms more complicated than a single variable, using a bullet to indicate the form of members of the set. For example,

${\displaystyle \{x:A\mid P(x)\bullet F(x)\}}$

denotes the set of all values F(x), where x is in A and P(x) holds.

Parallels in programming languages

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

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

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

See also

• Glossary of set theory

Notes