Set-Builder Notation

Recall that, by definition, S being a set is equivalent to ``x\in S" being an open sentence. This means that the theory of sets and the theory of logic are basically the same--differing only by notation and perspective. One can exploit this correspondence by using open sentences to define sets. Given an open sentence P(t), we can define the corresponding set S_P, which consists of all values t so that P(t) is true. We write

    \[S_P=\left\{t\middle\vert P(t)\right\}\]

and read aloud ``S_P is the set of all t such that P(t)." In other words, S_P is the set so that x\in S_P means exactly P(x). This way of defining sets has the unfortunately puerile name set-builder notation. It's how most sets in most mathematics texts are defined. By way of example, we'll rephrase some previous definitions.


  • A^c=\left\{x\middle\vert x\notin A\right\}
  • A\cup B= \left\{p\middle\vert p\in A\vee p\in B\right\}

Activity Complete the list of set operations by giving set-builder descriptions of each of the following set operations.

  • A\cap B
  • A\setminus B
  • \left(A\setminus B\right)\cup\left(B\setminus A\right)
  • 2^B

Exercise. Consider two sets, A=\left\{x\middle\vert P(x)\right\} and B=\left\{t\middle\vert Q(t)\right\}. What can we say about the open sentences P and Q if we know each of the following facts about the sets A and B?

  • A=B
  • A\subseteq B
  • A=\varnothing
  • B is the universe

The last exercise referenced the universe, which naturally leads to the question of how to specify the universe in set-builder notation. An even number is an integer which is twice some other integer. So we could write


*** QuickLaTeX cannot compile formula:
\begin{equation*}\left\{n\middle\vert n\in\mathbb{Z}\wedge\exists k:\left(k\in \mathbb{Z}\wedge n=2k\right) \right\}
But the right-hand side (after the pipe symbol $\vert$) is a little crowded. Doing the same trick as we did in, we want to handle the conditions $n\in\mathbb{Z}$ and $k\in\mathbb{Z}$ by changing the universe. We do this as follows:
<strong>Definition. </strong>The set of even numbers is the set \begin{equation*}\left\{n\in\mathbb{Z}\middle\vert \exists k\in\mathbb{Z}:n=2k\right\}\end{equation*}

*** Error message:
Display math should end with $$.
leading text: side (after the pipe symbol $\vert

We would read this aloud ``The set of all integers n such that there is an integer k with n=2k." In this version of set-builder notation, the left-hand side (before the pipe) is about what kind of objects the elements of the set being defined are; the right-hand side gives a condition that describes the set.

There is yet another way to use set-builder notation to define a set, as exemplified:


    \begin{equation*} \left\{2k\middle\vert k\in\mathbb{Z}\right\} \end{equation*}

We would read this aloud ``The set of a numbers of the form 2k, where k is an integer." Notice that n has disappeared entirely from this version. In this version of set-builder notation, the left-hand side gives the general form of the elements of the set, and the right-hand side tells us which elements of that form actually occur in the set.

Where are the quantifiers?

Learning to let go of your xs

An open sentence like

    \[E(x):\ \ \ \exists k: x=2k\]

has two variables and one quantifier. The two variables are used in quite different ways. First, notice that the only variable that's eligible for plugging in to E is x: we can sensibly ask Is it true that E(2)? and Is it true that E(3)?. But substituting for k like this:

    \[\exists 7: x=2\cdot 7\]

yields nonsense.

What's going on here? Variables where we can plug in values and get something sensible (like x here) are called free. The other kind of variable (like k here) is called a bound variable, from the verb bind. The idea is that the quantifier \exists has a binding effect on the variable. You can recognize bound variables in three ways:

  • Substituting for a bound variable results in nonsense; substituting for a free variable does not.
  • Bound variables almost always occur exactly twice; free variables occur once.
  • There is always a way to read a mathematical formula containing a bound variable in a way that makes the bound variable go away.

I'll illustrate these checks by giving some examples of bound variables, one of which you've seen before:

Consider the integral

    \[\int_a^b x^2\ dx\]

The variables a and b are free; the variable x is bound.

  • We could substitute in for a and b: \int_1^3x^2\ dx. If we substitute for x, we get \int_a^b 7^3\ d7, which is nonsense.
  • The variable x occurs twice: once in the integrand and once in the differential.
  • We could read this integral aloud as ``The integral, from a to b, of the squaring function."

Consider the (true) statement

    \[\forall x, x^2<9 \Rightarrow x^3<27\]

Here, the variable x is bound and there are no free variables.

  • If we tried to substitute, we'd get something like \forall 4, 4^2<9 \Rightarrow 4^3<27, which doesn't make sense.
  • The variable x occurs twice: once in the open sentence x^2<9 \Rightarrow x^3<27, and once in the quantifier.
  • We could read this aloud as ``If a number's square is less than 9, its cube is less than 27."

One very important trick to do with a bound variable is to replace it, across the board, with another variable. I call this letting go of your xs. So for example, in an integral we can change the integrating variable at whim:

    \[\int_1^3 x^2\ dx=\frac{26}{3}=\int_1^3 y^2\ dy\]

We can do the same with quantified statements and open sentences:

    \[\forall x, x^2<9 \Rightarrow x^3<27\text{ means the same thing as } \forall q, q^2<9 \Rightarrow q^3<27\]

What does all this have to do with sets and set-builder notation? Observe that the variables that appear in set-builder notation are almost all bound, which we can tell because they occur twice (once on each side of the pipe). For example:

    \[\left\{x\middle\vert -1<x<1\right\}\]

is the same set as

    \[\left\{g\middle\vert -1<g<1\right\}\]

which in turn is the same set as

    \[\left\{t\middle\vert -1<t<1\right\}\]

The point is that the particular choice of variable x or y or Z or p or \varphi has no significance at all. By way of example, if A=\left\{ x \middle\vert x^2 \in[1,3)\right\}, then

    \[t\in A\text{ means that } t^2\in[1,3)\]

    \[F\in A\text{ means that } F^2\in[1,3)\]

In particular, our definition of A does not create any particular link between the letter x and the set A. We could just as well have defined A=\left\{ z \middle\vert z^2 \in[1,3)\right\}.

Published in sets.