Math MOOC – Coming this fall. Let’s Teach the World.

Higher education as we know it just ended. Exactly what will take its place is not at all clear. All that can be said with certainty is that within a few short years the higher education landscape will look very different.

That is not to say that existing colleges and universities will suddenly go away, or indeed change what they do – though I think both will occur to varying degrees in due course. What is changing now is what classifies as higher education, who provides it, how they provide it, who will have access to it, how they will obtain it, and how it will be funded. Distance education, for many years the largely-ignored stepchild of the higher education system, is about to come of age.

This is not just my opinion. My own university, Stanford, recognizes what is going on, and is taking significant steps to lead and stay on top of the change, and a number of Silicon Valley’s famed venture capital firms, who make their fortunes by betting right on the future, have sunk significant funding into what they think may be key players in the new, higher ed world.

Last fall, Stanford computer science professor Sebastian Thrun used the Internet to open his on campus course in artificial intelligence to anyone in the world with Net access, and 160,000 students from 190 countries signed up. Some 22,000 of those students finished the course, receiving “certificates of completion” signed by Thrun (and co-teacher Peter Norvig of Google), but no Stanford credit. (For that, a student has to be on campus and officially registered; annual tuition is $40,050 and entry is fiercely competitive.)

Demonstrating the entrepreneurial spirit that Stanford faculty are famous for, Thrun promptly left Stanford to found a for-profit online university, Udacity. With Udacity receiving financial backing from a large Venture Capital firm, the MOOC – massive open online course – suddenly came of age. A short while later, two more Stanford computer science faculty, Andrew Ng and Daphne Koller, secured $16M of venture capital funding to launch a second Stanford spin-off company, Coursera, a Web platform to distribute a broad array of interactive courses in the humanities, social sciences, physical sciences, and engineering.

Initial courses offered on Coursera include, in addition to several from Stanford, offerings from faculty at the University of Michigan, the University of Pennsylvania, and Princeton. Stanford president John Hennessy appointed a blue-ribbon panel of Stanford faculty to develop a strategy for developing, and delivering, online courses. For free. To the world.

Yes, you read that correctly. The faculty, the universities, and the new platforms are making the courses available for free. All the funding is coming – for now – from for-profit investors and the private universities themselves. Why are they doing that? If you have to ask the question, you don’t really understand the Internet and how it changes everything. Think Napster and the music industry or Skype and the telephone industry. Like the settling of the American territories in the nineteenth century, the initial focus is on establishing a presence in the new land; monetization can come later – almost certainly in ways very different from today’s.

Computer-assisted, distance learning is not new, of course. Stanford was one of the universities that pioneered it the 1960s; many universities have for several decades offered adult professional education courses for a fee, largely to raise funds; and there are the for-profit online schools like the University of Phoenix. More recently, led by MIT, a number of universities started making recordings of their regular courses, together with course materials, available online for free. So what has changed now?

The answer is the platform and the target audience’s experience and expectations have changed. What has been missing so far is the active participation of the distant student in a learning community. Building on technology developed at Stanford to support flipped classroom experiences for its regular students, Udacity and Coursera have secured the major investments required to build scalable, robust platforms that can take the small learning seminar and create a similar experience across the Internet.

A generation that has grown up on the Web has taken to the new online medium like fish to water. During the term when Thrun made his AI course available online, most of the Stanford students enrolled in his class stopped attending his lectures and took their information delivery online, at times convenient to them.

Is this the beginning of the end of physical universities? I doubt it. Though online courses are excellent for in-career professional learning, the absence of being a member of a physical community makes them a poor substitute – arguably no substitute – for a traditional college or university when it comes to providing first-pass education. But what about the millions (make that billions) in the world who do not have access to a university education? “Let’s teach the world” is a buzz phrase you hear increasingly among the Stanford faculty these days. And Stanford is putting resources into making this attractive dream a reality.

What makes it fascinating to a faculty member, is figuring out how to take a learning experience that works in a small-group setting on a campus, and re-creating a similar – or equivalent – experience online. Having decided last December that I would offer a math MOOC this fall, I found myself at once faced with a number of challenges.

By far the greatest problem is how to provide the personal, expert feedback that is essential to good mathematics learning. Web delivery is fine for providing instruction, but that is just a part of learning, and a minor part at that, as I discussed in the March Devlin’s Angle. At first, it seemed an impossible task. But with Stanford and the now independent Coursera building innovative new platforms, I began to see the glimmer of opportunities. Over the coming months, I’ll use this forum to write about my progress. And hopefully get your assistance.

