yellowpigs.net

Appendix A

The Square Root of 2

In order to do mathematics it is important to understand the idea behind proofs and how to construct them. I have chosen to demonstrate a proof that the square root of 2 is irrational.

This may not seem to be an important result, but it was to the Greeks, who were horrified by the idea of irrational, or illogical, numbers. The existence of such numbers conflicted with their concept of numbers as ratios. The Pythagoreans believed in a link between number, the soul, and the universe. Thus, the illogical in numbers implied the illogical in the universe and a disruption of harmony in the soul. This was hardly something to be taken lightly. Ultimately, however, they had to accept the irrational numbers because they proved that some numbers could not be represented by ratios.

What is a proof? A proof is a step-by-step justification of a statement. But, says Ian Stewart, it is more than this:

Textbooks of mathematical logic say that a proof is a sequence of statements, each of which either follows from the previous statements in the sequence or from agreed axioms - unproved but explicitly stated assumptions that in effect define the area of mathematics being studied. This is about as informative as describing a novel as a sequence of sentences, each of which either sets up an agreed context or follows credibly from previous sentences. Both definitions miss the essential point: that both a proof and a novel must tell an interesting story (Stewart, Nature's Numbers, 39).

And so we end with a proof - a mathematically rigorous story. The proof that ÷2 is irrational is fairly straightforward and serves as a good example of a proof. It is what mathematicians call an elegant or beautiful proof. Beauty is of the utmost importance to mathematicians; as Godfrey H. Hardy said, ``Beauty is the first test: there is no place in the world for ugly mathematics.''

The first step in a proof is to state precisely what is to be proven.

Theorem: The number ÷2 is irrational.

What does this mean? Irrational numbers are, by definition, those which are not rational. Rational numbers are fractions. Any number which can be written as the ratio between two integers is a rational number. An irrational number, then, is a number which cannot be written in the form ^p/_q.

Proofs are puzzles, and a good puzzle solver has several tricks and tactics for solving puzzles. A mathematician doesn't rely only on these techniques but uses them as tools to tackle a problem. To prove a statement, it must follow as the logical conclusion from a series of valid premises and inferences. In our proof the premises are the axioms. If the premises are the pieces of a puzzle, the inferences are the way these pieces fit together. A mathematician knows how to put the pieces together, using standard methods such as induction, the pigeonhole principle, and reduction. It is sometimes difficult to know which method to use and how to begin approaching a problem.

We will use the method of contradiction. This method stems from a form in logic known as modus tollens, which states that ``if A implies B, then not-B implies not-A.'' Our theorem reads: ``If x = ÷2, then x is irrational.'' The reversal, or contrapositive, is ``If x is rational, then x cannot be ÷2.'' The idea behind a proof by contradiction is to begin with an assumption that negates the desired conclusion. When absurd statements that contradict the real hypothesis follow from this assumption, mathematicians can conclude that because impossible, or contradictory, conclusions follow, the assumption must be invalid. Then, the original hypothesis must lead to the original conclusion. This approach is like playing a game of make-believe. We pretend that instead of wanting to prove our theorem, we want to disprove it. For our theorem, we start out by considering that x is, in fact, rational, and we want to show that because x is rational, x cannot equal ÷2.

We begin our proof:

Proof: Suppose our theorem is false. That is, suppose ÷2 is rational.

We know that a rational number can be written as ^p/_q where p and q are integers. In fact, any rational number can be written not only as a fraction, but as a fraction in lowest terms. This means that it can be written so that the numerator and the denominator have no common factors. We should be convinced that statement is true, because given any fraction representation for a number, we can write the fraction in lowest terms by dividing out common factors. In a proof it is important to question and verify everything. A proof with gaps, falsities, or vagaries is open to failure. We continue our proof:

We write ÷2 = ^p/_q, where p and q are integers with no common factors greater than 1.

Now we have an equation on which we can perform simple algebra.

From which it follows by multiplication by q that ÷2q = p, and by squaring both sides, that 2q² = p².

What do we know about this quantity that is represented on both sides of the equation? We know that it is an integer and that it is even because 2q² is a multiple of 2.

Thus, p² is an even number.

Does anything follow from this? Can we determine anything about p? It turns out that we can. If p² is even, then p must be even as well. We can convince ourselves that the statement is true by considering several examples. The number 2 is even; 2² = 4 which is even. Another even square number is 16; the square root of 16 is 4 which is even. On the other hand, 25 is an odd square number and its square root, 5, is not even. Concrete examples often help to make generalizations easier to internalize. To be certain that this is true, we consider the generic even case 2n and the generic odd case 2n+1. The square of 2n is 4n², which is even, and the square of 2n+1 is 4n²+4n+1, which is odd.

And so p must be even.

At the beginning of our proof we used the fact that any rational number can be written in the form ^a/_b. Again, we find it useful to write an equation for p which tells us something about it. To say that a number is even means that it is divisible by 2, so it is true that p = 2a for some integer a.

We write p = 2a.

Now we substitute 2a where we previously had p, so the equation 2q² = p² becomes 2q² = (2a)². We can simplify this to 2q² = 4a² or q² = 2a².

By substitution, 2q² = (2a)² or q² = 2a².

Notice how similar this equation q² = 2a² looks to our earlier 2q² = p². We can apply the same logic as before to conclude that since 2a² is even, q² is even, and q is also even.

Just as before, we see that q is even.

Let's look again at precisely what we assumed. We started out by supposing that we could write ÷2 = ^p/_q, for some p and q with no common factors. But - this is the part that's key to the idea of contradiction - we have shown that p is even and that q is even. That means that both p and q are divisible by 2; 2 is a common factor of p and q. Oh no! That's a contradiction. We said that p and q didn't have any common factors, and we showed that our assumptions imply that they do.

Both p and q are even numbers, so they are both divisible by 2. This contradicts the assumption that p and q have no common factors.

Our assumption has been shown to be invalid. It falls to the ground with the big, loud thump of its own absurdity. We now know that we can't write ÷2 as ^p/_q, where p and q have no common factors. And that's what it means to say that ÷2 is rational.

So our assumption that ÷2 is rational is false. Then, ÷2 is irrational, which is what we wanted to prove.

At the end of proofs, mathematicians often write Q.E.D., an abbreviation for quod erat demonstrandum, which is Latin for ``which was to be demonstrated.''

Q.E.D.

Appendix B

Cantor and Infinity

The Yellow Pig introduces Alice to cardinality, and to rational and irrational numbers. He tells her that there are no more rational numbers than there are integers or natural numbers, but he does not tell her that there are more real numbers than rationals, so many more that the real numbers cannot be listed. The proof of this fact - credited to Georg Cantor - relies on the techniques of contradiction and enumeration. Suppose we do have a list with all of the real numbers. Or, for the sake of making a ``shorter'' list, suppose we have a list with just all of the real numbers between 0 and 1. This would be a sublist of our list of all real numbers.

We consider such a list. (Actually, we consider only the representations of reals between 0 and 1 that do not contain any 9's as digits. We must be careful because 0.99999 ... is equal to 1. This is the only way for two different decimals to represent the same real number. It is okay for us to be looking at representations of such a subset of the real numbers, because we need only to show that this subset cannot be listed to conclude that all of the reals cannot be listed.)

The list could begin like this:

To show that this list does not contain all of the reals between 0 and 1, we need to find a real number which is not already on the list. Cantor outlines a method for doing precisely this. We consider the digits along the diagonal.

Now, we look at the second number in the list. Again, we want to insure that our new number is different from this number. We see that the second digit to the right of the decimal place is a 2, so we can tack a 3 on after the 1 in our new number. Again for the third number in our list, we consider the third digit, 6. The third digit of our new number can be 7. And so on for all of the numbers in our list. Our new number might begin 0.13721 ....

This completely outlines one procedure for constructing a ``new'' number; that is, the nth place in the new number is 1 more than the n place in the nth number, unless the nth place in the nth number is 8, in which case the nth place in the new number is 0. Now, we just need to be certain that this number is not already on the list. But (if each representation is unique) how could it be? We constructed it to differ in the nth place from the nth number, so it must be different from all of the numbers in the list!

We conclude that we can't list all of the real numbers. There are infinitely many rational numbers, but there are even more reals - uncountably many.

To be more mathematically precise, we say that the cardinality of the set of real numbers is greater than that of the set of the rationals. What does cardinality mean? One way to look at cardinality is to consider correspondences between two sets. We say the cardinality of two sets is the same if there is a one-to-one correspondence, or bijection between elements of the two sets. Cantor proposed to call two sets equipollent if there exists such a correspondence between them. This terminology is useful because it allows us to distinguish various kinds of infinity.

A set D is denumerable or countable if there exists a bijection with the natural numbers. It is true that any subset of a denumerable set is denumerable, that the product of denumerable sets is denumerable, and that the set of finite subsets of a denumerable set is denumerable. Similarly, R, the set of the reals, and the set of finite subsets of R are equipollent. So, is there any set with greater cardinality than R? The answer is yes.

Given a set, there always exists another set whose cardinality is greater. Just as the collection of all subsets - not just finite subsets - of the natural numbers is not countable, the set of all subsets of the reals has a greater cardinality than that of the reals. There is no set with greatest cardinality. We can always create a set with greater cardinality than a set S by taking the set of all subsets of S.

Onward to another question: Are there any sets with cardinality greater than that of the natural numbers but less than that of the real numbers? When does infinity cease to be countable or denumerable? The result of this tricky question has been stated as the Continuum Hypothesis: Every infinite subset of the reals is equipollent with either the naturals or the reals.

Is this hypothesis true? There is no proof or disproof. I do not mean that no proof or disproof has been found; there is a proof that there can be no proof or disproof of this statement. In 1938 Kurt Gödel showed that the Continuum Hypothesis is both irrefutable and unprovable. This means that there is a problem in mathematics for which mathematics is at a loss to solve.

A paradox is a statement that cannot be either true or false. For example, if the statement ``This sentence is false'' is considered true, then it must be false. But if it is false, then it is true that ``This sentence is false,'' and this process continues. Just as ``This sentence is false'' is paradoxical, some problems in mathematics are undecidable. At the beginning of the twentieth century, David Hilbert and most mathematicians believed ``true'' and ``provable'' to be the same thing. That is, they believed that every statement in mathematics was either provable or disprovable; there was no such thing as unprovable.

Gödel, however, said that either the axiomatic system of mathematics was incapable of producing some results, or the system must contradict itself. In his terms, mathematics cannot be both complete and consistent. He showed this by constructing (via a system of encoding and manipulating mathematical statements) what is basically the self-referential mathematical theorem ``This theorem cannot be proven.'' Because of its paradoxical nature, this theorem has no proof or disproof.

What Gödel asserted in this mathematical madness was that if ``true'' and ``provable'' are the same thing, then such a self-contradictory statement exists. In other words, either our system is not complete and there are some things that we cannot prove or disprove, or our system is inconsistent and we are left with absurd conclusions. Because of this so-called Incompleteness Theorem, mathematics can no longer be viewed as a field in which everything can be proven or disproven. Gödel's results revolutionized the philosophy of mathematics.

Appendix C

The Golden Angle in Nature

The Pig points out much mathematics to Alice in the golden garden, but he doesn't explain why the Fibonacci numbers (1,1,2,3,5,8,13º) and the golden ratio f = ([(÷5+1)/ 2]) appear so frequently in nature.

Recently Stéphane Douady and Yves Couder came to the conclusion that the occurrence of Fibonacci numbers in plant matter arises from the plant's central spiral. The tip of a growing plant contains a central lump of tissue, known as the apex, from which the main features of the plant - leaves, petals, etc. - develop. Tiny lumps called primordia form around the apex. Then the apex moves away from the primordia, causing the generative spiral to appear.

Fibonacci numbers frequently appear in petals because petals represent the outer primordia of such a spiral. In 1907 G. Van Iterson explained the appearance of sunflower heads. Sunflowers seem to have two series of interpenetrating spirals, one clockwise and the other counter-clockwise. As a consequence of the golden angle in the generative spiral, these radial spirals contain successive Fibonacci numbers of primordia.

We have explained how Fibonacci numbers appear in plants, but not why. In 1979, H. Vogel performed experiments which suggested that a most effective packing is obtained when primordia are placed along the generative spiral using the golden angle. That's certainly a good reason why the golden angle occurs in nature.

But why does it lead to the most efficient packing? If a divergence angle of 90^ƒ is used, the primordia are arranged along four radial lines. This certainly isn't a tight packing, and it offers the plant very little support. This is true for other factors of 360^ƒ. The more irrational the angle is, the tighter the packing will be. The most irrational number - one that is most poorly approximable by rationals, as considered in the study of continued fractions - is f. So, the tightest packing is achieved when the divergence angle is 360(1-f)^ƒ, the golden angle. At angles just less than (below left) or just greater than (below right) the golden angle, a fairly tight packing is achieved; however, the tightest packing (below center) occurs when the angle of divergence is the golden angle.

Another theory is that the golden angle was not always present in the generative spiral, but that over time plants have been fine-tuned by natural selection to favor the tightest packing of primordia.

Evolution, genetics, geometry, and dynamics all involve this special number f. The golden ratio - and more generally, mathematics - are truly ubiquitous in beauty and nature.

Appendix D

Paul Erdos

Paul Erdos, pronounced ``air-dish'', was one of the greatest mathematicians. He not only studied and proved theorems in a variety of branches of mathematics, but he also encouraged and supported many other mathematicians. He co-authored papers with 485 mathematicians. These mathematicians are said to have an Erdos number of 1, and those who collaborated with them are said to have an Erdos number of 2; it is believed that all currently collaborating mathematicians have an Erdos number of less than 8. Erdos helped to transform a mostly solitary study into one of an open and cooperative community.

Erdos, a self-proclaimed ``poor great old man, living dead, archeological discovery, legally dead, counts dead,'' lived for mathematics. From his birth in Budapest, Hungary on March 26, 1913 until his death 83 years later on September 20, 1996, Erdos produced mathematics, often for over 12 hours a day, while sustained by a variety of substances. He remarked: ``A mathematician is a machine for turning coffee into theorems'' (Hoffman, 7).

In addition to such witty sayings, Erdos invented his own language in which wives were called ``bosses,'' God was ``the supreme fascist,'' people who stopped doing mathematics had ``died,'' and children were called ``epsilons.'' Erdos was eccentric; he owned little clothing and had limited personal possessions, he had obsessions with both death and cleanliness, and was almost completely dependent on others to feed and chauffeur him. Another Hungarian mathematician, Andrew Vázsonyi, recalls that even in his youth, Erdos was odd. When the two met in 1930, he immediately asked the 14 year old Vázsonyi for a four-digit number and proceeded to find its square. He also announced that he knew 37 proofs of the Pythagorean Theorem.

Erdos had a strong liking for small children and had a special interest in students of mathematics. He sought out child prodigies such as József Pelikán and Louis Pósa and supported their interest in mathematics. He was a patron of mathematics, sponsoring students and donating rewards for unsolved problems. He gave freely to numerous non-mathematical charities and causes, keeping hardly any money for himself.

He expended much of his energy in mathematics on combinatorics, ``the art of counting without counting,'' and graph theory. His studies included that of Ramsey Theory, named after Frank Plumpton Ramsey. The Yellow Pig explains one central question of Ramsey Theory, which involves coloring a complete graph with two colors. The Ramsey number of a graph is the minimum number of vertices needed to force a monochromatic subgraph, or a set of n points where all of the edges connecting those points are the same color. More rigorously: For two graphs G and H, let the Ramsey number R(G,H) denote the smallest integer m satisfying the property that if the edges of the complete graph K_m are colored in red or blue, then there is either a subgraph isomorphic to G with all red edges or a subgraph isomorphic to H with all blue edges.

As the Yellow Pig explains, R(3,3) is 6. That is, a two-colored graph of all edges connecting five vertices does not necessarily contain a monochromatic triangle, but one with six vertices must. Finding higher Ramsey numbers remains an open question. The table below lists many of the known Ramsey numbers.

This is just one of many intriguing open problems in mathematics.

Appendix E

Escher and Hyperbolic Geometry

Geometry, as we know it, is based on several postulates or axioms, rigorous assertions, and definitions. One that has caused much discussion in geometry is known as the Parallel Postulate. It states: Given any line and any point not on the line, there is only one line through the given point that never intersects the given line. This is something that we take for granted in Euclidean geometry, but it turns out that many results in geometry follow without using this postulate. Mathematicians have studied neutral geometry, without the postulate at all, and several non-Euclidean geometries based on the negation of the postulate.

In hyperbolic geometry there are infinitely many parallel lines through a given point, and the sum of angles in a triangle (left) is less than 180^ƒ. Spherical geometry is based on the idea that on a spherical surface any two lines intersect, and the sum of the angles in a triangle (right) is greater than 180^ƒ. In both of these alternative geometries, lines are not straight lines in the Euclidean sense, but appear as curves like arcs of circles or lines of latitude and longitude on a globe.

The problem of regularly dividing the plane interested Escher greatly. He wrote: ``I cannot imagine what my life would be like if this problem had never occurred to me. One might say that I am head over heels in love with it, and I still don't know why'' (Locher, 67). In the Euclidean plane there are seventeen essentially different ``wallpaper'' patterns using combinations of translations, rotations, reflections, and glide-reflections. Escher discovered these on his own and used them in his art.

Escher was greatly influenced by a number of mathematicians, including G. Pólya, R. Penrose, and H. S. M. Coxeter, the geometer who introduced him to hyperbolic geometry. Escher met Coxeter at the International Congresses of Mathematicians in 1954 and soon after asked for an explanation of how to construct a series of objects that decrease in size as they reach the boundary of a circle. Escher came across the idea of a hyperbolic plane in 1958 from a figure in ``A Symposium on Symmetry'' sent to him by Coxeter.

It was in his ``Circle Limits,'' which the Yellow Pig stops to admire, that Escher felt the greatest sense of achievement. He saw his use of the Poincaré disk model in ``Circle Limits'' as a milestone in his career. Escher created four ``Circle Limits'' pieces using lines in the Poincaré disk model. (Actually, the third ``Circle Limits'' doesn't use lines in the sense of hyperbolic geometry. The arcs of the backbones of the fish meet the outside circle at angles of approximately 80^ƒ, not 90^ƒ.)

Escher also experimented with hyperbolic tilings in rectangular regions and spirals, using hyperbolic geometry to shrink his figures while maintaining similarity, as in ``Smaller and Smaller I'' and ``Whirlpools.''

M.C. Escher was clearly an artist, but was he also a mathematician? Escher wrote: ``... I have often felt closer to people who work scientifically (though I certainly do not do so myself) than to my fellow artists'' (Locher, 71). Many Escher admirers suspect he had more mathematical talent than he was willing to admit, but others, including Coxeter, believe he was guided not by mathematics but by aesthetics. Escher's description of his ``Circle Limits III'', shows that he was unaware of the rigorous mathematical foundations. Surely he had no idea that mathematicians would puzzle over the precise 60^ƒ angles and their implications to the hyperbolic geometric model.

Escher's works correspond in many ways with those of crystallographers, scientists who study the structure of crystals, but there is an important distinction to make in the motivation for their studies. Escher saw crystallographers as interested in opening up the study of symmetry for its application, whereas he was intrigued by symmetry for the sake of beauty.

Escher was well aware that he was untrained in mathematics. In his Regelmatige vakverdeling (Regular Division of the Plane) Escher wrote that without the basic principles of mathematics and symmetry it was difficult at first for him to design congruent shapes for his work (Locher, 164). He did not consider himself to be a mathematician, but, like a pure mathematician, he had strong concepts of beauty and symmetry and realized the role that mathematics must play in achieving such symmetry. He developed mathematical principles in an effort to understand their beauty. Mathematics, for him, was not about formal training, but about intuition, experimentation, and aesthetics, characteristics shared by artists, mathematicians, and creative people in other fields.

Appendix F

Lewis Carroll and Logic

Lewis Carroll was born Charles Lutwidge Dodgson on January 27, 1832. His father, who had studied both the classics and mathematics, always encouraged him and his eleven brothers and sisters to learn. Dodgson attended Christ Church College where he received first honors in mathematics in 1852 and was offered a paid position. He began teaching at age 23 and became a fully established member of the community when he won a mathematical lectureship the following year.

At this time Christ Church got a new dean - Henry George Liddell. Dodgson met Liddell's daughter Alice on April 25, 1856, just before her fourth birthday. Like Erdos, Dodgson was very interested in children. He entertained them with his stories and often photographed them and drew their portraits. Alice and her older sisters, Lorina and Edith, quickly became good friends with Dodgson. In June 1862 Dodgson, two of his sisters, their aunt, the three Liddell sisters, and Robinson Duckworth, a friend of Henry Liddell, went on a picnic at Nuneham. Dodgson wrote about such a picnic with a lory (Lorina), an eaglet (Edith), a duck (Duckworth), and a dodo (Dodgson) in his Alice's Adventures in Wonderland, published in 1865 under the pseudonym Lewis Carroll (his name translated into Latin and back to English). He continued writing stories and mathematics until his death on January 14, 1898. His works include his 1871 sequel Through the Looking-Glass, his operetta of Alice in 1886, the Sylvie & Bruno stories, several volumes on logic, and many mathematical puzzles and games.

The horse in Logicland is puzzled by one of Lewis Carroll's exercises from Symbolic Logic:

1.
Babies are illogical.
Nobody is despised who can manage a crocodile.
Illogical persons are despised.

To ``solve'' this syllogism - series of logical statements - Lewis Carroll proposes the following abbreviations: a = able to manage a crocodile; b = babies; c = despised; d = logical.

The syllogism can then be rewritten as:

All b are not d.
No c are a.
All not d are c.

This gives us three statements each containing two of our letters. We see that the letters c and d both occur in two statements, once as the subject and once as the object, while the letters a and b each only occur once, as an object and a subject respectively. This suggests a reordering of the statements:

All b are not d.
All not d are c.
No c are a.

Now our statements appear tied together. We want to conclude something about b and a, and there is a natural progression from b to a via d and c.

First we consider only the first two statements. Since all b are not d, and all not d are c, we can conclude by a form of substitution that all b are c. We can represent this scenario with a diagram of three overlapping circles. This gives us eight regions: one outside of all of the circles, one inside all of the circles, three representing intersections between two circles, and three containing only one circle.

We then label the circles. For this pair of statements, we would label them c, b, and d. Next, we shade the regions that represent impossibilities. The first statement tells us that there are no b which are also d, so we can shade the two regions that represent the intersection of b and d. The second statement says that anything which is not d is c. That is, there is nothing which is neither d or c, so we can shade the remainder of the circle b which does not overlap c. Our diagram is a visual representation of the statement ``all b are c.''

While logic is not really math, the two are closely related. Perhaps most importantly, logic and mathematics require the same type of thinking. What I find most intriguing about Lewis Carroll is that he was interested in mathematics and writing, two things which are not often associated with each other but perhaps should be. After all, both are ways of communicating ideas, of telling stories.