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.

Definition.

• $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

Definition. \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:

Definition. 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*}

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:

Definition. \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.

Learning to let go of your $x$s

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 $x$s. 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\}$.

Meta Data

Title: Set-Builder Notation
Date Posted: October 10, 2018
Posted By:
Category: sets
Tags: