Set Theory

Abigail Huettig

13 Set Theory

Set theory is the study of sets (or collections) of numbers. Some common examples of sets in set theory would be the natural numbers, whole numbers, integers, rationals, irrationals, and reals. These are denoted as $\mathbb{N},\mathbb{W},\mathbb{Z},\mathbb{Q}, \mathbb{I},$ and $\mathbb{R}$ respectively. There is an infinite number of possibilities for sets as they are just a collection of numbers and can include anywhere from zero to an infinite number of elements.

Terminology
Before we can go any further, we must have a good understanding of some basic terminology. If $x$ is in a set $A$ , denoted $x \in A$ , then we call $x$ an element of $A$ . The set that has zero elements is called the empty or null set and is denoted as $\emptyset$ [23]. A set $A$ is a subset of a set $B$ , denoted $A\subseteq B$ , if every element that is in $A$ is also in $B$ . $A$ is a proper subset of $B$ , denoted $A\subset B$ , if every element in $A$ is also in $B$ and there is at least one element in $B$ that is not in $A$ . In other words, $A$ is a subset of but is not equal to $B$ . $A$ and $B$ are disjoint sets when they do not have any common elements. That is, for every $x \in A$ , $x \notin B$ and for every $y \in B$ , $y \notin A$ .

Operations
There are also operations that we can perform on sets. The union of sets $A$ and $B$ , denoted as $A\cup B$ , is the set of all elements in $A$ and all elements in $B$ . That is, if $x \in A\cup B$ , then $x$ must be in either $A$ or $B$ . The intersection of sets $A$ and $B$ , denoted as $A \cap B$ , is the set of all elements that $A$ and $B$ have in common. The difference of sets $A$ and $B$ , denoted $A-B$ , is the set of all elements in $A$ that are not in $B$ . That is, if $x \in (A-B)$ , then $x \in A$ and $x \notin B$ [23]. The complement of a set $A$ , denoted $A^c$ , is the set of all elements that are not in $A$ . That is, if $x \in A^c$ , then $x \notin A$ .

Now that we have covered the basic terminology and operations of sets, we are ready to discuss DeMorgan’s Laws and apply some of the concepts that we have just learned.

DeMorgan’s Laws for Sets

Recall that in chapter 10, we mentioned DeMorgan’s Laws as they applied to logic. Now, we are going to discuss DeMorgan’s Laws as they apply to set theory. Abbott provides us with the following theorem [1].

Theorem III.1 (DeMorgan’s Laws for Sets)

Let $A$ and $B$ be subsets of $\mathbb{R}$ .

$(A \cap B)^c=A^c \cup B^c$
$(A \cup B)^c=A^c \cap B^c$

In order to prove the first statement, we need to show that the two sets, $(A \cup B)^c$ and $A^c \cap B^c$ , are equal. But how do we do that? In short, we prove that they are subsets of one another. If $A\subseteq B$ , then every element in $A$ must also be in $B$ . But if $B \subseteq A$ , then every element in $B$ must also be in $A$ . Since every element in $A$ is also in $B$ , we know that $B$ contains all of the elements of $A$ . We also know that there does not exist an element in $B$ that is not in $A$ . It follows then that $B$ has the exact same elements as $A$ . Thus, $A=B$ . To prove that a set $A$ is a subset of $B$ , we show that if $x$ is in $A$ then $x$ must also be in $B$ .

We are now ready to prove the first of DeMorgan’s Laws. This is a homework problem I completed for Introduction to Analysis that comes from Abbott [1].

Example 28
Show that $(A \cap B)^c=A^c \cup B^c$ .

Proof.
If $x\in A\cap B$ , $x\in A$ and $x\in B$ by definition of intersection.
So, if $x\in (A\cap B)^c$ , $x\notin A$ or $x\notin B$ by definition of intersection and complement.
That is, $x\in A^c$ or $x\in B^c$ by definition of complement.
Thus, $x\in A^c \cup B^c$ by definition of union.
Therefore, $(A\cap B)^c \subseteq A^c \cup B^c$ .

If $x\in A^c \cup B^c, x \in A^c$ or $x \in B^c$ by definition of union.
That is, $x \notin A$ or $x \notin B$ so $x \notin A \cap B$ by definition of complement and intersection.
Thus, $x \in (A \cap B)^c$ by definition of complement.
Therefore, $A^c \cup B^c\subseteq (A \cap B)^c$ .

Therefore, $(A\cap B)^c = A^c \cup B^c$ .

The proof of the second of DeMorgan’s Laws can be done in a similar manner. Having discussed the basics of set theory, we are going to dive into a more advanced topic, relations. We will see how different sets are connected and how they relate to one other.

13 Set Theory

DeMorgan’s Laws for Sets

License

Share This Book