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 specify sets using logical notation: if $P(x)$ is a property that is true or false for each thing $x$, then

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

is the collection of all $x$ such that $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. For example, if $P(x)$ is the property that $x$ is an even integer then $\{x:P(x)\}$ is the set consisting of all the even integers $\mathrm{\dots },-4,-2,0,2,4,\mathrm{\dots }$

Sometimes we already have a set $X$ and a property $P(x)$ that is true or false for each $x$ in $X$. For example, $X$ might be the set $ℝ$ of all real numbers, and $P(x)$ the property $x>0$. We write

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

(2.1)

for the set of all things $x$ in $X$ such that $P(x)$ is true. In the example, this set would be the set of all strictly positive real numbers, sometimes written $(0,\mathrm{\infty })$ in interval notation. The symbol $\in$ means ‘is an element of.’

These two ways of specifying a set are called set builder notation.

Sometimes we want to specify a set simply by listing its elements one by one. For example, the set whose elements are 1, 2, and 3 is written $\{1,2,3\}$, which is a short way of writing for the set builder notation

$$\{x:(x=1)\vee (x=2)\vee (x=3)\}.$$

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 }$. 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.

Two sets $X$ and $Y$ are defined to be equal if for all things $a$ we have $a\in X$ if and only if $a\in Y$ — that is, if and only if they have the same elements. It’s helpful to write this in terms of logical equivalence: the two sets

$$X=\{x:P(x)\},Y=\{x:Q(x)\}$$

are equal if and only if $P(x)$ and $Q(x)$ have the same truth value for every $x$. This definition of set equality has some important consequences. First, if

$$X=\{1,2\},Y=\{2,1\}$$

then $X=Y$ because these are shorthand for

$$X=\{x:(x=1)\vee (x=2)\},Y=\{x:(x=2)\vee (x=1)\}$$

and for any propositional variables $p$ and $q$, the WFFs $p\vee q$ and $q\vee p$ are logically equivalent. The order in which we list the elements of a set doesn’t matter. Similarly, if

$$X=\{1,1\},Y=\{1\}$$

then $X=Y$, because the two definitions above are shorthand for

$$X=\{x:(x=1)\vee (x=1)\},Y=\{x:x=1\}$$

and the two formulas $p\vee p$ and $p$ are logically equivalent. Repetition doesn’t matter.

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 $\{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.