Cantor and his sets

Lately in class we have been studying the concept of "infinity," one of the most frequently used and frequently mis-understood of all mathematical terms. In this post we will talk about a notion more basic even than number (known also as ordinality). That notion is cardinality.

As we all know, "infinity" is not a number: most people will say it is concept, not a number. But what sort of concept? What are its parameters? Most people cannot give a definition, but will say something imprecise, like "its the thing bigger than all the numbers" or "it what you get when you put all the numbers together," or, worse, "it's what you get when you divide by zero."

The person who showed us how to put away all this imprecise, silly nonsense was Georg Cantor. Born to a German merchant family in St. Petersburg in 1845, sixteen years before the emancipation of the serfs in Russia, and about the time Tolstoy was flunking out of college. But he wouldn't spend his life in Russia; at 11 years of age, his family returned to pre-unification Germany.

His family, like many from the non-noble classes with higher aspirations, took advantage of the advancement opportunities that the expanding economies and liberalizing mentalities of 19th century Europe offered. Because his family was modestly wealthy, they had the opportunity to enroll Georg in schools teaching broad curricula in the humanities and science, as opposed to the trade/training schools most would attend in his day. These were the Realschule of aristocratic, pre-Bismarckian Germany.

He showed considerable skill in mathematics, and found himself, with his family's backing, able to attend the top schools (rubbing elbows with the likes of Kronecker and the great Karl Weierstrass). He finally landed a spot at Halle, a university that dates to 1502.

Cantor single-handedly developed the notion of cardinality, today regarded as a cornerstone mathematics---this notion is as valuable to modern mathematics as division is.

Definition: Two sets have the same cardinality if there is a one-to-one correspondence between them.

Now there are one-to-one correspondences between sets of finite size, provided the number of elements in the sets are the same: any two sets of fifty elements, say, have the same cardinality. For instance, there is a (very natural) one-to-one correspondence between the States in the US and the junior senators in the US senate.

In math, the notion of cardinality correlates to some, but not all, of our intuitive ideas about "amount." Take for instance the natural numbers and the primes. It would seen that there are far fewer primes than there are numbers, right? Well there is a one-to-one correspondence:

N. Number  |   Prime
---------------------------------

        1          |      2

        2          |      3

        3          |      5

        4          |      7

        5          |      11

        6          |      13

        7          |      17

        etc.      |      etc. 

Each natural number appears once and only one on the left side of the list, and each prime appears once and only once on the right side. The list itself demonstrates a one-to-one correspondence. Thus the cardinality of the primes is the same as the cardinality of the natural numbers.

Other one-to-one correspondences are possible, such as between the natural numbers and the integers:

N. Number  |   Integer

---------------------------------

        1          |      0

        2          |      1

        3          |      -1

        4          |      2

        5          |      -2

        6          |      3

        7          |      -3

        8          |      4

        9          |      -4

        etc.      |      etc. 

In this correspondence, we can actually write down a formula: the nth natural number corresponds to the integer n/2 if n is even, and to -(n-1)/2 if n is odd.

There are also many correspondences between natural numbers and fractions. The correspondence below is NOT one-to-one:

N. Number  |   Fraction

---------------------------------

        1          |      1

        2          |      1/2

        3          |      2/2

        4          |     1/3

        5          |      2/3

        6          |      3/3

        7          |      1/4

        8          |      2/4

        9          |      3/4

        10        |      4/4

        11        |      1/5

        etc.      |      etc. 

Why? There are repeats. We can make a one-to-one correspondence between the natural numbers and all fractions (strictly) between 0 and 1 by removing all the repeats. We obtain

N. Number  |   Fraction

---------------------------------

        1          |      1/2

        2          |      1/3

        3          |      2/3

        4          |      1/4

        5          |      3/4

        6          |      1/5

        7          |      2/5

        8          |      3/5

        9          |      4/5

        10        |      1/6

        11        |      5/6

        12        |      1/7

        13        |      2/7

        etc.      |      etc. 

