Perhaps the most fundamental question about Mathematics, as well as the one least explored by mathematicians is the nature of Mathematics. That is, how exactly can one define Mathematics as a field, properly and rigorously? We have rather good definitions about most fields of study. Chemistry is the study of the composition of matter, Biology is the study of living organisms, Medical Science is the study of disease and Sociology is the study of human societies. Mathematics, on the other hand, is a far more difficult field to encapsulate in a simple description like that.
To illustrate this difficulty, consider any simple definition of Mathematics. It cannot be the study of numbers and quantities, since the most fundamental fields of Mathematics (such as Set Theory, Group Theory, Logic and Proof Theory) rarely have much to do with these concepts. Similarly, it cannot be the study of proofs, since application of knowledge, rather than its formulation, is a very large part of Mathematics. Mathematics can be wholly taught without any symbols, but it can also be taught with only symbols. It is both conceptual and descriptive, both theoretical and applied.
So, what is Mathematics? As noted above, a simple definition as a field of study is hard to come up with. But perhaps Mathematics is not a field of study at all. Once we consider this idea, new possibilities arise. Mathematics is, in fact, a philosophy and a way of thinking. It is logic and inference, applied to any abstract or concrete structure, including numbers and quantities. It is the formulation and usage of knowledge about such structures, in a formal language which is shared by all mathematicians. In the end, it is the fruit of all curiosity. Whenever any field is studied in a formal and precise way, whenever a pattern is being sought out and described, whenever new knowledge is sought and created, the methods used are mathematical in nature.
Naturally, the above is too general a definition for a classroom subject; mathematical education is generally far less ambitious in its scope. But next time you are taking a course in Mathematics, or encounter a mathematical question, think of it as a chance for you to learn a new way of thinking; you may enjoy it, despite the amount of apparently irrelevant theory.
Thursday, May 23, 2013
Thursday, March 28, 2013
Graph Theory (III)
One of the largest topics within Graph Theory is that of Graph Colouring. Formally, a proper graph colouring is an assignment of labels, or "colours" to the vertices of a graph, so that no adjacent vertices share the same colour. The chromatic number of a graph is the smallest number of such labels that can be used to properly colour it. Consider the following assignment problem: A university has to offer certain classes in the next semester. Each specific class will be taught by a specific professor and at a specific time-slot in the day. Naturally, this means that two classes taught by the same professor, must not be offered at the same time; he can not be in two places at once. Furthermore, each class will have specific students who wish to take it. This means that if two classes will be taken by the same student, they also cannot be offered at the same time. The question then becomes, how can we assign the classes? What is the minimum number of time-slots that the university will need to use, to offer all its classes?
This question can be answered by using the idea of Graph Colouring. We draw a graph, as follows: The different classes to be offered, will be our vertices. The classes that cannot be offered together, either because they are taught by the same professor, or because they share a student, are connected together. Then, the given problem is simplified to finding a proper colouring of the graph, where the labels used will represent the time-slots. And, of course, if we want the smallest number of time-slots needed, we must find the chromatic number of the graph.
In practice, this sort of problem is far more complex, as it takes into account multiple sections, classroom availability, number of students expected to need the course and so forth. Also, the restriction on classes sharing a student is generally changed to a restriction on classes expected to share a significant number of students and only offered as single sections. Nevertheless, all problems of resource assignment can be represented as graph colouring problems. In addition to this, many other problems can be studied via Graph Colouring, particularly the all-important class of NP-Complete problems.
The name "colouring" originates in a rather old question: Given a map of a region, how many colours are needed to colour it, if no two adjacent regions (i.e. regions sharing a border) can have the same colour? The surprising answer is "no more than four". The proof for this is extremely long and complicated, which tells us that the field of Graph Colouring is a very deep one indeed.
This question can be answered by using the idea of Graph Colouring. We draw a graph, as follows: The different classes to be offered, will be our vertices. The classes that cannot be offered together, either because they are taught by the same professor, or because they share a student, are connected together. Then, the given problem is simplified to finding a proper colouring of the graph, where the labels used will represent the time-slots. And, of course, if we want the smallest number of time-slots needed, we must find the chromatic number of the graph.
In practice, this sort of problem is far more complex, as it takes into account multiple sections, classroom availability, number of students expected to need the course and so forth. Also, the restriction on classes sharing a student is generally changed to a restriction on classes expected to share a significant number of students and only offered as single sections. Nevertheless, all problems of resource assignment can be represented as graph colouring problems. In addition to this, many other problems can be studied via Graph Colouring, particularly the all-important class of NP-Complete problems.
The name "colouring" originates in a rather old question: Given a map of a region, how many colours are needed to colour it, if no two adjacent regions (i.e. regions sharing a border) can have the same colour? The surprising answer is "no more than four". The proof for this is extremely long and complicated, which tells us that the field of Graph Colouring is a very deep one indeed.
Thursday, January 31, 2013
Creative Thinking
The title of this post may not seem particularly related to Mathematics. Creativity, some might say, is limited to the world of Art. Mathematics, they may continue, is about using specific sets of tools, to solve problems, mechanically. Unfortunately, because of the way that arithmetic and Mathematics in general are taught in schools, this does seem to be the case. But, in reality, it could not be further from the truth.
Consider the following problem: 87 contestants are taking part in a knock-out tournament (perhaps in tennis, or chess; the specifics are irrelevant). The first round, will consist of 23 matches and 41 'byes'. That is, 41 contestants will move to the next round without a match and the remaining 46 will have their elimination matches (why 41 byes?). Then, the tournament will continue normally, with no more byes. How many matches will take place, before the champion can be declared?
This problem can be solved in a few different ways. The mechanical method would be to simply count the number of matches. The first round will have 23 matches. Then 64 players will remain. They will have a total of 32 matches in the second round. Continuing in this way, we find that the total number of matches needed is 23 + 32 + 16... + 1. But there is a more elegant and creative method to find the answer. There are 87 contestants. We can ignore the information on byes and so on. Each match will eliminate exactly one contestant. We need only one contestant to remain. So, 87 - 1 = 86 matches will be required. (This is also the answer we get by adding the number of matches in each round). This second method, is undeniably better. It is simpler, shorter and less prone to error from bad computation. That is where creativity enters the realm of Mathematics. It is often possible to solve a problem in many different ways. But some ways are clearly more creative than others.
The problem with this is that creativity cannot be taught. There is no way of knowing in advance which method will be most suitable to solving a specific problem. A good fundamental knowledge of many different methods can often give one a good idea of how to proceed, but again, this takes personal practice. A student needs to solve many problems, before they are fully familiar with a specific method. Unfortunately, this does not, generally, happen. School systems being what they are, do not create a setting whereby students are required to work through enough problems, to understand the concepts behind them. Worse, the students' natural curiosity for these things is not nurtured enough, for them to want to learn such things.
Consider the following problem: 87 contestants are taking part in a knock-out tournament (perhaps in tennis, or chess; the specifics are irrelevant). The first round, will consist of 23 matches and 41 'byes'. That is, 41 contestants will move to the next round without a match and the remaining 46 will have their elimination matches (why 41 byes?). Then, the tournament will continue normally, with no more byes. How many matches will take place, before the champion can be declared?
This problem can be solved in a few different ways. The mechanical method would be to simply count the number of matches. The first round will have 23 matches. Then 64 players will remain. They will have a total of 32 matches in the second round. Continuing in this way, we find that the total number of matches needed is 23 + 32 + 16... + 1. But there is a more elegant and creative method to find the answer. There are 87 contestants. We can ignore the information on byes and so on. Each match will eliminate exactly one contestant. We need only one contestant to remain. So, 87 - 1 = 86 matches will be required. (This is also the answer we get by adding the number of matches in each round). This second method, is undeniably better. It is simpler, shorter and less prone to error from bad computation. That is where creativity enters the realm of Mathematics. It is often possible to solve a problem in many different ways. But some ways are clearly more creative than others.
The problem with this is that creativity cannot be taught. There is no way of knowing in advance which method will be most suitable to solving a specific problem. A good fundamental knowledge of many different methods can often give one a good idea of how to proceed, but again, this takes personal practice. A student needs to solve many problems, before they are fully familiar with a specific method. Unfortunately, this does not, generally, happen. School systems being what they are, do not create a setting whereby students are required to work through enough problems, to understand the concepts behind them. Worse, the students' natural curiosity for these things is not nurtured enough, for them to want to learn such things.