Variables and Sets

What is a set, and why is it the right starting point for all of mathematics? A set is just a collection of objects, with one rule: any object is either in the set or it is not, no partial memberships, no duplicates. That apparent triviality is the foundation that lets us talk about everything we want to talk about: numbers, points, functions, propositions, even other sets. Once you can write down a set, you can quantify over it, build operations on it, and reason about it precisely. In this section we cover the notation (membership, set-builder, the standard number systems) and the all-important distinction between free and bound variables, a distinction that decides whether a formula is a statement at all.

Membership and set-builder notation

If $A$ is a set, we write $x \in A$ for "$x$ is an element of $A$" and $x \notin A$ for "$x$ is not an element of $A$." A small set can be listed in roster notation: $A = {2, 3, 5, 7}$. Larger or infinite sets are described by a defining property using set-builder notation:

Read aloud: "the set of all $x$ such that $P(x)$." The bar $\mid$ separates the dummy variable from the defining property. Often we restrict the dummy variable to a known set first: ${x \in \mathbb{Z} \mid x > 0}$ is the set of positive integers.

The standard number systems

Four number systems appear so often they get reserved blackboard-bold names:

$\mathbb{N} = {0, 1, 2, 3, \ldots}$, the natural numbers. Some authors start at 1; Velleman starts at 0.

the integers (German Zahlen).

$\mathbb{Q}$, the rational numbers, ratios $a/b$ with $a, b \in \mathbb{Z}$ and $b \neq 0$.

$\mathbb{R}$, the real numbers, every point on the number line.

They sit in a tidy chain of inclusions: $\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R}$. Each inclusion is strict: $-1 \in \mathbb{Z}$ but $-1 \notin \mathbb{N}$; $\tfrac{1}{2} \in \mathbb{Q}$ but $\tfrac{1}{2} \notin \mathbb{Z}$; $\sqrt{2} \in \mathbb{R}$ but $\sqrt{2} \notin \mathbb{Q}$.

Free vs. bound variables

A variable in a formula is bound if it is captured by a quantifier or by a set-builder; otherwise it is free. In ${x \mid x > y}$ the dummy variable $x$ is bound (its scope is the entire set definition) while $y$ is free, the meaning of the expression depends on what value of $y$ you have in mind. Renaming a bound variable does not change the set: ${x \mid x > y}$ and ${t \mid t > y}$ are exactly the same set.

A formula with no free variables is a statement: it has a definite truth value (true or false). A formula with free variables is sometimes called a predicate or an open sentence, its truth value depends on what values you plug into the free slots. So $x^2 = 4$ is not a statement (its truth depends on $x$), but $\forall x \in \mathbb{R}, x^2 \geq 0$ is a statement (it is true, period).

Pause and think: In the formula $\exists y \in \mathbb{Z}, y > x$, which variable is free and which is bound? If you replaced $x$ with the number $5$, would the result be a statement? (Hint: bound variables are absorbed by the quantifier; only free variables show up in the truth-condition.)

Try it

• Before listing: predict how many elements are in ${x \in \mathbb{Z} \mid -3 \leq x \leq 4}$. Then write them all out and check your count.
• Classify each by free/bound: in ${n \in \mathbb{N} \mid n^2 < k}$, name the bound variable, the free variable, and decide whether the formula is a statement.
• Predict first: is $\sqrt{9}$ in $\mathbb{N}$? Is it in $\mathbb{Z}$? Is it in $\mathbb{Q}$? Now verify by computing $\sqrt{9}$.
• Translate into set-builder notation: "all integers whose absolute value is less than 10." Then translate "the set of rational numbers strictly between $0$ and $1$."
• Pick a value of $x$ for which $x^2 < 5$ is true and one for which it is false. The formula itself is not a statement, explain why.

A trap to watch for

A surprisingly common mistake is treating set-builder notation as if it described a list rather than a set. Sets do not record order or multiplicity: ${1, 2, 2, 3} = {1, 2, 3} = {3, 1, 2}$. So when you write ${x \in \mathbb{Z} \mid x^2 \leq 4}$, you describe ${-2, -1, 0, 1, 2}$, not five separate items in a particular order, just five members of one set. If a problem cares about order or repetition, you want a sequence or a tuple, not a set; that distinction will matter once you start studying ordered pairs in Chapter 4.

What you now know

You can read and write set-builder notation, navigate the chain $\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R}$, and tell whether a formula is a statement by spotting its free variables. The next section combines pairs of sets with operations, union, intersection, complement, that mirror the logical connectives $\vee, \wedge, \neg$ you learned in §1.1.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, ch. 1.
• Halmos, P. R. (1960). Naive Set Theory. Van Nostrand, §§1–2.
• Enderton, H. B. (1977). Elements of Set Theory. Academic Press, ch. 2.
• Kunen, K. (2009). The Foundations of Mathematics. College Publications, ch. 1.