Master of Science in Mathematics

Lecture Notes. Accessed on: 2019-10-21 18:16:07

We discuss the basics of elementary set theory including set operations such as unions, intersections, complements, and Cartesian products. We also demonstrate how to work with families of sets.

For a brief discussion of the reviews of (elementary) Halmos’ Naive Set Theory read this. A solid understanding of propositional and predicate logic is strongly recommended. To get the most from this article, a basic understanding of number theory and linear algebra are also recommended – but not required.

We leave the term ** set** undefined. We also leave the term

**undefined. We say $x$ belongs to a set $A$ and we write $x\in A$. We instead, sometimes say $x$ is an**

*belonging***of $A$, or even $x$ is a**

*element***of a set $A$. We will say that a set is a collection of objects. The**

*member***, or universal set, usually denoted by $U,$ is the set of all elements under discussion. For example, if $U$ consists of the elements 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10, then the equation $$A=\{0,1,2,3,4,5\}$$ describes a set $A$ made up of the six elements $0,$ 1, 2, 3, 4, and $5.$**

*universe*A set is determined by its elements and not by any particular order. In other words set $A$ is just as easily specified by $$A=\{5,4,3,2,1,0\}.$$ Sets are often described by properties of the elements using the ** set-builder notation** $$ \{ \qquad \mid \qquad \qquad \} \qquad \text{ or } \qquad \{ \qquad : \qquad \qquad \}$$ A variable is indicated before the colon, and the properties are given after the colon. For example, \begin{equation} \label{setbuilder}\{n \mid n\in \mathbb{N} \text{ and $n$ is odd}\}.\end{equation} represents the set of nonnegative odd integers, i.e. the set $\{0,1,3,5,7,\ldots \}.$ The colon is alway read

**and so setbuilder can be read as \emph{the set of all $n$ such that $n$ is a natural number and is odd}. Certainly the most important sets are sets of numbers. Throughout we use $\mathbb{N}$, $\mathbb{Z}$, and $\mathbb{Q}$ to denote the set of natural numbers, the set of integers, and the set of rational numbers, respectfully. Note that we include 0 among the natural numbers: $$\mathbb{N}=\{0,1,2,3,4,5,6,\ldots\}. $$ The set of all positive, zero, or negative numbers, are called the**

*such that***. Numbers of the form $m/n,$ where $m,n$ are integers and $n\neq 0$ are called the**

*integers***since they are ratios of integers. The set of**

*rational numbers***, rational or not, contains all the numbers in $\mathbb{Q},$ and many others as well such as $\sqrt{2}$, $\sqrt{3}$, $\sqrt[3]{3}$, $\sqrt[5]{3}-\pi$, and $e$ and so on. The most basic property of belonging is that of**

*real numbers***. For example, if $$A=\{x\in \mathbb{R} \mid -9+21 x-10 x^2=0\}, \quad B=\left\{\frac{3}{5},\frac{3}{2}\right\}$$ then $A=B.$ To see this notice that $-9+21 x-10 x^2=(2x-3)(3-5x)=0$ precisely when $x=3/5$ or $x=3/2.$**

*equality*** Definition**. Two sets $A$ and $B$ are called

**, denoted by $A=B,$ provided they consist of the same elements. If $A$ and $B$ are not equal we write $A\neq B.$**

*equal*** Principle**. (

**) Two sets are equal if and only if they contain the same elements.**

*Extension*Let $A$ and $B$ be sets. If every element of $A$ is an element of $B,$ we say $A$ is a ** subset** of $B,$ or $B$

**$A,$ and we write $A\subseteq B,$ or $B\supseteq A.$ Notice that**

*contains***$\subseteq$ has a few nice properties. It is**

*set inclusion***, meaning $A\subseteq A$ for any set $A$; and is**

*reflexive***, meaning, if $A \subseteq B$ and $B\subseteq C$ then $A\subseteq C$ for all sets $A, B, C.$**

*transitive*By the principle of extension, set inclusion is also ** antisymmetric** meaning $A\subseteq B$ and $B\subseteq A$ together imply $A=B.$ You might have noticed that equality is also reflexive and transitive. Equality is also

**, meaning if $A=B$ then $B=A,$ for all sets $A, B.$**

*symmetric*The next principle is designed to produce new sets out of known ones. We use the notation $P(x)$ to mean a mathematical statement $P$ which depends on the free variable $x.$

** Principle**. (

**) To every set $A$ and to every condition $P(x)$ there corresponds a set $B$ whose elements are exactly those elements $x$ of $A$ for which $P(x)$ holds.**

*Specification*By Extension, the set $B$ in the Specification is uniquely determined. Also by Specification, the set $\{x\in A \mid x\neq x \},$ denoted by $\emptyset,$ exists and is called the ** empty set**. This of course assumes that there exists a set $A$ in the first place, as we have assumed all along. Of course the empty set is a subset of every set. The next question that comes to mind is: are there enough sets to ensure that every set belongs to some set? Let $A$ and $B$ be sets. If every element of $A$ is an element of $B$, we say $A$ is a

