Guram Bezhanishvili
Mathematical Sciences MSC-3MB, Box 30001 New Mexico State University Las Cruces, NM 88003 gbezhani@nmsu.edu |
Hing Leung
Computer Science MSC-CS, Box 30001 New Mexico State University Las Cruces, NM 88003 hleung@nmsu.edu |
Jerry Lodder
Mathematical Sciences MSC-3MB, Box 30001 New Mexico State University Las Cruces, NM 88003 jlodder@nmsu.edu |

David Pengelley
Mathematical Sciences MSC-3MB, Box 30001 New Mexico State University Las Cruces, NM 88003 davidp@nmsu.edu |
Desh Ranjan
Computer Science MSC-CS, Box 30001 New Mexico State University Las Cruces, NM 88003 dranjan@nmsu.edu |

- Our New Web Site
- Call for Site Testers
- Pedagogical Points of Departure
- General Benefits of Using Original Sources
- The Historical Projects
- Dissemination of the Projects
- Quick List of Projects
- Bibliography

Visit our new web site for projects written as part of the Phase II expansion grant.

Any instructor of computer science or mathematics is invited to test any of our projects in the classroom for courses in discrete mathematics, combinatorics, graph theory, algorithm design, logic, abstract algebra, foundations of mathematics, or the history of mathematics. Here is a list of projects to be written under a Phase II expansion proposal. For further information, contact either Jerry Lodder or Desh Ranjan above.

This site offers written curricular materials, based on primary historical sources, for beginning and advanced undergraduate courses in discrete mathematics and computer science. Such courses, which often cover combinatorics, deductive reasoning (logic) and algorithmic thought, draw a variety of majors, ranging from computer science, mathematics, the physical sciences and engineering to secondary education. Traditional methods of instruction follow ``The Modern American Discrete Mathematics Text,'' which although thorough and mathematically precise, present the material as a fast-paced news reel of facts and formulae, often memorized by the students, with the text itself offering only passing mention of the motivating problems and original work which eventually found resolution in modern concepts such as induction, recursion, or algorithm.

Our site offers written projects for a course in discrete or finite mathematics with the projects containing excerpts from primary sources for students to read along with a sequence of directed questions which illuminate how the source develops key mathematics ideas. Particular advantages of the historical approach include providing context and direction for the subject matter, honing the students' verbal and deductive skills through reading the original work of some of the greatest minds in history, and the rediscovery of the conceptual roots common to discrete mathematics and computer science. Additionally, students practice the skill of moving from verbal descriptions of problems to precise mathematical formulations, and must often recognize an organizing concept for a detailed procedure. Such abilities are vital not only for mathematics and the sciences, but especially today for software engineers, who must translate a verbal request into precise code changes, and then realize what effect these changes will have on the global structure of a large program or a body of interacting programs.

When working on an historical project, a student spends one to two weeks, either as an individual or in a group, writing a detailed paper, with two or three projects together counting for a significant percentage (about 50%) of the course grade, and often taking the place of two one-hour examinations. A written paper allows the students to organize their own thoughts, react to the original sources in much the same way as the contemporaries of the historical masterpiece, and explore the development of ground-breaking ideas. The written historical project builds naturally on the idea of calculus projects [CG], used extensively here at New Mexico State University.

To exemplify the historical approach, what better way to see induction in action than to read from Blaise Pascal's (1623--1662) ``Treatise on the Arithmetical Triangle'' [P1], in which Pascal notices a pattern in the ratio between consecutive entries in the same base of his triangle (Pascal's Twelfth Consequence), and then claims that the pattern holds in every base of the triangle, since if it holds in a given base, then it persists to the next base. It would be a wonderful exercise for students to read Pascal's original statement, explore its truth with a few concrete numerical values, and then grapple with the logic behind what today is known as induction. The students (and teachers) witness first hand the genesis of abstract concepts, and with a bit of historical background, realize that Pascal was motivated by solving actual problems of his day, such as computing the odds in a game of chance, or finding the summation of powers, with the eventual goal of computing area under curves. Another advantage to reading Pascal's original work is that the ratios between consecutive entries that he derives lead to the modern formula for binomial coefficients, a formula which is often announced today without exploration of its historical origin.

