Set Wars: Episode III - Revenge of the Sizes

In the previous post we began exploring infinite sets - namely the integers and subsets thereof. However, we know that these are not the only infinite sets; there are the rationals (which contain the integers) and irrationals. We might be interested in determining properties of both of these sets. What is ahead of us is a weird exploration full of twists and turns and foundation-shaking results.

In the last post, we discovered that the even integers have the same number of elements as the integers. For convenience we will say that the integers are countably infinite (or just countable for short). Calling them countable is weird because it seems to imply you could actually count all of them, however that is not the reason for calling them countable. Instead it means you can list them in some meaningful way. In the case of the natural numbers (the numbers $1, 2, 3, \ldots$) we can just list them in order, starting at $1$: $1, 2, 3, 4, 5, 6, \ldots$ Or for the even integers: $0, 2, -2, 4, -4, 6, -6, \ldots$.

We will first observe the rationals. Recall that a number is rational if and only if it can be written in the form $\dfrac{p}{q}$ where $p$ and $q$ are integers. Since the rationals contain the integers, there are definitely an infinite amount of them; the question is: are they countable? In order to determine if they are countable, we will create a table as seen below. (Note that the table is actually infinite in size, but I have truncated it for convenience.)

\begin{array}{cccccc}
1/1 & 1/2 & 1/3 & 1/4 & 1/5 & \cdots \\
2/1 & 2/2 & 2/3 & 2/4 & 2/5 & \cdots  \\
3/1 & 3/2 & 3/3 & 3/4 & 3/5 & \cdots \\
4/1 & 4/2 & 4/3 & 4/4 & 4/5 & \cdots \\
5/1 & 5/2 & 5/3 & 5/4 & 5/5 & \cdots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \ddots
\end{array}

The elements are created via the following construction: the numerator in each element is the row number and the denominator in each element is the column number. We will march through the table in the following manner. Start at $1/1$ and label this with the number $1$; migrate to $1/2$ and label this with the number $2$; move to $2/1$ and label this with $3$; move to $3/1$ and label this with $4$; move up to $1/3$ and label this with $5$, etc. The shape of the "graph" that resembles how we march through the elements in the table is a series of zig zags through the table. Note that $2/2$ since we had already accounted for it with $1/1$. This is a general procedure by which to enumerate the rationals. As we march through the graph, we label each rational in the table with a natural number. By this construction, we have created a bijective function (though we have not given it an explicit formula) that labels each rational with each natural number. Think: $f(1,1) = 1$, $f(1,2) = 2$, $f(2,1) = 3$, $f(3,1) = 4$, etc (this probably looks similar to an example from the last post). You may wonder why I elected to use a comma as opposed to a division symbol. It boils down to the fact that each rational will show up infinitely often so $f(1/1) = f(1) = f(2/2)$; instead I elected to use a multivariable function where the relation between the two elements is division and referring to that element in the table.

So since we have created a bijective function between the two, we have shown that the rational numbers are indeed countable. A property that we shall explore later is called the Archimedean property of the natural numbers, from this it follows that in any interval there exists a rational number. Another result is that in every interval there exists an irrational number. From this fact, we might figure that there are an equal amount of rationals and irrationals. It turns out that the rationals effectively take up no space on the real line as we can see with the following proof.

Since the rationals are countable, we can denote them in a list like so: $ q_1, q_2, q_3, \ldots $. Consider some $ q_i $. Let $ \varepsilon > 0 $ and select the interval $ \left (q_i - \dfrac{\varepsilon}{2^{i+1}}, q_i + \dfrac{\varepsilon}{2^{i+1}} \right ) = I_i.$

Since each rational is in one of the $ I_i $ (by definition), each rational is in $ \bigcup\limits_{i=1}^{\infty} I_i $. Therefore $ \mathbb{Q} \subseteq \bigcup\limits_{i=1}^{\infty} I_i$, where $ \mathbb{Q}$ represents the set of rationals.

A theorem we have not proved but makes logical sense is that if $A$ and $B$ are sets and $ A \subseteq B $, then $ |A| \leq |B| $ where $|A|$ represents the cardinality of $A$. So, $ |\mathbb{Q}| \leq \left |\bigcup\limits_{i=1}^{\infty} I_i  \right| .$

Each $ I_i $ has length $ \dfrac{\varepsilon}{2^i} $ and using the fact that $ \left |\sum_{i=0}^n a_n \right| \leq \sum\limits_{i=0}^n |a_n| $, so $ \left |\bigcup\limits_{i=1}^{\infty} I_i  \right| \leq \sum \limits_{i=0}^{\infty} \dfrac{\varepsilon}{2^i} = \varepsilon .$

Since we can set epsilon to as small a number we want, we conclude that the rationals have size $0$. We know that the real numbers are composed of the rationals and irrationals and that both sets are mutually disjoint. If the rationals take up basically no space on the real line, then we must conclude the irrationals take up most of the space on the real line. We are therefore led to the conclusion that the irrationals are much more numerous than the rationals. Before we motivate this, we will show that there are more reals than naturals.

For simplicity, we will consider the interval $(0,1)$. Assume (by way of contradiction) that the numbers in the interval $(0,1)$ are countable. We will consider the decimal expansions of numbers in this interval with one provision: we will omit numbers trailing in an infinite sequence of $9$s. Numbers like $.4\bar{9}$ we know to be equivalent to $.5$, so we will not be missing numbers like $.4\bar{9}$ since they will already be present.

To achieve our goal, we will construct another table (my! these seem handy!). ($n$ represents a natural number and $r$ represents a non-natural real number.)



\begin{array}{ccccc}
1 & .{r_1}_1{r_1}_2{r_1}_3{r_1}_4 \cdots \\
2 & .{r_2}_1{r_2}_2{r_2}_3{r_2}_4 \cdots \\
3 & .{r_3}_1{r_3}_2{r_3}_3{r_3}_4 \cdots \\
4 & .{r_4}_1{r_4}_2{r_4}_3{r_4}_4 \cdots \\
\vdots & \vdots
\end{array}