**of $B$, or sometimes we say $B$**

*subset***$A$, and we write $A\subseteq B$, or $B\supseteq A$. For example, $\{1,4,a\}\subseteq \{0,1,3,4,a,b\}$ or as another example the inclusions hold $\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q}\subseteq \mathbb{R}.$**

*contains*** Definition**. A set $A$ is called a

**of a set $B,$ denoted by $A\subseteq B,$ provided every element of $A$ is also an element of $B.$**

*subset*The symbol $\emptyset$ is the last letter in the Danish-Norwegian alphabet.

** Definition**. The unique set that has no elements is called the empty set and is denoted by $\emptyset.$

Recall the tautologies $p\rightarrow p$ and $((p\rightarrow q)\land (q\rightarrow r))\rightarrow (p\rightarrow r).$

** Theorem**. Let $A$, $B$, and $C$ be subsets of a universal set $U.$

$\qquad (1)$ $A\subseteq A$

$\qquad (2)$ $(A\subseteq B \land B\subseteq C) \rightarrow A\subseteq C.$

** Proof**. Let $x$ be an arbitrary element of $A.$ Then $x$ is in $A$ and so $A\subseteq A.$ For the second statement, assume $x$ be an arbitrary element of $A.$ Since $A\subseteq B,$ we have $x\in B$ by definition of subset. Since $B\subseteq C,$ we have $x\in C$ by definition of subset, whence $A\subseteq C.$

To show that $A=B$ one must prove that $x\in A\leftrightarrow x\in B$; that is, $x\in A$ if and only if $x\in B.$ This is equivalent to proving that $x\in A\rightarrow x\in B$ and $x\in B\rightarrow x\in A.$ There are two parts to such a proof: first assume that $x\in A$ and show that $x\in B$ follows. Then assume, independently, that $x\in B$ and show that $x\in A$ follows. The reader is encourage to justify each step in this proof.

** Theorem**. For any two subsets $A$ and $B$ of a universal set $U,$\begin{equation}\label{eqsetsone} A=B \leftrightarrow (A\subseteq B \land B\subseteq A). \end{equation}

** Proof**. We proceed as follows \begin{align*} A=B & \leftrightarrow \forall x, (x\in A \leftrightarrow x\in B) \\ & \leftrightarrow \forall x, [(x\in A\rightarrow x\in B)\land (x\in B\rightarrow x\in A)] \\ & \leftrightarrow [\forall x, x\in A \rightarrow x\in B]\land [\forall x, (x\in B\rightarrow x\in A)]\\ & \leftrightarrow (A\subseteq B) \land (B\subseteq A) \end{align*} as needed.

** Theorem**. For any two subsets $A$ and $B$ of a universal set $U,$ \begin{equation} \label{subsetsmean} A\subseteq B \leftrightarrow \forall C (C\subseteq A \rightarrow C\subseteq B). \end{equation}

** Proof**. First we show that \begin{equation} \forall C, (C\subseteq A\rightarrow C\subseteq B)\rightarrow A\subseteq B. \end{equation} Assume that for any set $C,$ if $C\subseteq A,$ then $C\subseteq B.$ Since $A\subseteq A,$ it follows that $A\subseteq B$ as needed. Next it must be shown that \begin{equation} A\subseteq B \rightarrow \forall C, (C\subseteq A \rightarrow C\subseteq B). \end{equation} Assume $A\subseteq B$ and let $C$ be any set such that $C\subseteq A.$ Then we have $C\subseteq A$ and $A\subseteq B,$ and so we have $C\subseteq B.$

** Theorem**. Let $A$ be a subset of a universal subset $U.$ Then for all $x\in U,$ \begin{equation} \label{elesubst} x\in A \leftrightarrow \{x\}\subseteq A. \end{equation}

** Proof**. The proof is left for the reader.

Set inclusion is also antisymmetric meaning $A\subseteq B$ and $B\subseteq A$ together imply $A=B$. Equality is also ** symmetric**, meaning if $A=B$ then $B=A$, for all sets $A, B$.

** Theorem**. For any two subsets $A$ and $B$ of a universal set $U,$

$\qquad (1)$ $A=B \leftrightarrow B=A,$ and

$\qquad (2)$ $(A\subseteq B \land B\subseteq A) \rightarrow A=B.$

** Proof**. The proof is left for the reader.

A subset $B$ of a set $A$ is said to be a ** proper subset** of $A$ if it is not equal to $A$ itself. Thus all subsets of $A$ are proper subsets except the set $A$ itself, which is referred to as the

**of $A.$**

*improper subset*** Definition**. A set $A$ is called a proper subset of a set $B$ provided $A\subseteq B$ and $A\neq B.$ We write $A\subset B$ to denote that $A$ is a proper subset of $B.$