By contrast, modern textbooks often give an abstract logical
formulation of induction first, and then, as homework, simply ask the
students to verify statements the (textbook) author already knows to
be true, such as the sum of `i`^{2} from `i`
= 1 to `n` is
(1/3)`n`^{3} + (1/2)`n`^{2} +
(1/6)`n`,
without mentioning why or how anyone discovered or
originally proved this formula.

It is being increasingly recognized that an historical point of view can provide context, motivation and direction to mathematics courses. For instance, an historical perspective is being advocated in teaching calculus [K1, K2, R1, R2], while original source materials are being incorporated in a variety of ways into calculus instruction [L1, O], and new texts are emphasizing the importance of studying original sources [BG, Ca, F, K3, K4, LP]. Also see the web page ``Teaching with Original Historical Sources in Mathematics''. This site, however, focuses on historical projects for undergraduate discrete mathematics courses. While there are presently excellent accounts of the history of algorithms such as [Ch], or the history of logic [Da, Gr], such texts do not focus on the needs of undergraduates and contain no curricular materials ready for classroom use.

The benefits of an historical point of view have been explained very convincingly by Miguel de Guzmán, President of the International Commission on Mathematical Instruction, in his talk at the 7-th International Congress on Mathematics Education [Gu]:

**
WHAT THE KNOWLEDGE OF THE HISTORY OF MATHEMATICS AND OF THE PARTICULAR SUBJECT
CAN OFFER US:
****
**

- A human vision of science and of mathematics: not just truths, methods, techniques coming from nowhere, not just facts and skills without soul, without history, but the results of the efforts of persons motivated by deep interest and passion; not as godlike science, but human and so incomplete and fallible; the human side of the great discoveries and discoverers.
- A frame in which all elements appear in their right place: not facts centuries apart in their origin presented together in the same bag without a single remark, but explorations in their own context and with their own motivation; past fashions in order to be able to understand present fashions; the deep connections along time of the different leitmotivs of the mathematical symphony.
- A dynamical vision of the evolution of mathematics: the motivation and driving forces at the roots of the ideas and methods of the subject; the primordial creativity around each particular subject, its genesis and its progress, . . . .

If a series of any number of lines be given, which exceed one another by an equal amount, and the difference be equal to the least, and if other lines be given equal in number to these, and in quantity to the greatest, the squares on the lines equal to the greatest, plus the square on the greatest and the rectangle contained by the least and the sum of all those exceeding one another by an equal amount will be the triplicate of all the squares on the lines exceeding one another by an equal amount.

