0123456789 in Europe: an infographic

Following up on my earlier post about 0 and 1 in Greek mathematics and my timeline of zero in Europe, here is a timeline for the use of Hindu-Arabic numerals in Europe up to René Descartes (click to zoom).


0 and 1 in Greek mathematics

Following up on an earlier post about zero in Greek mathematics and this timeline of zero, I want to say something more about the role of 0 (zero) and 1 (one) in ancient Greek thought. Unfortunately, some of the discussion on Greek mathematics out there is a bit like this:

0 and 1 as quantities

The ancient Greeks could obviously count, and they had bankers, so they understood credits and debts, and the idea of your bank account being empty. However, they had not reached the brilliant insight of Brahmagupta, around 628 AD, that you could multiply a debt (−) and a debt (−) to get a credit (+).

The ancient Greeks had three words for “one” (εἷς = heis, μία = mia, ἑν = hen), depending on gender. So, in the opening line of Plato’s Timaeus, Socrates counts: “One, two, three; but where, my dear Timaeus, is the fourth of those who were yesterday my guests … ? (εἷς, δύο, τρεῖς: ὁ δὲ δὴ τέταρτος ἡμῖν, ὦ φίλε Τίμαιε, ποῦ τῶν χθὲς μὲν δαιτυμόνων … ; )

The Greeks had two words for “nothing” or “zero” (μηδέν = mēden and οὐδέν = ouden). So, in the Christian New Testament, in John 21:11, some fisherman count fish and get 153, but in Luke 5:5, Simon Peter says “Master, we toiled all night and took nothing (οὐδὲν)!

0 and 1 in calculations

In ordinary (non-positional) Greek numerals, the Greeks used α = 1, ι = 10, and ρ = 100. There was no special symbol for zero. Greek mathematicians, such as Archimedes, wrote numbers out in words when stating a theorem.

Greek astronomers, who performed more complex calculations, used the Babylonian base-60 system. Sexagesimal “digits” from 1 to 59 were written in ordinary Greek numerals, with variations of ō for zero. The overbar was necessary to distinguish ō from the letter ο, which denoted the number 70 (since an overbar was a standard way of indicating abbreviations, it is likely that the symbol ō was an abbreviation for οὐδὲν).

Initially (around 100 AD) the overbar was quite fancy, and it became shorter and simpler over time, eventually disappearing altogether. Here it is in a French edition of Ptolemy’s Almagest of c. 150 AD:

In Greek-influenced Latin astronomical calculations, such as those used by Christians to calculate the date of Easter, “NULLA” or “N” was used for zero as a value. Such calculations date from the third century AD. Here (from Gallica) is part of a beautiful late example from around 700 AD (the calendar of St. Willibrord):

Outside of astronomy, zero does not seem to get mentioned much, although Aristotle, in his Physics (Book 4, Part 8) points out, as if it is a well-known fact, that “there is no ratio of zero (nothing) to a number (οὐδὲ τὸ μηδὲν πρὸς ἀριθμόν),” i.e. that you cannot divide by zero. Here Aristotle may have been ahead of Brahmagupta, who thought that 0/0 = 0.

0 and 1 as formal numbers?

We now turn to the formal theory of numbers, in the Elements of Euclid and other works. This is mathematics in a surprisingly modern style, with formal proofs and (more or less) formal definitions. In book VII of the Elements (Definitions 1 & 2), Euclid defines the technical terms μονάς = monas (unit) and ἀριθμὸς = arithmos (number):

  1. A monas (unit) is that by virtue of which each of the things that exist is called one (μονάς ἐστιν, καθ᾽ ἣν ἕκαστον τῶν ὄντων ἓν λέγεται).
  2. An arithmos (number) is a multitude composed of units (ἀριθμὸς δὲ τὸ ἐκ μονάδων συγκείμενον πλῆθος).

