We discuss the notions of set builder. It is another way to describe a set.
In set-builder form, a set #\blue A# is described by means of a property #P# for an element #a# to belong to #\blue A#.
This means that an object #a# is an element of #\blue A# if and only if property #P# holds for #a#.
The corresponding notation is #\blue A = \{a \mid P \}#. This can be read as "The set #\blue A# consists of all elements #a# that satisfy property #P#".
We use the following two methods for formulating the set builder more succinctly. Here #P# is a statement, #S# is a set, and #f(x)# is an expression involving #x#.
- #\{a\in S \mid P \} =\{a \mid P \land \left(a\in S\right)\}#
- #\{f(x) \mid P \} =\{a \mid P \land a=f(x)\}#
Example
\[\begin{array}{rcl}\blue{\mathbb{Z}}&=&\{\dots, -2, -1, 0, 1, 2, \dots\}\\&& \\ \blue {\mathbb{Z}}&=&\{x \mid x ~\text{is an integer} \} \end{array}\]
The set of even integers is
\[\left\{x\,\left|\, x\in\mathbb{Z} \text{ and } 2 \text{ divides } x\right.\right\}\]
It can also be given in one of the following forms.
- #\left\{a\in\mathbb{Z}\,\left|\, 2 \text{ divides } a\right.\right\}#
- #\left\{2x\,\left|\,x\in\mathbb{Z}\right.\right\}#
If we have \[ P = a\in \mathbb{Z} \text{ and } a \lt 10\text{ and } a\gt 0\] then #\left\{a\mid P\right\}# is the set of all natural numbers smaller than #10#.
If we instead have \[ P = \left(\rv{x,y}\text{ lies on the unit circle around the origin}\right)\] then #\left\{ \rv{x,y} \mid P \right\}# describes the set of points in the plane on the unit circle.
If #P# is always false, then #\blue A=\emptyset#.
If #P # is always true, then #\blue A# is the "universe"; each element we can think of belongs to #A#. This set is too big to be of use for us, so it hardly ever appears in mathematics and in our course.
The property #P# in the set-builder #\blue A = \{a\mid P\}# is a statement about #a# that can take the values true or false. Such statements are known as propositions in logic.
Verifying whether #P# is satisfied (that is, takes the value true) for a particular object #a# amounts to deciding whether #a# belongs to the set. For a good definition of a set, some requirements on the property #P# are needed.
We will not go into details, but give an impossible property in the Paradox appearing further on.
We also note that caution is needed in the choice of variables (also called proposition letters) occurring in #P#. For instance, for the definition #\blue A = \{a\mid P\}# to make sense, we cannot have #\blue A# occurring in #P# (imagine
#\blue A = \{a\mid a\not\in A\}#) and the possibilities are scarce if the variable #a# does not occur in #P# (think of the comment Two extremes).
The variable #a# is regarded as a bound variable. This relates to the following two important properties.
- The name of the variable has no other meaning than to relate one occurrence to another inside #\{a\mid P\}#. So if #\blue A = \{a\mid 3a\in \mathbb{N}\}#, then we regard the description as being the same as #\blue A = \{b\mid 3b\in \mathbb{N}\}#. Of course we need to avoid using a variable name that is already taken elsewhere in #P#. For example, in the description #\blue A = \left\{a\,\left|\, {a}\in \mathbb{N}\land \frac{a}{m}\in \mathbb{N}\right.\right\}#, where #m# is a natural number, we cannot replace #a# by #m#. We would get #\blue A = \left\{m\,\left|\, {m}\in \mathbb{N}\land \frac{m}{m}\in \mathbb{N}\right.\right\} = \{m\}#, where #m# is a natural number. Which is not the same.
- The scope of the name #a# is just the expression #\{a\mid P\}#. If #a# occurs outside this expression, it does not stand for the same internal variable #a#. So if #\blue A = \{a\mid 3a\in \mathbb{N}\}#, the expression #a\not\in \blue A # still makes sense; it just means #3a\not\in \mathbb{N}#.
A classical paradox making clear that requirements on #P# are needed arises from the property
\[P= \left(b \text{ is a barber who shaves all persons, and those only, who do not shave themselves}\right)\]
Now consider \(B=\left\{b\mid P\right\}\). If #b\in B#, then #b# is a barber who shaves all persons who do not shave themselves and none other. This implies that #b# is a barber. But does #b# shave himself? If he doesn't, then #b\in B# implies that #b# does shave himself, a contradiction. So #b# must shave himself. But #b\in B# implies that #b# shaves none other than those that do not shave themselves, so #b# does not shave himself, again a contradiction.
Logic can be set up so as to avoid such conflicts. Here, the paradox serves as a warning that propositions used for defining sets must be reasonable (pun intended).
The method of describing sets by enumerating its elements does not work for sets, such as #\mathbb{R}#, that are not enumerable. A typical example where the set-builder form works and enumeration does not is an interval of real numbers.
For instance, the interval of all real numbers #x# lying between #-\pi# and #\pi#, is given by
\[\ivcc{-\pi}{\pi} = \left\{x\mid x\in\mathbb{R}\ \land x\ge -\pi \land x\le \pi\right\}\]
This set is not enumerable.
Determine the value of the pair #\rv{a,b}# of integers for which the set
\[\left\{ x\,\left|\, x=a\cdot m+b\text{ for some natural number }m\right.\right\} \]
is equal to
\[\left\{3,4,5,\ldots\right\}\]
#\rv{a,b}=# #\rv{1,2}#
The expression #a\cdot m+b# increases for #m=1,2,\ldots#, so the first element , # 3 #, in the explicit description of the set must be equal to #a\cdot 1+ b# and the second to #a\cdot 2 + b#. This gives the system of equations
\[\eqs{ a+b &=& 3\\2a+b &=& 4}\]
The only solution of this system of two linear equations with two unknowns is #\rv{a,b}=\rv{1,2}#. Since #a# and #b# are integers, the answer is #\rv{a,b}= \rv{1,2}#.
Set builders