The project then asked the students to rewrite the statement using
symbolic logic. Such an exercise meshes well with a first chapter on
logic in many discrete mathematics texts, which often include homework
problems such as ``Write the statement `If it is cold and raining,
then I will stay home' in symbols, using the predicates, *P*: It is
cold, *Q*: It is raining, *R*: I will stay home.'' A particular
drawback of modern textbooks is their lack of motivation, perspective
and context. Why not apply symbolic logic to the very statements
which historically drove the development of mathematics, allowing the
students to hone their verbal and deductive skills on significant
problems?

A second project, ``In the Words of Archimedes II,''
built on the first by asking students to verify
Archimedes' statement about the sums of squares using ideas from his
original proof, a proof which did not involve induction. A third
project, ``In the Words of Pascal,''
presented Pascal's bold statement about the sums
of arbitrary powers taken from a translation of * Sommation des
Puissances Numériques*
[P2],
and asked the students to prove, now using induction, that
the sum of `i ^{k}` from

Guram Bezhanishvili has written a major project on Georg Cantor's
(1845--1918) revolutionary ideas concerning infinite sets using
excerpts from Cantor's memoir *Contributions to the Founding of
the Theory of Transfinite Numbers*
[Cn].
The project, ``Are All Infinities Created Equal?''
(pdf file)
(ps file),
begins by asking the students to identify certain properties of
``naive set theory'' as explicated by Cantor, and then write these
observations using modern notation. The project continues
with a comparison of the cardinality of various infinite sets,
such as the set of rational numbers, and the set of real numbers
in the interval [0, 1], and concludes with the observation that
certain infinite sets are larger than others
(2 to the aleph naught is greater than aleph naught),
a paradigm-breaking idea about the infinite.

Additionally, Jerry has introduced logic in a beginning discrete mathematics course [L2] via Alan Turing's (1912--1954) original paper ``On Computable Numbers with an Application to the Entscheidungsproblem'' [T]. Through the first project, ``An Introduction to Turing Machines'' (pdf file) (ps file), the students witness an idea which is the forerunner of a programmable computer, a Turing machine, and in the second, ``Turing Machines, Induction and Recursion'' (pdf file) (ps file), they observe how the concept of recursion arises naturally when writing a Turing machine to perform a basic operation such as multiplication of positive integers. Moreover, induction is used to verify that the output of the machine is correct. At the conclusion of the Turing projects, a student from an under represented minority remarked: ``I thought this course would just be about numbers, but instead, I learned how computers started.'' Another student, when describing the projects, claimed ``That's how I learn.''

The first two Turing projects deal with the construction and design of Turing machines to perform certain computational tasks, and remain at an introductory level, primarily to serve the needs of a beginning course in discrete mathematics. Of course, Turing's original motivation was to solve Hilbert's decision problem, which Turing masterfully does in [T], and in so doing, he develops the idea of a universal computing machine (known as a compiler or an interpreter today). The third project in this sequence, ``The Universal Computing Machine'' (pdf file) (ps file), outlines Turing's logical construction of this device, and is well-suited for an intermediate or an advanced undergraduate course in logic, discrete mathematics, or computer science. A fourth project in this sequence, ``The Decision Problem'' (pdf file) (ps file), offers Turing's (negative) solution to this issue, which today has become known as the halting problem in computer science. These last two Turing projects were used recently in an intermediate discrete mathematics course, at the conclusion of which student comments reveal: ``I found the two projects to be challenging and extremely pertinent to computer science.'' ``The two projects that dealt with the Turing machines and the halting problem gave me insight and understanding of the origins of computer science.''

During the Autumn semester of 2003 Jerry Lodder developed two projects
for an introductory course in discrete mathematics which trace the
development of binary arithmetic from the Enlightenment to the
electronic age. The first project (pdf file)
(ps file) begins with Gottfried Wilhelm
Leibniz's (1646--1716) work on binary numeration, offering excerpts
form his 1703 publication ``Explication de l'arithmétique
binaire, qui se sert des seuls caractères 0 et 1, avec des
remarques sur son utilité, et sur ce qu'elle donne des
anciennes figures Chinoises de Fohy,''
(An Explanation of Binary Arithmetic Using only the Characters 0 and
1, with Remarks about its Utility and the Meaning it Gives to the
Ancient Chinese Figures of Fuxi)
[Ge, p. 223--227]
[Le].
For Leibniz, binary numbers represented a confluence of several ideas,
including order, harmony, a candidate for his universal
language (*lingua generalis*), an analogy of creation with 0
denoting nothing and 1 denoting God, and an interpretation of
the ancient Chinese text of divination the *Yijing*
(*I-Ching* or *Book of Changes*) in terms of binary
numeration
[Sw].
Leibniz also cites an ease of calculation with base 2 numbers,
particularly for multiplication and division, which do not require the
memorization of a multiplication table or methods of trial and error,
as is often the case for long division in base 10.

The project continues with a brief account of the Electronic Numerical Integrator and Computer (ENIAC) developed at the University of Pennsylvania's Moore School of Electrical Engineering during the years 1943--1945, and discusses its use of base 10 arithmetic, requiring the storage of a multiplication table for numbers between zero and nine [Go]. The next generation of computing equipment, the Electronic Discrete Variable Automatic Computer (EDVAC), heavily influenced by the ideas of John von Neumann (1903--1957), performed arithmetical calculations in base 2. The project provides excerpts from von Neumann's 1945 white paper ``First Draft of a Report on the EDVAC'' [vN], in which he too cites the ease of calculation as an advantage to binary arithmetic, as well as an economy of representing numerical values with this system. Moreover, the EDVAC is a model for a ``universal computing machine'' in the sense of Turing [T]. This project, ``Binary Arithmetic: From Leibniz to von Neumann'' (pdf file) (ps file) is ideal for beginning students in discrete mathematics, particularly those with no previous knowledge of base 2 calculations.

Leibniz's paper on binary arithmetic can be used to motivate and provide significant material for other topics in discrete mathematics, such as induction and divisibility properties of integers. Although these ideas are not developed in the project per se, they could be easily implemented as classroom activities after completion of the project. For example, Leibniz claims that following a study of binary numeration, ``we see the reason for the famous property of the double geometric progression in whole numbers, which states that given only one of these numbers in each degree, we can form all other whole numbers below the double of the highest degree,'' a statement which today is easily proved by induction. A present-day formulation of this property might read: Given the values 2The second project on binary arithmetic ``Arithmetic Backwards from von Neumann to the Chinese Abacus'' (pdf file) (ps file), builds on the first, beginning with von Neumann's claim that a high-speed vacuum tube computer performs arithmetic most efficiently in base 2. The project then proceeds in a chronologically reverse order, next examining Claude Shannon's (1916--2001) design of circuits for computations in Boolean algebra and logic. The project provides excerpts from Shannon's 1938 paper ``A Symbolic Analysis of Relay and Switching Circuits'' [Sh], and asks the students to construct the circuits necessary for binary addition. A careful study of these examples provides motivation for writing logic statements in what today is known as ``disjunctive normal form,'' a concatenation of sub-statements with the connective ``or,'' where each sub-statement contains only negations and the connective ``and.''

The project continues with the realization that writing a number in
base 2 often requires many digits, and examines an alternative base
that can be easily converted to base 2. Surprisingly a Chinese abacus
provides the ideal tool for computations in base 16, which the
students are asked to realize on their own by exploring all possible
values that can be represented by bead arrangements on a single bar of
this type of abacus. As an in-class activity while the project was
assigned, we discussed base 10 addition and subtraction on an abacus,
with the base 16 analogues of these operations left to the students.
Today hexadecimal notation (base 16) is common place in computer
science, and serves as shorthand for binary numbers, with the
conversion between base 2 and base 16 a simple operation. With
Leibniz's interest in China and the interpretation of the hexagrams of
the *Yijing* in terms of binary numeration, the Chinese abacus
provides a pleasing confluence of historical, cultural and
computational ideas for the second project, particularly as a tool for
place value arithmetic in a two-power base. Concerning the benefits
of teaching with historical sources, at the conclusion of the course,
students wrote: ``You get an understanding of why you are doing
something.'' ``It ties in better, links can be made.'' ``Gives
meaning to problems.'' ``We can understand why we do certain things
in certain ways.''

David Pengelley has authored a project track to teach induction from Pascal's ``Treatise on the Arithmetical Triangle," (pdf file) (ps file), where Pascal proves that certain patterns occur in his triangle via a logical argument that would later become known as induction. Desh Ranjan has written ``Counting Triangulations of a Polygon," (pdf file) (ps file), which develops the sequence of Catalan numbers from a simple observation of Lamé. Desh's project contains David's translation of a letter from Lamé to Liouville, which serves as the primary source for this work. Hing Leung has completed a project (pdf file) (ps file) that outlines the reduction of two-way deterministic finite automata to one-way automata via the work of Shepherson, and builds on the notion of a Turing machine. Additionally, Guram Bezhanishvili has outlined Church's thesis using excerpts from the work of Gödel, Kleene and Turing, which establish that general recursive functions coincide with Turing computable functions (pdf file) (ps file).

The teaching community is invited to use any of the above projects in relevant mathematics or computer science courses. Typically two or three projects, chosen around a specific theme, such as Turing machines, are used in a one-semester course, with the projects counting for a significant portion (40%--50%) of the course grade. For each project the students are given one to two weeks, working as an individual or in groups of two or three, to produce a written paper addressing the issues raised in the project. Each project usually replaces an in-class examination. For further general information about the use of projects see [CG].

1. ``Are All Infinities Created Equal?'' | pdf file | ps file | latex file | |

2. ``An Introduction to Turing Machines'' | pdf file | ps file | latex file | |

3. ``Turing Machines, Induction and Recursion'' | pdf file | ps file | latex file | |

4. ``Turing Machines and Binary Addition'' | pdf file | ps file | latex file | |

5. ``The Universal Computing Machine'' | pdf file | ps file | latex file | |

6. ``The Decision Problem'' | pdf file | ps file | latex file | |

♦
All Turing projects to appear in print
| pdf file | ps file | latex file | |

7. ``Binary Arithmetic: From Leibniz to von Neumann'' | pdf file | ps file | latex file | |

8. ``Arithmetic Backwards from von Neumann to the | ||||

Chinese Abacus'' | pdf file | ps file | latex file | |

9. ``Treatise on the Arithmetical Triangle'' | pdf file | ps file | latex file | |

10. ``Counting Triangulations of a Polygon'' | ||||

The Mathematical Version | pdf file | ps file | latex file | |

11. ``Counting Triangulations of a Polygon'' | ||||

The Programming Version | pdf file | ps file | latex file | figure file |

12. ``Two-Way Deterministic Finite Automata'' | pdf file | ps file | latex file | |

13. ``Church's Thesis'' | pdf file | ps file | latex file | |

14. ``Euler Circuits and the Königsberg Bridge Problem '' | pdf file | ps file | latex file | figure files |

15. ``Topological Connections from Graph Theory'' | pdf file | ps file | latex file | figure files |

16. ``Hamiltonian Circuits and Icosian Game'' | pdf file | ps file | latex file | figure file |

♦ ♦
All projects to appear in print
[Ba]. |
pdf file | |||

♦ ♦ Visit our new web site for additional projects written as part of the Phase II expansion grant.

The development of curricular materials for discrete mathematics has been partially supported by the National Science Foundation's Course, Curriculum and Laboratory Improvement Program under grant DUE-0231113, for which the authors of this web site are most appreciative. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

[Ba]
Barnett, J., Bezhanishvili, G., Leung, H., Lodder, J., Pengelley, D.,
Ranjan, D.,
"Historical Projects in Discrete
Mathematics and Computer Science" in
*Resources for Teaching Discrete Mathematics*,
Hopkins, B. (editor), Mathematical Association of America, Washington,
D.C., 2009.

[BG]
Berlinghoff, W., Gouvêa, F., *Math through the Ages: A
Gentle History for Teachers and Others*, Oxton House Publishers,
Farmington, Maine, 2002.

[Be]
Bernoulli, J., *Die Werke von Jakob
Bernoulli*, Naturforschende Gesellschaft in Basel, Birkhäuser
Verlag, Basel, 1975.

[Ca]
Calinger, R., (ed.), * Classics of Mathematics*,
second ed., Prentice-Hall, Engelwood Cliffs, New Jersey, 1995.

[Cn]
Cantor, G., *Contributions to the Founding of the
Theory of Transfinite Numbers*, Dover, New York, 1952.

[Ch]
Chabert, J-L., * A History of Algorithms From
the Pebble to the Microchip*, Chris Weeks (trans.), Springer Verlag, New
York, 1994.

[CG]
Cohen, M., Gaughan, E., Knoebel, A., Kurtz, D., Pengelley, D.,
*Student Research Projects in Calculus*, Mathematical Association
of America, Washington, D.C., 1992.

[Da]
Davis, M., *The Universal Computer: The Road From Leibniz to
Turing, * W. W. Norton & Company, New York, 2000.

[Di]
Dijksterhuis, E., * Archimedes *, Princeton
University Press, Princeton, New Jersey, 1987.

[F]
Fauvel, J., Van Maanen, J., * History in
Mathematics Education*, Kluwer, Boston, 2000.

[Ge]
Gerhardt, C. I., (ed.), * G. W. Leibniz Mathematische
Schriften*, Vol. VII, Olms, Hildesheim, 1962.

[Go]
Goldstine, H. H., *The Computer from Pascal to von Neumann*,
Princeton University Press, Princeton, New Jersey, 1972.

[Gr]
Grattan-Guinness, I., * The Search for
Mathematical Roots, 1870--1940: Logics, Set Theories and The
Foundations of Mathematics from Cantor through Russell to Gödel*,
Princeton University Press, Princeton, 2000.

[Gu]
Guzmán, M. de,
``Origin and Evolution of Mathematical
Theories: Implications for Mathematical Education," * Newsletter of the
International Study Group on the History and Pedagogy of Mathematics,
* # 28 (March 1993) 2--3.

[K1]
Katz, V., ``An Historical Approach to Precalculus and
Calculus," * Newsletter of the Humanistic Mathematics Network*, # 6, May
1991.

[K2]
Katz, V., ``Using the History of Calculus to Teach
Calculus," * Science and Education*, ** 2**, # 3, Fall 1993.

[K3]
Katz, V., * A History of Mathematics: An
Introduction*, second ed., Addison-Wesley, New York, 1998.

[K4]
Katz, V., (ed.), * Using History to Teach
Mathematics*, Mathematical Association of America, Washington, D.C.,
2000.

[LP]
Laubenbacher, R., Pengelley, D.,
*Mathematical
Expeditions: Chronicles by the Explorers*, Springer-Verlag, New York,
2000.

[Le]
Leibniz, G. W., ``Explication de l'arithmétique
binaire, qui se sert des seuls caractères 0 et 1, avec des
remarques sur son utilité, et sur ce qu'elle donne des
anciennes figures Chinoises de Fohy,'' *Memoires de
l'Académie Royale des Sciences*, ** 3 ** (1703) 85--89.

[L1]
Lodder, J., ``Curvature in the Calculus
Curriculum,'' * American
Mathematical Monthly*, ** 110 **, 7 (2003) 593--605.

[L2]
Lodder, J.,
``Introducing Logic via Turing Machines,'' in *From
Calculus to Computers: Using the Last 200 Years of Mathematics
History in the Classroom*, A. Shell-Gellasch, D. Jardine (eds.),
Mathematical Association of America, Washington, D.C., 2005,
125--133.

[O]
Otero, D., ``An Historical Calculus Course for Liberal
Arts Students'', * Newsletter of the International Study Group on the
History and Pedagogy of Mathematics*, # 28 (March 1993),
7--9.

[P1]
Pascal, B., ``Treatise on the Arithmetical
Triangle,'' in * Great Books of the Western World*, M. Adler (ed.),
Encyclopedia Britannica Inc., Chicago, 1991.

[P2]
Pascal, B., * Oeuvres*, L. Brunschvieg (ed.),
Paris, 1908--14; Kraus Reprint, Vaduz, Liechtenstein, 1976, Vol. III,
341--367.

[R1]
Rickey, F., ``My Favorite Ways of Using History in
Teaching Calculus,'' in * Learn From the Masters*, F. Swetz,
J. Fauvel, O. Bekken, B. Johansson, V. Katz, (eds.), Mathematical
Association of America, Washington, D.C., 1995, 123--134.

[R2]
Rickey, F., ``The Necessity of History in Teaching
Mathematics,'' in * Vita Mathematica: Historical Research and
Integration with Teaching*, R. Calinger (ed.), Mathematical
Association of America, Washington, D.C., 1996, 251--256.

[Sh]
Shannon, C. E., ``A Symbolic Analysis of Relay and Switching
Circuits,'' *Transactions American Institute of Electrical
Engineers*, ** 57 ** (1938) 713--723.

[Sw]
Swetz, F. J., ``Leibniz, the *Yijing*, and the Religious
Conversion of the Chinese,'' *Mathematics Magazine*, ** 76**,
No. 4 (2003) 276--291.

[T] Turing, A.,
``On Computable Numbers with an Application
to the Entscheidungsproblem,'' * Proceedings of the London
Mathematical Society*, ** 42 ** (1936) 230--265.

[vN] von Neumann, J.,
``First Draft of a Report on the EDVAC,'' in
* From ENIAC to UNIVAC: An Appraisal of the Eckert-Mauchly Computers,*
N. Stern, Digital Press, Bedford, Massachusetts, 1981, 177--246.

Return to top of page Return to the quick list of projects Visit our new web site