So 1 is the monas (unit), and the technical definition of arithmos excludes 0 and 1, just as today the technical definition of natural number is taken by some mathematicians to exclude 0. However, in informal Greek language, 1 was still a number, and Greek mathematicians were not at all consistent about excluding 1. It remained a number for the purpose of doing arithmetic. Around 100 AD, for example, Nicomachus of Gerasa (in his Introduction to Arithmetic, Book 1, VIII, 9–12) discusses the powers of 2 (1, 2, 4, 8, 16, 32, 64, 128, 256, 512 = α, β, δ, η, ιϛ, λβ, ξδ, ρκη, σνϛ, φιβ) and notes that “it is the property of all these terms when they are added together successively to be equal to the next in the series, lacking a monas (συμβέβηκε δὲ πᾱ́σαις ταῖς ἐκθέσεσι συντεθειμέναις σωρηδὸν ἴσαις εἶναι τῷ μετ’ αὐτὰς παρὰ μονάδα).” In the same work (Book 1, XIX, 9), he provides a multiplication table for the numbers 1 through 10:

The issue here is that Euclid was aware of the fundamental theorem of arithmetic, i.e. that every positive integer can be decomposed into a bag (multiset) of prime factors, in no particular order, e.g. 60 = 2×2×3×5 = 2×2×5×3 = 2×5×2×3 = 5×2×2×3 = 5×2×3×2 = 2×5×3×2 = 2×3×5×2 = 2×3×2×5 = 3×2×2×5 = 3×2×5×2 = 3×5×2×2 = 5×3×2×2.

Euclid proves most of this theorem in propositions 30, 31 and 32 of his Book VII and proposition 14 of his Book IX. The number 0 is obviously excluded from consideration here, and the number 1 is special because it represents the empty bag (even today we recognise that 1 is a special case, because it is not a prime number, and it is not composed of prime factors either – although, as late as a century ago, there were mathematicians who called 1 prime, which causes all kinds of problems):

  • If two numbers (arithmoi) by multiplying one another make some number, and any prime number measure the product, it will also measure one of the original numbers (ἐὰν δύο ἀριθμοὶ πολλαπλασιάσαντες ἀλλήλους ποιῶσί τινα, τὸν δὲ γενόμενον ἐξ αὐτῶν μετρῇ τις πρῶτος ἀριθμός, καὶ ἕνα τῶν ἐξ ἀρχῆς μετρήσει) – i.e. if a prime p divides ab, then it divides a or b or both
  • Any composite number is measured by some prime number (ἅπας σύνθετος ἀριθμὸς ὑπὸ πρώτου τινὸς ἀριθμοῦ μετρεῖται) – i.e. it has a prime factor
  • Any number (arithmos) either is prime or is measured by some prime number (ἅπας ἀριθμὸς ἤτοι πρῶτός ἐστιν ἢ ὑπὸ πρώτου τινὸς ἀριθμοῦ μετρεῖται) – this would not be true for 1
  • If a number be the least that is measured by prime numbers, it will not be measured by any other prime number except those originally measuring it (ἐὰν ἐλάχιστος ἀριθμὸς ὑπὸ πρώτων ἀριθμῶν μετρῆται, ὑπ᾽ οὐδενὸς ἄλλου πρώτου ἀριθμοῦ μετρηθήσεται παρὲξ τῶν ἐξ ἀρχῆς μετρούντων) – this is a partial expression of the uniqueness of prime factorisation

The special property of 1, the monas or unit, was sometimes expressed (e.g. by Nicomachus of Gerasa) by saying that it is the “beginning of arithmoi … but not itself an arithmos.” As we have already seen, nobody was consistent about this, and there was, of course, no problem in doing arithmetic with 1. Everybody agreed that 1 + 2 + 3 + 4 = 10. In modern mathematics, we would avoid problems by saying that natural numbers are produced using the successor function S, and distinguish that function from the number S(0) = 1.

