Set Theory

Maggie Schildt

13 Set Theory

Bridge to Abstract Math, for some, is a very challenging course in mathematics. In previous classes such as calculus, differential equations, and statistics, although we learned abstract theorems, we applied them to problems or real world situations where variables were given finite values. With abstract math we have to prove problems abstractly which means very few finite values, if any, in order to prove the problem for every possible value of a variable. In this course much of what we learn to create proofs for are theorems.

Now a theorem cannot prove itself and in this class you are taught to utilize related theorems, axioms, definitions, and proof techniques in order to prove a theorem to be true. Not only did this mean that students needed to learn how to recognize the relationship between numerous definitions, rules, and logical propositions efficiently but the class also teaches students to be concise in developing proofs.

With every proof we needed to provide the key points that would lead to a sound conclusion. This requires students to learn how to clean up proofs as well as how to present information neatly in a proof process, structured by logic and proof techniques, that flows smoothly to a strong conclusion, founded by established axioms and definitions.

In the following subsections we introduce some of the topics discussed in the course Bridge to Abstract Mathematics. This includes set theory, relations, functions, and cardinality. We begin with set theory.

Set theory, as it suggest, discusses the many theorems for sets. We touched briefly on sets early on in this chapter but for a quick review a set is by definition “a well-determined collection of objects that are called elements of the set” [7]. When we study pure set theory we are only discussing theorems for sets whose elements are also sets which means the sets are infinite. Let us consider the operations involved with sets.

Union and Intersection

We have already introduced the union and intersection of sets in the section on DeMorgan’s laws but we will cover them again. The union of two sets, denoted by “ $\cup$ “, is when we combine two sets into one set that contains all the elements of both sets. The intersection of two sets is denoted by “ $\cap$ “, which creates a set that only contains like elements. We explained this earlier but for the union, given sets $A$ and $B$ , if $x\in A$ or $x\in B$ then $x\in A\cup B$ and for the intersection this means if $x\in A\cap B$ then it must be that $x\in A$ and $x\in B$ .

Now union and intersection do not always involve only two sets. We can denote the union of more than two sets as the following [7].

$\begin{equation*} \bigcup_{i=1}^{n}{A_{i}}=A_{1}\cup A_{2}\cup A_{3}...\cup A_{n}. \end{equation*}$

We can see here in the notation that the sets are denoted $A_{i}$ for with the first set being $A_{1}$ . Using this same notation for the sets we see the formal notation for intersection of more than two sets as the following [7].

$\begin{equation*} \bigcap_{i=1}^{n}{A_{1}}=A_{1}\cap A_{2}\cap A_{3}...\cap A_{n}. \end{equation*}$

Let’s now consider some basic examples for the union and intersection of sets.

Example:

Let set $A=\left\lbrace 1,3,4,6 \right\rbrace$ and let set $B=\left\lbrace 1,6,7,8,9 \right\rbrace$ then then union of sets $A$ and $B$ is

$\begin{equation*} A\cup B= \left\lbrace 1,3,4,6 \right\rbrace \cup \left\lbrace 1,6,7,8,9 \right\rbrace = \left\lbrace 1,3,4,6,7,8,9 \right\rbrace \end{equation*}$

Here we see that the union of sets $A$ and $B$ results in a set with all values of both set $A$ and $B$ .

The intersection of $A$ and $B$ would be as follows

$\begin{equation*} A\cap B=\left\lbrace 1,3,4,6 \right\rbrace \cap \left\lbrace 1,6,7,8,9 \right\rbrace =\left\lbrace 1,6 \right\rbrace \end{equation*}$

Results in a set which only contains the elements that are shared between $A$ and $B$ .

We can see a key aspect of union in the example above, when we combined the two sets we only accounted for like elements once. This also holds for a union of more than two sets as well. In the intersection we saw that the only elements for the intersection of sets $A$ and $B$ were elements {1} and {6}, this is because these are the only elements that are contained in both sets independently. We can see an image below illustrating the intersection of two sets below.

