Sunday, December 16, 2012

Uncountable Infinity and The Diagonalization Method

Introduction


I took a class on Discrete Mathematics this past semester, and one of the topics we covered very briefly was the concept of countable and uncountable infinity. I didn't end up getting a great grasp on it, however, and the topic I'm writing about today didn't make a lick of sense to me at the time. It was never covered on exams, so I never had to revisit the idea. But, I've been reading through Douglas R. Hofstadter's Gödel, Escher, Bach, and it just so happens that the topic is covered in the book. As it turns out, it's not actually too difficult a thing to understand, so I'm hoping to relay the ideas in this blog post. If you've heard about the concept of multiple infinities but not understood it, hopefully this will shed some light! If you haven't yet heard about the concept of multiple infinities, enjoy the read!

Anyway, on with the show...

Natural Numbers Form an Infinite Set


It is a widely known fact (axiom of ZFC Set Theory) that the set of natural numbers (all non-negative integers) extends on to infinity. That is to say, there is no "largest" natural number. We can order the set of natural numbers in this way:

$$
\begin{matrix}
N_0 & = & 0 \cr
N_1 & = & 1 \cr
N_2 & = & 2 \cr
N_3 & = & 3 \cr
N_4 & = & 4 \cr
N_5 & = & 5 \cr
\cdots
\end{matrix}
$$
This ordering comes very naturally to us. The nth term of the set of natural numbers will be, simply, n. Because of this fact, we can tell that this set of natural numbers contains all of them -- if you give me any natural number, it will correspond to the nth number in the set.

There is a similar way of ordering the integers (including negatives) in this fashion. It may not be heavily intuitive at first, because we have to extend in two directions rather than one. But, it is apparent that this ordering of integers will allow us to find the location of any integer in it:

$$ \begin{matrix}
Z_0 & = & 0 \cr
Z_1 & = & 1 \cr
Z_2 & = & -1 \cr
Z_3 & = & 2 \cr
Z_4 & = & -2 \cr
Z_5 & = & 3 \cr
\cdots
\end{matrix}
$$
Any integer, positive or negative, is contained in this infinite set. An infinite set that can be ordered in a way such as this is said to be countably infinite.

What About Real Numbers?


For the purposes of this post, we're going to focus on the real numbers between 0 and 1. We can represent them in the following way:

$$
\begin{matrix}
R_0 & = & 0 . & a_0 & a_1 & a_2 & a_3 & a_4 & \cdots \cr
R_1 & = & 0 . & b_0 & b_1 & b_2 & b_3 & b_4 & \cdots \cr
R_2 & = & 0 . & c_0 & c_1 & c_2 & c_3 & c_4 & \cdots \cr
R_3 & = & 0 . & d_0 & d_1 & d_2 & d_3 & d_4 & \cdots \cr
\cdots
\end{matrix}
$$
We can see that this set goes on forever, that is, extends infinitely, just as the set of integers and naturals does. However, the set of real numbers is "built" in a different way. Both of these facts are important in what we will observe next.

Cantor's Diagonalization Method


I claim now that I can produce a number that the above set does not contain. To do this, I will be using Georg Cantor's famous Diagonalization Method. Here's how it works.

First, I will grab the $n$th term of each $n$th element in our set of real numbers to compose a new number, like so:

$$
\begin{matrix}
R_0 & = & 0 . & \color{red}{a_0} & a_1 & a_2 & a_3 & a_4 & \cdots \cr
R_1 & = & 0 . & b_0 & \color{red}{b_1} & b_2 & b_3 & b_4 &\cdots \cr
R_2 & = & 0 . & c_0 & c_1 & \color{red}{c_2} & c_3 & c_4 & \cdots \cr
R_3 & = & 0 . & d_0 & d_1 & d_2 & \color{red}{d_3} & d_4 & \cdots \cr
\cdots &&& &&&& \color{red}{\ddots}
\end{matrix}
$$
So my new number becomes:

$$
\begin{matrix}
0 . & a_0 & b_1 & c_2 & d_3 & \cdots
\end{matrix}
$$
Now I'm going to perform some transformation on each digit of this number to produce a new digit. A simple way (the simplest way?) to do this would just be to add 1 to each digit. This will produce a new number as follows:

