# 4.1.2: Set-builder notation

- Page ID
- 10172

\(\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 *a*is 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 *y*are 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.