Mathematical Proof

Course Overview

This course introduces set theory, constructive proofs and proof by contradiction.

As you progress through this course, you will find links to related topics in other courses (such as calculus and partial differential equations). This interconnected structure is designed to help you quickly revisit prerequisite ideas without breaking your workflow.

Introduction to sets

One of the most important places to start for many advanced mathematics proof based courses is the basics of set theory. We should begin with, what exactly is a set? A set is a collection of unique elements. Sets are very flexible, while we will be primarily interested in sets containing numbers, sets, with very limited restrictions (for mathematical purposes we do place some restrictions on what sets can contain to avoid "sticky" situations, we will discuss Russell's paradox later which is the source of the aforementioned sticky situations) on what they can contain. So for example, a set might contain shapes, circles, conics, squares, rectangles, octagons and so on. Or a set might contain tree types such as balsam, oak, pine, birch etc. Or it might contain a mixture of things, like letters and the numbers 0 through 9. In any case, we need a common way of expressing sets, so typically we will refer to sets as capital letters, like $A$, and we will enclose the elements with a set (or it's description) inside "curly" brackets $\{\}$, for example $$A = \{1,2,3,4,5,6\},$$ is the set of all the numbers you typically find on a die. For a mixed set example, we will call $B$ the set of all of the "typical" (non case sensitive) characters you might find in a password, $$B = \{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,0,1,2,3,4,5,6,7,8,9,.,!,@,\&,\$\}.$$ I obviously didn't capture all possible characters that could be found in a password, but you get the point. Now, when dealing with sets, we are often interested in a particular property of the set, namely, how many elements does it contain? In our examples above, we can see that the cardinality of the set is, $$|A| = 6.$$ The cardinality of a set is represented by placing the name of the set, (in this case $A$) inside the absolute value sign, and the cardinality is simply the total number of elements in the set. So for $B$, $$|B| = 41.$$ We will return to this topic later, after we dive into operations on sets.

If you want the fast version, below is a short video introducing set theory basics.

Introduction to operations on sets

We also have some rules for combining sets. The union $\cup$ is one way of combining sets, and it creates a new set (generally from 2 or more sets, with the union applied iteratively if it is more than 2), which contains all of the elements that were in either the first set, or the second one. For example, if we have $C = \{1,3,5,7\}$ and $D = \{2,6,7\}$, then, $$C_D = C \cup D = \{1,2,3,5,6,7\}.$$ Notice that the number $7$ is only contained once in the set $C_D$, this is because sets only contain unique elements. Also note that $C \cup D = D \cup C$, that is, the ordering does not matter.

There are other operations on sets as well, for instance the intersection $\cap$. We will use $C$ and $D$ from above, $$C^D = C \cap D = \{7\}.$$ That is, the intersection contains the elements that were in both $C$ and $D$. There was only 1 element in both in this case. Now we will define, $$E = \{2,4,6\},$$ notice that $E \cap C = \{\}$, that is there are no elements contained in both $E$ and $C$, such sets are called disjoint. The empty brackets are sometimes referred to as the empty set, and a special symbol is given, $\emptyset = \{\}$.

Another operation is set difference, which has a couple of typical representations, one is the normal subtraction sign, the other being $\backslash$, and set difference represents all of the elements that are in the first set that are not in the second set. For example, using our sets from above, $$C - D = C \backslash D = \{1,3,5\}.$$ Note however that in general the ordering of the set difference matters, we can see this by taking $D-C$, $$D \backslash C = \{2,6\} \neq C \backslash D,$$ thus we say that the set difference operation is not commutative.

The Cartesian product of a set, represented by the $\times$ symbol, is also an important set operation that we run into frequently, and it represents all of the unique ordered pairs that we can make from the two sets (note that the sets may both be the same set in the cartesian product). So for example, $$C \times D = \{(1,2),(1,6),(1,7),(3,2),(3,6),(3,7),(5,2),(5,6),(5,7),(7,2),(7,6),(7,7)\},$$ and this operation is also not commutative as, $$D \times C = \{(2,1),(2,3),(2,5),(2,7),(6,1),(6,3),(6,5),(6,7),(7,1),(7,3),(7,5),(7,7)\}.$$ It is important to note that, as is implied by the name ordered pair, the ordering matters here, that means that $(1,2) \neq (2,1)$, but even so it is clear from the above example that $C \times D \neq D \times C$. If we take the Cartesian product of a set with itself, for example the set $C$, then we will write a power to denote this, for instance, $$ C \times C = C^2, C \times C \times C = C^3, ...$$