Now consider some slightly more complex operations of sets.

Complement of Sets

Consider that we have a universal set $S$ , let $A$ be a set within $S$ . Now set $A$ does not contain all elements of the universal set, just a cluster of elements. All other elements are contained in what we call the compliment to set $A$ , denoted as $A^{c}$ . It follows then that if $x\in S$ but $x\neq A$ then it must be that $x\in A^{c}$ , as well if $x\in S$ and $x\neq A^{c}$ then it must be that $x\in A$ .

Difference of Sets

We discussed the intersection of sets already but the difference of sets is very close to the opposite of intersection. Similar but not the same though, as intersection only included the shared elements between overlapping sets, a difference is what does not over lap, in a way. Consider sets $A$ and $B$ again, the difference of sets is the resulting set from $A-B$ or $B-A$ . This essentially means if $A-B$ then the resulting set contains all elements other than elements only in $B$ and shared between $A$ and $B$ . Consider the example below.

Example:

Let $A=\left\lbrace 1,3,4,6 \right\rbrace$ and let $B=\left\lbrace 1,6,7,8,9 \right\rbrace$ the difference of $A-B$ is the following

$\begin{equation*} A-B=\left\lbrace 1,3,4,6 \right\rbrace-\left\lbrace 1,6,7,8,9 \right\rbrace=\left\lbrace 3,4 \right\rbrace \end{equation*}$

Vice versa then difference of $B-A$ is the following

$\begin{equation*} B-A=\left\lbrace 1,6,7,8,9 \right\rbrace-\left\lbrace 1,3,4,6 \right\rbrace=\left\lbrace 7,8,9 \right\rbrace \end{equation*}$

We see in the above example that we only focus on the elements contained in the set being subtracted from. What this means is that any elements in the set on the right hand side of the subtraction symbol are not included in the resulting set, they are excluded as well as any elements shared between the sets. Now lets look at sets that carry no association at all.

Disjoint Sets

Recall complimentary sets and the universal set $S$ . Now imagine that just as $A$ only contains a few elements of $S$ , there is another set $B$ that contains a few other elements of $S$ such that for every $x\in A$ , $x\neq B$ and vice versa. Furthermore we can have yet another set $C$ that contains a few other elements not shared with either $A$ or $B$ . These are all examples of disjoint sets. They contain no mutual elements which makes them mutually exclusive to one another. With this being said the intersection set between any or all disjoint sets in $S$ is an empty set. Consider the below example.

Example:

Let $S=\left\lbrace 1,2,3,4,5,6,7,8,9,10 \right\rbrace$ , let disjoint sets $A=\left\lbrace 1,2,3 \right\rbrace$ and $B=\left\lbrace 8,9,10 \right\rbrace$ by definition of disjoint sets there is no element in $A$ that is also contained in $B$ and as such the intersection of $A$ and $B$ is as follows.

$\begin{equation*} A\cap B=\left\lbrace 1,2,3 \right\rbrace \cap \left\lbrace 8,9,10 \right\rbrace =\left\lbrace \emptyset \right\rbrace \end{equation*}$

We continue to expand on the idea of disjoint sets in the next classification.

Partition of Sets

We have a collection of nonempty sets under the universal set $S$ again, where each set is disjoint and contains some elements of $S$ such that there is no elements $x\in S$ that is not contained in some disjoint set $A_{i}$ . We can say that each $A_{i}$ is a partition of $S$ if $\cup_{i=1}^{n}{A_{i}}=A$ . Consider an example using the universal set $S$ from disjoint sets.

Example:

Let $S=\left\lbrace 1,2,3,4,5,6,7,8,9,10 \right\rbrace$ and contain the following 5 partitions: $S_{1}=\left\lbrace 1,2,3 \right\rbrace$ , $S_{2}=\left\lbrace 8,9,10 \right\rbrace$ , $S_{3}=\left\lbrace 4 \right\rbrace$ , $S_{4}=\left\lbrace 5,6 \right\rbrace$ , $S_{5}=\left\lbrace 7 \right\rbrace$ . Then by the definition of partitions the union of all partitions is as follows.