$$
\begin{matrix}
M_0 & = & 0 . & a_0 + 1 & b_1 + 1 & c_2 + 1 & d_3 + 1 & \cdots
\end{matrix}
$$
We can see $M_0$ cannot be the same as $R_0$ because its first term differs. Same goes for $R_1$ with its second digit, and so on, ad infinitum. Therefore, each element of set of real numbers between 0 and 1 is going to differ from $M_0$ by at least one digit. We can conclude from this observation that our (infinite!) set of real numbers excludes $M_0$. That is to say, our set of real numbers between 0 and 1 isn't actually complete, and cannot actually be complete.

That last part, "cannot be complete," may sound confusing, because, why can't we just add $M_0$ to the set, and call it complete?

Well, let's do it! We'll tack on $M_0$ to the set to produce something like this:

$$
\begin{matrix}
M_0 & = & 0 . & a_0 & b_1 & c_2 & d_3 & e_4 & \cdots \cr
R_0 & = & 0 . & a_0 & a_1 & a_2 & a_3 & a_4 & \cdots \cr
R_1 & = & 0 . & b_0 & b_1 & b_2 & b_3 & b_4 & \cdots \cr
R_2 & = & 0 . & c_0 & c_1 & c_2 & c_3 & c_4 & \cdots \cr
R_3 & = & 0 . & d_0 & d_1 & d_2 & d_3 & d_4 & \cdots \cr
\cdots \cr\
\end{matrix}
$$
You might foresee what's going to happen next. We can perform diagonalization again:

$$
\begin{matrix}
M_0 & = & 0 . & \color{red}{a_0} & b_1 & c_2 & d_3 & e_4 & f_5 & \cdots \cr
R_0 & = & 0 . & a_0 & \color{red}{a_1} & a_2 & a_3 & a_4 & a_5 & \cdots \cr
R_1 & = & 0 . & b_0 & b_1 & \color{red}{b_2} & b_3 & b_4 & b_5 & \cdots \cr
R_2 & = & 0 . & c_0 & c_1 & c_2 & \color{red}{c_3} & c_4 & c_5 & \cdots \cr
R_3 & = & 0 . & d_0 & d_1 & d_2 & d_3 & \color{red}{d_4} & d_5 & \cdots \cr
\cdots & & & &&&&& \color{red}{\ddots} \cr
\end{matrix}
$$
...to produce a new number...