In class we demonstrated a one-to-one correspondence between the natural numbers and ALL positive fractions. It would seem, so far, that there is only one infinity.

But Cantor showed us otherwise. His proof was by contradiction: that is, assume there IS a one-ton-one correspondence between, say, all natural numbers and all real numbers between 0 and 1. This would mean there is some list of the sort

N. Number  |   Fraction

---------------------------------

        1          |      .123456789123...

        2          |      .101001000100001.....

        3          |      .1112131415161......

        4          |      .141518191819.....

        5          |      .1111111111111.....

        6          |      .8989898989898989....

        7          |      .0000001000000001000000.....

        etc.      |      etc. 

Given such a list, one first forms the diagonal decimal number: the number whose first digit is the first digit of the first number, whose second digit is the second digit of the second number, and so forth. For the list above, the diagonal is .10155191....

Then one create the modified diagonal, in which each digit of the diagonal is increase by 1, except the digit "9" which becomes the digit "1." In our case, the modified diagonal is .21266202....

It is a simple matter to show that the modified diagonal is not on the list: it differs from the first number on the list in the first digit, from the second number in the second digit, and so on.

Therefore, given any list of decimals, you can find a number that is not on the list. This means there is NO complete list of decimals, and therefore NO one-to-one correspondence between the decimals and the natural numbers.

Twelve hundred years of Pythagoras' cultural history

I post normally on Wednesday afternoons, but I've fielded some questions on last week's post that I wanted to address without taking space away from new topics. It is tempting to trace western cultural roots to the Greeks, but this is arbitrary: the reason they are given special emphasis is that they are the earliest culture to leave behind writing. Prior to, say, 550BC there is no real historical record. Prior to about 700BC there is little-to-no literary record. The reason, again, is the development of alphabets: the people's writing. For at least a millennium prior to that, writing was mainly used by centralized governments and religious authorities. Their purposes seemed mainly to have been religious observation, mundane record keeping and other functionary necessities, and state propaganda (inscriptions on monuments, etc). Exceptions certainly exist, such as the epic of Gilgamesh, the code of Hammurabi, and some scientific/technical works such as astronomical observations, mathematical texts, harvesting and planting techniques, etc.

Pythagoras' cultural inheritance would have seemed rather thin to us, which may help explain why he travelled so far to gather knowledge---he was seeking out the remnant heritage of the destroyed high cultures of a past age. With no writing, very little was handed down through the Greek dark age aside from the assortment of myths and observances, along with a more-or-less confining field of religious strictures (exemplified by Hesiod's Works and Days) of the isolated cultures that settled down after the fall of the old realms.

For us in the modern world, knowledge is sought in the present, or in the future. Pythagoras, too, wanted to break out of the outmoded traditions that were perhaps useful to a simpler age, but no more. But in his time, knowledge lay in a deep, vanquished past.

For the visual among us, I am attaching a rough historical timeline of the eras surrounding Pythagoras: from the fall of the great empires, through the long dark ages, and on to the next ages of empires.

Descent and dissent: math and the revolution (of 500 BC)

The world of Pythagoras' youth was a rapidly changing place, and, in his time, change was generally for the better. Yet he was unhappy.

Society was progressing out of a broad dark ages, and it found its material conditions improving. But spiritually and intellectually people found a growing alienation. Political and social ties were changing, and so too were previously stable religious forms and cultural modes.

A little background might be in order. The high civilizations of the eastern mediterranean, the "Bronze Age" Mycenaean, Egyptian, Anatolian, and Levant cultures, had developed from far more ancient Mesopotamian and Egyptian roots---and had followed the same arc into destruction. They had crested perhaps a millennium prior, and by Pythagoras' time (the 500's BC) these civilizations and those before were long, long gone. They were as much a memory to the bustling sea-side port town of Pythagoras' boyhood as Rome was to the artists of renaissance Florence.