** Theorem**. For any two subsets $A$ and $B$ of a universal set $U,$ \begin{equation} A\subset B \leftrightarrow [A\subseteq B \land \exists x, (x\in B \land x\notin A)]. \label{eqsets} \end{equation}

** Proof**. Assume $A\subset B.$ Then $A\subseteq B$ and $A\neq B.$ By definition of $A\neq B,$ one must hold $$ \exists x, (x\in A\land x\notin B) \quad \text{ or }\quad \exists x, (x\in B \land x\notin A). $$ If the first one holds, then we have $x\in B$ and $x\notin B,$ a contradiction. Hence the former holds as needed. Conversely, assume $A\subseteq B$ and ${\exists x, (x\in B \land x\notin A).}$ Then by definition of $A\neq B,$ since $B$ contains an element not in $A,$ we have $A\neq B.$ Therefore we have $A\subseteq B$ and $A\neq B,$ and thus $A\subset B.$

In the foundations of mathematics, Russell’s paradox, discovered by Bertrand Russell in 1901, showed that the naive set theory created by Georg Cantor leads to a contradiction. According to naive set theory, any definable collection is a set. Let $R$ be the set of all sets that are not members of themselves. If $R$ is not a member of itself, then its definition dictates that it must contain itself, and if it contains itself, then it contradicts its own definition as the set of all sets that are not members of themselves. This contradiction is Russell’s paradox. Symbolically: $$ \text{If $R = \{ x \mid x \notin x \},$ then $R \in R \leftrightarrow R \not \in R$.}$$ In 1908, two ways of avoiding the paradox were proposed, Russell’s type theory and the Zermelo set theory. There is a long interesting history of this problem and the reader is encourage to explore.

## Set Operations

The next question that comes to mind is: is the collection of subsets of a set, a set itself? In other words, given a set $A$ does there exist a set $\mathcal{P}$ such that if $X\subseteq A$ then $X\in \mathcal{P}\,$?

** Definition**. The set consisting of all subsets of a given set $A$ is called the power set of $A$ and is denoted by $\mathcal{P}(A).$

** Theorem**. If $A$ is a set, then $\emptyset \in \mathcal{P}(A)$ and $A\in \mathcal{P}(A).$

** Proof**. Notice that the empty set is a subset of every set (including itself). Thus, $\emptyset \in \mathcal{P}(A)$ is immediate. The second statement follows immediately; that is, $A\subseteq A$ implies $A\in \mathcal{P}(A).$

** Theorem**. If $A$ has $n$ elements, then $\mathcal{P}(A)$ has $2^n$ elements.

** Proof**. If $n=0,$ then $A$ is the empty set. The only subset of the empty set is the set itself; thus the number of elements in $\mathcal{P}(A)$ is $1$ which is $2^0$ as needed to verify the basis step. Assume that the statement holds for $n.$ Let $X$ be a set with $n+1$ elements and assume $x\in X.$ We claim that exactly half of the subsets of $X$ contain $x,$ and half do not. To see this, notice that each subset of $X$ that contains $x$ can be paired uniquely with a subset obtained by removing $x$. $$ \begin{matrix} \text{ subsets of $A$ that contain $x$ } & \text{ subsets of $A$ that do not contain $x$ } \\ \hline \{x\} & \emptyset \\ \{x,y\} & \{y\} \\ \{x,z\} & \{z\} \\ \{x,y,z\} & \{y,z\} \end{matrix} $$ If we let $Y$ be the set obtained from $X$ by deleting $x,$ $Y$ has $n$ elements. By the inductive hypothesis $\mathcal{Y}$ has exactly $2^n$ elements. But the subsets of $Y$ are precisely the subsets of $X$ that do not contain $x.$ It follows that the number of elements in $\mathcal{Y}$ is one-half the number of elements in $\mathcal{X}.$ Therefore, the number of elements in $\mathcal{X}$ is twice the number of elements in $\mathcal{Y}.$ Whence the number of elements in $\mathcal{X}$ is $2^{n+1}.$

** Theorem**. If $A$ is an infinite set, then $\mathcal{P}(A)$ is also.

** Proof**. The proof is left for the reader.

** Principle**. (

**) For every collection of sets there exists a set that contains all the elements that belong to at least one set of the given collection.**

*Unions*Given a collection of sets $\mathcal{C}$ we want their union to consist of only those elements that belong to at least one of the subsets in the collection. So we apply the principle of specification to the set $U$ and define the ** union** of a collection of sets as $$ \bigcup_{X\in \mathcal{C}}X=\{x\in U \mid x\in X \text{ for some $X$ in $\mathcal{C}$\}}.$$ This set exists by the principle of specification and is unique by the principle of extension. In the case $\mathcal{C}=\{A, B\}$ we usually write $$A\cup B=\{x \mid x\in A \text{ or } x\in B\}.$$

** Theorem**. Let $A,$ $B,$ and $C$ be sets. Then