I will now introduce another common operation on a set, which is something called the power set, $P$. The power set is the set of all subsets of a set. We need a definition here, a subset is a set that contains some (or all) of the elements from the original set, and does not contain any elements from outside of that set. For a moment we will talk generally about sets and then give examples later, rather than defining what values the sets take on. If we have a set $G$ (which can be any set you want to imagine) and a subset of $G$ that for the purposes of illustration we will call $S$ (which can also be any set you can imagine), then the following statements must be simultaneously true, $$S \cup G = G,$$ and $$S \cap G = S.$$ If those two statements are simultaneously true, then we may write, $$ S \subseteq G,$$ since $G$ is technically a subset of itself, and if $S \neq G$ we will write, $$ S \subset G,$$ which means that $S$ is a proper subset of $G$. For example, $$F = \{2,6\}$$ is a proper subset of $D$ (recall that $D = \{2,6,7\}$), but $$H = \{2,8\}$$ is not a subset of $D$, since $8 \notin D$, where the $ \in $ means is an element of, and thus, $\notin$ means is not an element of, so this should read as $8$ is not an element of $D$. Now we need one last idea before finally defining the power set. It is vacuously true that $\emptyset$ is a subset of every set, this is because $\emptyset$ contains no elements, thus all of its elements are by default inside of every set. Now armed with all of these ideas, we may finally see the power set in action, recall that the power set is the set of all subsets of a particular set. For example, the power set of $D$, $$P(D) = \{\emptyset,\{2\},\{6\},\{7\}, \{2,6\}, \{2,7\}, \{6,7\}, \{2,6,7\}\}.$$ Notice that $P(D)$ contains $\emptyset$ and also contains $D$ itself inside of it. This is true of every power set, it will always contain the empty set and the set itself.

Now we will define yet another operation, called the complement. The complement in general needs two sets defined, the "outer" set, and a subset of that set. For this example, I am going to remind you that we said above that $A = \{1,2,3,4,5,6\}$. This will be our set, and our subset of $A$ will be $K = \{1,2,3\}$. Then the complement $K_A^C$ in $A$ is, $$K^C = \{4,5,6\},$$ that is $K_A^C$ contains all of the elements in $A$ that are not in $K$, or using our notation from above, $K^C = A - K$. Note here the importance that $K \subseteq A$, it must be a subset of the set we are taking a complement in (and it does not have to be a proper subset, it is perfectly valid for the complement to be an empty set). We must make reference to the outer set, however, in order to determine what the complement is. For instance, suppose we have another set $L = \{1,2,3,4,5,6,7,8\}$, then the complement of $K$ in $L$ is, $$K_L^C = L-K = \{4,5,6,7,8\}.$$ So if $K$ is a subset of multiple defined sets, then we must say which set we are taking the complement in.

We will also occasionally run across something called the symmetric difference, which is given by the symbol $\Delta$. Recall that the difference between two sets is not commutative, we can produce a difference that is commutative by defining the symmetric difference as follows, for a set $A$ and $B$, $$A \Delta B = (A\backslash B) \cup (B\backslash A).$$ For the purposes of illustration, I will use $B = \{5,6,9,11\}$, then the symmetric difference defined above is, $$ A \Delta B = (\{1,2,3,4\}) \cup (\{9,11\}) = \{1,2,3,4,9,11\},$$ and just to show that this is in fact commutative, $$ B \Delta A = (\{9,11\})\cup (\{1,2,3,4\}) = \{1,2,3,4,9,11\},$$ which shows that $A \Delta B = B \Delta A$ (we will not prove this now, we will save that for when we have a solid grasp on proof itself later).

de Morgan's laws

We will state (without proof for now) important relations between sets and their complements, the first of de Morgan's laws states, given a collection of sets $A_\alpha$ indexed by $\alpha$, we have that the following is true: $$(\bigcup \limits_\alpha A_\alpha)^C = \bigcap \limits_\alpha A_\alpha^C.$$ That is, the complement of the union of many sets is the same as the intersection of the complements of those sets. This wording is a bit confusing, so it will

Place holder

The Cartesian Product

We will discuss the cartesian product here!

Place holder