In both cases, the long centuries of intervening time were troubled. The older cultures (extinguished by 1200 BC) had crumbled from over-extended militaries, collapsing agricultural productivity, declining trade, persistent warfare, and finally political revolutions and a destructive migratory period: Germans and the Huns in the Roman case, the Sea Peoples, Dorians, Indo-Europeans, and others in the Mediterranean case. What followed was recognizably similar: centuries of dark ages where economies were localized, cities virtually non-existent, populations in decline, social organization built around honor and kinship hierarchies, art reverting to simpler forms, written literature all but gone, and religious observance, though fragmented, absolute.

By about 800 BC, the alphabet (from obscure origins) was introduced into the eastern mediterranean cultural basin. This lead first to more effective trade, then to revitalized and more democratized governments (the common people could read and write), and then to new literary forms. Persistent warfare was brought under control, possibly through sea-faring innovations and new technologies in iron-based weaponry, which allowed strengthened municipalities to exert control and offer protection in larger geographical areas and in sea lanes.

These trends were a few centuries old when Pythagoras was born---roughly as old as colonial times are to us. By then the motley, atomized world of the past had coalesced into more uniform associations of varying sizes and strengths (the city-states and their dependents) that were connected by a variety of cultural and economic ties, and were sometimes in conflict. Broadening trade brought wide-reaching cultural exchange: the Ionians (Athens and most of the greek colonies) wrestled with incorporating the new ideas; the Dorians (Sparta and laconia) generally retrenched and built internal responses to re-inforce the old mores.

To some, this was confusion. To others, enlightenment. Pythagoras was born in Samos, a port city of the Anatolian littoral and one of the wealthiest independent cities in the Ionian cultural sphere----and at the crossroads of the growing trade networks of the mediterranean. Exactly what influenced Pythagoras' upbringing is difficult to determine, but ancient writers agree he had traveled widely in youth, learning everything he could about mind, spirituality, science, politics, and ethics. He was certainly in Egypt for a time, likely in the levant, possibly in mesopotamia, and could have been as far away as India.

As a result he was among the very most learned of his day. And what did he do with his knowledge? What anyone would do! He started a revolutionary humanistic movement.

I say humanistic, because he was among the first of his age to believe in the supremacy of the human mind: he did not deny the supernatural, but he completed the break, begun two generations earlier with Thales, from his era's confining religious heritage. To him, knowledge and society's norms were not of the gods, but could be questioned, and, maybe, re-formed. They were subjects of human understanding; humans were not subject to them.

Hubris? In the eyes of his contemporaries, yes, very much so. In fact he was considered dangerous: Pythagoras' political movement was violently suppressed, and at age 75 he was forced to flee his adopted hometown of Croton (which is still a town in southern Italy), and likely died stateless. Apparently nobody else wanted to admit an incendiary like this into their protection.

Of course Pythagoras' ethical, political, and spiritual ideas have little resonance today. But his mathematical achievement outlasted not just his political organization, not just the rise and fall of Greek civilization, but survives intact to the present and has become part of our common world culture. Specifically, the achievement begun by him and his contemporaries, and completed by the time of Euclid 200 years later, was this: formal proof.

What could Pythagoras do with proof? Well for one he could show that his rulers were idiots. They believed they had Knowledge (big knowledge with a big K) and so should govern the cities. But Pythagoras knew they could not answer the simplest of queries.

For instance, what is the ratio of the hypotenuse of an isosceles right triangle to its side length?

Pythagoras could show that there was no such ratio! This kind of pure thought, of knowledge-as-such, made up the cornerstone of Pythagoras' thinking. The direct human contact with truths, whether simple or profound, mathematical or political, was Pythagoras' revolution.

Returning to math, in class we gave two proofs that such a ratio does not exist: Pythagoras' original proof using the method of infinite descent, and a simpler proof using Euclid's theory of factorization applied to fractions. Here we will give just the simpler proof.

Proof that the square root of 2 cannot be expressed as a fraction.

For a proof by contradiction, assume that there is a ratio that squares to 2. Assume m/n is that ratio, meaning m and n are natural numbers and m²/n²=2. By using Euclid's theorem of unique factorization and then canceling common terms, we know we can write such an m and n with no common factors.