My focus for this first foray into this new educational landscape is the high school to university transition. As every university mathematics instructor knows, many students encounter difficulty going from high school math to college-level mathematics. Though the majority survive the transition, many do not. To help them make the shift, colleges and universities often have a transition course. I myself developed one of the first transition courses in the late 1970s, when I was teaching at the University of Lancaster in England.

Such courses typically comprise a mix of some elementary mathematical logic, proof techniques, some set theory through to an analysis of relations and functions, with a bit of elementary number theory and introductory real analysis thrown in to provide examples.

Given the problems students typically have when they meet this material for the first time, doing this at a distance is a challenge. Even if they did well at math in school, most beginning university students are knocked off course for a while by the shift in emphasis, from the K-12 focus on mastering procedures to the “mathematical thinking'' characteristic of much university mathematics. Clearly, offering such a course as a MOOC is a huge experiment.

This is where you come in. (I hope.) One of the things we’ve learned at Stanford from offering MOOCs, is that a key component is the creation of a strong online community. Learning is all about human interaction. The technology just provides the medium for that interaction. In offering my math transition MOOC at the start of the fall term, when many colleges and universities offer their own transition course, I am inviting any instructor who will be giving such a course, together with their students, to join me and my MOOC students online, making interaction with other students around the world a part of a much larger learning community.

The result could be a total failure. I won’t know until I try. On the other hand, anyone who joins me might just find themselves at the start of something major, new, and exciting. The online learning revolution is going to happen, and existing educational institutions are going to have to adjust to it, just as the music industry did to the iTunes revolution. Why not jump on the train as it is leaving the station?

I’m going to make my course just five weeks long, starting in early October. By incorporating participation in my Stanford course part of your students’ learning experience, everyone could benefit. For one thing, your students are likely to be inspired by being part of an educational revolution that for millions of less privileged people around the globe can quite literally be life changing.

Because they will be supported by being part of a physical learning community, with the personal support of you, their instructor, your students will be highly empowered, privileged members of that online community. They can take advantage of your support so that they can help others. And as we all know, there is no more powerful way to learn than to try to teach others.

For that student half way round the world, trying to improve his or her life through education – by learning to think mathematically – the potential benefit is, of course, far greater. Helping that unknown young (or not so young) person make that step might just help inspire your own students to put in that bit of extra effort to master that tricky new transition material. Everyone wins.

If my Stanford MOOC draws a student body in the tens of thousands, which it might, based on the experience of my colleagues here, there is no way I and a couple of graduate TAs can provide individual feedback to every student. But if instructors and their students across the US join me, then maybe we can collectively achieve something remarkable.

I am making my MOOC deliberately short, five weeks, so participation will leave most of the semester open for participating instructors to concentrate on giving their own course, perhaps using their students’ initial experience in the MOOC community as a springboard for the rest of the course.

By the time I post next month’s column, I hope to have more details available. In the meantime, I ask anyone giving a transition course this fall to consider joining me in this experiment. The only cost is our time. There is no need to make any advance commitment to me or to Stanford. At this stage, all I ask is that you consider joining me. I believe we will all benefit. Let’s teach the world.

When math and art meet

In 1991, two mathematicians proved that you cannot always hear the shape of a drum. There are different shaped drums that make the same sound.

What about hearing numbers? For instance, can you hear pi? The answer is yes, you can. In fact you can listen to two renderings, though it took a recent court ruling to make this possible.

The story begins on Pi Day (March 14, or 3.14) 2011, when New Scientist posted a video by a musician called Michael John Blake, in which he played a piano rendering of the first 31 decimal places of pi, played at a tempo of 157 beats per minute (314 divided by two).

The video immediately went viral, but a few hours later, YouTube was contacted by a lawyer representing jazz musician Lars Erickson, who claimed that Blake's work sounded very similar to his 1992 composition "Pi Symphony", which he had registered with the US copyright office. With a claim of copyright infringement, YouTube removed the video. But Blake decided to lodge an appeal.

Both musicians had produced their works by converting decimal digits to notes on the musical scale and then adjusted tempo, phrasing, and harmonies to give the resulting composition recognizable musicality. The basis for Blake’s appeal was whether it was legally possible to copyright such a representation of pi. This is clearly an interesting question, since books and articles talking about pi and visual art based on pi clearly are copyrightable. Indeed, this very blog post  automatically carries copyright.

One year later, on March 14 of this year, US district court judge Michael H. Simon, deliberately choosing to announce his decision on Pi Day, dismissed Erickson’s claim of copyright infringement. "Pi is a non-copyrightable fact, and the transcription of pi to music is a non-copyrightable idea," Simon wrote in his legal opinion. “The resulting pattern of notes is an expression that merges with the non-copyrightable idea of putting pi to music.” (Ideas are not copyrightable.) The only features of his work that Erickson’s registered copyright protected, the judge said, were the musical flourishes he added to give the result a pleasing sound, and on the face of it the flourishes the two composers added were different. Erickson disagrees with Judge Simon’s opinion on that point. Readers can make up their own mind.

