Skip to main content

Section B.2 Intersections and Unions

When \(X\) and \(Y\) are sets, the intersection of \(X\) and \(Y\text{,}\) denoted \(X\cap Y\), is defined by

\begin{equation*} X\cap Y = \{x: x\in X, x\in Y\} \end{equation*}

Note that this notation uses the convention followed by many programming languages. Namely, the “comma” in the definition means that both requirements for membership be satisfied. For example, if \(X=\{b,c,e,g,m\}\) and \(Y=\{a,c,d,h,m,n,p\}\text{,}\) then \(X\cap Y=\{c,m\}\text{.}\)

Subsection B.2.1 The Meaning of \(2\)-Letter Words

In the not too distant past, there was considerable discussion in the popular press on the meaning of the \(2\)-letter word is. For mathematicians and computer scientists, it would have been far more significant to have a discussion of the \(2\)-letter word or. The problem is that the English language uses or in two fundamentally different ways. Consider the following sentences:

  1. A nearby restaurant has a dinner special featuring two choices for dessert: flan de casa or tirami-su.

  2. A state university accepts all students who have graduated from in-state high schools and have SAT scores above \(1000\) or have grade point averages above \(3.0\text{.}\)

  3. A local newspaper offers customers the option of paying their for their newspaper bills on a monthly or semi-annual basis.

In the first and third statement, it is clear that there are two options but that only one of them is allowed. However, in the second statement, the interpretation is that admission will be granted to students who satisfy at least one of the two requirements. These interpretations are called respectively the exclusive and inclusive versions of or. In this class, we will assume that whenever the word “or” is used, the inclusive interpretation is intended—unless otherwise stated.

For example, when \(X\) and \(Y\) are sets, the union of \(X\) and \(Y\text{,}\) denoted \(X\cup Y\text{,}\) is defined by

\begin{equation*} X\cup Y = \{x: x\in x \text{ or } x\in Y\}. \end{equation*}

For example, if \(X=\{b,c,e,g,m\}\) and \(Y=\{a,c,d,h,m,n,p\}\text{,}\) then

\begin{equation*} X\cup Y=\{a,b,c,d,e,g,h,m,n,p\}. \end{equation*}

Note that \(\cap\) and \(\cup\) are commutative and associative binary operations, as is the case with addition and multiplication for the set \(\posints\) of positive integers, i.e., if \(X\text{,}\) \(Y\) and \(Z\) are sets, then

\begin{equation*} X\cap Y = Y\cap X \quad\text{ and } \quad X\cup Y = Y\cup X. \end{equation*}

Also,

\begin{equation*} X\cap(Y\cap Z)= (X\cap Y)\cap Z\quad\text{ and } \quad X\cup(Y\cup Z)= (X\cup Y)\cup Z. \end{equation*}

Also, note that each of \(\cap\) and \(\cup\) distributes over the other, i.e.,

\begin{equation*} X\cap(Y\cup Z)= (X\cap Y)\cup (X\cap Z)\quad\text{ and } \quad X\cup(Y\cap Z)= (X\cup Y)\cap (X\cup Z) \end{equation*}

On the other hand, in \(\posints\text{,}\) multiplication distributes over addition but not vice-versa.

Subsection B.2.2 The Empty Set: Much To Do About Nothing

The empty set, denoted \(\emptyset\) is the set for which \(x\notin \emptyset\) for every element \(x\text{.}\) Note that \(X\cap \emptyset =\emptyset\) and \(X\cup \emptyset=X\text{,}\) for every set \(X\text{.}\)

The empty set is unique in the sense that if \(x\notin X\) for every element \(x\text{,}\) then \(X=\emptyset\text{.}\)

Subsection B.2.3 The First So Many Positive Integers

In this text, we will use the symbols \(\posints\text{,}\) \(\ints\text{,}\) \(\rats\) and \(\reals\) to denote respectively the set of positive integers, the set of all integers (positive, negative and zero), the set of rational numbers (fractions) and the set of real numbers (rationals and irrationals). On occasion, we will discuss the set \(\nonnegints\) of non-negative integers. When \(n\) is a positive integer, we will use the abbreviation \([n]\) for the set \(\{1,2,\dots,n\}\) of the first \(n\) positive integers. For example, \([5]=\{1,2,3,4,5\}\text{.}\) For reasons that may not be clear at the moment but hopefully will be transparent at the right moment, we use the notation \(\bfn\) to denote the \(n\)-element set \(\{0,1,2,\dots,n-1\}\text{.}\) Of course, \(\bfn\) is just the set of the first \(n\) non-negative integers. For example, \(\mathbf{5}=\{0,1,2,3,4\}\text{.}\)

Subsection B.2.4 Subsets, Proper Subsets and Equal Sets

When \(X\) and \(Y\) are sets, we say \(X\) is a subset of \(Y\) and write \(X\subseteq Y\) when \(x\in Y\) for every \(x\in X\text{.}\) When \(X\) is a subset of \(Y\) and there exists at least one element \(y\in Y\) with \(y\notin X\text{,}\) we say \(X\) is a proper subset of \(Y\) and write \(X\subsetneq Y\). For example, the \(P\) of primes is a proper subset of the set \(\posints\) of positive integers.

Surprisingly often, we will encounter a situation where sets \(X\) and \(Y\) have different rules for membership yet both are in fact the same set. For example, let \(X=\{0,2\}\) and \(Y=\{z\in\ints: z+z=z\times z\}\text{.}\) Then \(X=Y\text{.}\) For this reason, it is useful to have a test when sets are equal. If \(X\) and \(Y\) are sets, then

\begin{equation*} X = Y \quad\text{ if and only if } \quad X\subseteq Y \text{ and } Y\subseteq X. \end{equation*}