Set Theory

Sets are among the fundamental ideas in math. We cannot define them in terms of other things because of this. They are sometimes called a "primitive notion." Like points and lines in geometry we simply assume they exist and say so in the axioms used as the foundation of math. They just are. In hopes of making this important concept more clear, we will think of a Set as a "bag" which objects can be put in. This informal definition is useful conceptually, but inadequate as a rigorous definition. Feel free to explore Wikipedia's Introduction to Sets concurrently. If you want the more rigorous Axiomatic Set Theory then ZFC Set Theory is the most common introduction. ZFC resolves many problems with Naive Set Theory, including Russell's Paradox.

Fundamentals

We must have a large set to place the sets we are interested in. This set is often called Universe of Discourse or just the Universe. The symbol $U$ is typically used to denote the universe. For $A$ to be a Well Defined Set (and all sets we are interested in are well defined) it is required that all the objects in the universe be either in or out of the set $A$, but not both. We write $x\in A$ to mean "$x$ is an object in the set $A$". This can also be stated by saying "$x$ is an element of $A$", "$x$ is in $A$", and many other ways.

We often write sets with a finite number of elements explicitly. For instance $A=\{1,{\frac {2}{3}},\bigstar ,\blacktriangle ,{\text{blue}}\}$ is a set $A$ with the elements $1$, ${\frac {2}{3}}$, $\bigstar$, $\blacktriangle$, and ${\text{blue}}$. Note Set Equivalence works just as one would expect. Two sets are equivalent if and only if they have exactly the same elements. It is often useful to depict a set with a Venn Diagram like the one below.

With the universe $U=\{1,{\frac {2}{3}},\bigstar ,\blacktriangle ,{\text{blue}},\blacklozenge ,\blacksquare \}$.

As an example of how to use notation, we note that $\bigstar \in A$, and $\blacksquare \in U$. We use the symbol $\notin$ to say an element is not in a set. For instance $\blacksquare \notin A$ in the above example. We also note this is a logical statement and is equivalent to $\lnot (\blacksquare \in A)$. As we progress we will find a variety of such connections between logic and set theory.