$\qquad (1) $ $A\cup \emptyset =A ,$

$\qquad (2) $ $A\cup B=B\cup A,$

$\qquad (3) $ $A\cup (B \cup C) =(A\cup B)\cup C,$

$\qquad (4) $ $A \cup A =A,$ and

$\qquad (5) $ $A\subseteq B$ if and only if $A\cup B=B.$

** Proof**. The proof is left for the reader.

If $A$ and $B$ are sets we then define, using the principle of specification, their intersection as the set $A \cap B=\{x\in A \mid x\in B\}.$ It is very easy to show the more familiar form, $A\cap B=\{x \mid x\in A \text{ or } x\in B\}.$ More generally, let $\mathcal{C}$ be a non-empty collection of sets, the principle of specification allows us to define a set $$ I=\{x \in A \mid x\in X \text{ for every $X$ in $\mathcal{C}$}\}$$ where $A$ is some set in $\mathcal{C}.$ In fact the use of a set $A$ is arbitrary (but necessary in order to use the principle of specification). Thus we are lead to the definition of the ** intersection** of a collection of sets $$ \bigcap_{X\in \mathcal{C}} X=\{x\mid x\in X \text{ for all $X$ in $\mathcal{C}$ }\} $$ where uniqueness is guaranteed by the principle of extension.

** Theorem**. Let $A$, $B$, and $C$ be sets. Then

$\qquad (1) $ $A\cap \emptyset =\emptyset ,$

$\qquad (2) $ $A\cap B=B\cap A,$

$\qquad (3) $ $A\cap (B \cap C) =(A\cap B)\cap C,$

$\qquad (4) $ $A \cap A =A,$ and

$\qquad (5) $ $A\subseteq B$ if and only if $A\cap B=A.$

** Proof**. The proof is left for the reader.

Let $A$ and $B$ be subsets of a set $C.$ The ** difference** between $A$ and $B,$ known as the

**of $B$ in $A,$ is the set defined by $A-B=\{x\in A \mid x\not\in B \}$; and the**

*relative complement***of $A$ and $B$ is defined by $A+B=(A-B)\cup (B-A).$ Notice that the principle of specification guarantees existence and the principle of extension guarantees uniqueness of these sets for a given $A$ and $B.$ These sets are of course, by definition, also subsets of $C.$ The next question that comes to mind is: is the collection of subsets of $C$ a set itself? In other words, given a set $C$ does there exist a set $\mathcal{P}$ such that if $X\subseteq S$ then $X\in \mathcal{P}\,$?**

*symmetric difference*** Principle**. (

**) For each set there exists a collection of sets that contains among its elements all the subsets of the given set.**

*Principle of Powers*Thus, given a set $C$ we can form a collection of sets, denoted by $\mathcal{P},$ that contains the subsets of $C.$ We can use the principle of specification to ensure that this set will consist only of subsets of $C$ and the principle of extension to ensure that this set is unique. We call this set the ** power set** of $C,$ and denote it by $\mathcal{P}(S)=\{X \mid X\subseteq S\}$ or sometimes even $2^S.$ The fundamental most frequently used operations of set theory are union, intersection, and difference. In this section we discuss these operations and some of their properties. The

**of a collection of sets is the set of all distinct elements in the collection.**

*union*** Definition**. Let $A$ and $B$ be subsets of some universal set $U.$ The

**of $A$ and $B$ is the set $A\cup B$ defined by $$ A\cup B =\{x\mid x\in A \lor x\in B\}.$$**

*union*Recall that $p\rightarrow (p\lor q)$ is a tautology. This immediately yields that for any sets $A$ and $B,$ \begin{equation}\label{subsetcup}A\subseteq A\cup B \qquad \text{ and } \qquad B\subseteq A\cup B. \end{equation}

This follows because $A\subseteq A\cup B$ is equivalent to $\forall x, x\in A\rightarrow (x\in A \lor x\in B)$ by definition of subset. Similarly for $B\subseteq A\cup B.$

** Example**. Let $U=\{1,2,3,\ldots, 10\},$ $A=\{2,4,6\},$ $B=\{1,3,5,7,9\}$ and $C=\{5,10\}.$ Find and compare the sets: $A\cup (B \cup C)$ and $(A\cup B)\cup C.$

** Solution**. We find $B\cup C=\{1,3,5,7,9,10\}$ and so $$A\cup(B\cup C)=\{1,2,3,4,5,6,7,9,10\}.$$ Also, $A\cup B=\{1,2,3,4,5,6,7,9\}$ and so $$ (A\cup B)\cup C)=\{1,2,3,4,5,6,7,9,10\}. $$ Therefore we find that $A\cup (B \cup C)=(A\cup B)\cup C$.

** Theorem**. Let $A$ and $B$ be subsets of some universal set $U.$

$\qquad (1) $ $A\cup \emptyset = A $

$\qquad (2) $ (

**) $A\cup B=B\cup A$**