The words monas and arithmos occur in other Greek writers, not always in the Euclidean technical sense. For example, in a discussion of causes and properties in the Phaedo (105c), Plato tells us that “if you ask what causes an arithmos to be odd, I shall not say oddness, but the monas (οὐδ᾽ ᾧ ἂν ἀριθμῷ τί ἐγγένηται περιττὸς ἔσται, οὐκ ἐρῶ ᾧ ἂν περιττότης, ἀλλ᾽ ᾧ ἂν μονάς).” Aristotle, in his Metaphysics, spends some time on the philosophical question of what the monas really is.

In general, the ancient Greeks seem to have had quite a sophisticated understanding of 0 and 1, though hampered by poor vocabulary and a lack of good symbols. Outside of applied mathematics and astronomy, they mostly worked with what we would call the multiplicative group of the positive rational numbers. What they were missing was any awareness of negative numbers as mathematical (not just financial) concepts. That had to wait until Brahmagupta, and when it came, 0 suddenly became a whole lot more interesting, because it eventually became possible to define more advanced mathematical concepts like fields.


The history of zero: an infographic

Following up on an earlier post about Zero in Greek mathematics, here is a timeline for the use of zero in Europe (click to zoom). I have used images of, or quotes from, primary sources where possible (reliably dated Indian primary sources are much harder to find than Greek ones, unfortunately).

Chinese uses of zero are probably also derived from the Greeks, but Mayan uses are clearly independent.


Modal logic, ethics, and obligation

Recently, I posted about necessary truth, the logic of belief, and epistemic logic. I would like to follow up on that one more time by discussing deontic logic, the logic of obligation and moral action. We can capture this concept using the 4 rules of D4 modal logic. The first 3 of these are the same as those I used for belief. I am replacing the previous modal operators with  Ⓞ  which is intended to be read as “it is obligatory that” (hence the O in the circle):

  • if P is any tautology, then  Ⓞ P
  • if  Ⓞ P  and  Ⓞ (PQ)  then  Ⓞ Q
  • if  Ⓞ P  then  Ⓞ Ⓞ P
  • if  Ⓞ P  then  ~ Ⓞ ~P

where  ~ Ⓞ ~P  is read as “~ P is not obligatory,” i.e. “P is permissible.” For those who prefer words rather than symbols:

  • if P is any tautology, then P is obligatory
  • if P and (P implies Q) are both obligatory, then Q is obligatory
  • if P is obligatory, then it is obligatory that P is obligatory
  • if P is obligatory, then P is permissible

For these rules as they stand, the only things that are obligatory are necessary truths like 2 + 2 = 4. This is because you can’t get an “ought” from an “is.” Apart from the first rule, there is no way of introducing a  Ⓞ  symbol out of nowhere. Consequently, if we are to reason about ethics and morality, we must begin with some deontic axioms that already contain the  Ⓞ   symbol. For people of faith, these deontic axioms may be given by God, as in the 10 Comandments, which include:

Ⓞ  you do not murder.
Ⓞ  you do not commit adultery.
Ⓞ  you do not steal.
Ⓞ  you do not bear false witness against your neighbor.

Immanuel Kant famously introduced the categorical imperative, a deontic axiom which Kant thought implied all the other moral rules, and thus provided the smallest possible set of deontic axioms:

Ⓞ  [you] act only according to that maxim whereby you can, at the same time, will that it should become a universal law.

Others have suggested the greatest happiness of the greatest number as a principle. Fyodor Dostoevsky, William James, and Ursula Le Guin are among those who have explained the problem with this:

Tell me yourself, I challenge your answer. Imagine that you are creating a fabric of human destiny with the object of making men happy in the end, giving them peace and rest at last, but that it was essential and inevitable to torture to death only one tiny creature – that baby beating its breast with its fist, for instance – and to found that edifice on its unavenged tears, would you consent to be the architect on those conditions?” (Fyodor Dostoevsky, “The Grand Inquisitor,” in The Brothers Karamazov, 1880; 4.35 on Goodreads)