$\begin{equation*} \bigcup_{i=1}^{5}{S_{i}}=S_{1}\cup S_{2}\cup S_{3}\cup S_{4}\cup S_{5}=\left\lbrace 1,2,3,4,5,6,7,8,9,10 \right\rbrace=S \end{equation*}$

Now that we know how to operate with sets lets consider some of the basic set classification and how it can be used to compare sets.

Subsets

In these last few operations we kept utilizing these sets with universal set $S$ . We can also call these sets subsets. By definition a set which contains every element of another set is therefore a subset of the other set. If $A$ is a subset of $S$ then we can denote this relationship by $A\subseteq S$ or $A\subset S$ .

$A\subset S$ denotes when every element in $A$ is in $S$ while $A\subset S$ denotes when every element in $A$ is in $S$ but there are far more elements not in $A$ that are in $S$ ; we call this a proper subset. Let us look at an example utilizing a few set operations.

Example:

For any sets $A$ and $B$ prove that $B-A\subseteq B$ .

Proof: Let there be element $x$ such that $x\in (B-A)$ then by the definition for the difference of sets $x\neq A$ and $x\in B$ . Thus by the definition of subsets $B-A\subseteq B$ .

This was quite a simple example and easily proven by definitions. Before we move on to set equality consider one more example of subset relations.

Example:

For all sets $A$ , $B$ , and $C$ if $A\subseteq B$ and $B\subseteq C$ then $A\subseteq C$ [20].

Proof: Assume $A$ , $B$ , and $C$ are sets such that $A\subseteq B$ and $B\subseteq C$ . Let $x$ be an arbitrary element where $x\in A$ . Given that $A\subseteq B$ then every element in $A$ is an element in $B$ , thus we can conclude that $x\in B$ . As such, since $B\subseteq C$ then every element in $B$ is an element in $C$ , thus $x\in C$ . Now, since we have proven that every element in $A$ is an element in $C$ , we can conclude that $A\subseteq C$ .

We have seen how sets can be related by introducing the definition of a subset. We will now prove how two different sets can be equal to one another using our definition for subsets.

Example:

Let set $A=\left\lbrace n:n=6k-3\ for\ some\ k\in \mathbb{Z}\right\rbrace$ and set $B=\left\lbrace n:n=2k-5\ for\ some\ k\in \mathbb{Z}\right\rbrace$ . Prove $A=B$ .

Proof: Consider $x\in A$ , then by the definition of $A$ , $x=6a-3$ for some $a\in \mathbb{Z}$ . If $b=3a+1$ then, for set $B$ , $2b-5=2(3a+1)-5=6a+2-5=6a-3=x$ and thus we can say that $x=2b-5$ for some $b\in \mathbb{Z}$ . Thus we can conclude that $x\in B$ and therefore $A\subseteq B$ . Now consider that $B\subseteq A$ , then by definition of $B$ , $x=2b-5$ for some $b\in \mathbb{Z}$ . If $a=\frac{1}{3}b-\frac{1}{3}$ then, for set $A$ , $6a-3=6(\frac{1}{3}b-\frac{1}{3})-3=2b-2-3=2b-5=x$ and thus we can say that $x=6a-3$ for some $b\in \mathbb{Z}$ . Thus we can conclude that $x\in A$ and therefore $B\subseteq A$ .

Since we have proven that $A\subseteq B$ and $B\subseteq A$ we can conclude that $A=B$ .

Now that we have established subsets and set equality we can continue on to some fundamental theorems for sets.

DeMorgan’s Laws

We already discussed DeMorgan’s laws earlier on but we will brush up on them here. There are two laws, both of which apply to sets. We considered the laws before but only with two sets. Since DeMorgan’s laws are applicable to larger collections of sets as well we can denote them, with a slight adjustment, below.

