Foundations of Mathematics
Summer Program for High School Students
Columbia University, July 2001
Week #1 Notes -- Roger B. Blumberg
1. Introduction: We begin with a discussion of the syllabus and the course requirements, and what we'll be doing with this web site.
The primary goal of the course is to introduce varieties of mathematics, and mathematical approaches to questions, that you may not have encountered in elementary or secondary school. In the mathematics courses you've taken so far a great deal of emphasis has probably been placed on calculation (rather than proof), and mastering a small set of mathematical techniques (rather than seeing how different mathematical disciplines are related). This is only right, since you need basic mathematical skills (e.g. the ability to manipulate and solve equations) to do higher mathematics; but it also may have left you with too narrow a view of what mathematics is and how mathematics can be used.
There is a aspect of how we learn mathematics as children that is rather misleading, or at least confusing. Consider how we learn about Pi. First, we take measurements of the circle's circumference and diameter, and see that the ratio seems to approach a particular value; but shortly thereafter we are told that Pi is an irrational number, which therefore could not (by definition) be equal to the ratio of those actual measurements (no matter how careful you are). So let's ignore the terms rational and irrational for a moment and talk about patterns and proof, thinking of doing mathematics as most like playing a game.
What do we mean by "pattern" and "proof"?
Consider the following sequences, each of which contains six terms, and try to predict the next entry in each one:
In this kind of game, we are trying to detect a pattern expressed in the individual terms and/or in the relation between the terms. Once we detect a pattern, we might guess the next term in each sequence (the next terms are 221, 720, and 47, respectively); but, how are we to have confidence that our guess is correct and what is the difference between identifying a next term and identifying a pattern? In the case of a sequence, we often look for a pattern in the form of a function or mapping that will generate that sequence (and only that sequence). Finding such a function is considered a more powerful solution than merely guessing the next term, both because it allows us to predict not merely the next term in the sequence but any term (e.g. the 100th term) in the sequence, and because it deepens our understanding of the structure of the sequence itself.
Aside: I have put some terms in boldface, like "function" and "map", because you need to be familiar with them in order to really understand what I'm writing about here and will be discussing in class. If you are not sure what the terms in boldface mean (in their mathematical sense), I suggest you look them up in a mathematical dictionary or encyclopedia in the library, or use one of the on-line resources on our Reference Page. (If you know of other resources that you would like added to the Reference Page, please let me know.)
Of course there are patterns everywhere, not just in among numbers. We'll look at an example from literature, an excerpt from Georges Perec's novel, La disparition, followed by its English translation (titled A Void). Is there anything about the excerpt that strikes you as interesting, or different from other texts you've read? What is some of the differences between the way we talk about patterns in nature, in literature, and among numbers?
Although we cannot always apply mathematics to the patterns we find, we often use mathematics when we want both to identify patterns in systems of various sorts, and also to prove that the patterns we recognize are significant structural features of those systems.
2. What is an analytic solution?
In the following examples, we start by recognizing patterns and then consider how to prove that those patterns are an essential (rather than an accidental) feature of what we're looking at. In doing so, we want to understand what constitutes a mathematical solution to a problem, what it means to know that a solution to a problem exists and what it means to know that such a solution is unique (i.e. that there is only one true answer to the question).
Example 1: Consider an infinite sequence of integers, beginning with 2 and 3, and generated according to a simple single-digit multiplication rule that yields the sequence [1]:
If we calculate a few more terms, and start looking at the details of the sequence we notice that the numbers 9, 7, 5, and 0 do not seem to appear. Can we prove that they don't appear no matter how many terms we generate?
We find that we can rule out the appearance of 9s by recognizing that no two odd integers can appear next to each other in the sequence, and indeed because odd products are not possible (because the sequence begins with 2 and 3). From there we can easily rule out the appearance of the other terms.
During our discussion we found reason to prove that the product of two even numbers is always even, that the product of two odd numbers is always odd, and that the product of an even number and an odd number is always even.
What have we done in proving that this pattern was "real"? Or rather: have we done anything besides figuring out what is actually implied by the rule we are using to generate the sequence? Can we generalize our knowledge about what terms can and cannot appear to sequences generated with the same rule but beginning with different digits?
Although we're concerned here with mathematical solutions to different kinds of problems, the subject of integer sequences is fascinating all by itself, and could easily be the subject of a four-week mathematics course. For a glimpse into some of the wonders of integer sequences, try out Neil Sloane's On-Line Encyclopedia of Integer Sequences (at AT&T).
Example 2: Consider the infinite set of integers and the density of prime numbers as the numbers grow larger. Since the density of primes seems to decrease as the set we consider gets larger (e.g. compare the number of primes between 1-100 and between 1-1,000,000), we might be tempted to think that eventually we will no longer see any prime numbers, and that would mean that there must be a largest or greatest prime number (which in turn would mean that the set of primes is finite). Can we prove that there is or isn't a greatest prime?
Aside: Obviously, this is very different the question of how to find very large primes.
We first note that one of the ways primes play a role in working with integers is in factoring. That is, we find that all integers greater than 1 are either prime or products of primes. How do we know that this is true? Doesn't it come from just understanding what is meant by the terms "integer", "prime" and "factor"?
Armed with this knowledge, we consider whether there could be a greatest prime which, for the sake of argument, we'll call: p(g). Suppose such a number exists. If we suppose p(g) is the greatest prime number, we can define a new integer, z, by the equation:
But now let's look at the properties of this new number, z. Can we tell whether it is odd or even? Can we tell whether it is prime? (Hint: We can prove that every integer is either prime or the product of primes.) If z is prime then we have contradicted ourselves, since we originally said that p(g) was the greatest prime, and this new number is clearly greater than p(g). Does this contradiction prove there is no greatest prime?
Let's try another one (and ask ourselves what, if anything, these "proofs" we are doing have in common).
Example 3: If Pi wasn't the first number you learned was irrational then it was probably the square-root of 2. After being clear about the definitions of rational and irrational numbers, we come to the important question of how you can demonstrate that a particular number is irrational.
Once we recognize that part of the definition of a rational number is that it can be expressed as a ratio of integers in "most-reduced form," we have a way into a proof. Like the previous example, we will give what is called an indirect proof; just as we showed that assuming the existence of a greatest prime number led to a contradiction, we'll show that assuming the rationality of the square-root of 2 leads to a contradiction.
The strategy for the proof is to show that, if we assume that the square-root of 2 can be expressed as a ratio of integers, m/n, in a most-reduced form, we find that the numerator and denominator are both necessarily even, therefore contradicting the assumption that the ratio is in most reduced form.
What we show, in fact, is that the inability to find a ratio of two integers in most-reduced form equal to the square-root of 2 is analytic to the square-root of 2. That is, it is inherent in the meaning of the square-root of 2. Can we show that the square-root of 3 is irrational by a similar method?
But numbers are not the only domain in which this sort of game can be played.
Example 4: Consider a polygon of arbitrary size and shape (make it as complicated or simple as you like). Pretend further that the polygon represents an art gallery at your favorite (or least favorite) museum. A question raised by one of the great artists of this century, Paul Klee, was: For an arbitrary polygon-shaped gallery with n sides, how many guards will suffice if every area of the room must be visible to at least one guard at all times, and the guards are each stationary but can turn (in place) 360 degrees?
Here we should take some time to play around with the problem, both to see what was motivating Klee's question and just to see how extreme our polygons can be! Even without much playing, however, it's clear that a solution here probably won't be just a matter of setting up an equation. Rather, we have to figure out what we really mean by a polygon and what some of its properties are.
One remarkable property of any polygon is that it can be triangulated (i.e. turned into a patchwork of triangles). We may prove that this is true later in the course, but for now it seems so obvious that we'll take it for granted. Below is an picture of a polygon with 10 sides and beside it a picture of that same polygon triangulated.
Aside: If we triangulate a polygon with n vertices, how many triangles have we? And if we know that the number of triangles produced is (n-2), then what is the sum of the interior angles of the polygon? And you thought this course wouldn't be useful for those stupid multiple-choice exams you're always asked to take!
If every polygon can be triangulated, then every polygon is three-colorable. That is, with only three colors we can assign a color to each vertice so that no two adjacent vertices (i.e. vertices connected by a line in the triangulated polygon) are the same color. Again, we can prove this later, but for now we'll just talk about what we mean by a graph being colorable and assume the three-coloring of a triangulated polygon because it is so obvious.
A guard standing at one of the points of a triangle can see the entire interior of that triangle. So, if we station guards at the points of one particular color (e.g. the blue points), those guards can see the entire interior of the polygon. How many points of each color will there be? Well, it might vary, but certainly a whole number no greater than n/3.
The way to refer to the number we're talking about is the "floor" of n/3, or the greatest integer less than or equal to n/3, and this number of stationary guards which will always suffice to guard the room.
What do all of these examples, or "proofs" of solutions, have in common? And how does this notion of "proof" differ from how problems are solved in science, in medicine, in the study of history?
Now we move to two last examples, which will help us examine not just mathematical solutions to problems, but what it means to know how many different solutions there are.
Example 5: Suppose you are shopping for a two-door car at a very large used car lot, and the dealer tells you that he carries only two-door and four-door cars, and that he currently has in stock 5000 cars (I told you it was large) that have a total of 14000 doors. The dealer tells you that if you can tell him how many two-door cars he has in stock, he'll give you 25% off the price of whatever car you want.
This is sometimes called a "word problem," as in the puzzling but commonly heard sentence: "I can't do word problems."
Aside: This raises at least two interesting questions we won't deal with in this course: 1) What sorts of problems are not word problems (after all)?; and 2) What is it about these so-called word problems that gets people so upset? I welcome your theses and monographs concerning either or both of these questions.
The great mathematician and educator Geoge Polya, whose books How to Solve It and Mathematical Discovery: On Understanding, Learning and Teaching Problem Solving you should read someday, stressed that the key to word problems was understanding clearly the unknowns, the data and the conditions of the problem. Without this understanding, word problems are indeed a nightmare, so let's identify them in this problem.
Here the unknowns are clearly: the number of two-door cars (we'll call this unknown "x") and the number of four-door cars (we'll call this unknown "y"). What's the data? Well, what do we know? We know there are 5000 cars and 14000 doors. What is/are the condition(s)? We know that every car is either a two-door or a four-door; therefore, two equations immediately follow:
2x + 4y = 14000
The solution of the problem should be familiar to you from high school algebra (which I will assume you remember or will effectively pretend to remember for the purposes of this course); but now comes a trickier part: suppose the dealer says that while your answer is correct algebraicly, it is not the only correct answer. Furthermore, he says that it is not the answer that corresponds to how many two-door and four-door cars he actually has on the lot. Assuming you don't simply leave the dealership in disgust -- that's what I would do -- how would you explain to the dealer that there is only a single correct answer and you've found it?
Hint:
Would the problem have been more complicted if there were also 6-door cars in the lot?
a. What can you tell me about the numbers that will appear in a
sequence beginning with 6,7 and generated
using the rule we used in Session #1?
b. Can you prove that the square-root of 3 is irrational?
c. What is the sum of the interior angles of a polygon with 15 vertices?
d. Suppose you are in the snack business, and you want to make 50 pounds
of a mixture of
raisins and peanuts such that the mixture costs you 45 cents per pound.
Raisins cost you 35 cents per pound and peanuts cost you 60 cents per pound.
How many
pounds of raisins and how many pounds of peanuts should you use in the mix?
How would the answer change if you also put sunflower seeds in the mixture,
and they cost you 50 cents per pound?
e. What is the aesthetic, philosophical and/or political appeal of
mathematical modeling and mathematical/analytical solutions?
3. The 7 Bridges of Königsburg and beyond.
We start by considering ideas about why the problem apparently has no solution (i.e. why finding a path that crosses each bridge in Königsburg once and only once seems impossible), and why, by adjusting the number and/or configuration of bridges and islands other examples can be made to work. The question is whether the existence of a path that uses each bridge once and only once depends most on the number of islands, the number of bridges, or the particular arrangement of bridges on islands. We notice that whether a particular island has an even or an odd number of bridges attached to it seems to play a role in determining whether a successful path can be made from that island.
By looking at both successful and unsuccessful journeys, we realize that there is a simple rule correlating the number of bridges crossed and the number of times land is touched; namely,
While this may seem trivial, it makes clear that if we were to cross the 7 bridges of Königsberg successfully we would need to touch land exactly 8 times. This is helpful, since we can figure out how many times we need to touch each of the four pieces of land in order to use every bridge that is attached to it. Using a chart modeled after Euler's solution to the problem, we find that the sum of the numbers of times we will need to touch each body of land, in order to use up every bridge, is 9, and this "explains" why the 7 bridges of Königsberg has no solution. We can also use the chart to show that different configurations of the bridges and islands, that do allow for successful "once-and-only-once" paths, yield a sum that is equal to (the number of bridges + 1).
Now we want to generalize further, and get rid of the chart. Let's try to find a general solution to bridge problems of every kind. This is easier than it might seem because, given the problem we are trying to solve, there are really only three kinds of bridge problems: 1) problems in which all the islands have an even number of bridges attached; 2) problems in which all islands have an odd number of bridges attached; and 3) problems in which there are a mixture of islands with an odd number of bridges attached, and islands with an even number of bridges attached.
For the purposes of generalization, we first map our discussion into the theory of graphs, and we begin speaking about vertices (rather than islands), edges (rather than bridges), and degrees of vertices (rather than the number of bridges attached to each island). For example, the 7 Bridges of Königsberg problem can be represented as a 2-D (or "planar") graph:
Is it possible to trace this figure in a single stroke of a pen, such that every edges is drawn once and only once?
Now we consider the various classes of graphs, and try to solve the problem of whether there exists a path that uses each edge once and only once for the entire class:
Class 1: Graphs in which every vertice has an even degree.
Solution: Yes, there always exists such a path, and the vertice from which you
begin the path is where you will end up if you completed the path successfully.
Class 2 (first try): Graphs in which every vertice has an even degree, except for one vertice that has an odd degree.
One of the fascinating things about mathematics is the way it makes clear the distinction between things and/or states of affairs that can be described, and things and/or states of affairs that can exist. For example, while it is easy to say: "I'm thinking of an even prime number between 100 and 110," it is just as easy to show that such a number cannot exist. Here we find that while it is easy to say "I'm imagining a graph with only one vertice with odd degree," in fact no such graph can exist (at least given the our accepted meaning of "vertice" and "edge").
Aside: In any planar graph, the number of vertices with odd degree must be even. Can you prove it?
Class 2 (second try): Graphs in which every vertice has an even degree,
except for two vertices with odd degrees.
Solution: Yes, there always exists such a path, but it necessarily begins on
one of the vertices with odd degree and necessarily ends up on the other.
Class 3 : Graphs with more than two vertices with odd degree.
Solution: No, a path is never possible no matter it begins.
We have now solved the question of whether a "once-and-only-once" path exists, for all graphs. Euler generalized his analysis of the 7 Bridges problem even further, into both the domain of graph theory, and that of what we now call topology. For example, he was inspired by the Königsberg problem to find that, for any connected graph in a 2-D plane, the number of vertices, edges and regions carved by the graph was always the same:
In 3-D, Euler proved that the relationship between the vertices, edges and faces of regular polyhedra was always the same:
Aside: For an interesting (though pretty advanced) look at different ways to prove Euler's theorem, have a look at the Fifteen Proofs of Euler's V-E+F=2 pages at the Geometry Junkyard.
Finally, we can generalize these results in a different way, by noting different domains in which we might apply what we've learned about graphs. For example, suppose we consider a "society" as a group of individuals who are or are not friends with one another, where friendship is considered a mutual and 1:1 relation (i.e. a friendship can be represented by an edge). Given this fact, why does it follow that, in any closed society, the number of people with an odd number of friends is necessarily even?
4. How do the methods of establishing the truth of a statement in mathematics differ from the methods used to establish truth in other fields?
Having seen a few examples of mathematical statements and mathematical proof, consider the following statements drawn from various walks of life. Ask yourself: "Are these statements true?" and "Are there differences between the way I go about figuring out whether the statements are true?"
1. All bachelors are unmarried males.
2. 7 + 5 = 12
3. The earth revolves around the sun.
4. In the criminal justice system of the United States, a defendant is
presumed to be innocent until he or she is proven guilty.
5. Albany is the capital of New York State.
6. The square-root of 5 is an irrational number .
7. Table salt is a combination of sodium and chlorine.
8. Smoking cigarettes is hazardous to your health.
9. The product of two vectors can be used to measure whether or not they point
in the same direction.
10. The resurgence of religious fundamentalism in the United States has played
a large role in the recent rise in racism and violence in American society.
[1]The rule is: Multiply the first two digits and write their product as the next term, then multiply the second and third digits and write their product as the next term, and so on; but, if the product of two terms requires more than one digit to represent, then break it up into two terms, writing the digit in the "ten's place" first and the digit in the "one's place" second. For example, in the sequence, when we multiply 3 and 6 we get 18, so we write 1,8 as the next terms in the sequence.