The individual terms are the numbers in the decimal expansion of each $r_i$.

Let's construct a number $r$ in $(0,1)$. $\Bbb R$ will differ from every number in the following way: $r$ will differ from $r_1$ in the first element, $r$ will differ from $r_2$ in the second element, $r$ will differ from $r_3$ in the third element, and so on. The way it shall differ is by adding $1$ to the $i$th element of $r_i$ unless the element is $9$, in which case the way it shall differ is by becoming $0$. It is evident that $r$ is definitely a number in $(0,1)$ with this construction, and that it differs from every number in our table. However, our table contains all numbers in $(0,1)$, so $r$ must be located somewhere in the second column of our table. So $r$ is in the table and it is not in the table, which gives a contradiction.

The only assumption we made at the get go was that we could find a one-to-one correspondence between the natural numbers and the numbers in $(0,1)$. Because we reached a logical contradiction we are forced to conclude that the numbers in $(0,1)$ are not countable. Since the real line includes $(0,1)$ we conclude that the real line is not countable. And since the reals are composed of the irrationals and rationals only and since the rationals are countable, we must conclude the irrationals are uncountable.

We have determined some deep properties of the rationals and irrationals and there are plenty more, but for the sake of brevity, I must stop here. There are some interesting things to note about the irrationals: there is an important countable subset of them called the (irrational) algebraic numbers. The algebraic numbers are roots of polynomials with rational coefficients. Those numbers that are irrational but not algebraic are transcendental and these numbers are those that are most (read: all others take up no space on the real line) abundant on the real line. Important examples are $\pi$ and $e$. There are many others listed and can be found on the Wikipedia article on them.

The preceding proof is due to Gregory Cantor and many at first found this concept utterly false. How can there possibly be a hierarchy of infinities? Surely infinity is the same regardless of context. As time progressed, set theory became very well accepted, however set theory has taken many interesting twists and turns since. There are many different axiomatic set theories and each has its strengths and weaknesses. The topic of advanced set theory is interesting, but beyond the scope of this blog as it carves a very fine description of mathematics. While important, it will not serve to enlighten the reader at this time. At the present time, coarseness is preferred.

Set Wars: Episode II - Attack of the Cardinalities

Now that we have developed the framework for sets, we can finally use it to discover things about the nature of some very special sets (those that you and I work with on a daily basis). In this post I will cover some oddities surrounding infinite sets. You already know of one infinite set: the integers. Of course there are subsets of this set and there are other infinite sets, but I will focus on this one as it is quite familiar to you. For now, consider the following questions. Are there more integers than even integers? Why or why not? The answer to these two questions will be given later in the post.


Before we get to the weird results, we first need some more dreaded definitions and explanations behind the definitions. The upcoming definitions will, again, be a little strange and you might wonder why we define them as so, but once you see some examples you should be convinced.


Definition: The cardinality of a set is a measure of the elements in the set.


There are two possibilities: either a set is finite or it is infinite. We can easily see how to determine if there are the same number of elements in two finite sets: write the sets out and count the elements. Take for example the following sets:


$ A = \{ 1, 3, 5, 7 \} $ and $ B = \{ 2, 4, 6 \} $. We see that $A$ has four elements, whereas $B$ has three elements and conclude that $A$ and $B$ do not have the same number of elements, i.e. do not have the same cardinality. So far, so good. Unfortunately we cannot count (try as we might!) the amount of elements in an infinite set, so this approach seems less than satisfactory. We may need a shift in paradigm in order to approach the case of infinite sets. You might wonder why we even care; if two sets have an infinite amount of elements, then they have the same number of elements! However by that logic, infinity/infinity should equal one! But we know from calculus that isn't necessarily so. Initial intuition often fails when dealing with infinities, which is often caused by conceptions on shaky foundation.


To create a proper paradigm, we will imagine mathematics without the concept of numbers (it will turn out thinking about numbers is somewhat misleading). How would we then determine if two sets were the same size? We can't make a reference to the number of elements since we don't even know what numbers are, so that is out.