In any event, the world now has access to two musical renderings of pi.

I’ve always been intrigued by artists who try to push the boundaries of their form, as indicated by an aside I made during my talk at Wonderfest 2010. As a mathematician, I’m particularly fascinated by attempts to interpret mathematics in different artistic media, novels, movies, TV shows, painting, sculpture, and of course music and dance.

Which brings me to the “Devlin’s Angle” column I posted back in January, when I mentioned the project I worked on with the choral group Zambra, where we set out to interpret some of my favorite mathematical equations in song. I ended my article by promising to say more about that project, but then other topics came up that seemed more pressing, and that promise was not fulfilled.

The equations/formulas we chose were Euler’s equation, Pythagoras’ equation, Area of a circle formula, Einstein’s energy equation, Leibniz’s series for pi, Newton’s second law of motion, and Euler’s polyhedron formula. You can find a description of the entire project on my website.

The stage performances of our show also involved dance, provided by math professor and dancer Karl Schaffer and members of his dance troupe MoveSpeakSpin, but unfortunately we did not have the funding for a video recording.

There is clearly considerable potential in the use of music and dance (and other artistic media) in school mathematics education. Someone else I am aware of, in addition to Schaffer, who is doing great things in this area is Malke Rosenberg with MathInYourFeet.

There is also a new TV series that includes some mathematics, Touch, on Fox TV. I commented on the portrayal of mathematics in that new series in a recent commentary in The Huffington Post. As I said there, I have positive and negative feelings about that particular portrayal, but surely anything that connects mathematics to an aspect of everyday life, particularly recreational activities and popular culture, provides an excellent opportunity for the mathematics educator faced with interesting students in a crucial subject whose many important applications are, to a large extent, hidden from public view.

The difference between teaching and instruction

A brief discussion with a reader of my personal blog (profkeithdevlin) reminded me once again of the common confusion between instruction/training and teaching/learning.

As a child, I never experienced what I would now call mathematics teaching. (I revised my understanding of what teaching is, when, as an adult, I saw it in action on several occasions. Although I have no memory of having been taught that way, I guess it is possible that as a very young child I was.)

What I was presented with at school was instruction. The quality varied a lot, but looking back it was definitely instruction, not teaching. The teacher would explain some new concept or demonstrate to the class a method to solve a particular kind of problem, and then we would all work through several problems of the same type. And that was the procedure followed in all the math classes I can remember.

I quickly figured out how to play that game successfully – success in that case being measured by my being able to solve under exam conditions, problems like the ones the teacher had shown us and we had practiced in class and done for homework. Many of my fellow students did not master that game, and fell by the (well-populated) mathematical wayside.

The technique I mastered early for succeeding in that regime lasted me all the way through to calculus and on into university. Then things changed dramatically. Most of my professors provided little more than rapid summaries of new concepts and gave minimal instructions as to how to solve problems. I had to figure it out for myself afterwards, in collaboration with my fellow students, occasionally supplemented by going to the professor for help. It was at university then, when I discovered (collaborative) learning (the long sessions with my fellow students) and the power of real teaching (the activity that took place when I sat down with my professor to get help), and both were powerful and transformative.

As far as I can tell, most people in the US (and the UK) who last took a math class at high school have never experienced good mathematics teaching. Nor have many students who went on to take math classes at college level, but were not able to sit down one-on-one or in a small-group setting with the professor, as I did. All they have ever had is instruction. They often refer to it as teaching, since that is their only model. But it isn’t teaching; to call it that is to unintentionally insult the many thousands of good teachers out there.

Instruction is primarily one-directional, from an instructor (we should not use the word teacher here) to the student. Education in the instruction mode proceeds along the lines: first provide information, then give an opportunity to practice, then test.

Many students do learn to do well in this system. Some of the ones who do well actually learn what the course is supposed to be about, though others (and I suspect most) simply learn how to pass the course tests. Case in point: I got straight A’s on all my high school calculus courses (“freshman calculus” in US terms), but only when I was a doctoral student in mathematics faced with running problem sessions for math undergraduates did I actually start to understand calculus. At school I had merely learned how to pass the tests. At graduate school, five years later, I finally learned calculus, by way of trying to teach it.

The point is, unlike instruction, which is essentially unidirectional and provides no guarantee of learning that which is ostensibly being “taught,” teaching (the real kind) is bi-directional. In fact, you can’t separate real teaching from learning. They are simply two perspectives of the same human interactive process. From the teacher’s perspective it is teaching, from the student’s perspective it is learning.