Or if the hypothesis were offered us of a world in which Messrs. Fourier’s and Bellamy’s and Morris’s Utopias should all be outdone and millions kept permanently happy on the one simple condition that a certain lost soul on the far-off edge of things should lead a life of lonely torture, what except a specifical and independent sort of emotion can it be which would make us immediately feel, even though an impulse arose within us to clutch at the happiness so offered, how hideous a thing would be its enjoyment when deliberately accepted as the fruit of such a bargain?” (William James, “The Moral Philosopher and the Moral Life,” 1891)

Some of them understand why, and some do not, but they all understand that their happiness, the beauty of their city, the tenderness of their friendships, the health of their children, the wisdom of their scholars, the skill of their makers, even the abundance of their harvest and the kindly weathers of their skies, depend wholly on this child’s abominable misery.” (Ursula K. Le Guin, “The Ones Who Walk Away from Omelas,” 1973; reprinted in The Wind’s Twelve Quarters, 1975; 4.05 on Goodreads)

The meaning of deontic statements can be described using Kripke semantics, which exploits the idea of possible worlds (i.e. alternate universes). To say that some statement is obligatory is to say that the statement would be true in better possible worlds (we write w1 → w2 to mean that w2 is a better possible world than w1).

In any given world v, the statement  Ⓞ P  is equivalent to :

  • P  is true in all better worlds wi (i.e. all those with v → wi)

Likewise, in any given world v, the statement  ~ Ⓞ ~P  (P is permissible) is equivalent to:

  • P  is true in at least one better world wi (i.e. one with v → wi)

The rules of deontic logic imply two conditions on these arrows between possible worlds:

  • if  w1 → w2 → w3  then  w1 → w3  (i.e. chains of arrows are treated like arrows too)
  • in every world v there is at least one arrow  v → w  (i.e. chains of arrows don’t stop; this includes the case of  v → v)

A number of philosophers have suggested that deontic logic leads to paradoxes. In all cases that I have seen, these “paradoxes” have involved simple errors in the use of deontic logic – errors that become obvious when the deontic statements are translated into statements about possible worlds.

There are limitations to deontic logic, however. For example, if we say that it is obligatory not to steal, this means that, in all better possible worlds, nobody steals. If we also say that it is obligatory to punish thieves, this means that, in all better possible worlds, thieves are punished. However, if it is obligatory not to steal, better possible worlds have no thieves, so the two statements do not combine well.

Some people would, no doubt, suggest that fiction like that of Dostoevsky is a better tool than logic for exploring such issues. In cases where the writer is a genius, they are probably right.


In this post series: logic of necessary truth, logic of belief, logic of knowledge, logic of obligation


Modal logic, knowledge, and an old joke

Recently, I posted about necessary truth and about the logic of belief. I would like to follow up on that by discussing epistemic logic, the logic of knowledge. Knowledge is traditionally understood as justified true belief (more on that below), and we can capture the concept of knowledge using the 4 rules of S4 modal logic. These are in fact the same 4 rules that I used for for necessary truth, and the first 3 rules are the same as those I used for belief (the fourth rule adds the fact that knowledge is true).

Knowledge is specific to some person, and I am replacing the previous modal operators with  Ⓚ  which is intended to be read as “John knows” (hence the K in the circle):

  • if P is any tautology, then  Ⓚ P
  • if  Ⓚ P  and  Ⓚ (PQ)  then  Ⓚ Q
  • if  Ⓚ P  then  Ⓚ Ⓚ P
  • if  Ⓚ P  then  P

For those who prefer words rather than symbols:

  • if P is any tautology, then John knows P
  • if John knows both P and (P implies Q), then John knows Q
  • if John knows P, then John knows that he knows P
  • if John knows P, then P is true

Epistemic logic is useful for reasoning about, among other things, electronic commerce (see this paper of mine from 2000). How does a bank know that an account-holder is authorising a given transaction? Especially if deceptive fraudsters are around? Epistemic logic can highlight which of the bank’s decisions are truly justified. For this application, the first rule (which implies knowing all of mathematics) actually works, because both the bank’s computer and the account-holder’s device can do quite sophisticated arithmetic, and hence know all the mathematical facts relevant to the transaction they are engaged in.