*commutativity*$\qquad (3) $ (

**) $A\cup (B \cup C) =(A\cup B)\cup C$**

*associativity*$\qquad (4) $ (

**) $A \cup A =A$**

*idempotence*$\qquad (5) $ $A\subseteq B$ if and only if $A\cup B=B$.

** Proof**. We prove (1) and (5) and leave the remainder of the proof for the reader. (1): Let $x$ be an arbitrary element of $A\cup \emptyset.$ Then, by definition of union, either $x\in A$ or $x\in \emptyset.$ Since there are no elements in $\emptyset,$ we must have $x\in A$; hence $A\cup \emptyset\subseteq A.$ Conversely, follows from \eqref{subsetcup}. (5): Assume $A\subseteq B.$ We must show that $A\cup B=B.$ By \eqref{subsetcup} we immediately see that $B\subseteq A\cup B.$ To show the remaining inclusion, let $x\in A\cup B.$ Then either $x\in A$ or $x\in B.$ In the case that $x\in A,$ then we have $x\in B$ by hypothesis. Thus, in either case we have $x\in B,$ and so $A\cap B\subseteq B.$ Therefore, we have shown that if $A\subseteq B,$ then $A\cap B=B.$ Conversely, we now assume that $A\cup B=B$ and we wish to conclude that $A\subseteq B.$ To do so, let $x$ be an arbitrary element of $A.$ Then $x\in A\cup B$ by \eqref{subsetcup}, and so $x\in A\cup B=B.$ Hence $A\subseteq B$ as needed.

The intersection of a collection of sets is the set that contains all elements, each of which are in each of the sets in the collection, and no other elements.

** Definition**. Let $A$ and $B$ be subsets of some universal set $U.$ The intersection of $A$ and $B$ is the set $A\cap B$ defined by $$ A\cap B =\{x\mid x\in A \land x\in B\}. $$

** Theorem**. Let $A$ and $B$ be subsets of some universal set $U.$

$\qquad (1) $ $A\cap \emptyset =\emptyset $

$\qquad (2) $ (

**) $A\cap B=B\cap A$**

*commutativity*$\qquad (3) $ (

**) $A\cap (B \cap C) =(A\cap B)\cap C$**

*associativity*$\qquad (4) $ (

**) $A \cap A =A$**

*idempotence*$\qquad (5) $ $A\subseteq B$ if and only if $A\cap B=A$.

** Proof**. We prove (2) and (3) and leave the remainder of the proof for the reader. (2): Let $x$ be an arbitrary element in $A\cap B.$ Then \begin{alignat*}{2} & x\in A \cap B & \qquad & \\ & \quad \rightarrow x\in A\land x\in B & & \text{by Definition of $\cap$} \\ & \quad \rightarrow x\in B\land x\in A & & \text{by commutativity of $\land$} \\ & \quad \rightarrow x\in B \cap A & & \text{by Definition of $\cap$} \end{alignat*} Thus $x\in A\cap B\rightarrow x\in B\cap A$ and consequently $$ A\cap B\subseteq B\cap A.$$ In a similar fashion (simply reverse the implications) one may prove that $B\cap A\subseteq A\cap B.$ Therefore, $A\cap B=B\cap A$. (3): Let $x$ be an arbitrary element in $(A \cap B)\cap C.$ Then \begin{alignat*}{2} & x\in (A \cap B)\cap C & \qquad & \\ & \quad \rightarrow [ x\in (A \cap B) \land x\in C ] & & \text{by Definition of $\cap$} \\ & \quad \rightarrow [ (x\in A \land x\in B)\land x\in C ]& & \text{by Definition of $\cap$} \\ & \quad \rightarrow [ x\in A \land ( x\in B \land x\in C) ] & & \text{by associativity of $\land$} \\ & \quad \rightarrow [ x\in A \land ( x\in B \cap C) ]& & \text{by Definition of $\cap$} \\ & \quad \rightarrow [ x\in (A \cap B) \cap C ] & & \text{by Definition of $\cap$} \end{alignat*} Thus $x\in (A\cap B)\cap C \rightarrow x\in A\cap (B\cap C)$ and consequently $$(A\cap B)\cap C\subseteq A\cap (B\cap C).$$ In a similar fashion (simply reverse the implications) one may prove that $A\cap (B\cap C)\subseteq (A\cap B)\cap C.$ Therefore, $A\cap (B\cap C)=(A\cap B)\cap C.$

** Theorem**. Let $A$, $B$, $C$ be subsets of some universal set $U.$

$\qquad (1) $ $A\cap (B \cup C) = (A\cap B)\cup (A\cap C)$

$\qquad (2) $ $A\cup (B \cap C) = (A\cup B)\cap (A\cup C)$