For anyone who has experienced real teaching, what I am saying is obvious. Unfortunately, someone who has not experienced it likely has no idea what I am talking about. So let me give some examples that most people are familiar with.

Compare your school math classes with learning to drive, taking tennis lessons, being taught how to ride a bicycle, being taught to play a musical instrument, or being taught how to ski or improve your golf. Unless you were being seriously ripped off or shortchanged, each of those was highly interactive, with your teacher watching your performance and guiding you toward improvement.

Along the way, your teacher almost certainly gave you some instruction. Indeed, you might have stopped the learning activity and gone into a classroom where the teacher explained something at a whiteboard, or showed a video. Teaching and learning usually involve instruction. But giving and receiving instruction no more is teaching/learning than bricklaying is architecture. One is just a part of the other. An essential part, to be sure, but still just a part.

Long after I left school, I found myself visiting math classrooms where real teaching takes place, and nothing could be more different from what I experienced. Though I have observed many different styles of good teaching, two things they all have in common is that they are highly interactive and there is learning going on at the same time, as part of the process.

The distinction between instruction and teaching/learning becomes significant when cash-strapped education districts look to technology for assistance. For whereas technology can provide instruction and can provide teachers and students with resources to assist them, what is cannot do on its own is teach them. (Whether you think that is an inherent limitation of today’s technology or a fact of nature likely depends on your view as to how far artificial intelligence can go. I stated my position in my book Goodbye Descartes way back in 1998 and it has not changed since. But let’s leave that to one side, since my focus here is on the educational world today.)

The magnitude of the problem facing any teacher is made clear when you carry out a simple test that is all too infrequently done. (Actually, although simple in concept, it is time-consuming and difficult to carry out well, which is probably why it is done so rarely.) You sit down and talk with the student to find out what she or he has learned.

You might think that this is what the end-of-the-course test does, but nothing could be further from the truth. The well known educational consultant Marilyn Burns is an expert in carrying out such tests. Take a look at the following example of the kind of thing she discovers.

Watch this video on YouTube

If you are like me, when you heard Cena’s answer in the class, you will have concluded that the young girl understood place value representation. She certainly gave the right answer, and to those of us who do understand place-value, her verbally articulated reasoning screamed out conceptual understanding. But as the subsequent interview made clear, at best she has a rudimentary understanding in a particular context, and if truth be told we really have no idea what she knows.

The fact is, the human brain is a remarkable pattern-recognizing device. It will discern a pattern – usually many patterns – in a random display of dots on a screen. But is it the “right” pattern? Cena clearly recognized some pattern. But  it is not clear what it was.

This problem bedevils all of us who seek to develop educational software or technologically-delivered courseware, from the free-to-all Khan Academy and the online classes given by MIT and my own Stanford, to for-profit spinoffs like Sebastian Thrun’s Udacity. They can be good. (I am planning to give my own online Stanford class this fall, and I surely would not attempt that if I did not see value in it.) But what they can be good at is providing instruction. They don’t teach and they do not guarantee learning of the intended material. For that, you still need a teacher, and the instructional material should be a tool that the teacher actively uses.

The kinds of problem exhibited by Cena are surely less worrying for older students, particularly students who have already learned how to learn – arguably the most important goal of schooling. But still there are dangers.

For example, my fall course will include lots of video, and there are known, significant problems with video instruction, as this video (sic) shows:

Khan Academy and the Effectiveness of Science Videos

(Khan Academy, the example in this video, is in the limelight at the moment, so tends to be the example of choice, but the problem with instructional video is a general one, and will be just as pertinent to my upcoming course. I’ve asked the editor of this column to reject comments focusing on KA as being off-topic.)

It’s tempting to try to overcome the Cena-type problem by introducing an interactive component. But that too does not work, as was discovered in 1973. In what rapidly became one of the most famous and heavily studied papers in the mathematics education research literature, Stanley Erlwanger exposed the crippling limitations of what at the time was thought to be a major step forward in mathematics education: Individually Prescribed Instruction (IPI).

But already this column has gone on long enough. If you want to find out about Erlwanger’s findings, skip over to my personal blog, profkeithdevlin, where I discuss "Benny's Rules" in the context of my work on mathematics education video games.

If You Don’t Have a Web Presence, Are You Doing Your Job?

“The times they are a-changing.” - Bob Dylan

“Professor, when did you last post a blog or publish a webcast aimed at teachers?” - Me

Last month I promised I would say a bit more about my collaboration with the choral group Zambra to provide musical interpretations of mathematical equations. I will definitely come back to that in a future column, but right now I want to pick up a theme that emerged in a Finnish-American education summit at Stanford last month, for which I led the home-team organization. 