Theorem: DeMorgan’s Laws

Let $A$ be a universal set with $A_{n}$ subsets, by DeMorgan’s Laws

$\left(\bigcup_{i=1}^{n}{A_{i}}\right)'=A_{1}'\cap A_{2}'\cap A_{3}'...\cap A_{n}'$
$\left(\bigcap_{i=1}^{n}{A_{i}}\right)'=A_{1}'\cup A_{2}'\cup A_{3}'...\cup A_{n}'$

Having already summarized DeMorgan’s laws we will now quickly look at some applications with more than two sets before moving on to the next theorem.

Example:

Consider sets $A_{1}=\left\lbrace a,b,c,d,e,f,g,h\right\rbrace$ and $A_{2}=\left\lbrace d,e,h,i,j,k\right\rbrace$ and the universal set $A=\left\lbrace a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p\right\rbrace$ . Using DeMorgan’s law for the negated union of sets solve for $(A_{1}\cup A_{2})'$ .

$\begin{equation*} \begin{split} (A_{1}\cup A_{2})'&=(\left\lbrace a,b,c,d,e,f,g,h,i,j,k\right\rbrace )'\\ &=\left\lbrace l,m,n,o,p \right\rbrace \\ &=\left\lbrace i,j,k,l,m,n,o,p\right\rbrace \cap\ \left\lbrace a,b,c,f,l,m,n,o,p\right\rbrace \\ &= A_{1}'\cap A_{2}' \end{split} \end{equation*}$

Thus $(A_{1}\cup A_{2})'=\left\lbrace l,m,n,o,p\right\rbrace = A_{1}'\cap A_{2}'$ .

In this last example we see that by negating the union of sets $A_{1}$ and $A_{2}$ we are essentially finding the complementary set to the union of $A_{1}$ and $A_{2}$ which is the same as if you were to find the intersection for the complementary sets for $A_{1}$ and $A_{2}$ .

We move on to look at yet another theorem for set theory, the distributive law.

Theorem:

For any sets $A$ , $B$ , and $C$ , by applying the distributive law for sets we have the following:

$A\cap (B \cup C) = (A\cap B)\cup (A\cap C)$
$A\cup (b\cap C) = (A\cup B) \cap (A\cup C)$

Just as in arithmetic when we multiplied an entire function by a value or variable by multiplying each element of the function by that value or variable, the same is said for sets. The best way to understand this theorem is by looking at the proofs for these two laws for our examples.

Example:

Prove $A\cap (B \cup C) = (A\cap B)\cup (A\cap C)$ .

Proof: Let $x\in \left( A\cap (B\cup C)\right)$ , then

$\begin{equation*} \begin{split} x\in \left( A\cap (B\cup C)\right)&\\ iff&\ x\in A\ and\ x\in (B\cup C)\\ iff&\ x\in A,\ and\ x\in B\ or\ x\in C\\ iff&\ x\in A\ and\ x\in B,\ or\ x\in A\ and\ x\in C\\ iff&\ x\in(A\cap B),\ or\ x\in(A\cap C)\\ iff&\ x\in \left((A\cap B)\cup (A\cap C) \right) \end{split} \end{equation*}$

Here we use $iff$ to denote “if and only if”. As well, we can note through this work above we use our understanding of elements in relation to unions and intersections of sets to prove $A \cap (B\cup C)\subseteq (A\cap B)\cup (A\cap C)$ . We know from previous examples that if a set $A$ is a subset of a set $B$ then every element in $A$ is an element in $B$ . Thus we utilize this relationship to prove that an arbitrary element in $(A\cap (B\cup C))$ is an element in $(A\cap B) \cup (A\cap C)$ and thus we have proven $A \cap (B\cup C)\subseteq (A\cap B)\cup (A\cap C)$ .

Now let $x\in (A\cap B)\cup (A\cap C)$ , then