** Proof**. We prove (1) and leave the remainder of the proof for the reader. (1): Let $x$ be an arbitrary element in $A\cap (B \cup C).$ Then \begin{alignat*}{2} & x\in A\cap (B \cup C) & \qquad & \\ & \quad \rightarrow [ x\in A \land x\in B\cup C ] & & \text{by Definition of $\cap$} \\ & \quad \rightarrow [ x\in A \land (x\in B \lor x\in C) ]& & \text{by Definition of $\cup$} \\ & \quad \rightarrow [ (x\in A \land x\in B) \lor (x\in A \land x\in C) ] & & \text{by distributivity of $\land$} \\ & \quad \rightarrow [ (x\in A \cap B) \lor (x\in A \cap C) ] & & \text{by Definition of $\cap$} \\ & \quad \rightarrow [ (x\in A \cap B) \cup (A \cap C) ] & & \text{by Definition of $\cup$} \end{alignat*} Thus $x\in A\cap (B \cup C) \rightarrow x\in (A\cap B)\cup (A\cap C)$ and consequently $$ A\cap (B \cup C) \subseteq (A\cap B)\cup (A\cap C). $$ In a similar fashion (simply reverse the implications) one may prove that $(A\cap B)\cup (A\cap C) \subseteq A\cap (B \cup C).$ Therefore, $A\cap (B \cup C)=(A\cap B)\cup (A\cap C).$

The relative complement of $B$ with respect to a set $A$ is the set of elements in $A$ but not in $B.$

** Definition**. Let $A$ and $B$ be subsets of some universal set $U.$ The

**of $B$ in $A$ is the set $A-B$ defined by $$A-B =\{x\mid x\in A \land x\notin B\}.$$ The relative complement of $B$ in $A$ is also denoted by $A\setminus B.$**

*relative complement*When all sets under consideration are considered to be subsets of a given set $U,$ the absolute ** complement** of $A$ is the set of all elements in $U$ but not in $A,$ and is denoted by $A’,$ that is, the complement of a set $A$ is defined by $$A’=\{x\in U \mid x\not\in A\}. $$ To be redundant, by definition $A’=U-A.$

** Example**. Let $S=\{a,b,c\},$ $T=\{1,a\},$ and $V=\{1,2,3,c\}.$ Find and compare the sets, $(S-T)-V$ and $S-(T-V).$

** Solution**. We find $S-T=\{b,c\}$ and $T-V=\{a\},$ and so $(S-T)-V=\{b\}$ and $S-(T-V)=\{b,c\}.$ Thus, $(S-T)-V\subseteq S-(T-V).$

** Theorem**. Let $A$ and $B$ be subsets of some universal set $U.$

$\qquad (1) $ $(A \cup B)’=A’ \cap B’$

$\qquad (2) $ $(A \cap B)’=A’ \cup B’$.

** Proof**. We prove (1) and leave the remainder of the proof for the reader. Let $x$ be an arbitrary element in $(A \cup B)’.$ Then \begin{alignat*}{2} & x\in (A \cup B)’ & \qquad & \\ & \quad \rightarrow [x\notin A \cup B] & & \text{by Definition of complement} \\ & \quad \rightarrow [\neg(x\in A \cup B)] & & \text{by Definition of $\notin$} \\ & \quad \rightarrow [\neg(x\in A \lor x\in B)] & & \text{by Definition of $\cup$} \\ & \quad \rightarrow [\neg(x\in A) \land \neg(x\in B)] & & \text{DeMorgan’s Law} \\ & \quad \rightarrow [x\notin A \land x\notin B] & & \text{by Definition of $\notin$} \\ & \quad \rightarrow [x\in A’ \land x\in B’] & & \text{by Definition of complement} \\ & \quad \rightarrow [x\in A’ \cap B’] & & \text{by Definition of $\cap$} \end{alignat*} Thus $x\in (A \cup B)’ \rightarrow x\in A’ \cap B’$ and consequently $(A \cup B)’ \subseteq x\in A’ \cap B’.$ In a similar fashion (simply reverse the implications) one may prove that $A’ \cap B’ \subseteq (A \cup B)’.$ Therefore, $(A \cup B)’=A’ \cap B’$.

** Theorem**. Let $A$ and $B$ be subsets of some universal set $U.$

$\qquad (1) $ $(A’)’=A$

$\qquad (2) $ $\emptyset ‘=U$

$\qquad (3) $ $U’=\emptyset $

$\qquad (4) $ $A \cap A’=\emptyset$

$\qquad (5) $ $A \cup A’ =U$

$\qquad (6) $ $A-B=A\cap B’$

** Proof**. The proof is left for the reader.

** Theorem**. Let $A$ and $B$ be subsets of some universal set $U.$

$\qquad (1) $ $A \subseteq B$ if and only if $B’\subseteq A’$

$\qquad (2) $ $A\subseteq B$ if and only if $A-B=\emptyset$