In particular, take a look at this brief video clip of math-teacher/blogger Dan Meyer making a point in a panel discussion at the conference. (Sorry about the low sound level. The recording was from Dan’s flip-video camera.)

For a broad overview of the summit, see the report in The Huffington Post. To see Dan’s complete blog post on the panel, which includes the full, hour-long video recording, see http://blog.mrmeyer.com/?p=12592. I’ll come back to that panel in just a moment. (And in a future column, I’ll tell you about the other person on the panel, Karim Ani, the founder of that wonderful, innovative, math-educational resource Mathalicious.) First, the summit itself.

Patterns? What patterns?

In the early 1990s I deliberately set out to help create a meme: mathematics is the science of patterns. My inspiration was an article written by Lynn Arthur Steen, published in SCIENCE Vol. 240 No. 4852, 29 April 1988, pp. 611-616. Steen’s piece was a high-level overview of mathematics as practiced by late twentieth century pure mathematicians, titled simply “The Science of Patterns.” In 1994, I published a full color book in W. H. Freeman’s prestigious Scientific American Library series with the title Mathematics: The Science of Patterns.

Both Steen and I were motivated by a desire to see major improvements in mathematics education, and (a closely related issue) an improved image and understanding of mathematics in American society. (This was long before the stakes were raised by the GOP declaring war on science.) But neither of us claimed originality to the view of mathematics captured by that catchy phrase. Back in 1940, the accomplished English mathematician G. H. Hardy wrote, in his book A Mathematicians Apology:

The mathematician's patterns, like the painter's or the poet's, must be beautiful,the ideas, like the colours or the words, must fit together in a harmonious way. Beauty is the first test; there is no permanent place in the world for ugly mathematics. … It may be very hard to define mathematical beauty, but that is just as true of beauty of any kind  – we may not know quite what we mean by a beautiful poem, but that does not prevent us from recognizing one when we read it.

The beauty to which Hardy was referring is, for the most part, a highly abstract, inner beauty, a beauty of abstract form and logical structure, a beauty that can be observed, and appreciated, only by those sufficiently well trained in the discipline. It is a beauty “cold and austere,” according to Bertrand Russell, the famous English mathematician and philosopher, who wrote, in his 1918 book Mysticism and Logic:

Mathematics, rightly viewed, possesses not only truth, but supreme beauty – abeauty cold and austere, like that of sculpture, without appeal to any part ofour weaker nature, without the gorgeous trappings of painting or music, yetsublimely pure, and capable of a stern perfection such as only the greatest artcan show.

But I digress – as I often do when I reflect on the natural beauty of mathematics, a beauty more fundamental than that of the best poetry or art, the latter capturing the beauty in life and the human cognitive system’s response to its existence and environment, mathematics providing a glimpse of the even deeper beauty of the universe itself, the very substrate on which we and everything we know exist.

The one obvious drawback with the “science of patterns” meme is, and always was, that it does not stand up to reflection. Not because it misses the target. Rather, it is, like many memes, altogether too general. It only captures mathematics for someone who already knows what mathematics is; it does not serve as an explanatory definition. “What kinds of pattern?” is the obvious initial response from someone not well versed in mathematics who meets our meme for the first time. Practically any science (including the life, human, and social sciences) can be described as “the science of patterns of type X” for a suitable X.

Of course, both Steen and I had the answer at the ready. His entire SCIENCE article was devoted to providing examples of the kinds of pattern whose scientific study constitutes mathematics, as was my considerably longer book. Our hope was that that catchy phrase would provoke curiosity to read our explanations and learn what it was we were trying to convey.

If I were asked to provide a “dictionary definition” of mathematics as it is practiced today, I would come up with something along the following lines.
Mathematics is:

• The systematic study of number, shape, form, structure, relations, motion and change, and other concepts, represented by precisely defined abstractions; and
• the development and application of procedures for reasoning with those concepts; and
• the use of rigorous logical argument to determine truth on the basis of accepted assumptions (axioms); and
• the application of that methodology to the real world.

More accurate than our meme to be sure; but nothing like as catchy. And decidedly not destined to become a meme.

Still, accuracy aside, thinking of mathematics in terms of patterns is far more reflective of the bulk of contemporary mathematics than is the computational-centric view of the subject that still seems the dominant one in society at large. It also leads naturally to comparisons with other “pattern-delineated” human activities. Music for example.

With its high degree of abstraction and its formal, symbolic language, music has long been one of my favorite examples when trying to explain mathematics – and its attraction – to non-mathematicians. Yet like all good comparisons, music and mathematics serve to illuminate each other by their differences as much as their similarities.

