Skip to main content

# 3.1.2: Set-builder notation

$$\mathbb{N}=\{0,1,2,3, \ldots\}$$

However, this is an informal notation, which is not really well-defined, and it should only be used in cases where it is clear what it means. It’s not very useful to say that “the set of prime numbers is {2, 3, 5, 7, 11, 13, . . . }”, and it is completely meaningless to talk about “the set {17, 42, 105, . . . }”. Clearly, we need another way to specify sets besides listing their elements. The need is fulfilled by predicates.

If P(x) is a predicate, then we can form the set that contains all entities a such that ais in the domain of discourse for P and P(a) is true. The notation {x | P(x)} is used to denote this set. This is the intensional definition of the set. The name of the variable, x, is arbitrary, so the same set could equally well be denoted as {z | P(z)} or {r | P(r)}. The notation {x | P(x)} can be read “the set of x such that P(x)”. We call this the set-builder notation, as you can think of the predicate as a building material for the elements of the set. For example, if E(x) is the predicate ‘x is an even number’, and if the domain of discourse for E is the set N, then the notation {x | E(x)} specifies the set of even natural numbers. That is,

$$\{x | E(x)\}=\{0,2,4,6,8, \dots\}$$

It turns out, for deep and surprising reasons that we will discuss later, that we have to be a little careful about what counts as a predicate. In order for the notation {x | P(x)} to be valid, we have to assume that the domain of discourse of P is in fact a set. (You might wonder how it could be anything else. That’s the surprise!)

Often, it is useful to specify the domain of discourse explicitly in the notation that defines a set. In the above example, to make it clear that x must be a natural number, we could write the set as {x ∈ N | E(x)}. This notation can be read as “the set of all x in N such that E(x)”. More generally, if X is a set and P is a predicate whose domain of discourse includes all the elements of X, then the notation

$$\{x \in X | P(x)\}$$

is the set that consists of all entities a that are members of the set X and for which P(a) is true. In this notation, we don’t have to assume that the domain of discourse for P is a set, since we are effectively limiting the domain of discourse to the set X. The set denoted by {x X | P(x)} could also be written as {x | x X P(x)}.

We can use this notation to define the set of prime numbers in a rigorous way. A prime number is a natural number n which is greater than 1 and which satisfies the property that for any factorization n = xy, where x and yare natural numbers, either x or y must be n. We can express this definition as a predicate and define the set of prime numbers as

$$\{n \in \mathbb{N} |(n>1) \wedge$$

$$\forall x \forall y((x \in \mathbb{N} \wedge y \in \mathbb{N} \wedge n=x y) \rightarrow(x=n \vee y=n)) \}$$

Admittedly, this definition is hard to take in in one gulp. But this example shows that it is possible to define complex sets using predicates.