2.1 Introduction to set theory

A set is a collection of (mathematical) objects. There is an entire field of mathematics called set theory dedicated to the study of sets and to their use as a foundation for mathematics, but in MATH0005 we are going to give only an informal introduction to sets and their properties. If you want to know more, see the further reading section at the end of this chapter.

We use curly brackets to denote sets and commas to separate the things in the set. $\{1,2,3\}$ is the set containing 1, 2, and 3.

Sets are what we use for reasoning about unordered collections of objects, ignoring repetition. Unordered means that we consider $\{1,2\}$ and $\{2,1\}$ the same set, ignoring repetition means that $\{1,1\}=\{1\}$. You will see why this is true when we make a definition of set equality shortly.

The things in a set are called its elements or members. We write $a\in X$ to mean that $a$ is an element or member of the set $X$, and $a\notin X$ to mean that $a$ is not an element or member of $X$.

There is a unique set with no elements, called the empty set and written $\mathrm{\varnothing }$ or $\{\}$. No matter what $a$ is, $a\notin \mathrm{\varnothing }$.

We allow any kind of mathematical object, including sets themselves, as elements of sets. Sets can contain functions, matrices, vectors, numbers, and sets themselves.

We need vocabulary for talking about one set being contained in another.

Thus $X$ being a proper subset of $Y$ means that $X$ is a subset of $Y$ and $Y$ contains something that $X$ does not contain.

There is an important way to rephrase the definition of two sets being equal: $X=Y$ if and only if $X\subseteq Y$ and $Y\subseteq X$. This is sometimes useful as a proof technique, as you can split a proof of $X=Y$ into first checking $X\subseteq Y$ and then checking $Y\subseteq X$.

Why is the last equality true? The only things which are elements of $\{1,2,1\}$ are 1 and 2. The only things which are elements of element of $\{1,2\}$ are 1 and 2. So the two sets are equal according to our definition. There’s no concept of something being an element of a set “more than once.”

This is the way in which our definition of set equality captures the idea of sets being unordered collections of objects which disregard repetition.

The definition of subset means that the empty set is a subset of any set. $\mathrm{\varnothing }\subseteq X$ for any set $X$, because $\forall x:x\in \mathrm{\varnothing }⟹x\in X$ is vacuously true: there’s nothing in $\mathrm{\varnothing }$ which could fail to be in the set $X$ in order to make $\mathrm{\varnothing }\subseteq X$ false.

Suppose we have a set $X$ and a property $P(x)$ that is true or false for each element $x$ of $X$. For example, $X$ might be the set $\mathbb{Z}=\{\mathrm{\dots },-2,-1,0,1,2,\mathrm{\dots }\}$ of all integers and $P(x)$ might be the property “$x$ is even”. We write

$$\{x\in X:P(x)\}$$

(2.1)

for the set of all elements of $X$ for which the property $P(x)$ is true. This is called set-builder notation. In our example,

$$\{x\in \mathbb{Z}:x\text{ is even}\}$$

is the set $\{\mathrm{\dots },-4,-2,0,2,4,\mathrm{\dots }\}$. In other texts you may see a $|$ in place of a $:$ in set builder notation; they mean exactly the same thing.

We sometimes use the notation $\{x:P(x)\}$ to mean the set of all things for which the property $P(x)$ is true.¹¹ 1 You have to be slightly careful with this kind of unrestricted comprehension because it can lead to contradictions. You can ignore this for the purposes of MATH0005, but if you want to know more then check out the Further Reading section at the end.