The similarities and the differences between mathematics and music motivated me to collaborate with a choral group (Zambra) a few years ago. The idea was that we should work together to find musical interpretations of some of my favorite mathematical equations. The result was a stage show called Harmonius Equations. We started with – no prizes for guessing the right answer here – Euler’s Identity. Here is the result:



Next month I’ll take a look at the rest of that collaboration.

Christmas Trees from the Land of Santa Claus

I’m writing this month’s column from the Arctic Circle, Rovaniemi in Finland to be precise, home of the University of Lapland, where I am visiting to give a lecture, and home too for the real Santa Claus, or so they say around these parts. Surrounded by trees as far as the eye can see - which is not very far at this time of the year when the sun never rises above the horizon - my thoughts turned to trees even taller than those in the Finnish forests. Infinite trees that can be found only in the conceptual forest where mathematicians tread.

This brief foray into the fascinating world of the infinite extends my discussion last month of the Recursion Principle, and shows not only that infinity has a habit of surprising us, but even seemingly “obvious” constructions and proofs involving infinity can require powerful axioms, in the case of this month’s column not only the Recursion Principle again, but a principle far better known to non-professional mathematics aficionados called the Axiom of Choice.

So fasten your seat belt and prepare for a wild ride into the world of infinite trees.

To the mathematician, a tree is a well-founded, partially ordered set such that the set of all predecessors of any element is totally ordered, having a unique minimal element (called the root of the tree). Well-founded means that every nonempty subset has a minimal element, so there can be no infinite chains going downwards.

At first encounter that formal definition looks pretty complicated, but the notion is a pretty simple one that a diagram quickly makes clearer. A tree typically looks like this.

In terms of its basic structure, this is not unlike the trees that surround me here in Lapland.

To keep the diagram simple, I have drawn only a few nodes (the points). The partial order is represented by the lines that connect nodes. Each node can have any number of immediate successors in the tree (i.e., nodes immediately above it in the partial ordering), possibly an infinite number. Some nodes may have no immediate successors (and hence no successors at all).

A totally ordered path through the tree that follows the connecting lines is called a branch. Because nodes can have more than one immediate successor, a branch going up through the tree can at some node split into two or more separate branches. But going in the opposite direction, downwards, from a node there is exactly one branch, leading all the way down to the root of the tree. Thus, when you climb a tree, you have opportunities to “branch out”, like Robert Frost in his famous walk through the wood, but there is only one way to get back down to the bottom.)

Mathematical trees arise in studies of family descendancy in history or genetics, such as the tree that represents all women and their female offspring, though in those studies the trees are conventionally drawn growing downwards, with their roots at the top.

Since the unique branch that leads up to a given node is a well-ordered set (i.e., totally ordered and well-founded), each node can be assigned a unique “height” in the tree. The root has height 0, all immediate successors of the root have height 1, all their immediate successors height 2, etc. All the nodes having a specific height N in the tree are said to constitute the N’th “level” of the tree.

Trees that arise in history or genetics are finite, and hence there will be one or more nodes that have maximum height in the tree and constitute a “top level”, but mathematicians consider infinite trees. When they started to do that, they encountered a number of surprises, as is often the case with the infinite.

One initial curiosity is that whereas infinite trees can have infinite paths going upwards, heading in different directions, all paths downwards are finite and end at the root. (A path, whether it goes upward or downward, has to be specified in terms of step-by-step instructions: start here, then go there, then go there, etc., possibly into the transfinite. More specifically, you need to specify a function from an ordinal number into the tree.)

But a far bigger surprise came from trying to generalize a fairly simple result about infinite trees called Koenig’s Lemma: an infinite tree, all of whose levels are finite, must have an infinite branch (i.e., a path that goes all the way to the top of the tree - though even there you have to be careful, since an infinite tree does not necessarily have a top level).

Proving Koenig’s Lemma is fairly straightforward. You apply the Recursion Principle, which I discussed in last month’s column. Using that principle, you define an infinite branch by recursion. Call the branch you will construct B. To determine B, you specify for each natural number N the node in B on level N, and you do that in such a way that B(N) always has infinitely many nodes above it. B(0) is the root of the tree. With B(N) defined, for B(N+1) you take any immediate successor of B(N) that itself has infinitely many successors.

A simple induction proof shows that for every N, with B(N) suitably defined there always will be at least one node above it on level N+1 that has infinitely many nodes above it, so the above recursive definition works. Here is that proof.

Since the tree is infinite, there are infinitely many nodes above the root. Level 1 is finite, so at least one node on level 1 must have infinitely many nodes above it. (Because a finite union of finite sets is finite.) Likewise, if the node B(N) has infinitely many nodes above it, then because level N+1 is finite, at least one node above B(N) on that level must also have infinitely many nodes above it, and can be taken for B(N+1). So the recursive definition is sound.