But let’s get back to the idea of knowledge being justified true belief. In his Theaetetus, Plato has Theaetetus suggest exactly that:

Oh yes, I remember now, Socrates, having heard someone make the distinction, but I had forgotten it. He said that knowledge was true opinion accompanied by reason [ἔφη δὲ τὴν μὲν μετὰ λόγου], but that unreasoning true opinion was outside of the sphere of knowledge; and matters of which there is not a rational explanation are unknowable – yes, that is what he called them – and those of which there is are knowable.” (Theaetetus, 201c)

Although he also uses essentially this same definition in other dialogues, Plato goes on to show that it isn’t entirely clear what kind of “justification” or “reason” is necessary to have true knowledge. In a brief 1963 paper entitled “Is Justified True Belief Knowledge?,” the philosopher Edmund Gettier famously took issue with the whole concept of justified true belief, and provided what seemed to be counterexamples.

My personal opinion, which I have argued elsewhere, is that “justified true belief” works fine as a definition of knowledge, as long as the justification is rigorous enough to exclude beliefs which are “accidentally correct.” For analysing things like electronic commerce, a sufficient level of rigour would involve the use of epistemic logic, as described above.

One of Gettier’s supposed counterexamples involves a proposition of the form  P ∨ Q  (P or Q) such that:

  • Smith believes and knows  P ⇒ (PQ)
  • Smith believes P
  • P is false
  • Q is true, and therefore so is  P ∨ Q

From these propositions we can use doxastic logic to infer that Smith believes the true statement  P ∨ Q,  but we cannot infer (using epistemic logic) that Smith knows  P ∨ Q. A famous old joke is perhaps relevant here:

A physicist, a philosopher, and a mathematician are travelling through Scotland by train. Through the window, they observe a black sheep in a field. ‘Aha,’ says the physicist, ‘I see that Scottish sheep are black!’ The philosopher responds, ‘No! Some Scottish sheep are black!’ The mathematician, looking shocked, replies: ‘What are you guys saying? All we know is that at least one sheep in Scotland is black on at least one side.’


In this post series: logic of necessary truth, logic of belief, logic of knowledge, logic of obligation


Modal logic, belief, and the “flat earth”

Recently, I posted about necessary truth. I would like to follow up on that by discussing doxastic logic, the logic of belief. We can capture this concept using the 3 rules of K4 modal logic, which are in fact identical to the first 3 rules for necessary truth. The main difference is that beliefs need not be true.

Since beliefs are specific to some believing person, I am replacing the modal operator  □  with  Ⓙ  which is intended to be read as “John believes” (hence the J in the circle):

  • if P is any tautology, then  Ⓙ P
  • if  Ⓙ P  and  Ⓙ (PQ)  then  Ⓙ Q
  • if  Ⓙ P  then  Ⓙ Ⓙ P

For those who prefer words rather than symbols:

  • if P is any tautology, then John believes P
  • if John believes both P and (P implies Q), then John believes Q
  • if John believes P, then John believes that he believes P

These rules are very useful for helping computer systems (such as autonomous vehicles) reason about the beliefs of other entities (“If John believed a car was coming, he would not cross the road. But he is crossing the road. Therefore he does not believe that a car is coming. We should warn him.”).

As stated above, however, the rules are extremely optimistic about John’s knowledge of mathematics and logic. For some applications, we may need to assume that John believes less of that stuff. There is also a problem in assuming that John accepts the logical consequences of his beliefs. Real people do not always do that. Some years ago, I posted about the idea of a flat earth (an idea that medieval people were too wise to accept). Most believers in a “flat earth” do not accept the logical consequences of their beliefs. In particular, for the most popular “flat earth” model, sunsets would never be observed, because the sun always remains above the “disc of the earth.” Flat-earthers refuse to admit such consequences. Common air travel routes to and from Australia would also be impossible (see below), but flat-earthers generally realise the incompatibility of those routes, and simply deny that they exist. Logic is perhaps not the best tool for describing such patterns of thought.