$$ \begin{matrix} 0. & a_0 & a_1 & b_2 & c_3 & d_4 & \cdots \end{matrix} $$
We perform some transformation on its elements (let's add one, again) in order to get a new number, say $M_1$.

$$ \begin{matrix} M_1 & = & 0. & a_0 + 1 & a_1 + 1 & b_2 + 1 & c_3 + 1& d_4 + 1 & \cdots \end{matrix}$$
However, note that $M_1$ must differ from $M_0$ now, as well as every other number in the set, by at least one digit. As such, $M_1$ must not yet exist in the set. We can add $M_1$ to the set, and repeat this process as many times as we want, but we'll always be able to produce a number outside of the set! We call a set with this fascinating property uncountably infinite.

What does this mean? We can see that the set of integers is countably infinite, while the set of real numbers between 0 and 1 is uncountably infinite. We have successfully proven in this blog post that there are actually more numbers between 0 and 1 than there are integers!

Cantor's Diagonalization Method has been used to prove several difficult problems in Mathematics, including the Church-Turing Theorem and Gödel's Incompleteness Theorems. All three of these theorems have had major effects on the nature of Mathematics, so you can see that Cantor's Diagonalization Method can be quite useful!

If you have any questions, or if anything was unclear, please leave a comment!

Until next time,

Ben

Thursday, December 6, 2012

Graphs and Topological Sorting in the Functional Paradigm

What is a Graph?

From Wikipedia
In mathematics, a graph is a representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges.
Simply put, a graph is just a bunch of points with links between them. A road map is a simple example: roads  being edges, and intersections being vertices.  In fact, Google maps uses graphs for just this purpose! Graphs are widely used in a wide variety of places. Facebook uses graphs to model your friend connections and likes. In fact, the entire internet is just a giant graph; websites act as vertices, with hyperlinks as edges. Graphs are highly useful structures, as they can be used to model many different types of situations, and as such, they will be the focus of this blog post. I am going to discuss one way to represent a graph in the Haskell programming language, and how to functionally solve a common problem using graphs.

Graphs are often represented visually like this:

Graph representing abstract data

This graph links the first six letters of the alphabet in an arbitrary way. This data doesn't really mean anything, but it will serve as a simple foray into the world of graphs, and provides an initial graph to work towards representing in Haskell.

Let's get right to it; here's the data structure we'll be using, along with some convenience methods:


First we define the actual Graph a data type: It's simply a set vertices and edges in the form of 2-tuples (The tuple (a, b) connects vertex a to vertex b), which fits our definition. I've also defined the removeEdge method, which does just what you'd expect. The outbound and inbound methods find the outbound and inbound connections to any point in the graph, respectively. They make use of the polymorphic connections method in order to get this done in a small amount of code. Finally, the Graph module exports the relevant functions at the top of the file.

Now that we've got our framework in order, we can go ahead and build the graph we mentioned above:



We import the Graph module and define a simple Letter data type, then build our Graph from it. The set of vertices are the letters A, B, C, D, E, and F, and the edges are modeled as above.

Now that we know how to build graphs, we can start modeling more important information with them.


Modeling Actual Scenarios using Graphs

Suppose some of the characters from NBC's Parks and Recreation have just finished competing in a dance competition, and we know the following about their rankings:

Leslie beat April.
April beat Ann.
Ron beat April.
Ron beat Ann.
April beat Andy.
Leslie beat Ron.
Andy beat Jerry.
Ron beat Andy.
Ann beat Jerry.
Leslie beat Andy.
Ann beat Andy.

This is a little hard to understand, so why don't we model it as a graph to make it a little more readable? Each person can be represented as a vertex, with outgoing edges representing connections to the people they beat.


A graph of dance competition results

It would be nice to be able to be able to read scenarios like this from a text file containing the important data and parse it into a graph. Let's go ahead and set up a function to do this for us, so we don't have to hard-code each and every graph that we want to use:

Here's our data file, with a list of space-separated connections, one on each line:




And our parsing function:


The graphFromFile function takes a String and returns an IO (Graph String).  The function reads a file, parses it into two important pieces: verts (the set of all unique strings in the file, or, our vertices) and conns (the set of connections between strings in the file). It then builds a Graph from this data, wraps it in the IO monad with return, and gives it back.

Now you might have been wondering from the beginning of this section what the ranking from the dance competition was (maybe you even figured it out on your own!). How do we do this programmatically, using our graph?

Enter Topological Sort

Again, from Wikipedia:
In computer science, a topological sort of a directed graph is a linear ordering of its vertices such that, for every edge uvu comes before v in the ordering.
In our case, this just means that each person must come before all of the people that he or she beat in the competition, in the ordering.

The basic procedure for topological sort is as follows:

L = {} --sorted list
S = Set of vertices with no incoming connections
while S is not empty:
    for each vertex v in S with no incoming connections:
        push v to L
        for each edge e from v to u:
            remove e from graph
            if u has no more incoming connections:
                push u to S

if edges still exist in the graph:
    error: there is at least one cycle in the graph

else return L

If you do not understand this, I urge you to work through topologically sorting a graph on paper first; it's not too tough to understand once you've done it on paper, but can get a little confusing in psuedocode.

The problem with this algorithm is that you see a ton of loops -- control structures that we do not have in Haskell. Therefore, we must rely on recursion, folds, and maps to achieve what we want to do. Here's how it looks:



Our tsort function first finds the elements in the graph with no incoming edges using the function noInbound.  We pass this into a sub-routine tsort' that takes a sorted list l, a list of vertices with no incoming connections (n:s), and a graph g.

We operate on the first element of the set of vertices with no incoming connections n, finding outEdges (the outgoing edges from n), and outNodes (the nodes that n points to). We build a new graph g' with the outEdges removed, and find the nodes in g' with no inbound connections, and add them to s.

We then recursively call tsort' with these new parameters (and prepend our current n to the sorted list), until there are no more nodes to check. At this point, if the edge list in the graph is empty, all is well and we return the list of sorted elements. Otherwise, an error is thrown stating that there is at least one cycle in the graph.

Now that we've got that, we're ready to find out how everyone ranked in the dance competition!



This produces the output:
["Leslie", "Ron", "April", "Ann", "Andy", "Jerry"]

(Of course Jerry lost.)

Conclusion

As you can see, Graphs are very useful data structures. They can be used to model a huge variety of things (see how many more you can come up with, they're everywhere!). Topological sort in particular is a pretty remarkable algorithm, and can be applied in many different situations from the one above. For example, finding paths through college courses with prerequisites. It's even used in UNIX systems to schedule processes according to their dependencies.

Hope you enjoyed the post! Until next time,

Ben