But note that this process of defining an infinite branch assumes that it is possible to make infinitely many choices. (At each stage N we choose for B(N+1) one node above B(N) on level N+1 that has infinitely many nodes above it.) Unless the tree has some additional structure that provides a uniform means of making this selection, this requires a basic assumption about infinite sets called the Axiom of Choice. Though the Axiom of Choice in its full generality has been the subject of much discussion in the history of mathematics regarding its assumption as an axiom for mathematics, the simple version used for proving Koenig’s Lemma, called the Axiom of Dependent Choices, has generally been spared most of the attention.

Most people find Koenig’s Lemma intuitively obvious and accept the proof I just sketched. The surprise comes when you try to generalize it. The most obvious generalization is to uncountable trees all of whose levels are countable. (An infinite set is called uncountable is it cannot be put into a one-to-one correspondence with the natural numbers. In the 19th century, Georg Cantor famously proved that the real numbers constitute an uncountable set.)

An uncountable tree all of whose levels are countable has to have an uncountable number of levels, so the natural numbers are not sufficient to number them; you need the transfinite ordinal numbers, which extend counting beyond the natural numbers. But apart from that tweak, at first encounter most people feel sure they can generalize the proof of Koenig’s Lemma to show that an uncountable tree all of whose levels are countable must have an uncountable branch. (Again, this will require the Axiom of Choice, this time to make an uncountably-infinite number of selections.)

That was definitely my reaction when I came across this question as a first-year graduate student in set theory. I was therefore surprised when I sat down and tried to sketch the proof and ran into an unexpected obstacle at limit ordinals. Those are transfinite ordinals that do not have an immediate predecessor, a phenomenon that does not arise for the finite ordinals (aka the natural numbers together with 0).

My difficulty turned out to be more than my inability to make the proof work. The generalization is false. In 1934, a Polish-American mathematician called Nachman Aronszajn constructed a specific uncountable tree that has only countable levels yet has no uncountable branch.

For anyone who feels comfortable with transfinite recursion (i.e., recursion that allows you to define functions whose domain extends into the transfinite ordinals), it is easy to work out Aronszajn’s construction if I give you a couple of clues. A cryptic clue, that will help get you started but won’t spoil your enjoyment when you get the construction yourself, is that it is important to think rationally. With that, you should give it a try.

STOP READING NOW IF YOU WANT TO TRY IT ENTIRELY ON YOUR OWN.

Here are some more extensive clues to Aronszajn’s construction. The tree will have an N’th level for every countable ordinal N. The nodes on level N will be strictly increasing, bounded N-sequences of positive rational numbers. You define the tree by transfinite recursion (using the Axiom of Choice as well as the Principle of Transfinite Recursion). To ensure that the recursion works, you give every node countable-infinitely many immediate successors, and do it so as to preserve the condition that for every level N, for every N-sequence S of rationals on level N, for every countable ordinal M above N, and for every positive rational Q greater than the supremum of S, there is an M-sequence on level M that extends S, whose supremum is less than Q. From here on it’s all your’s. Enjoy!

How multiplication is really defined in Peano arithmetic

A familiar joke in mathematical logic (the field I worked in for the first twenty years of my career) is the following hypothetical entry in a mathematical dictionary:

Recursion

See “Recursion”.

Though recursion is ubiquitous in modern mathematics, even at the most basic level of the analysis of the arithmetic of natural numbers, it is a subtle concept, easily misunderstood. At its heart is the always problematic step from the finite to the infinite. Having taught set theory and the foundations of mathematics for many years at various universities, I long ago learned that many students never do fully grasp it.

Many sources gloss over it. For example, the Wikipedia entry for the Peano Axioms for the natural numbers, which on the whole is pretty good, refers to “recursion” to justify its definitions of addition and multiplication on the natural numbers, but the Wikipedia page it links to punts when it comes to properly explaining the all important Recursion Principle, let alone proving it (the set-theoretic Recursion Theorem), giving a sketch proof of uniqueness (easy) but not the crucial existence part (which many people find tricky). [My comments refer to the pages when I accessed them on October 31, 2011.]

The widespread lack of appreciation for the Recursion Principle (it’s a principle you use when you are developing Peano arithmetic, a theorem you prove when you are doing set theory) lay behind many of the erroneous comments I received in response to my series of articles on multiplication not being repeated addition (not even on the natural numbers). Those articles appeared on MAA Online in June 2008, July-August 2008, September 2008, and January 2011.

If you really understand the Recursion Principle, which is what is required in order to construct addition from the successor function and to define multiplication from addition, then you will know that addition is not repeated successor (though oddly, no one ever claimed that to be the case) and multiplication is not repeated addition.