The meaning of doxastic statements can be described using Kripke semantics, which exploits the idea of possible worlds (i.e. alternate universes). To say that John believes some statement is to say that the statement is true in the alternate universes that John thinks he might be living in. In those alternate universes, the earth might indeed be flat.


In this post series: logic of necessary truth, logic of belief, logic of knowledge, logic of obligation


Modal logic, necessity, and science fiction

A necessary truth is one that is true in all possible universes. We can capture the concept of necessary truth with the 4 rules of S4 modal logic (where □ is read “necessarily”):

  • if P is any tautology, then  □ P
  • if  □ P  and  □ (PQ)  then  □ Q
  • if  □ P  then  □ □ P
  • if  □ P  then  P

For those who prefer words rather than symbols:

  • if P is any tautology, then P is necessarily true
  • if P and (P implies Q) are both necessarily true, then Q is necessarily true
  • if P is necessarily true, then it is necessarily true that P is necessarily true
  • if P is necessarily true, then P is true (in our universe, among others)

The first rule implies that the truths of mathematics and logic (□ 2 + 2 = 4, etc.) are necessary truths (they must obviously be so, since one cannot consistently imagine an alternate universe where they are false). The second rule implies that the necessary truths include all logical consequences of necessary truths. The last two rules imply that  □ P  is equivalent to  □ □ P,  □ □ □ P,  etc. In other words, there is only one level of “necessary” that needs to be considered.

As it stands, these rules only allow us to infer the truths of mathematics and logic (such as  □ 2 + 2 = 4). One must add other necessary axioms to get more necessary truths than that. A Christian or Muslim might, for example, add “Necessarily, God exists,” and spend time exploring the logical consequences of that.

Countless things that are true in our universe are not necessarily true, such as “Water freezes at 0°C” or “Trees are green” or “Bill Clinton was President of the United States in the year 2000.”

For historical truths like the latter, it’s obvious that they are contingent on events, rather than being necessary. There is a substantial body of “alternate history” fiction which explores alternatives for such contingent truths, such as these four novels (pictured above):

  • Fatherland (Robert Harris, 1992): a detective story set in a universe where Hitler won the war; it is the week leading up to his 75th birthday (3.99 on Goodreads)
  • The Peshawar Lancers (S.M. Stirling, 2002): European civilisation is destroyed by the impact of comet fragments in 1878; a new Kiplingesque Anglo-Indian steampunk civilisation arises (3.86 on Goodreads)
  • SS-GB (Len Deighton, 1978): Hitler defeats Britain in 1941; British police face moral dilemmas cooperating with the SS (3.74 on Goodreads)
  • Romanitas (Sophia McDougall, 2005): the Roman Empire is alive and well in present-day London; slaves are still crucified (3.24 on Goodreads; first of a trilogy)

Three plant pigments: green beech, brown kelp, and red gracilaria algae (cropped from photographs by Simon Burchell, Stef Maruch, and Eric Moody)

The truths of biology are just as contingent as the truths of history. Trees are (mostly) green, but even on our own planet, brown and red are viable alternative colours for plants. From an evolutionary perspective, Stephen Jay Gould expresses the contingency this way:

any replay of the tape [of life] would lead evolution down a pathway radically different from the road actually taken.” (Stephen Jay Gould, Wonderful Life: The Burgess Shale and the Nature of History, 1989)

(some of his colleagues would take issue with the word “radically,” but still accept the word “different”). From a Christian point of view, the contingency of biology follows from the doctrine of the “Free Creation” of God, independently of any beliefs about evolution. To quote Protestant theologian Louis Berkhof:

God determines voluntarily what and whom He will create, and the times, places, and circumstances, of their lives.” (Louis Berkhof, Systematic Theology, Part I, VII, D.1.c)

The Catholic Church shares the same view, as none other than Thomas Aquinas makes clear (using the terminology of necessary truth):