Rearranging, m²=2n². Therefore m² is even, so m is even, so m=2q for some natural number q.

The equation is then 4q²=2n², so 2q²=n². This means n² is even, so therefore n is even.

And we have derived a contradiction: although m and n had no common factors, we proved that m and n have a common factor of 2. This contradiction implies that the assumption, that the ratio m/n squares to 2, must be false.

Inside and Outside the Box

The past two classes have dealt with the "division algorithm" and a variety of concepts surrounding it. For convenience I'll restate it: given any natural numbers m and n, there exist unique integers q and r with

        0 ≤ r < n

and

        m = nq + r.

The integer q is called the quotient of m by n, and r is called the remainder. This expression can be put into quotient form, by simply diving both sides by n:

        m ⁄ n = q + r ⁄ n .

We also went over a few definitions that you are responsible for. If the remainder of m by n is zero, we say that n divides m, written

        n | m.

Using this definition of "divides," you should be able to prove the following two facts: if m is any natural number, then

        m | m    and   1 | m.

That is, any number is divisible by itself and 1. If a number m has no divisors except these two, then it is called a prime number.

All of this is very ancient. The formal proof of the division algorithm can be found in Euclid (circa 300 BC), but the proof likely goes back to the Pythagoreans of two centuries prior, if not earlier. The practical use, but not the formal understanding, of the division algorithm is far, far older still.

Indeed it is present in one form or another at the very beginnings of essentially all civilizations---the practicum of mathematics appears to be a requirement for cities and trade, and the equivalent of the division algorithm is found in actuarial tables left in Sumerian cuneiform tablets, the intricate calendrics of the Maya, and taxation records of the Shang dynasty. What motivates its development, apparently, is the needs of tandem developments of economic systems (trade and taxation), legal systems (arbitration, settlement of land/goods disputes), the measurement of time, and the military.

We may take a simple example from the military. Suppose you live in a city-state whose smallest military unit is the phalanx, and that training is based around blocks of soldiers 8 deep and 12 wide (96 individuals). Conscription records indicate you have 5,012 recruits. To plan a campaign you need to arrange, ahead of time, supplies, logistics, and battlefield organization, and you need to know at any given time how many phalanges you'll have. Now, in the days before calculators or even before efficient number systems, this is actually quite serious problem! A city's administrative core would require a scribe or scholar who could answer (or show methods for how to answer) myriads of similar questions. In this case the scribe would tell you that enough soldiers are present for 52 phalanges, with 20 soldiers left over (maybe they can serve as scouts). That is, 5,012 by 96 has a quotient of 52 with a remainder of 20.

Now most cultures did not develop math beyond these practical uses, possibly because most cultures' needs extend no further, possibly because many cultures didn't have time for that development (many civilizations in the archeological past lasted 1,000 years or less), and possibly because of internal cultural proclivities---sometimes people are not interested in math for its own sake. Go figure!

I want to say something about this. The simple use of mathematics in solving other kinds of problems is what I call "in the box" thinking with regards to math. To relate this to our political system, it is a framework that you can function within, and attempt to use, as a tool, to accomplish your goals. If politics is used this way, you choose a side that suits you (left or right, Repubs or Dems), and you lobby, vote, speak, or participate in other ways. Or you can jump out of the box and think about the system, for instance you can think about what kind of system we should have instead, whether or not the current paradigm is just what we have to live with, and how we could change the system.

Likewise math can be used just to compute, calculate, and problem solve: that is, the system (math in this case) can be used. In some places and times in human history, people have left the system's confines and thought about the system. In mathematics, this originally occurred (to my knowledge) in two human cultures: during either the late Zhou dynasty or early Warring States period (records are unclear owing to the destruction of that period), and during the classical Greek enlightenment. Both periods were in the rough time frame of 500-200BC. In the Greek world, the concept of formal mathematical proof---a crowning jewel of that culture's intellectual achievement---was developed. Through the ebb and flow of cultural history (empire, fall, feudalism, enlightenment, global trade, technology), the concept of proof persisted, and remains with us, virtually unchanged, in the present day. The concept of proof is the main tool we use to understand math, as opposed to just using math.

