Infinity is a topic which is generally rather hard to grasp. Our world does not readily provide anything infinite for us to study in the Sciences. Indeed, if some structure was infinite, we would not be able to study it fully; indeed, we would not be able to find all its edges. It would have no shape, no measurable volume, no mass, energy or velocity which we would be in any way able to comprehend. And yet, in mathematics, the idea of infinity can actually have meaning, which shows that our imagination is not solely confined to the extent of our experiences. More than that, infinity can actually help us understand the finite physical, chemical, biological etc. structures with which scientists deal all the time. Infinity helps us understand sequences, which in turn helps in the understanding of limits, giving rise to the ideas of calculus, on which most contemporary Science and Engineering methods rely.
So, what is infinity? In general, we often treat it as a number. We may put it in the limits of a sum, a product or an integral, we may even give it as the result of these things. However, infinity is not, in fact a number. (This assertion is true in the reals. There are formal systems, like the hyperreal numbers, where infinity is a number. These systems are not what I am talking about here.)
Probably the most important work on infinity was done by Georg Cantor, when he formalised the ideas of infinite sets. Indeed, the best way to think of infinity is as a measure of the elements of an infinite set. As for finding such an infinite set, this is simple. We can simply take the positive integers (also known as the natural numbers), 1, 2, 3... and so on. We call this set N and consider the number of elements it contains. Obviously, it cannot be empty, as it contains the number 1. It cannot have only 1 element, as it contains the numbers 1 and 2. Similarly, it cannot contain only 100 elements, as every number from 1 to 101 is in N. For any positive integer we think of, we can find that many elements in N, and more. This is the very idea of infinity: something that is not bounded, which is larger than any number.
As we can see, this set of the natural numbers is infinite, in that it has infinitely many elements. Naturally, this means that any set which contains the natural numbers and others as well (a "superset" of N, as it is called) would also be of infinite size. We can take, for example, the set of all integers, Z. This includes the natural numbers (since they are the positive integers), as well as the negative integers and zero. Intuitively we can see that this must be a bigger set than N. Unfortunately, our intuition is wrong. When it comes to infinite sets, the only way to decide if Z is larger than N is to examine whether a bijection (one-to-one and onto function) exists between the two sets. If such a function can be found, then automatically the sets must have the same "size". Note that the natural numbers are essentially the numbers we count with, 1, 2, 3 and so on. So, finding a bijection between Z and N is the same as finding some way of listing all the elements of Z, without missing any, in a certain order. If such a sequence exists for Z, then Z and N have the same "size". This sequence is extremely easy to come up with: 0, 1, -1, 2, -2... and so on. Obviously this ordering will go through every single integer, much in the same way that 1, 2, 3... goes through every natural number.
The above shows us that Z has, in a sense, the same number of elements as N. Except that, as they both have infinitely many elements, we are not really talking about a number of elements. Because of this, the idea of cardinality was formulated. Cardinality can be thought of as the size of infinite sets, like the naturals or the integers. so, our example above shows that in fact both N and Z have the same cardinality, even if one is a subset of the other. This is a very important concept; infinity does not behave in the same way that other numbers do. Cutting infinity in half or doubling it does not actually change its size at all.
At this point one might think that all infinite sets must have the same cardinality as the natural numbers. After all, it should be easy to find a sequence that lists all the elements in a set. This is often the case; sets like the rational numbers, the algebraic numbers, the set of polynomials with integer coefficients and so on are certainly all countable (i.e. have the same cardinality as N). But there are sets which are actually much larger. The set of real numbers is actually uncountable. Any attempt to make a comprehensive list of all the reals, will result in failure. Indeed any such list can be shown to be missing some real numbers (in fact, an infinite amount of them). The proof for this uses a rather elegant method devised by Cantor, known as Cantor's diagonal argument.. I do not propose to present it here, as it is readily available online in other places. However, it should be clear from all this that the subject of cardinalities and the nature of infinity is one with a lot of substance.
Saturday, July 28, 2012
Wednesday, July 25, 2012
Group Theory
This post will assume some fundamental knowledge of Set Theory, as well as Functional Analysis. Only the basic ideas, e.g. what a set is, what functions are, what a bijection is, and so on are required.
Ideally, I should have titled this post "Algebra", however I hesitate to do this, as there are many misconceptions about what algebra actually is. In middle-school people learn it informally as equations with letters replacing some of the numbers. In fact, algebra is the study of relations between mathematical objects.
A group G is a set which has a built-in binary function, F(x, y). This function takes two elements from the set and returns one element from the set. This property is known as closure and is one of the requirements for a group. The other properties a group must have, with respect to its binary function are:
1) An identity element. This is an element e for which F(e, x) = F(x, e) = x. Think of this as the number 0, when we add integers. 0 + x = x + 0 = x, for any integer x. Note that the identity element is unique.
2) Inverses. Every element of the set must also have an inverse in the set. Two elements a and b are inverses of each other if F(a, b) = F(b, a) = e, where e is the identity. This is similar to the negative of a number. When adding integers, x + (-x) = (-x) + x = 0. Note that each element has a unique inverse. This includes the identity, which is its own inverse.
3) Associativity. Using the addition example, this means that (a + b) + c = a + (b + c). That is, the order in which the additions are carried out does not matter; whereas the order of the elements added does.
The last part may seem strange, in light of the addition example. After all, 2 + 3 = 3 + 2 = 5. The order is irrelevant! This is, in fact, not the case, with more general groups. For example, if we take the set of 2x2 matrices with non-zero determinant, under normal matrix multiplication, they form a group. But in this group AB is not equal to BA. The order of the elements added (or multiplied) matters in many groups. The groups for which a + b = b + a are known as abelian groups; the integers under addition are such a group.
Having read all these rather abstract notions which define a group, one may ask what the point of Group Theory is. Why should it be a field of study, when it seems so disconnected from anything which can relate to the experience of our senses? In fact, the same question could be asked of most high-level fields of Mathematics, and the answer will roughly be the same. There are in fact three reasons to study Group Theory, or indeed any sort of Mathematics. The first is because of the applications they have. With Group Theory these may not be readily apparent, however modern Physics, Chemistry and Cryptography rely on the study of Group Theory. The second reason is that we humans have a natural curiosity and a tendency to look for patterns. In many ways, the study of Mathematics in general and Algebra in particular is the study of patterns. The third reason is that mathematical study helps one develop a rational way of thinking. Abstracting problems into mathematical models is the only way which has been discovered so far, which is consistently successful in solving said problems.
Ideally, I should have titled this post "Algebra", however I hesitate to do this, as there are many misconceptions about what algebra actually is. In middle-school people learn it informally as equations with letters replacing some of the numbers. In fact, algebra is the study of relations between mathematical objects.
A group G is a set which has a built-in binary function, F(x, y). This function takes two elements from the set and returns one element from the set. This property is known as closure and is one of the requirements for a group. The other properties a group must have, with respect to its binary function are:
1) An identity element. This is an element e for which F(e, x) = F(x, e) = x. Think of this as the number 0, when we add integers. 0 + x = x + 0 = x, for any integer x. Note that the identity element is unique.
2) Inverses. Every element of the set must also have an inverse in the set. Two elements a and b are inverses of each other if F(a, b) = F(b, a) = e, where e is the identity. This is similar to the negative of a number. When adding integers, x + (-x) = (-x) + x = 0. Note that each element has a unique inverse. This includes the identity, which is its own inverse.
3) Associativity. Using the addition example, this means that (a + b) + c = a + (b + c). That is, the order in which the additions are carried out does not matter; whereas the order of the elements added does.
The last part may seem strange, in light of the addition example. After all, 2 + 3 = 3 + 2 = 5. The order is irrelevant! This is, in fact, not the case, with more general groups. For example, if we take the set of 2x2 matrices with non-zero determinant, under normal matrix multiplication, they form a group. But in this group AB is not equal to BA. The order of the elements added (or multiplied) matters in many groups. The groups for which a + b = b + a are known as abelian groups; the integers under addition are such a group.
Having read all these rather abstract notions which define a group, one may ask what the point of Group Theory is. Why should it be a field of study, when it seems so disconnected from anything which can relate to the experience of our senses? In fact, the same question could be asked of most high-level fields of Mathematics, and the answer will roughly be the same. There are in fact three reasons to study Group Theory, or indeed any sort of Mathematics. The first is because of the applications they have. With Group Theory these may not be readily apparent, however modern Physics, Chemistry and Cryptography rely on the study of Group Theory. The second reason is that we humans have a natural curiosity and a tendency to look for patterns. In many ways, the study of Mathematics in general and Algebra in particular is the study of patterns. The third reason is that mathematical study helps one develop a rational way of thinking. Abstracting problems into mathematical models is the only way which has been discovered so far, which is consistently successful in solving said problems.
Wednesday, June 13, 2012
Iteration and Chaos Theory
Obviously, this post will not be too involved, as the subject is an extremely deep one. In all probability, you have already heard about chaos theory, from some source of other. The idea, such as it was, may have been that, for example, a butterfly flapping its wings in the desert, can cause hurricanes, or something similar. As analogies go, it is a horrible one, since it is extremely obfuscated. The only way to understand what it is an analogy for, is to already know the thing it is an analogy for.
In fact, what the butterfly truism tells us is that, with some processes, a small change in the initial conditions can have a disproportionate, enormous effect on the results. It is not that a butterfly causes hurricanes; but if all the other necessary conditions are already there (within a specific distance of the equator, a sufficiently high temperature, a sufficiently low pressure, a large area of water), then a butterfly's flapping could be the catalyst which starts a process, which itself eventually pushes the system over the edge and causes the hurricane to emerge. In the same way, however, a butterfly's flapping wings could be the catalyst that slightly increases the air pressure and therefore stops a hurricane from appearing, instead.
The type of process studied by chaos theorists is known as a dynamic process. In general, one tries to find out the effect of taking a function and applying it to a successive sequence of inputs, each input generally being the previous output. As a very trivial example, we could take the function f(x) = 2x. If we start with some number for x, e.g. 3, and then each time we apply the function, we use the new result as our new x, we get the following sequence: 3, 6, 12, 24, 48, 96, 192 and so on. Clearly, the numbers in this sequence, will grow without limit. That is, the sequence goes to infinity, or diverges. If, instead, we start with x = 0, our sequence becomes 0, 0, 0 ... i.e. x never changes. The sequence is convergent. It is also fixed.
The process of applying the same function successively to its own outputs is known as iteration. The numbers 3 and 0, used as the initial values are known as the seeds for our iteration. 0 is also known as a fixed point of the function.
As we can easily see, unless x = 0, this function will diverge. This makes it simple to understand and therefore uninteresting. The same is true of a function like f(x) = x/2 where, for any seed we get convergence to the fixed point 0. However, there are functions which produce surprisingly unexpected results. These are known as chaotic functions. For example, we have the function f(x) = 1.25 - x^2. It has two fixed points, but beyond those, any conceivable seed between -2 and 2 will create a sequence that is simply unpredictable in its course. Naturally, the same is true of other types of functions.
As I mentioned, a chaotic function is interesting, because it is not simple to predict how it will behave over iteration. For example, it is not a simple matter to predict stock market fluctuations. This is partly because of the huge number of parametres involved, but also because of the chaotic nature of the processes involved.
In fact, what the butterfly truism tells us is that, with some processes, a small change in the initial conditions can have a disproportionate, enormous effect on the results. It is not that a butterfly causes hurricanes; but if all the other necessary conditions are already there (within a specific distance of the equator, a sufficiently high temperature, a sufficiently low pressure, a large area of water), then a butterfly's flapping could be the catalyst which starts a process, which itself eventually pushes the system over the edge and causes the hurricane to emerge. In the same way, however, a butterfly's flapping wings could be the catalyst that slightly increases the air pressure and therefore stops a hurricane from appearing, instead.
The type of process studied by chaos theorists is known as a dynamic process. In general, one tries to find out the effect of taking a function and applying it to a successive sequence of inputs, each input generally being the previous output. As a very trivial example, we could take the function f(x) = 2x. If we start with some number for x, e.g. 3, and then each time we apply the function, we use the new result as our new x, we get the following sequence: 3, 6, 12, 24, 48, 96, 192 and so on. Clearly, the numbers in this sequence, will grow without limit. That is, the sequence goes to infinity, or diverges. If, instead, we start with x = 0, our sequence becomes 0, 0, 0 ... i.e. x never changes. The sequence is convergent. It is also fixed.
The process of applying the same function successively to its own outputs is known as iteration. The numbers 3 and 0, used as the initial values are known as the seeds for our iteration. 0 is also known as a fixed point of the function.
As we can easily see, unless x = 0, this function will diverge. This makes it simple to understand and therefore uninteresting. The same is true of a function like f(x) = x/2 where, for any seed we get convergence to the fixed point 0. However, there are functions which produce surprisingly unexpected results. These are known as chaotic functions. For example, we have the function f(x) = 1.25 - x^2. It has two fixed points, but beyond those, any conceivable seed between -2 and 2 will create a sequence that is simply unpredictable in its course. Naturally, the same is true of other types of functions.
As I mentioned, a chaotic function is interesting, because it is not simple to predict how it will behave over iteration. For example, it is not a simple matter to predict stock market fluctuations. This is partly because of the huge number of parametres involved, but also because of the chaotic nature of the processes involved.
Saturday, May 26, 2012
Combinatorics
Combinatorics is usually one of the first non-introductory topics in discrete mathematics that students encounter in their mathematical studies. This also makes it one of the hardest topics to get to grips with, as it often requires a different way of thinking from other mathematical fields, such as calculus.
Combinatorics encompasses various subfields of study of discrete structures. In general, when given a problem in combinatorics, it will usually belong to one of three categories:
1) The existence problem. Given a problem, with specific characteristics and parametres, does a solution to this problem exist? For example, the dean's office at a college will want to assign time slots and classrooms to the various courses which will be taught in the semester. Such an assignment must not have two courses at the same time if the same professor is teaching them. (It is also usually desired that, if a lot of students are expected to take two courses concurrently, these courses not be assigned at the same time, if possible). Furthermore, if two courses are at the same time, they should not be assigned to the same room. Finally, if certain courses are expected to have large numbers of students, they should be assigned to large classrooms, so that everyone can have a seat. Given a list of courses, time slots and classrooms can such an arrangement be found? This is the existence problem. Sometimes there are no solutions to these problems. If, for example there is only one professor teaching both calculus and algebra, both classes needing the same single amphitheatre, and there is only one available time slot, the problem becomes impossible.
2) The counting problem. As mentioned before, some problems cannot be solved. Sometimes, on the other hand, a problem will have more than one possible solution. In our classroom assignment question, there could be several different assignments, which all work with the given parametres. The counting problem asks us to find how many different ways a problem can be solved. If there are two courses to be assigned to two different classrooms, at the same time, we can do this in two different ways; either have the first course in the first room and the second one in the second room, or vice versa.
3) The optimisation problem. Having figured out the different ways in which we can solve a given problem, we may then be interested in the best (whatever this means) solution out of the possible ones. For example, in the classroom assignment problem, we may want to pick the assignment that uses the fewest time slots, or the one that uses the fewest classrooms, or even the one with the fewest clashes between courses with common students. The optimisation problem is probably the most important one of the three, in the sense of solving applied problems, but it is often impossible to get started on, without a thorough understanding of the other two.
I will close this post by mentioning that the field of combinatorics is probably the largest one in mathematics, as it encompasses theory which is needed for almost all other mathematical fields. It would be impossible for a simple blog to present it properly, but perhaps in future posts, I may be able to present some of the more fundamental ideas.
Combinatorics encompasses various subfields of study of discrete structures. In general, when given a problem in combinatorics, it will usually belong to one of three categories:
1) The existence problem. Given a problem, with specific characteristics and parametres, does a solution to this problem exist? For example, the dean's office at a college will want to assign time slots and classrooms to the various courses which will be taught in the semester. Such an assignment must not have two courses at the same time if the same professor is teaching them. (It is also usually desired that, if a lot of students are expected to take two courses concurrently, these courses not be assigned at the same time, if possible). Furthermore, if two courses are at the same time, they should not be assigned to the same room. Finally, if certain courses are expected to have large numbers of students, they should be assigned to large classrooms, so that everyone can have a seat. Given a list of courses, time slots and classrooms can such an arrangement be found? This is the existence problem. Sometimes there are no solutions to these problems. If, for example there is only one professor teaching both calculus and algebra, both classes needing the same single amphitheatre, and there is only one available time slot, the problem becomes impossible.
2) The counting problem. As mentioned before, some problems cannot be solved. Sometimes, on the other hand, a problem will have more than one possible solution. In our classroom assignment question, there could be several different assignments, which all work with the given parametres. The counting problem asks us to find how many different ways a problem can be solved. If there are two courses to be assigned to two different classrooms, at the same time, we can do this in two different ways; either have the first course in the first room and the second one in the second room, or vice versa.
3) The optimisation problem. Having figured out the different ways in which we can solve a given problem, we may then be interested in the best (whatever this means) solution out of the possible ones. For example, in the classroom assignment problem, we may want to pick the assignment that uses the fewest time slots, or the one that uses the fewest classrooms, or even the one with the fewest clashes between courses with common students. The optimisation problem is probably the most important one of the three, in the sense of solving applied problems, but it is often impossible to get started on, without a thorough understanding of the other two.
I will close this post by mentioning that the field of combinatorics is probably the largest one in mathematics, as it encompasses theory which is needed for almost all other mathematical fields. It would be impossible for a simple blog to present it properly, but perhaps in future posts, I may be able to present some of the more fundamental ideas.
Sunday, April 29, 2012
Graph Theory
We come now to my own personal field of interest, the subject of graph theory. This has nothing to do with pie charts or bar graphs; these are a different kind of graph.
Formally, a graph is a special type of mathematical structure, composed of two parts. The first part is a set, a collection of distinct elements called vertices or nodes. The second is a collection of 2-tuples of the vertex set. These 2-tuples are the edges. Visually, we represent a graph as a network. The vertices are points and the edges are lines connecting these points. More specifically, we are usually interested in graphs with a finite vertex set and where the edges are distinct and connect distinct vertices. The networks we draw for these graphs will have at most one edge between two vertices and no loops on any single vertex.
Graph theorists are interested in many different characteristics of graphs. The reason these characteristics are studied is that there are many applications to real world problems which are more easily solved with graphs. For example, computer networks could not run smoothly and successfully without a proper understanding of graph theory, resource allocation problems become much harder to solve and so on and so forth.
The biggest problem for students learning graph theory is its apparent lack of connectivity to other mathematical topics. More often than not, students have a background that is (perhaps detrimentally) over-abundant in calculus (or rather, the techniques of calculus) and therefore lack a proper foundation in more fundamental branches of Mathematics, including set theory. This means that they will be bombarded with several new definitions and almost none of them will be present in their mathematical background; they will have no previous knowledge to draw upon, to help them understand these new topics. In this post (and hopefully future ones), I will attempt to give these definitions in a slower, more relaxed pace, than a graph theory course would require. Perhaps this method would be best suited for a two semester graph theory course, but that is neither here nor there.
We first consider the idea of measuring things about a graph. How large or small a graph is can depend on what we are using it for. The two most generals ways in which we measure graphs are the number of vertices it has (known as the order of the graph) and the number of edges it has (known as the size). For example, if you look at a map of, say, major motorways and represent these motorways as edges in a graph, the size of the graph will be the number of motorways you have. On the other hand, the order will be the number of destinations (cities for example) that are connected by these motorways. The order and size of a graph, give us an idea of how large our graph is. They also tell us other things, like how dense or sparse a graph is. For example, if a graph has 10 vertices, the largest number of edges it can possibly have is 45. If we have a graph with 10 vertices and only 15 edges, this could be considered a very sparse graph. If on the other hand it had 40 edges, this would be a very dense graph. The ideas of density and sparsity become more important when other measurements are made on graphs, but they're interesting enough on their own as well.
The next simplest definition we can give for graphs is that of adjacency. We say that two vertices are adjacent (or neighbouring), if there is an edge between them. That is, if we have an edge connecting the vertices u and v, then u and v are adjacent. We also say that v belongs in the neighbourhood of u (and vice-versa). In computer networking, if we take a graph of connections in a serve-client model, we could say that a server is adjacent to the clients it is connected to.
It is often the case that we want to know how many neighbours a vertex has (usually because we want to minimise them or maximise them). The number of neighbours of a vertex u, or the number of vertices adjacent to u, is denoted as d(u) and is known as the degree of u. Vertices with many neighbours will have a high degree. In the server-client model, the degree of each server is the number of clients it connects to.
Clearly, there are many more questions one can ask about graphs. (Is there a way to get from a certain vertex to another, following the edges between adjacent vertices? Is there a way to start at some vertex in a graph, and go through every edge exactly once, going sequentially through adjacent vertices? How many colours do we need to colour the countries of a map, so that no neighbouring countries share the same colour?) However, this post is a mere introduction to the idea of what a graph is, and will not delve any deeper into the theory. Perhaps in future posts, I will try to answer these and other questions about graphs.
Formally, a graph is a special type of mathematical structure, composed of two parts. The first part is a set, a collection of distinct elements called vertices or nodes. The second is a collection of 2-tuples of the vertex set. These 2-tuples are the edges. Visually, we represent a graph as a network. The vertices are points and the edges are lines connecting these points. More specifically, we are usually interested in graphs with a finite vertex set and where the edges are distinct and connect distinct vertices. The networks we draw for these graphs will have at most one edge between two vertices and no loops on any single vertex.
Graph theorists are interested in many different characteristics of graphs. The reason these characteristics are studied is that there are many applications to real world problems which are more easily solved with graphs. For example, computer networks could not run smoothly and successfully without a proper understanding of graph theory, resource allocation problems become much harder to solve and so on and so forth.
The biggest problem for students learning graph theory is its apparent lack of connectivity to other mathematical topics. More often than not, students have a background that is (perhaps detrimentally) over-abundant in calculus (or rather, the techniques of calculus) and therefore lack a proper foundation in more fundamental branches of Mathematics, including set theory. This means that they will be bombarded with several new definitions and almost none of them will be present in their mathematical background; they will have no previous knowledge to draw upon, to help them understand these new topics. In this post (and hopefully future ones), I will attempt to give these definitions in a slower, more relaxed pace, than a graph theory course would require. Perhaps this method would be best suited for a two semester graph theory course, but that is neither here nor there.
We first consider the idea of measuring things about a graph. How large or small a graph is can depend on what we are using it for. The two most generals ways in which we measure graphs are the number of vertices it has (known as the order of the graph) and the number of edges it has (known as the size). For example, if you look at a map of, say, major motorways and represent these motorways as edges in a graph, the size of the graph will be the number of motorways you have. On the other hand, the order will be the number of destinations (cities for example) that are connected by these motorways. The order and size of a graph, give us an idea of how large our graph is. They also tell us other things, like how dense or sparse a graph is. For example, if a graph has 10 vertices, the largest number of edges it can possibly have is 45. If we have a graph with 10 vertices and only 15 edges, this could be considered a very sparse graph. If on the other hand it had 40 edges, this would be a very dense graph. The ideas of density and sparsity become more important when other measurements are made on graphs, but they're interesting enough on their own as well.
The next simplest definition we can give for graphs is that of adjacency. We say that two vertices are adjacent (or neighbouring), if there is an edge between them. That is, if we have an edge connecting the vertices u and v, then u and v are adjacent. We also say that v belongs in the neighbourhood of u (and vice-versa). In computer networking, if we take a graph of connections in a serve-client model, we could say that a server is adjacent to the clients it is connected to.
It is often the case that we want to know how many neighbours a vertex has (usually because we want to minimise them or maximise them). The number of neighbours of a vertex u, or the number of vertices adjacent to u, is denoted as d(u) and is known as the degree of u. Vertices with many neighbours will have a high degree. In the server-client model, the degree of each server is the number of clients it connects to.
Clearly, there are many more questions one can ask about graphs. (Is there a way to get from a certain vertex to another, following the edges between adjacent vertices? Is there a way to start at some vertex in a graph, and go through every edge exactly once, going sequentially through adjacent vertices? How many colours do we need to colour the countries of a map, so that no neighbouring countries share the same colour?) However, this post is a mere introduction to the idea of what a graph is, and will not delve any deeper into the theory. Perhaps in future posts, I will try to answer these and other questions about graphs.