It seems that whatever God wills He wills necessarily. For everything eternal is necessary. But whatever God wills, He wills from eternity, for otherwise His will would be mutable. Therefore whatever He wills, He wills necessarily. … On the contrary, The Apostle says (Ephesians 1:11): ‘Who works all things according to the counsel of His will.’ Now, what we work according to the counsel of the will, we do not will necessarily. Therefore God does not will necessarily whatever He wills.” (Summa Theologiae, Part I, 19.3)

Having taken this line, one might ask why mathematical truths are necessary rather than contingent. The astronomer Johannes Kepler resolves this problem this by telling us that they are not created:

Geometry existed before the Creation, is co-eternal with the mind of God.” (Johannes Kepler, Harmonices Mundi)

In fiction, alternative biologies are normally explored in the context of some other planet, because alternate earths are pretty much logically equivalent to other planets. Here are four examples of fictional biology:

  • Out of the Silent Planet (C.S. Lewis, 1938): written from a Christian perspective, this novel has three intelligent humanoid alien species living on the planet Mars (3.92 on Goodreads; see also my book review)
  • The Mote in God’s Eye (Larry Niven and Jerry Pournelle, 1974): this novel is one of the best alien-contact novels ever written (4.07 on Goodreads)
  • the xenomorph from the film Aliens (1986)
  • the Klingon character Worf from the TV series Star Trek: The Next Generation (1987–1994)

The truths of physics are contingent as well; our universe could have been set up to run on different rules. Science fiction authors often tweak the laws of physics slightly in order to make the plot work (most frequently, to allow interstellar travel). Fantasy authors invent alternate universes which differ from ours far more dramatically:

  • Dune (Frank Herbert, 1965): faster-than-light travel is a feature of the plot; it follows that interstellar navigation requires looking into the future (4.25 on Goodreads; see also my book review)
  • Great North Road (Peter F. Hamilton, 2012): “Stargate” style portals are a key feature of this novel (4.07 on Goodreads)
  • The Many-Coloured Land (Julian May, 1981): a science fiction incorporating psychic powers (4.07 on Goodreads; first of a series)
  • Magician (Raymond E. Feist, 1982): a classic fantasy novel which explores some of the internal logic of magic along the way (4.31 on Goodreads; first of a series)

Because mathematical truths are necessary truths, they are potentially common ground with intelligent aliens. This is one theme in the book (later film) Contact:

‘No, look at it this way,’ she said smiling. ‘This is a beacon. It’s an announcement signal. It’s designed to attract our attention. We get strange patterns of pulses from quasars and pulsars and radio galaxies and God-knows-what. But prime numbers are very specific, very artificial. No even number is prime, for example. It’s hard to imagine some radiating plasma or exploding galaxy sending out a regular set of mathematical signals like this. The prime numbers are to attract our attention.’” (Carl Sagan, Contact, 1985; 4.14 on Goodreads)

Of course, Carl Sagan or his editor should have realised that 2 is prime. Even intelligent beings can make mistakes.


In this post series: logic of necessary truth, logic of belief, logic of knowledge, logic of obligation


Brouwer and his fixed point theorem

    

The Brouwer fixed-point theorem is one of my favourite mathematical theorems. It is named after the Dutch mathematician Luitzen Egbertus Jan Brouwer (above right). Brouwer is also known for his work in Intuitionism. I have mentioned the Brouwer fixed-point theorem before.

The theorem states that any continuous function f on a compact convex set (and specifically, on a disc in the plane) will have at least one fixed point – that is, there will be at least one point p such that f(p) = p. The picture below is intended to illustrate the theorem; it is explained further down.

In the case of a disc, the theorem can be proved by contradiction. Assume that f(p) ≠ p for every point p. Then the pair of f(p) and p always defines a continuous mapping g from p to the boundary of the disc, as illustrated above (left). However, such a continuous mapping is impossible (for complex reasons, but in simple terms, because it creates a hole, which continuous mappings cannot do).