** Proof**. We prove (1) and leave the remainder of the proof for the reader.Assume $A\subseteq B$ and let $x$ be an arbitrary element in $B’.$ Thus, $x\notin B.$ Assume for a contradiction that $x\in A.$ By hypothesis, we have $x\in B$ and $x\notin B.$ Thus, $x\in A’$ must occur. Conversely, assume $B’\subseteq A’$ and let $x$ be an arbitrary element of $A.$ Assume for a contradiction that $x\in B’.$ By hypothesis, we have $x\in A$ and $x\notin A.$ Thus, $x\in B$ must occur.

The symmetric difference of two sets is the set of elements which are in either of the sets and not in their intersection.

** Definition**. If $A$ and $B$ are sets, we define the symmetric difference of $A$ and $B$ by $$ A\bigtriangleup B=(A-B)\cup (B-A). $$

** Theorem**. Let $A$ and $B$ be subsets of some universal set $U.$ Then \begin{equation} \label{symmdiff} A\bigtriangleup B=(A\cup B)-(A\cap B). \end{equation}

** Proof**. Let $x$ be an arbitrary element of $A\bigtriangleup B.$ Then \begin{align*} & x\in A\bigtriangleup B & \\ & \qquad \rightarrow x\in (A-B) \cup (B-A) & \\ & \qquad \rightarrow x\in A-B \lor x\in B-A & \\ & \qquad \rightarrow (x\in A \land x\notin B) \lor (x\in B\land x\notin A) & \\ & \qquad \rightarrow (x\in B\land x\notin A) \lor (x\in A \land x\notin B) & \\ & \qquad \rightarrow [(x\in A\land x\notin A) \lor (x\in B\land x\notin A)] \\ & \qquad \qquad \qquad \lor [(x\in A \land x\notin B)\lor (x\in B \land x\notin B)] \\ & \qquad \rightarrow [(x\in A \lor x\in B)\land x\notin A)] \lor [(x\in A \lor x\in B) \land x\notin B)] & \\ & \qquad \rightarrow (x\in A \lor x\in B) \land (x \notin A \lor x\notin B) & \\ & \qquad \rightarrow (x\in A \lor x\in B) \land \neg (x\in A \land x\in B) & \\ & \qquad \rightarrow x\in (A\cup B) \land \neg (x\in A \cap B) & \\ & \qquad \rightarrow x\in (A\cup B) \land x\notin A\cap B & \\ & \qquad \rightarrow x\in (A\cup B) -(A\cap B) & \end{align*} The justification of the above steps and the remainder of the proof is left for the reader.

** Theorem**. Let $A$, $B$, and $C$ be subsets of some universal set $U.$

$\qquad (1) $ $A\bigtriangleup B=B\bigtriangleup A$

$\qquad (2) $ $A\bigtriangleup (B\bigtriangleup C)=(A\bigtriangleup B)\bigtriangleup C$

$\qquad (3) $ $A\bigtriangleup \emptyset = A$

$\qquad (4) $ $A\bigtriangleup A=\emptyset $

** Proof**. The proof is left for the reader.

** Theorem**. Let $A$ and $B$ be sets. Then

$\qquad (1) $ $A+B=B+A,$

$\qquad (2) $ $A+(B+C)=(A+B)+C,$

$\qquad (3) $ $A+\emptyset = A,$ and

$\qquad (4) $ $A+A=\emptyset .$

** Proof**. The proof is left for the reader.

A collection of sets is called ** disjoint** if they have no elements in common.

** Definition**. If $A$ and $B$ are sets and $A\cap B=\emptyset,$ then $A$ and $B$ are disjoint sets.

** Theorem**. Let $A$ and $B$ be subsets of some universal set $U.$ Then $A$ and $B$ are disjoint if and only if $A\cup B=A\bigtriangleup B.$

** Proof**. The proof is left for the reader.

## Cartesian Products

** Principle**. (

**) For any two sets there exists a set that they both belong to.**

*Principle of Pairing*For example, suppose $a$ and $b$ are sets that are elements of the set $A,$ then by the principle of specification the set $\{a, b\}:=\{x\in A \mid x=a \text{ or } x=b \}$ exists, and by the principle of extension is unique. This set is called the ** pair** (or

**) formed by $a$ and $b.$ Given any set $a$ we have the pair $\{a,a\}$ which is usually just denoted by $\{a\},$ and is called the**

*unordered pair***of $a.$**

*singleton set*Let $\mathcal{C}$ denote a collection of sets. By the following principle we can define the set $U$ consisting of those elements $x$ such that if $x\in X$ for some $X\in \mathcal{C},$ then $x\in U.$ An ordered pair $(a, b)$ is a pair of mathematical objects. The order in which the objects appear in the pair is significant: the ordered pair $(a, b)$ is different from the ordered pair $(b, a)$ unless $a = b.$ (In contrast, the unordered pair $\{a, b\}$ equals the unordered pair $\{b, a\}.$)

** Definition**. Given any two sets $A$ and $B,$ the Cartesian product of $A$ and $B$ is the set $A\times B$ defined by $$ A\times B =\{(a,b)\mid a\in A \land b\in B)\}. $$