So we want to ask about numbers. We have these special numbers, the primes, that have no divisors except the two that any number must have. In a sense, primes are natural phenomena: they have been observed by many cultures in disparate times and places. We have some examples of primes (2, 3, 5, 7, etc), but in total, how many primes are there? What is the proportion of all numbers that are prime? The second question was asked long ago but not answered with any degree of precision until the Prime Number Theorem was proved in 1896:

        The number of primes between 1 and n is approximately n / ln(n).

The answer to the first question was provided more than two millennia earlier by the Greeks themselves: there are infinitely many prime numbers. The proof is by contradiction. To begin, we assume there are just finitely many primes, and, using this assumption, derive a contradiction.

So let's start. Assume just finitely many primes exist, and that p₁, p₂,  . . . ,  p_N is the full list of all prime numbers. Then consider the number

        T = p₁ p₂ . . .  p_N + 1

formed by multiplying all the primes together, and adding 1. From here it is easy to show that the remainder of T by p₁ is 1, the remainder of T by p₂ is also 1, etc. That is, the quotient of T by any of the primes is 1. Therefore T is not divisible by any prime, and it must therefore be a new prime number. But we assumed that that  p₁, p₂,  . . . ,  p_N  was a list of ALL primes!

This impossibility means that it could not have been the case that  p₁, p₂,  . . . ,  p_N  was a list of all primes. This means is that ALL primes cannot be put into any finite list---the quantity of primes, then, must be infinite.

I mentioned that time-keeping was one of the earliest uses for math. Coming up in class, we will discuss special kinds of mathematical systems designed for exactly this kind of application.

Formal reasoning and the real world

This week we started on the course material proper. At the beginning of the book, the authors get a little silly with their "problems," for instance how a knight could cross a perfectly square 20ft moat onto a perfectly square landmass within, while for some reason only having 19ft 8in logs available.

Realistic? No. So what's the point? Maybe nothing. Could be the authors are weird or a little crazy. But then Ed Burger is a professor and consultant, and Mike Starbird is a distinguished professor at UT and both are professional mathematicians, so maybe they're ivory-tower types giving students flip little problems meant to "teach" something condescending. It could be that's too harsh; maybe the problems were just meant to be readable: math-y enough to communicate something, but easy enough that people don't get turned off to the book.

There is another purpose though. Just like skills in writing and communication, mathematical skills have a point, which they are trying to bring in. Yes the problems are silly, but they do resemble things in the real-world. Of course the real world does not come with its own interpretations or its own structures: it's there, doing its own thing, and we humans have to deal with it. Reality doesn't have problems, humans have problems, and most of us want to deal effectively with them, and of the many ways of dealing with what's out there, the process of formal reasoning, when used properly, is extremely effective. It works like this. Something in reality is encountered and a mental model is formed to reflect it, at least parts which can be understood as a formal structure. Formal or mathematical reasoning can be used to solve the problem in the mental model, and one attempts to translate this into a real-world solution.

The moat-crossing knight is an example. He finds a moat, which he perceives to be a problem (for whatever reason he wants to be on the moat's interior). He ascertains the situation, and creates a mental picture---in this case, a useful interpretation is as a geometry problem. The items around him are also given geometric interpretations: nearby logs can be seen as line segments for instance. His task is to use these line segments, and a few concrete rules, to draw a path across the geometrically-abstracted moat. If this strictly formal problem can be solved, he then attempts to translate the mental solution into the real world.

This is quite a philosophical approach to what is ultimately a collection of very simple story problems, and possibly my observations are pedestrian or ridiculously obvious. Maybe you see some value in this way of thinking. But I'm going through this because I want to encourage you to do likewise: don't just ask how to solve a particular problem from the book (yes, actual problem solving is important too), but why you are solving it. Don't be led by the nose, doing just what the book asks, trying to get through. Be active. Try to see why you're being asked to do it, and ask what of value is in it. You're not in this class to solve ridiculous little problems after all!