So what about that picture? It shows a continuous function f from the disc to itself, combining an irregular rotation about the centre (rotating least towards the east of the disc) with a “folding” operation that leaves the centre and boundary untouched. The picture below shows a cross-section of the folding in action. The shades of blue in the picture above show how far each point p is from f(p), with lighter colours representing smaller values. Arrows show the action of the function on 6 randomly chosen points. There are two fixed points, marked with black dots: the centre and one other point where the folding and the irregular rotation cancel each other out.

The three-dimensional version of the theorem tells us that, when I stir my morning cup of coffee, at least one speck of liquid will wind up exactly where it started.


Pi Day!

Pi Day is coming up again (3/14 as a US date). The number π is, of course, 3.14159265… Here are some possible activities for children:

  • Search for your birthday (or any other number) in the digits of π
  • Follow in the footsteps of Archimedes, showing that π is between 22/7 = 3.1429 and 223/71 = 3.1408.
  • Calculate 333/106 = 3.1415 and 355/113 = 3.1415929, which are better approximations than 22/7.
  • Measure the circumference and diameter of a round plate and divide. Use a ruler to measure the diameter and a strip of paper (afterwards measured with a ruler) for the circumference. For children who cannot yet divide, try to find a plate with diameter 7, 106, or 113.
  • Calculate π by measuring the area of a circle (most simply, with radius 10 or 100), using A = πr2. An easy way is to draw an appropriate circle on a sheet of graph paper.

You can also try estimating π using Buffon’s needle. You will need some toothpicks (or similar) of length k and some parallel lines (such as floorboards) a distance d apart (greater than or equal to k). Then the fraction of dropped toothpicks that touch or cross a line will be 2 k / (π d), or 2 / π if k = d. There is an explanation and simulator here (see also the picture below). And, of course, you can bake a celebratory pie and listen to Kate Bush singing π, mostly correctly!

This picture by McZusatz has 11 of 17 matches touching a line, suggesting the value of 2×17/11 = 3.1 for π (since k = d).

Actually, of course, π = 3.1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679 8214808651 3282306647 0938446095 5058223172 5359408128 … (digits in red are sung by Kate Bush, accurately, although some have said otherwise).


Fast Fibonacci numbers

There was some discussion on reddit recently of the Fibonacci numbers (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1,597, 2,584, 4,181, 6,765, 10,946, 17,711, 28,657, 46,368, 75,025, 121,393, 196,418, 317,811, 514,229, 832,040, …) and efficient ways of calculating them.

One way of doing so is using numbers of the form a + b σ where  σ is the square root of 5. Multiplication of such numbers satisfies:

(a + b σ) × (c + d σ) = ac + 5bd + (ad + bc) σ.

We can define the golden ratio φ = (1 + σ) / 2 and also ψ = 1 − φ = (1 − σ) / 2, in which case the nth Fibonacci number Fn will be exactly (φn − ψn) / σ. This is known as Binet’s formula.

We can use this formula to calculate Fibonacci numbers using only integer arithmetic, without ever evaluating the σ. We will have:

(2 φ)n − (2 ψ)n = (1 + σ)n − (1 − σ)n = 0 + p σ

for some integer p, and division by a power of two will give Fn = p / 2n.

I am using the R language, with the gmp package, which provides support for large integer matrices, and this allows us to use the relationship:

If we call this matrix A and calculate An−1, the first number in the resultant matrix will be the nth Fibonacci number Fn. The following R code calculates F10 = 55 using a combination of multiplication and squaring:

n <- 10

A <- matrix.bigz(c(
	1, 1,
	1, 0), 2)

p <- function(n) {
	if (n == 1) A
	else if (n %% 2 == 1) A %*% p(n-1)
	else {
		b <- p(n/2)
		b %*% b
	}
}

p(n-1)[1,1]

This same code will calculate, for example:

The time taken to calculate Fn is approximately proportional to n1.156, with the case of n = 1,000,000,000 (giving a number with 208,987,640 digits) taking about a minute.