** Theorem**. If $A$, $B$, and $C$ are sets, then

$\qquad (1) $ $A\times (B\cup C)=(A\times B)\cup (A\times C)$

$\qquad (2) $ $A\times (B\cap C)=(A\times B)\cap (A\times C)$

$\qquad (3) $ $A\times (B- C)=(A\times B)- (A\times C)$

$\qquad (4) $ $A\times (B\bigtriangleup C)=(A\times B)\bigtriangleup (A\times C)$

** Proof**. The proof is left for the reader.

The idea of ordered pair can be extended to more than two elements. Given $n$ elements $a_1, a_2, \ldots, a_n,$ where $n\geq 3,$ we can define the ** ordered** $n$-tuple $(a_1, a_2, \ldots a_n),$ in which $a_1$ i the first element, $a_2$ is the second element, and so on, and $a_n$ is the $n$-th element. We can now generalize the idea of Cartesian product.

** Definition**. Given any $n$ sets $A_1, A_2, \ldots, A_n,$ the Cartesian product of $A_1, A_2, \ldots, A_n$ is the set defined by $$ A_1\times A_2 \times \cdots \times A_n =\{(a_1, a_2, \ldots, a_n) \mid a_i\in A_i \text{ for each $i,$ $1\leq i \leq n$}\}. $$

It follows immediately, $$ (a_1, a_2, \ldots, a_n)=(b_1, b_2, \ldots, b_n) \text{ if and only if $a_i=b_i$ for each $i,$ $1\leq i \leq n.$} $$ Also notice that $A_1\times A_2 \times \cdots \times A_n=\emptyset$ if and only if $A_i=\emptyset$ for some $i,$ $1\leq i \leq n.$ For this reason, when working with Cartesian products of sets, it is normally the case that each of the sets is nonempty.

** Example**. Prove or disprove that $$ \mathcal{P}(A\times B)=\mathcal{P}(A)\times \mathcal{P}(B), $$ for any sets $A$ and $B.$

The ** ordered pair** of $a$ and $b,$ with first coordinate $a$ and second coordinate $b$ is defined as the set $\{\{a\},\{a,b\}\}$ and is denoted more naturally by $(a,b).$ The reader should show that this definition is well-defined by proving the following lemma. If $(a,b)$ and $(x,y)$ are ordered pairs and if $(a,b)=(x,y)$ then $x=a$ and $y=b.$ The proof is left as an exercise for the reader. The next question that comes to mind is: if $A$ and $B$ are sets, does there exist a set that contains all the ordered pairs $(a,b)$ with $a\in A$ and $b\in B.$ Surely so; for example, $\{a\}\subseteq A$ and $\{b\}\subseteq B,$ and therefore $\{a,b\}\subseteq A\cup B.$ Thus, by definition, $(a,b)=\{\{a\},\{a,b\}\}\subseteq \mathcal{P}(A\cup B).$ It follows that ${(a,b)\in \mathcal{P}(\mathcal{P}(A\cup B)).}$ We can do much better than this though.

The Cartesian product of two sets is a set of ordered pairs. Conversely, every set of ordered pairs is a subset of the Cartesian product of two sets. By the above argument, every set of ordered pairs is contained in some subset, via $$ (a,b)\in \mathcal{P}(\mathcal{P}(A\cup B)) \quad \text{whenever } \quad a\in A, b\in B. $$ By the principle of specification, we define a set $$ A\times B = \{x \in \mathcal{P}(\mathcal{P}(A\cup B)) \mid x=(a,b) \text{ for some $a\in A$ and $b\in B$}\}. $$ By the principle of extension, this set is unique; and is called the ** Cartesian product** of $A$ and $B.$ Thus, as desired, the Cartesian product of two sets is a set of ordered pairs. Conversely, let $P$ be a set that consists of ordered pairs and let $x\in P.$ Then by definition of ordered pair $x=\{\{a\},\{a,b\}\}$ for some $a$ and for some $b.$ Since $P$ is a set consisting of sets, we form the union and observe $\{a,b\}\in \cup_{X\in P} P.$ Observe further that ${\cup_{X\in P} P:=P’}$ is a set consisting of sets, so it follows both $a$ and $b$ are elements of $$ U:=\bigcup_{Y\in P’} \bigcup_{X\in P} P. $$ Let $A$ and $B$ be such that $A=B=U.$ Thus $P,$ a set of ordered pairs, is a subset of the Cartesian product of two sets, namely $U\times U.$ We can use the principle of specification to refine the sets $A$ and $B,$ namely $$ A=\{ a \in U \mid (a,b) \in P \text{ for some } b \} $$ and $$ B=\{ b \in U \mid (a,b) \in P \text{ for some } a \}. $$ These sets are unique by the principle of extension and are called the

**of $P$ onto the first and second coordinates, respectively.**

*projections*