$\begin{equation*} \begin{split} x\in (A\cap B)\cup (A\cap C)&\\ iff&\ x\in (A\cap B)\ or\ x\in (A\cap C)\\ iff&\ x\in A\ and\ x\in B,\ or\ x\in A\ and\ x\in C\\ iff&\ x\in A,\ and\ x\in B\ or\ x\in C\\ iff&\ x\in A,\ and\ x\in (B\cup C)\\ iff&\ x\in \left( A\cap (B\cup C)\right) \end{split} \end{equation*}$

Here we start by looking at an arbitrary element in $(A\cap B)\cup (A\cap C)$ and we use this, with our understanding of elements as they relate within unions and intersections of sets to conclude that $x$ is also in $(A\cap (B\cup C))$ . Thus proving $(A\cap B)\cup (A\cap C)\subseteq A \cap (B\cup C)$ .

Since we have proven $A \cap (B\cup C)\subseteq (A\cap B)\cup (A\cap C)$ and $(A\cap B)\cup (A\cap C)\subseteq A \cap (B\cup C)$ , thus we can conclude that $A\cap (B \cup C) = (A\cap B)\cup (A\cap C)$ .

Example:

Prove $A\cup (B\cap C) = (A\cup B) \cap (A\cup C)$ .

Proof: Let $x\in \left( A\cup (B\cap C)\right)$ , then

$\begin{equation*} \begin{split} x\in \left( A\cup (B\cap C)\right)&\\ iff&\ x\in A\ or\ x\in (B\cap C)\\ iff&\ x\in A,\ or\ x\in B\ and\ x\in C\\ iff&\ x\in A\ or\ x\in B,\ and\ x\in A\ or\ x\in C\\ iff&\ x\in (A\cup B),\ and\ x\in (A\cup C)\\ iff&\ x\in \left( (A\cup B)\cap (A\cup C)\right) \end{split} \end{equation*}$

Just as we did in the previous example, we begin with an arbitrary element in $\left( A\cup (B\cap C)\right)$ . Through our knowledge of elements as they relate to the union and intersections of sets we draw the conclusion that $x\in \left( (A\cup B)\cap (A\cup C)\right)$ . Since every element in an arbitrary set $A$ is an element in an arbitrary set $B$ if $A\subseteq B$ then we draw the conclusion that $A\cup (B\cap C) \subseteq (A\cup B) \cap (A\cup C)$ .

Let $x\in (A\cup B) \cap (A\cup C)$ , then

$\begin{equation*} \begin{split} x\in (A\cup B) \cap (A\cup C)&\\ iff&\ x\in (A\cup B)\ and\ x\in (A\cup C)\\ iff&\ x\in A\ or\ x\in B,\ and\ x\in A\ or\ x\in C\\ iff&\ x\in A,\ or\ x\in B\ and\ x\in C\\ iff&\ x\in A\ or\ x\in (B\cap C)\\ iff&\ x\in \left( A\cup (B\cap C)\right) \end{split} \end{equation*}$

As we did in the previous portion of this example we prove that $x\in (A\cup B) \cap (A\cup C)$ and $x\in \left( A\cup (B\cap C)\right)$ and, since every element in an arbitrary set $A$ is an element in an arbitrary set $B$ if $A\subseteq B$ then we can conclude that $(A\cup B) \cap (A\cup C)\subseteq ( A\cup (B\cap C)$ .

Since we have now proven that $A\cup (B\cap C) \subseteq (A\cup B) \cap (A\cup C)$ and $(A\cup B) \cap (A\cup C)\subseteq ( A\cup (B\cap C)$ then we conclude that $A\cup (B\cap C) = (A\cup B) \cap (A\cup C)$ .

Here we can see how by using the definitions for union and intersection we can solve the proofs for the distributive laws by simply following element $x$ as it relates to each set. On the topic of relations we will now progress to the next section covered in the course Bridge to Analysis, relations.

13 Set Theory

License

Share This Book