ASIDE: This is not an article about mathematics education. How teachers introduce addition and multiplication is another issue. I am not, repeat not, suggesting we teach recursion in the K-12 system. My complaint throughout that previous exchange was that, whatever and however we teach in our schools, we should not be stating things that are flat wrong. In this column I want to explain the recursion principle, its importance, its power, its need in mathematics, and how it is used, so you too will know why it is flat wrong to tell kids that multiplication is repeated addition. Remember, even if you don’t see the purpose of all the mathematical navel-inspection that led to the formulation of the principle, some of the students in your class may well find themselves wanting or needing to understand it in a few years time. While it is often pedagogically wise to say less than the whole truth, we should not lie to our students.

Okay, I’m back off my pulpit. The Recursion Principle is a rabbit-out-of-the-hat existence assertion. When used to construct addition from the successor function in Peano arithmetic, it tells you that there is a function from NxN to N that, lo-and-behold, can in any specific instance (i.e., for any pair of specific natural number arguments) be calculated by repeatedly applying the successor function a fixed number of times. Likewise, when the recursion principle is used to construct multiplication from addition in Peano arithmetic, it tells you that there is a function from NxN to N that, again wonder-of-wonders, can in any specific instance (i.e., for any pair of specific natural number arguments) be calculated by repeatedly adding a fixed number of times.

You need to invoke the Recursion Principle in order to obtain addition and multiplication because without it you just don’t get those functions. Period.

Let’s see how the Wikipedia entry I referred to earlier handles the Peano constructions of addition and multiplication.

(click image for full size)

If you read that Wikipedia account carefully, you will see that it does not actually tell you how to define addition or multiplication. Rather it tells you the properties those functions will have once they have been defined. The closest you get to an indication of how the two functions are defined is that word “recursively”, which as I noted earlier, links to another Wikipedia page that also does not tell you how the function is defined.

The definition is actually not difficult, provided you are used to working in abstract set theory. But since most people are not, authors typically leave it out, an instance where saying less than the whole truth is, in my view, justifiable. (Though I think they should explicitly note that what is being missed out is fundamental and important.)

Let’s re-write the Wikipedia definitions of addition and multiplication in standard functional notation. Thus, addition is a function P:NxN -> N such that for all numbers a, b,

1. P(a,0) = a

2. P(a,S(b)) = S(P(a,b))

and multiplication is a function M:NxN -> N such that

1. M(a,0) = 0

2. M(a,S(b)) = P(a,M(a,b))

The Recursion Principle guarantees that such functions exist. In general form, the principle says (and this is the version for binary functions over N):

Given a function H:NxN -> N and a number c, there is a function F:NxN -> N such that

1. F(a,0) = c

2. F(a,S(b)) = H(a,F(a,b))

In words, 2 says that for any given first argument a, the value of F where the second argument is the successor of b is defined in terms of the value of F where it is b. The function H tells you precisely how those two values are related.

Actually, the Recursion Principle also guarantees that the function F is unique. But that part is easy to prove from the two conditions, using induction. (Wikipedia sketches the proof.)

There are variants of the principle for unary functions and for n-ary functions for all other n, as well as for other domains besides N.

Here is how the function F is defined within set theory. Remember, in set theory, a function from NxN to N can be defined as a set of ordered triples (x,y,z) of numbers such that for each pair x, y of numbers there is exactly one number z such that the triple (x,y,z) is in the set.

Let W be the family of all sets of ordered triples T of numbers such that

1. (a, 0, c) is in T, for all numbers a

2. if (a, x, y) is in T, then (a, S(x), H(a,y)) is in T.

Then let F be the intersection of the family W. It is a routine exercise in set theory to prove that F is the required function. (That last sentence means that a mathematician having some familiarity with set theory will find it routine. It is a typical early exercise in an undergraduate course in set theory.)

So now you know.

This may all seem like a great deal of fuss about nothing. But what is going on here is really very deep. Much of modern mathematics involves finding ways to handle the infinite - calculus exclusively and spectacularly so. Mathematicians learned over many years of painful lessons that the step from the finite to the infinite is a tricky one that requires considerable finesse. In particular, you have to exercise great care to set it up correctly and do it right. The Recursion Theorem is one of those crucial bridges that allow us to go beyond the finite to the infinite, to extend human intellect from its finite physical limitations to the infinite world beyond that our minds can construct. By getting the mathematics right, we can make that step with total confidence. Confidence both in that abstract world itself and in the concrete conclusions it allows us to reach about our lives, our science, and our technologies. That is huge for Humankind. To say “multiplication is repeated addition” is like saying “differentiation is division”; for both boil down to saying that the infinite is no big deal, little different from the finite. That’s not just a lie, it is to deny two thousand years of human progress.