(I will try to avoid using numeric quantifiers so I don't contradict myself.) Imagine a basket with apples in it and imagine a basket with oranges in it. If we were told to determine if there were the same amount of each, we could reach a hand into each basket and pull out a single unit of each. We'll keep them paired when we place them on the ground: an orange with an apple. If we happen to run out of oranges at the same time that we run out of apples, we would be assured that we have the same amount of apples and oranges. Each individual apple is paired with an orange and each orange is paired with an apple. If we have an excess of either apple or oranges, we would have an empty basket and a basket with objects inside it.


This seems logical, but does it reduce down to what we devised before? It turns out that it does. Remember, we can't state how many elements there are since we don't know what numbers are, but we can say whether two collections have the same number of elements.


It turns out that this is the proper way of thinking about cardinality and this notion works wonderfully for infinite sets. We no longer talk about the actual size of the set, but whether or not we can form a proper pairing. If we have an infinite number of oranges and apples, yet we are able to pair one orange with one apple (and vice versa) we would undoubtedly have to say that they have the same cardinality. But if we have an excess of apples when pairing them with oranges, then we would be forced to say that the set of apples is larger than that of the oranges.


Before I continue and make this more concrete, I must define one term which will come up a lot in future discussion. You have undoubtedly heard the term or know what it is without knowing it by name.


Definition: A function $f$ is a bijection from the set $A$ into the set $B$ if $f$ is both one-to-one and onto. (Note: the range of $f$ must be contained in $B$.)


(Muffled groans) You might be thinking: Greaaat. Now what does that mean?


Well, if $f$ were an onto function, it would mean that nothing in our set $B$ is left out. In mathematical jargon, we say that every element in $B$ gets mapped to. See the picture below.

In this diagram, our function's domain is the set $\{a_1, a_2, a_3, a_4 \} $ and its codomain is the set $\{1, 2, 3\}$. The arrow represents what acting our function does to each element. So $f(a_1) = 1$, $f(a_2) = 1$, $f(a_3) = 2$ and $ f(a_4) = 3 $. As you can see, every element of our set $B$ gets mapped to. If an element were left out, it would not have an arrow going to it and our function would not be onto. Since this is not the case, it must be onto.


Okay so now what does one-to-one mean?


You're also familiar with one-to-one, though maybe not this term exactly. Colloquially, a one-to-one function is a function that passes the horizontal line test. An example of a function that is not one-to-one would be the function $f:\Bbb R\to\Bbb R$ given by $f(x) = x^2$. Take for example $x = \pm 1$. For both of these values $f(x) = 1$ so we conclude that $f$ is not one-to-one (two different $x$ values map to the same $y$ value!).


You might be wondering what functions are both one-to-one and onto? Well first we have to define a domain and codomain (our $A$ and $B$ as mentioned in the definition, respectively).


We'll work with what you're used to: the real numbers. We'll use the real numbers for both the domain and codomain. The function $f(x) = x$ is a bijection. The proof of this is left to the reader. (Hint: to show a function is one-to-one amounts to the following. If $f(x) = f(y)$, then $x = y$ - meaning that the only way $f$ can have the same value for two values in its domain is if the two values are in fact the same. To show it is onto, you want to make sure every element in the codomain gets mapped to. Pick $y$ in codomain. Try to find an $x$ such that $f(x) = y$. If no such $x$ exists, then the function is not onto.)


Okay, you've survived the definition of a bijective function (mark that off on your bucket list!). With this definition and the apples and oranges thought experiment from before, we can now give the formal concept behind equating cardinalities.


Concept: Two sets have the same cardinality if there exists a bijective function from one set into the other.


This concept is succinct and quite exact. There is no wiggle room to speak of. But you may not be convinced that this definition works. We'll test it out for our set of apples and oranges from before. The tricky part of showing two sets have the same cardinality is devising the function you need. While you may not be convinced, but we will rig our function to work properly.


Returning to out example of the apples and oranges, suppose $O = \{o_1, o_2, o_3\}$ and $A = \{a_1,a_2,a_3\}$ represent the set of oranges and apples, respectively. We will define $f$ by the following: $f:O\to A$ ($f$ is a mapping from the set of oranges into the set of apples) and

$$ f(o_1) = a_1,\quad f(o_2) = a_2,\quad f(o_3) = a_3.$$

As you can see, each orange is paired with a single apple and each apple is paired with a single orange, so by our previous concept we should have the same amount of each. Now we will show that this is the case within the new paradigm we have created. Is this function onto? The answer is obviously yes. We only had three apples and each one is mapped to by our function (the $ a_1$, $a_2$ and $a_3$). Now is it one-to-one? The answer is also yes. Each apple is paired with one and only one orange (no two oranges map to the same apple; recall the hint to the problem). We have successfully created a bijective function from the set of oranges into the set of apples and therefore they have the same number of elements.

Of course that was somewhat a waste of time since we already knew they had the same number of elements; we could just count them! The utility of this definition really only comes into play when discussing infinite sets and it is this very definition that causes all kinds of conceptual headaches as we are about to see.

Now that we have a proper framework, we can finally answer the question I asked at the beginning of the post, i.e. whether or not the integers and even integers have the same number of elements, i.e. have the same cardinality. We can now very easily answer this question, but first I will appeal to your intuition.

Imagine the finite set $\{1, 2, 3, 4, 5, 6\}$. The set of even integers within this set is $\{2, 4, 6\}$. Of course we would say that these two sets do not have the same number of elements; one has six elements, the other has three. What if there are an infinite amount of both? Well our sets look like the following: $\{\ldots, -4, -3, -2, -1, 0, 1, 2, 3, 4,\ldots\}$ and $\{\ldots, -4, -2, 0, 2, 4,\ldots\}$. Of course we know that the set of even integers are a subset of the integers, but also that there are numbers in the integers that are not in the set of even integers. Our intuition would tell us that the even integers and and the integers do not have the same number of elements. And of course our intuition is never wrong.

We'll check that our intuition is right with our hot-off-the-presses definition. Let's let $f : \Bbb Z\to \Bbb Z_e $, where the [; \Bbb Z_e ;] represents the even integers, and let $f(n) = 2n$, for the sake of argument.

Now, if $n$ is an integer, we know that $2n$ must be an even integer, so we are on the right track (our function's range is inside the codomain). We'll check if $f$ is onto.

Let $y\in \Bbb Z_e$, then $y$ is even. If $y$ is even, then it can be written in the form $2m$, where $m$ is some integer. But our domain is the entire set of integers, so surely $m$ must be in there somewhere! So we must conclude $f$ is onto. Now we'll check that it isn't one-to-one. (Otherwise if it is, our intuition was wrong. And our intuition cannot be wrong. Our intuition is infallible.)

Let $x$ and $y$ be in $\Bbb Z$ and suppose $f(x) = f(y)$. Then $f(x) = 2x$ and $f(y) = 2y$. However if $f(x) = f(y)$, then $2x = 2y$. We then obtain that $x = y$. So $f$ is also one-to-one.

We have created a function from the integers into the even integers that is one-to-one and onto. But one-to-one and onto functions are bijective functions and by our concept concerning cardinalities, we must conclude that $\Bbb Z$ and $\Bbb Z_e$ have the same number of elements. But our intuition says that they can't. What are we to do? Well the answer lies in the fact that we aren't built to understand infinite sets of objects intuitively. When was the last time you came across an infinite collection of apples (much less an infinite collection of both apples and oranges)? The answer is, of course, never. In mathematics we are often led astray by our intuition which leads us to something a professor once told me: Our intuition is never wrong. Except when it is.

Again, for the sake of brevity, I will cut this post short. If these ideas seem weird or mysterious, it is because they are - at least at first. A lot of early work in set theory was accomplished by a man named Gregory Cantor. A man whose ideas shook the foundations of modern mathematics. Many mathematicians believed his work to be factually incorrect purely because they disagreed with its premises. But the best - or worst, depending on which camp you are in - is yet to come. In the next post I will explore the real numbers and the supreme strangeness surrounding these incredible numbers.

Set Wars: Episode I - The Phantom Mathematics

Much of the early material in an introductory analysis class includes sets and their properties. Finite sets, infinite sets, empty sets. There are many elementary operations on sets such as union, intersection, complement and relative complement. Before we talk about these operations we must first define what a set is.

Definition: A set is a collection of mathematical objects.

This is a somewhat ambiguous definition. What are mathematical objects? Mathematical objects can be numbers, functions, other sets, you name it. Sets are typically written in the following way:

$ S = \{1, 2, 3, 4 \} $. (Meaning our set $S$ has for elements the numbers $1$, $2$, $3$ and $4$.)

Important examples of sets are the integers (as we mentioned before), rational numbers, irrational numbers, the real numbers, the natural numbers, the empty set, the list goes on and on. Now that we understand what a set is, we can talk about elements of the set.

You might wonder why we are concerned with sets and how on earth they could be important. For starters, sets give us a way of collecting objects in a meaningful way. If we are interested in the properties of some collection of numbers, it might be best to group all of them together in a set and prove general properties the collection has. Example: whether or not there are an infinite amount of prime numbers. There are at least two ways to attack this problem and both would be difficult without having some concept of a set - whether or not you use the word "set." Or perhaps you want to know if there are an infinite amount of irrational numbers. First you'd have to have a collection of them (read: a set of them) and then you'd have to devise a way of finding out if there are finitely many of them.

Concept: An object $x$ is said to be an element of a set $S$ if it is contained in $S$.

From our previous example of a set, the numbers $1$, $2$, $3$ and $4$ are all elements of $S$. If $x$ is an element of $S$, we write $x\in S$ as shorthand (read: $x$ is in $S$). We can now talk about subsets (a very important concept). The technical definition of a subset is somewhat difficult to swallow at first, so I will first refer to our previous example. Let $A$ be the following set:

$$ A = \{1, 2 \}.$$

$A$ is a subset of our previous set $S$ because the all of the numbers in $A$ are also in $S$. However, if $A$ included the number $9$, then $A$ would no longer be a subset of $S$ since it would no longer be contained in $S$ (i.e., it would have an element that is not in $S$). Now for the technical definition of a subset.

Definition: A set $A$ is said to be a subset of a set $B$ if and only if when $x$ is an element of $A$, then it is an element of $B$.

It may appear as though this definition isn't correct at first glance since we seemingly only mentioned one element - $x$ - in $A$. When stating definitions, mathematicians try to be as succinct as possible. The element $x$ is supposed to represent an arbitrary element in $A$, not a specific element and implicit in the statement is that we range over $x$. An alternative definition is as follows: A set $A$ is said to be a subset of $B$ if and only if all elements of $A$ are elements of $B.$

Minor definition: A set $A$ is a proper subset of $B$ if $A$ is a subset of $B$ and $A$ is not equal to $B$.

Question: Let $A$ be a set. Is $A$ a subset of itself? Why or why not? I will leave this to you to determine.

Before I mentioned something called the empty set. The empty set is exactly that: empty. It has no elements. The empty set is a subset of every set, and this will be shown later. There are multiple proofs of this claim, but the proof I intend to employ will rely on operations on sets we have not yet defined.

Operations on Sets

There are multiple operations on sets. Notable examples are union, intersection, complement and symmetric difference (this last one is important in abstract algebra). Union will be fairly similar to the logical disjunction from propositional logic and intersection akin to logical conjunction. For those who know more than basic logic, symmetric difference is akin to exclusive or.

Again the operations are easiest to see with examples first. Let $A = \{1, 2, 3, 4, 5\}$ and $B = \{3, 4, 6\}.$

The union of the two sets is the combination of the two without double counting common elements. So the union of $A$ and $B$ as above is then the set $\{1, 2, 3, 4, 5, 6\}$ (notice we did not double count). We could have double counted, but by convention we do not since sets only see membership, not frequency of occurrence.

The intersection of $A$ and $B$ is the set of elements they have in common; in this case, it gives the set $\{3, 4\}$. $3$ and $4$ are in both sets and are the only elements common to both, so these are the elements in the intersection of the two sets.

The relative complement is the weird one out of the bunch. Unlike the previous two, $A$ relative complement $B$ is not the same as $B$ relative complement $A$ in general (in mathematical terms, relative complement does not commute). Colloquially, $A$ relative complement $B$ is the set of the elements in $A$ which are not in $B$. In our case, it would be $\{1, 2, 5\}$ and $B$ relative complement $A$ is $\{6\}$.

Notation: The union of $A$ and $B$ is denoted by $A\cup B$. The intersection of $A$ and $B$ is denoted by $A\cap B$. The relative complement of $B$ in $A$ is denoted by $A\setminus B$.

There is one final major concept we must explore: the universal set. The universal set is the set from which you are drawing elements. Common examples include the integers or the real numbers. We have a notion of relative complement and we also have a notion of an absolute complement.

Definition: Let $R$ be your universal set and $A$ be a subset of $R$. The (absolute) complement of $A$ is the set of all elements in $R$ that are not in $A$. This is often written as $R\setminus A$ or $\bar{A}$ or even $A^c$. The barred and $^c$ notations are particular to absolute complement and are not used in relative complements.

Question: Let $R$ be a set. What is $R\setminus R$?

Answer: We know that $R\setminus A$ is the set of all elements in $R$ that are not in $A$. If $A = R$, then our result will be the set of all of the elements in $R$ which are not in $R$. There is not a single element that is both in $R$ and not in $R$ (as this would be a contradiction), so we conclude that $R\setminus R$ has no elements, i.e. $R\setminus R$ is the empty set. This makes sense since if you take all of the elements of $R$ out of $R$ you're left with nothing!

For the sake of keeping future posts short, I will end this post here. The next post will detail methods of proof concerning sets and some oddities that surround sets. Many strange results arise from infinite sets. Including (but not limited to) the fact that the integers have the same cardinality (think: size) as the natural numbers and that the irrational numbers far outnumber the rational numbers even though there are an infinite amount of both.

The Importance of Mathematics

This post is a change of pace and the mathematics included will be minimal. Before continuing with the first of multiple posts on set theory, I would like to explain the importance of mathematics and why you should study it (i.e., why you should continue to follow my blog!).

Since the dawn of mathematics, it has been used as a tool for understanding the natural world. Newton developed differential calculus in order to explain motion of moving bodies, differential equations have been used to study motion, population growth, and decay rates of materials, partial differential equations were used to study heat conduction in metals, the way waves propagate in media and the study of quantum mechanics. Mathematics is everywhere: in the fan circling above your head, in the satellites orbiting the Earth providing you with GPS navigation, in the warming body that we call the Sun. Each of these three topics will be treated in a physics blog I intend to create later down the road.

When grinding through a mathematics class, it is easy to miss the forest despite all of the trees. Sometimes you may feel inadequate as you are learning a new topic. It is imperative that you remind yourself that the world's best men had difficulty developing many topics you learn as an undergraduate. Mathematics was not built in a day. Newton and Leibniz developed calculus in the 1600s, but at the time calculus was considered mysterious. Newton's fluxions - as they were called - became what we call differentials (extremely small quantities); even the great Bishop Berkeley called these fluxions "ghosts of departed quantities" and many others felt similarly. Calculus was heavily used by mathematical physicists (called natural philosophers at the time), but some true mathematicians considered calculus incomplete or possibly incorrect. It was not until the 1800s that Weierstrass gave us our current definition of what a limit is. As you can see, it was not an easy task even for the best mathematicians at the time to make calculus a rigorous topic in its own right. The moral of the story is that in your courses you are learning potentially hundreds of years of mathematics in a very short period of time, so do not be discouraged.

Having said that, mathematics becomes more abstract from here. Mathematics is wonderful because it has the ability to explain, but is not limited to, the natural world. Some people believe all of mathematics will find its way into explaining the world around us and it certainly is true that much of mathematics has. I am unsure of whether or not all branches of mathematics will find its way into explaining the natural world, but it is an exciting concept!

In the near future, I will make a post concerning abstractions found in mathematics. The idea of a factorial can be extended, the ideas surrounding vectors (as you probably used in physics in high school) can be generalized and so can the concept of a length. You might ask: why generalize these ideas? At first generalization can seem unwarranted or perhaps even unnecessary, but many times these "unnecessary" generalizations are used when modeling something in the real world. The abstraction of vectors into vector spaces and length is hugely important in quantum mechanics (as will be covered in my physics blog).

On that note, I end this post. The upcoming topic of set theory is very rich and full of intrigue and mystery, concreteness and abstraction. Some of the arguments may be difficult to internalize at first, but I will try to make them as clear and understandable as possible. And in case I don't see you, good afternoon, good evening and goodnight.

Modes of Proof

To fully grasp mathematical arguments one must understand the underlying logic and proof structure. We have already given a fair treatment of the logic underlying mathematics, so we will now explore proofs. There are three varieties of proof: direct proofs, proofs by contradiction and proofs by mathematical induction. When to use each of the three changes from problem to problem, but often proofs by mathematical induction can be easily spotted. In the upcoming subsections I will give an account of each type of proof and give classical examples of each. For those who have taken an analysis class, these should be very familiar (in fact, you can probably guess which I will use).

DIRECT PROOFS

In a direct proof, one attempts to prove a proposition true from the basic assumptions stated within the proposition. An example of such a proof would be as follows. Show that the sum of two even integers is again an even integer*. We will prove this statement momentarily, but first we must first know what it means to say an integer is even. 

Definition: An integer, z, is even iff** it can be written in the form z = 2k for some integer k. (Equivalently, we say that z is divisible by 2.)

Definition: An integer, y, is odd iff it can be written in the form y = 2j + 1 for some integer j. (Equivalently, we can say that y is not even.)

Why do we choose to use this definition for evens and odds? For starters, it is very convenient notation. I will illustrate the definitions with examples. 2 = 2*1, 0 = 2*0, 4 = 2*2, and so on. The definition seems to make sense. How about the definition for the odds? 1 = 2*0 + 1, -1 = -1*2 + 1, 3 = 2*1 + 1, and so on. This definition seems to be consistent and logical as well. With this in mind, we can prove the aforementioned statement.

Example: Show the sum of two even integers is again even.

Proof: Let x and y be even integers. If x and y are even integers they can be written in the form x = 2j and y = 2k for some integers j and k. We wish to look at the sum of x and y, i.e.: x + y.

x + y = 2j + 2k = 2*(j + k). Because j and k are integers, their sum is again an integer*, call it m. Then, x + y = 2*m. Because m is an integer, 2*m is an even integer (by definition!), and therefore x + y is an even integer.

Q.E.D. (quod erat demonstrandum - Latin for "which was to be shown"). Q.E.D. has historically been used to signify the completion of proofs and I will adopt this convention as well. However, you can use whatever you wish to signify the end of your own proof.

In the realm of proofs this is among the simplest, but it is an instructive example. As you can see, we only used properties we already knew and what was given to arrive at the conclusion. In the next section we will see that the execution of a proof by contradiction is very different in setup.

PROOF BY CONTRADICTION

Proof by contradiction is a very powerful tool. The methodology outlining a proof by contradiction is as follows. Suppose you believe a proposition to be true, but a direct proof proved (hah!) fruitless. A possible avenue to explore would be a proof by contradiction. What you wish to do is assume that what you believe to be true is actually false and follow the steps of a direct proof. If at some point you reach a contradiction that logically followed from assuming your proposition was indeed false, then the only possible alternative is that what you actually set out to disprove is actually true (as you hoped!). 

The reason behind why a proof by contradiction is a valid mode of proof stems from the definition of a proposition. It can only be true or false and not both. If we arrive at a contradiction at some point in the proof (i.e. a proposition is true and false, like 2 is even and odd - obviously we know it is even), then we should be forced to reject that what we initially said was false (since it led to mathematical impossibilities) and accept that it was actually true.

A classic example if the proof that the square root of two is irrational. Before we delve into the proof, we must first understand what it means for a number to be irrational, and to understand this requires that we know what it means for a number to be rational.

Definition: A number is said to be rational iff it can be expressed as [; \frac{a}{b} ;], where a and b are integers (with b not being zero of course!). Examples would be [; \frac{1}{2} ;], [; \frac{-2}{3} ;], [; \frac{1}{1} ;], and so on. A follow-up question to this is: are all integers rational numbers? (I will leave this to you to consider.)

Definition: A number is said to be irrational iff it is not rational. Examples of irrational numbers you probably know are π, e (Euler's number), and φ (the golden ratio).

Before we show that the square root of two is irrational, we must establish an important fact: if a^2 is divisible by two (for some integer a) then a is divisible by two. This can be done by contradiction, in fact.

Proof: Take a^2 to be divisible by two to be true (i.e., a^2 is even). Assume that a is not divisible by two. If a is not divisible by two, then a = 2k + 1 for some integer k. a^2 then becomes 4k^2 + 4k + 1. Then, a^2 = 2(2k^2 + 2k) + 1. 2k^2 + 2k is an integer, call it y. Then, a^2 = 2y + 1, yet we said that odd integers were by definition of this form! This conflicts with our initial assumption that a^2 is even, so we conclude that if a^2 is even, a must be even.

Now we can begin our proof. We will assume that the square root of two is not irrational (i.e., it is rational). If the square root of two is rational, it can be written as the ratio of two integers a and b (again, b cannot be 0). Without loss of any generality, we will assume that a and b have no common divisors - and if they do, we will divide them out ahead of time.

[; \sqrt{2} = \frac{a}{b} ;]. Because it is impractical to work with square roots, we will square both sides of the equation to end up with:

[; 2 = \frac{a^2}{b^2} ;]. Again, this is not quite a practical form to work with, so we will multiply both sides by b^2 to obtain:

[; a^2 = 2b^2 ;]. We see that a^2 is an even integer, but from what we just proved, a must then be an even integer, so we will write a = 2a', for some integer a'. Substituting this expression for a into our previous expression yields

[; 4(a')^2 = 2b^2 ;] which yields [; b^2 = 2(a')^2 ;]. This says that b^2 is an even integer, therefore b must be an even integer as well, so we can write b = 2b' for some integer b'. At this point something weird seems to be going on. Both a and b were even integers, and therefore had a mutual divisor of 2, but we assumed that both a and b had no mutual divisors. At this point we have reached a contradiction: a and b have common divisors and they do not. From this and the previous reasoning, we conclude that our assumption that the square root of two is rational is false, and is therefore irrational (by definition).

We have been able to prove two statements about numbers with a direct proof and a proof by contradiction, however these two are not always efficient for proving a proposition is true, enter proof by mathematical induction. Problems provable with mathematical induction are very noticeable many times, as we shall see in the next section.

PROOF BY MATHEMATICAL INDUCTION

Mathematical induction can be used to prove formulas like

[; \sum_{i=1}^{n}i = \frac{n(n+1)}{2} ;] or [; \sum_{i=1}^{n}ar^i = \frac{a(1-r^{n+1})}{1-r} ;]

(if r does not equal 1). Even places where one might not guess it can be used it shows up, such as in the part of the proof of the Fundamental Theorem of Arithmetic (we will touch upon this later).

The first equation can be proved in multiple ways, but mathematical induction is the technique that will be employed here. (For those interested, a topic called finite calculus is of interest.)

Definition: The principle of mathematical induction: Let P(n) be a proposition for n in the positive integers. If P(1) is true and the truth of P(k) implies the truth of P(k+1), then P(n) is true for all positive integers n.

This definition seems odd and impossible to work with, but in fact is very useful as we shall observe in the following example.

Example: Show that [; \sum_{i=1}^n i = \frac{n(n+1)}{2} ;].

Proof by mathematical induction: Let P(n) be the proposition that [; \sum_{i=1}^n i = \frac{n(n+1)}{2} ;]. First we should check that it is a proposition. Either P(n) is true or it is false - the left- and right-hand sides cannot be "kind of" equal; either the left- and right-hand sides are equal or are not. There is no gray area. So it is a proposition.

We must check that P(1) is true. P(1) says [; \sum_{i=1}^1 i = \frac{1(1+1)}{2} ;], but we should check that this is the case.

The left-hand side (LHS, for short) is [; \sum_{i=1}^1 i = 1 ;]. The right-hand side (RHS, for short) is [; \frac{1(1+1)}{2} = 1 ;]. So indeed, the LHS = RHS and we conclude that P(1) is true.

Now we may continue onto the next step of a proof by induction: stating the inductive hypothesis. We will assume that P(k) is true (where k is a positive integer). P(k) says [; \sum_{i=1}^k i = \frac{k(k+1)}{2} ;]; this is called the inductive hypothesis. Now we will check whether P(k+1) is true or not (hint: the statement P(k) is necessary when showing P(k+1) is true! Otherwise, why would we bring it up in the first place?).

P(k+1) states that [; \sum_{i=1}^{k+1} i = \frac{(k+1)(k+2)}{2} ;], however we must check that this is true.

[; \sum_{i=1}^{k+1} i = \sum_{i=1}^k i + (k+1) ;].

From the inductive hypothesis, [; \sum_{i=1}^k i = \frac{k(k+1)}{2} ;], so we can rewrite the previous formula as:

[; \sum_{i=1}^{k+1} i = \frac{k(k+1)}{2} + (k+1) ;]. Combining both terms gives [; \sum_{i=1}^{k+1} i = \frac{(k+1)(k+2)}{2} ;], just as we predicted!

What happened was we assumed P(k) to be true and ended up with P(k+1) being true! We found that P(1) was true and the truth of P(k) implied the truth of P(k+1), therefore by the principle of mathematical induction, P(n) is true for all n in the positive integers. Q.E.D.

To further illustrate the idea behind mathematical induction, we will tackle another example. We will show that the sum of the consecutive (positive) integers is a perfect square.

Proof: Show [; \sum_{i=1}^n (2i - 1) = n^2 ;].

Let P(n) be the proposition [; \sum_{i=1}^n (2i - 1) = n^2 ;] for n in the positive integers. To begin we must check that P(1) is true.

P(1) states that [; \sum_{i=1}^1 (2i - 1) = 1^2 ;]. The LHS is [; \sum_{i=1}^1 (2i - 1) = 2\times 1 - 1 = 1 ;]. The RHS is [; 1^2 = 1 ;]. Indeed, the LHS = RHS and conclude that P(1) is true.

Now we make the inductive hypothesis. We will assume that P(k) is true and check the truth of P(k+1).

P(k) states [; \sum_{i=1}^k (2i - 1) = k^2 ;]. Now, P(k+1) states that [; \sum_{i=1}^{k+1} (2i - 1) = (k+1)^2 ;], but of course this needs to be shown.

Like before we will work with the sum on the LHS of P(k+1): [; \sum_{i=1}^{k+1} (2i - 1) = \sum_{i=1}^k (2i-1) + (2(k+1) - 1) ;]. We will make use of the inductive hypothesis and rewrite the RHS: [; \sum_{i=1}^{k+1} (2i - 1) = k^2 + 2k + 2 - 1 ;]. We can easily see that this is just (k+1)^2 in disguise. Since P(k+1) is also true, we conclude (by mathematical induction) that P(n) is true for all n in the positive integers. Q.E.D.

To get a feel of the underpinnings of the proof, one can write out the first several P(n)s:

[; 1 = 1 = 1^2 ;]

[; 1 + 3 = 4 = 2^2 ;]

[; 1 + 3 + 5 = 9 = 3^2 ;]

[; 1 + 3 + 5 + 7 = 16 = 4^2 ;] and so on.

The astute observer will note that we could have easily proven this based upon the result of the previous proof, but I felt as though this proof would have helped familiarize one with the structure and execution of a proof by induction.

Being able to do a proof by induction does not necessarily mean one understands the logic underlying the proof. The reason we state that our P(n) is true for all n (given certain conditions) based on P(1) being true and the truth of P(k) implying the truth of P(k+1) can be seen as follows:

If P(1) is true and the truth of P(k) implies the truth of P(k+1), then P(1) has to imply P(2) (just let k = 1!). And if P(2) is true (which we just showed it was!), then P(3) must be true since P(k) implies P(k+1), and if P(3) is true, then P(4) must be true, ad infinitum. So the two statements that P(1) is true and P(k) -> P(k+1) are enough to show that P(n) is true for all positive integers n.

Rick makes an excellent point in the comments below. The principle of mathematical induction can be extended to start at any integer and is called the Second Principle of Mathematical Induction (we have so far used the first). There is a stronger version of mathematical induction called the Complete Principle of Mathematical Induction, but we will encounter this later when proving part of the Fundamental Theorem of Arithmetic.

There is one final thing to note about proof: often it is easiest to disprove a proposition than it is to prove it. In mathematics we take the convention that if a proposition is false for any reason at all (even if it is only false in one case!) then it is completely false. There is no such thing as "kind of" false. This statement receives no partial credit (the horrors!). If you are able to find one case where the proposition breaks down and is false (or leads to a contradiction), then you have successfully disproven the proposition.

The next post will be a change of pace from tools of mathematics into our first real topic: set theory. Set theory is all over mathematics and there are many surprising and counter-intuitive results that arise from it. Sets will be separated into multiple posts as there is much to cover. The first post will cover introductory set theory (what sets are, how we combine them, and so on), the following post(s) will likely cover infinite sets and will reference some of Gregory Cantor's work.

* The integers are the numbers ... -3, -2, -1, 0 , 1, 2, 3, ... continuing on indefinitely in both directions.

** Iff is shorthand for "if and only if" (for those in-the-know, this is a biconditional statement).

Propositional Logic

All mathematical arguments boil down to "if p, then q" statements, such as if x is even, then x is divisible by two. It is therefore imperative that one understands propositional logic (the branch of mathematics that studies statements like "if p, then q") in order to fully comprehend mathematical arguments and proofs. Before we begin to study the elementary operations, such as ∧ (logical conjunction - also known as "and"), ∨ (logical disjunction - also known as "or"), and ¬ (negation), we must first describe propositions.


PROPOSITIONS


Definition: A proposition is a declarative statement that is either true or false, but not both.


An example of a proposition is: "Propositional logic is fundamental to mathematics." An example of a statement that is not a proposition is: "It may rain in New York City tomorrow." Why? The answer lies in the fact that it is not declarative; it is merely stated that it might rain in New York City tomorrow, but does not state definitively one way or the other.


Why must we include "but not both" in the definition of a proposition? The inclusion of this sentence fragment would lead one to think that there are statements that can be both true and false. An incredibly popular example of a statement that is both true and false is the statement "This statement is false."


Let's try to assign a truth value to this statement. If it is to be a proposition, then it is either true or false. Let's start by assigning a truth value of true to the statement. If the statement is true, then it must be false (because it said so!). So on one hand, the statement is true and yet it is false. Strange, but let's check if it is false. If it is false, it agrees with what we said, but if it agrees with it then it must be true!


It seems like there is no way to win with this statement! What we have invented is a self-contradicting statement. If it is true, then it must be false and if it is false, it must be true. We cannot assign a truth value to the statement; it can neither be true nor false. In order to perform meaningful logical arguments, we must avoid statements like these at all costs, else we will get nowhere. Hence the inclusion of "but not both" in the definition of a proposition.


Paradoxes are very interesting in and of themselves, but for now I will continue with propositions and logic. Another example of a proposition is: "The sum of the first n nonnegative integers is n(n+2)/2" (this statement is actually false). Again, this is a definitive statement and can only be true or false - either the formula holds or it does not. It is conceivable that the statement does hold true for some value of n, but if this statement is not true for all values of n, then it is false. So, in mathematics, we take the stance that a statement is only true if it is always true.


Now that we have an understanding of propositions, we can begin to formulate logical combinations of propositions using the elementary logical operations mentioned earlier.


LOGICAL OPERATIONS


We can combine propositions in different ways, such as: "It is Sunday and it is sunny outside", or "It is Saturday or Sunday", or "It is Saturday or Sunday but not Monday." Each of these three statements can be written using logical operations. Take, for example, "It is Sunday and it is sunny outside." We will represent the proposition "it is Sunday" by the symbol p and we will represent the proposition "it is sunny outside" by q. We would then write the compound proposition as p ∧ q.

NEGATION

The negation of a proposition means to take the truth value and reverse it. To be more clear, if your proposition is true, then the negation of the proposition is false; if the proposition is false, then the negation is true.

Take for example the proposition 1 = 2. 1 = 2 is false. The negation reads 1 ≠ 2 (the equality symbol with a slash through it represents not equal to). We know for a fact that 1 ≠ 2, so it is true. And this agrees with our statement that the negation swaps the truth value of the statement.

LOGICAL CONJUNCTION


The statement p ∧ q (read p and q) is defined to be true if and only if both p and q are true, otherwise it is false. This can be summarized in what is called a truth table, as seen below:

The first line reads, if p is true (T) and q is true (T), then p and q is true (T). Similarly, the second line reads if p is true and q is false, then the compound proposition p and q is false.


An example will help to illustrate the idea: Let p be the proposition that 1 = 1 and q be the proposition that 1 = 2. p and q says 1 = 1 and 1 = 2. Obviously this compound proposition is false. While 1 does indeed equal 1, 1 does not equal 2; by definition, the conjunction of two proposition is only true if both statements are true.


Another example is: Today is Friday and today is Sunday. Obviously, it cannot both be Friday and Sunday so we conclude that the proposition is false.


Another fundamental logical operation is disjunction, as we shall see in the next section.


LOGICAL DISJUNCTION


The proposition p ∨ q (read p or q) is defined to be true if at least one of the proposition is true. Alternatively, the proposition is only false if both are false. The truth table representing the logical disjunction is shown below:

As you can see, if either p or q is true, the truth value of p or q is true. The utility of truth tables becomes very apparent as they graphically represent the truth values of compound propositions. For simple compound propositions like p and q or p or q the utility isn't so apparent, however for complicated expressions, they are very useful (as we shall see later).

An example will help illustrate the idea behind the logical disjunction of two statements. Take our proposition to be 1 = 1 or 1 = 2. 1 = 1 is true, whereas 1 = 2 is not, yet because at least one is true, we say that the compound proposition is true.

With these three tools under our belt, we can finally discuss the most important logical operation: implication.

IMPLICATION

The statement p→q is a little odd at first and trips many students up the first time they encounter it and for good reason. While I defined the previous three logical operations before giving examples, I will present this with an example and then give the general statement. Take as our example the proposition: "If it is Sunday, I will go to the park." 

This is obviously a proposition, so it must (based upon the truth values of the propositional variables - the p and q) either be true or false. We will determine when the proposition is false and otherwise it must be true.

The only time this statement is false is if it is Sunday but I am not going to go to the park. The question to ask is: When can you call me a liar? (Meaning, when does the output not match the input?) You can only call me a liar if I do not go to the park on Sunday. In this case, the overall statement is false, but any other combination cannot be said to be false. Therefore all other cases must be true.

The truth table for implication then looks as follows:

TAUTOLOGIES

With this in mind, we will explore an important logical construct called a tautology.

Definition: A proposition is said to be a tautology if it is always true regardless of the truth values of its propositional variables. An important example is the statement p ∨ ¬p is a tautology. Unlike before, we only have two possible scenarios to check since ¬p is a function of p.

p has only two possible truth values, true or false. We will check both cases. If p is true, then ¬p is false. The disjunction of T and F is T. If p is false, then ¬p is true and the disjunction of these two again yields a truth value of T. So we conclude that regardless of the truth value of p, this statement is always true and is therefore a tautology.

There are many other tautologies to observe, but I do not wish to spend too much time on them, as there are many other topics left to cover.

LOGICAL EQUIVALENCE AND DE MORGAN'S LAWS

Two compound propositions are said to be logically equivalent if they have the same truth values for the same truth values of their propositional variables. Logical equivalence is denoted by p ≡ q.

An example are the compound propositions ¬(p ∨ q) and ¬p ∧ ¬q, as can be seen in the following truth tables:

This is actually an example of what is known as one of De Morgan's Laws. The other is of very similar form:  ¬(p ∧ q) and ¬p ∨ ¬q.  These are widely used in introductory electronics classes when breadboarding and are very helpful for reducing what could be considered messy Boolean algebra statements into very clean and concise ones.

For those interested, Boolean algebra is very interesting and can be used to implement basic circuitry. You can use logic to make cool programs!

This is the conclusion of propositional logic. The next blog post will be an introduction to set theory and proof. There are three main kinds of proof: direct, inductive and contradiction. Each has their own merits and drawbacks. Often times only one can be used to prove a statement and determining which to use can be tricky, but I will attempt to make recognizing which proof to start with easier. Many similarities between sets and propositional logic will arise, namely a similar formulation for De Morgan's Laws will be realized. This is part of a much deeper theorem concerning propositional logic and set theory and will be discussed later.