Sets are not allowed to have repeated elements, $\{1,1,2,3\}$ is not allowed. Sets themselves can also be elements of other sets, $B=\{1,2,A,\{1,2\},3\}$ is allowed. Note A and $\{1,2\}$ can themselves contain elements which are also elements of $B$ because the set $A$ or $\{1,2\}$ are distinct objects. We also note that a set cannot contain itself as an element (this would lead to Russell's Paradox).

The Empty Set (sometimes Null Set or Void Set) is the set $\{\}$ and is usually denoted $\emptyset$. The empty set has no elements in it.

While arbitrarily selected set elements are fine, it is often more useful to have a rule for deciding whether to include elements in a set. For instance, we might have a set of red objects, a set of even numbers, a set containing all birds, a set of perfect squares, etc.

Basic Set Operations

Please read Wikipedia's Set Operations concurrently to compare and contrast. Please pay special attention to the Venn Diagrams, more of which can be found here. The diagram for the symmetric difference is of particular interest to computer programmers, as it is the set equivalent to the logical XOR.

Compliment

Operations can be defined on sets too. The easiest operation is the compliment. The compliment of $A$ is denoted $A^{\prime }$. The Compliment of $A$ is every element which is in $U$, but not in $A$. The region of the Venn Diagram where elements of $A^{\prime }$ may appear is coloured yellow below.

This set can also be defined using rules as follows. $A^{\prime }=\{x\in U|x\notin A\}$. This means the elements of $A^{\prime }$ are the elements of $U$ subject to the condition that they are not also elements of $A$.

The remaining operations of interest all require two sets to be defined within the universe.

Intersection

The Intersection of two sets $A$ and $B$ is denoted $A\cap B$. These are all the elements of U which are both in $A$ and in $B$. The equivalent logic statement is $(x\in A\cap B)\Leftrightarrow (x\in A)\wedge (x\in B)$. The brackets are not strictly required here, but are used to emphasize the edges of each logical statement. We represent the intersection of $A$ and $B$ with the Venn Diagram below.

Union

The Union of two sets $A$ and $B$ is denoted $A\cup B$. These are all the elements of U which are in $A$ or in $B$. The equivalent logic statement is $(x\in A\cup B)\Leftrightarrow (x\in A)\vee (x\in B)$. The following Venn Diagram represents the union of $A$ and $B$.

Set Relations

Subsets and Super Sets

We can also define subsets. A Subset is a set wholly contained within another set. Every element of a subset is an element of the set it is contained in. We write $A\subseteq B$ to mean $A$ is a subset of $B$. The equivalent logical statement is $(x\in A)\Rightarrow (x\in B)$. $B$ is also called the Superset. The subset symbol is written much like the less than equal to symbol ($\leq$). This is to indicate that it is allowed that the sets are equal. A Proper Subset would be written $A\subset B$ and would not allow $A$ and $B$ to be equal, ie at least one element exists in $B$ which is not in $A$. A Venn Diagram representing $A\subseteq B$ (in fact $A\subset B$ as well) follows.

Set Equality

As mentioned earlier, two sets are equivalent if and only if they have exactly the same elements. This is written $A=B$. Note in the case $A=B$ the Venn Diagram would be one yellow circle inside a white rectangle and the circle would be labelled both $A$ and $B$.

If you can show that $A\subseteq B$ and $B\subseteq A$ then the elements of $A$ and $B$ are the same (more explicitly there are no elements of one that are not in the other) and thus $A=B$.

Disjoint Sets

Two sets $A$ and $B$ are said to be Disjoint Sets if they share no elements, ie if $A\cap B=\emptyset$.

Further Set Operations

Set Difference

The Set Difference $A-B$ (also written $A\backslash B$) is defined to be the set which contains all the elements of $A$ which are not in $B$. In terms of logic we state $(x\in A-B)\Leftrightarrow (x\in A)\wedge (x\notin B)$. This is sometimes called the Relative Compliment of $B$ in $A$. Note $A^{\prime }=U-A$. This gives us an expression for the complement of a set (defined earlier). The Venn Diagram for $A-B$ is below.

Cartesian Product

The Cartesian Product of two sets $A$ and $B$ is the set of all ordered pairs which can be created by combining the elements of $A$ and $B$ with the elements of $A$ in the first position and the elements of $B$ in the second position. It is denoted $A\times B$. An illustrative example is instructive.

Consider $A=\{1,2,3\}$ and $B=\{2,4,5\}$, then $A\times B=\{(1,2),(1,4),(1,5),(2,2),(2,4),(2,5),(3,2),(3,4),(3,5)\}$.

This notation should look a lot like how we write the coordinates of points in the x-y plane. More on that later. You may notice that the order of operations for set theory are implied by the order of operations of logic and are exactly as one would expect. We won't be testing that in this course though.

Set Properties

Cardinality

The Cardinality of a set $A$ is the number of elements in the set. It is denoted $|A|$ (sometimes $n(A)$). For example, the cardinality of $\{1,3,5,7\}$ is 4 $(|\{1,3,5,7\}|=4)$. It is a way of thinking about the "size" of a set. The first exercise on the Principle of Inclusion Exclusion illustrates this further.

Defining Sets

While it is perfectly fine to define sets arbitrarily (ie. just say what elements are in the set), it is often useful to define them with some rule. Most useful sets have some defining characteristic like the set of colours, the set of emotions, the set of animals, etc. We use sets this way to classify elements. The sets we will usually be interested in are numbers, and more complex things constructed from numbers. To define a set using a rule (say the set of odd Natural Numbers) you could write $O=\{x|x{\text{ is an odd number}}\}$ or equivalently $O=\{x:x{\text{ is an odd number}}\}$. Both these statements say the set $O$ is the set of elements $x$ such that $x$ is an odd number. To remove English sentences entirely you could write $O=\{x\in \mathbb {N} |{\frac {x}{2}}\notin \mathbb {N} \}$. This statement says the set $O$ is the set of elements that are Natural Numbers, such that when they are divided by 2, they do not yield a Natural Number. There are plenty of variations on this. As long as you can translate the symbols to English, you'll be able to make sense of them. Check out this Wikipedia link if you want more detail.

Some Familiar Infinite Sets

When doing math there are certain favourite sets which come up often. You have already met several of them.

• $\mathbb {N}$ is the symbol used for the set of Natural Numbers $\{1,2,3,\ldots \}$.
• $\mathbb {W}$ is the symbol we will use for the set of Whole Numbers $\{0,1,2,3,\ldots \}$. In actual fact Mathematicians just redefine the Natural Numbers to include zero when it suits them, but this makes for ambiguous notation so I introduce $\mathbb {W}$ for clarity.
• $\mathbb {Z}$ is the symbol used for the set of Integers $\{\ldots ,-3,-2,-1,0,1,2,3,\ldots \}$.
• $\mathbb {Q}$ is the symbol used for the set of Rational Numbers, the set of all fractions with any integer as the numerator, and any natural number as the denominator. All fractions are stated in lowest terms and repeated elements are discarded. The rationals can also be described as every decimal number than terminates or ends in some repeating pattern.
• $\mathbb {I}$ is the symbol used for the set of Irrational Numbers. The symbol $\mathbb {I}$ is commonly used elsewhere in math though, so it is more common to use $\mathbb {R} -\mathbb {Q}$ (or $\mathbb {R} \backslash \mathbb {Q}$) for the irrationals. The irrationals are all the decimals which do not have a repeating pattern ever and do not terminate. They come in two varieties. Algebraic Irrationals are the roots of polynomials with rational coefficients. The square root of a rational which is not a perfect square is an example. Transcendental Irrationals are the rest of the irrationals (numbers like $\pi$ and the Euler number $e$)
• $\mathbb {R}$ is the symbol used for the set of Real Numbers. The reals are the rationals and the irrationals combined. $\mathbb {R}$ contains all the numbers that usually show up in high school.

Note, that all these set have infinite cardinality (number of members). Investigating the different sizes of infinity (Aleph Number) represented here is left to the student's interest and discretion.

There are other useful sets like: the Imaginary Numbers, Complex Numbers, sets of vectors, sets of Matrices, etc. We will discuss more in time.

Quantifiers

It can be useful to know if all, some, or none of the elements of a set have a certain property. Lets look at how one might write this. To begin lets define a set according to a certain rule. We will define the set of even natural numbers and call it $E$. The the elements of the set (lets call an arbitrary element $x$) are all divisible by $2$. In symbols we could write $\forall x\in E,{\frac {x}{2}}\in \mathbb {N}$. It is also a true statement to say $\exists x\in E;{\frac {x}{2}}\in \mathbb {N}$. Some of the elements are divisible by two, because all of them are. It would not be true to say no elements are divisible by two though. That is to say, $\nexists x\in E;{\frac {x}{2}}\in \mathbb {N}$ is a false statement.

As another example take the set $A=\{1,2,3,4,5\}$ and denote the set of prime numbers by $P$. Some of these numbers are prime ($\exists x\in A;x\in P$). It would be false to state that all of the elements of $A$ are prime ($\forall x\in A,x\in P$) or to state that none of them are prime ($\nexists x\in A;x\in P$).

Applications

Set theory provides the base objects from which many of the other statements in math are constructed. Set theory and logic, together, lay much of the ground work for the rest of math.

In particular Sets are useful when talking about probabilities, when we do arithmetic and algebra with their elements and when used as what we map between when discussing functions. We will use sets explicitly and implicitly very often.

Exercises

Principle of Inclusion Exclusion

${\begin{aligned}A=\{1,2,3,6\},B=\{2,3,4,7,8\},C=\{3,4,5,6,9,10\}\\|\emptyset |=0\\|\{\emptyset \}|=1\\|\{\emptyset ,\{\emptyset \}\}|=2\\|A|=5\\|B|=5\\|C|=6\\|A\cap B|=2\\|A\cup B|=8\\|A\cap C|=3\\|A\cup C|=8\\|B\cap C|=2\\|B\cup C|=9\\|A\cap B\cap C|=1\\|A\cup B\cup C|=10\end{aligned}}$

Consider $|A|$, $|B|$, $|A\cap B|$, and $|A\cup B|$. Do you see a relationship to get $|A\cup B|$ from the other three values? Try repeating for $A,C$ and $B,C$? Does your relationship hold? Now consider $|A\cup B\cup C|$ in terms of $|A|$, $|B|$, $|A\cap B|$, $|A\cap C|$, $|B\cap C|$, and $|A\cap B\cap C|$. Use the Venn Diagram for inspiration. Hint get rid of double counting. This relationship is called the Inclusion-Exclusion Principle. If you'd like to check your relationship, have a look online. Wikipedia has a nice article with everything you need at the top of the page.

Set Algebra

We can do Algebra on sets, just like in logic. Compare the following identities to the rules of replacement from logic. Do you see a connection? What do the two new compliment laws at the bottom correspond to? The intersection and union symbols are chosen suggestively. For the rules which result in a single symbol of the right hand side, consider how this simplification comes about, and how it might feed into another simplification later to further simplify the whole expression. Please draw the Venn Diagrams for the expressions with more than one symbol on the right side. Reminder the $A$s, $B$s, and $C$s here are sets. In the logic section they were statements. The same symbols are used to mean two different things. This was done to emphasize the similarity between the two kinds of algebra. We will see many of the same rules show up again when we talk about algebra on numbers, vectors, and matrices.

${\begin{aligned}(A^{\prime })^{\prime }&=A&{\text{Double Compliment}}\\(A\cap B)\cap C&=A\cap (B\cap C)&{\text{Associativity of Intersections}}\\(A\cup B)\cup C&=A\cup (B\cup C)&{\text{Associativity of Unions}}\\A\cap B&=B\cap A&{\text{Commutivity of Intersections}}\\A\cup B&=B\cup A&{\text{Commutivity of Unions}}\\A\cap (B\cup C)&=(A\cap B)\cup (A\cap C)&{\text{Distribution of Intersections over Unions}}\\A\cup (B\cap C)&=(A\cup B)\cap (A\cup C)&{\text{Distribution of Unions over Intersections}}\\A\cap \emptyset &=\emptyset &{\text{Annihilation for Intersection}}\\A\cup U&=U&{\text{Annihilation for Unions}}\\A\cap U&=A&{\text{Identity for Intersection}}\\A\cup \emptyset &=A&{\text{Identity for Unions}}\\A\cap A&=A&{\text{Idempotence for Intersection}}\\A\cup A&=A&{\text{Idempotence for Unions}}\\A\cap (A\cup B)&=A&{\text{Absorption of Unions by Intersections}}\\A\cup (A\cap B)&=A&{\text{Absorption of Intersections by Unions}}\\A\cap A^{\prime }&=\emptyset &{\text{Complimentation for Intersections}}\\A\cup A^{\prime }&=U&{\text{Complimentation for Unions}}\\(A\cap B)^{\prime }&=A^{\prime }\cup B^{\prime }&{\text{Demorgan's Law for Intersections}}\\(A\cup B)^{\prime }&=A^{\prime }\cap B^{\prime }&{\text{Demorgan's Law for Unions}}\\\\{\text{And introducing}}&&\\\\U^{\prime }&=\emptyset &{\text{Compliment Law for the Universal Set}}\\\emptyset ^{\prime }&=U&{\text{Compliment Law for the Empty Set}}\\\end{aligned}}$

Have a peek at Wikipedia's Algebra of Sets if you would like more detail.

Infinite Set Venn Diagram

Please draw a Venn Diagram illustrating how $\mathbb {N} ,\mathbb {W} ,\mathbb {Z} ,\mathbb {Q} ,$ and $\mathbb {I}$ are subsets of $\mathbb {R}$ and eachother. You may wish to choose to partition the rationals and irrationals inside the reals for clarity (as all reals are either rational or irrational). It may also be nice to set the universe as the reals. That is to say you may want to start with something like this.

As a note, the diagram is for understanding the hierarchy of subsets only. The relative sizes of the images do not connote the relative sizes of the sets. For instance the irrationals are considered a larger infinity than the rationals.

Extensions

Try Set Algebra

If you would like to try using the set identities, here are a few problems. If you ever get stuck, check the Venn Diagram of the left hand side and right hand side to see if they still match. If they don't you have an error. Alternatively you can directly replace $\prime$ with $\lnot$, $\cap$ with $\wedge$, $\cup$ with $\vee$, $\subseteq$ with $\Rightarrow$, $\emptyset$ with F, U with T, and $=$ with $\equiv$, then compare truth tables. They should match. Using the order of operations from logic you can infer the order of operation in set theory (using the replacements just indicated). Wolfram Alpha will again be useful for checking your answers.

${\begin{aligned}(A\cap B^{\prime })\cap (A\cap B)&=\emptyset \\A^{\prime }\cup (A\cap B)&=A^{\prime }\cup B\\(A\cup B^{\prime })\cap (A^{\prime }\cap B)^{\prime }&=A\cup B^{\prime }\\A\cup C\cap (B\cup C)\cup B^{\prime }\cup (C\cup B)\cap (C^{\prime }\cup B)&=U\\(A\cup C)\cap (B\cup C)\cup (C\cup B)\cap (C^{\prime }\cup B)&=B\cup C\\(A\cup C)\cap (B\cup C)\cap (A\cup B)^{\prime }&=C\cap (A\cup B)^{\prime }\\((A\cap B)^{\prime }\cap C)^{\prime }\cap ((B\cup C)\cap A)&=A\cap B\end{aligned}}$

Defining Numbers with Sets

Interested students may want to read about the Cardninal and Ordinal properties of the Naturals and von Neumann Ordinals. Wikipedia has a nice resource Defining Natural Numbers

Suggested Resources

Set Calculator with Example