#Tale of logic become algebra

#Leibniz dream sit on shelf

End of last tale, old big brain Leibniz have dream. Two big brain club each other, everyone hurt, no one win. Leibniz say: what if argue could be like sum? Two big brain disagree, both sit at machine, both turn handle, machine give answer. Calculemus. Let us calculate.

Beautiful dream. Useless dream. To calculate reasoning, you need rules for reasoning. Not just rules for sum. Rules that say and, or, not, if like rules say plus and minus. Leibniz never have these rules. Nobody for two hundred winter have these rules.

Then in year 1846, in big island called Britain, two big brain start clubbing each other in public over logic. Big clubs use. In journal where everyone read. Their clubbing useless, but it reach quiet man in city of Lincoln. Quiet man read about it and have small thought. Small thought turn out to be the rules.

Tale of how that happen.

#Aristotle still rule logic

First grug must say what logic look like before quiet man come.

Long time ago, big brain Aristotle write down rules for argue. Rules called syllogism. Look like this: all men are mortal. Socrates is a man. Therefore Socrates is mortal. Two starting sentence. One conclusion. Move from starting to conclusion follow strict pattern. Aristotle list patterns and give them names. Barbara. Celarent. Darii. Ferio. Hundreds of years, students learn the names.

Two thousand winter pass. Roman go to ancient spirits. Christian come. Christian go. Renaissance come. Renaissance go. Steam engine come. Through all of this, logic still mean Aristotle’s syllogism. In year 1826, Cambridge man named Whately write big book that say syllogism still good, still alive, still the right way to do logic. Book very popular. Students keep learning Barbara and Celarent.

But syllogism have problem. Three problem.

Problem one: syllogism only handle simple sentence. All A is B. Some A is B. That’s it. Cannot say “A and B together” or “if A then B”. Compound thinking just not in the toolbox.

Problem two: syllogism can talk about subject of sentence (“all men”) but not really about predicate (“are mortal”). Cannot say “all of A is all of B” properly. Big brain at Edinburgh named Sir William Hamilton (NOT the Irish big brain William Rowan Hamilton who invent quaternion. Totally different big brain, both called Hamilton, both Sir, both knighted, this confuse everyone for hundred winter, grug just want to say it once: the Edinburgh one) try to fix this. He call the fix “quantification of the predicate”. Sound boring. Was boring.

Problem three, biggest problem: syllogism cannot do mathematics. When mathematician try to write proof in syllogism form, the form just break. Mathematician say: this not the right shape for our work.

So by 1840, several big brain in Britain getting frustrated with old craft. They want logic that work like algebra. Symbols. Rules. Manipulate. Done.

They just cannot find it.

#two big brain club each other

Year 1846. London. Big brain Augustus De Morgan, Professor of Mathematics at University College London, write paper about syllogism. Send draft to friend Whewell at Cambridge. Whewell hold draft, plan to read paper at Cambridge meeting.

While paper sit with Whewell, De Morgan get letter from Edinburgh big brain Sir William Hamilton. Letter contain Hamilton’s own idea about quantification of the predicate. De Morgan ask Whewell for draft back. De Morgan make some change to draft. Then De Morgan publish.

Hamilton see published paper. Hamilton blow up. Hamilton accuse De Morgan of stealing his idea. Plagiarism, Hamilton call it. De Morgan say: my changes was already in the works, Hamilton’s letter not the source. Public clubbing follow. In journals. In pamphlets. For winter on winter.

Modern big brain who study this all conclude same thing: De Morgan not steal anything. Hamilton’s “quantification of the predicate” and De Morgan’s logic of relations are just different idea, both interesting, neither one’s property. But the clubbing itself was loud and ugly and could not be settled. Two big brain. Both think they right. Everyone hurt. No one win.

Exactly the situation Leibniz dream about.

Quiet shoemaker’s son in Lincoln read about the clubbing in spring of 1847. He write later, in preface of book he was about to publish:

In the spring of the present year my attention was directed to the question then moved between Sir W. Hamilton and Professor De Morgan; and I was induced by the interest which it inspired, to resume the almost-forgotten thread of former inquiries.

#shoemaker son listen

Now grug must tell who Boole was.

George Boole born in Lincoln, year 1815. Same winter as Lovelace, who grug already meet. Father John Boole make and repair shoes. Family poor. Father was sweet man who liked science more than shoes, and shoes bring more shiny rocks than science.

Father teach George Latin. George teach himself the rest. When father’s shoe business fail, George was sixteen winter old. He become the one bringing shiny rocks home. He take job teaching at school in town called Doncaster, and between lessons he teach himself mathematics from a textbook in tongue of France. Old story say it took him two weeks just to figure out what one page meant.

George keep teaching, keep reading. He start writing papers. Cambridge big brain Duncan Gregory like the papers. Gregory and De Morgan recommend Boole’s longer paper for the Royal Society’s Philosophical Transactions. In year 1844, Royal Society give George Boole the Royal Medal for it. First Royal Medal ever given for mathematics. Boole was 29 winter old. He had no university degree. He had no university anything. He was a school-keeper from Lincoln who taught himself out of books in tongue of France.

By spring 1847, when Boole read about De Morgan and Hamilton clubbing each other, an idea about logic was already in him. Had been in him for many winter. The clubbing was the spark, not the fuel.

#Boole have idea

Boole sit down in 1847 and write fast. Eighty-two pages. The book come out in November 1847. Title: The Mathematical Analysis of Logic, Being an Essay Towards a Calculus of Deductive Reasoning.

Same month. Possibly same week. Old story even say same day, but grug not trust the same-day story. De Morgan publish his own book on logic. Called Formal Logic. They are friends. They have been writing letters for five winter already. They are not racing. They are both, on their own, doing what logic had needed for two thousand winter.

Boole’s book is grug’s main subject. Here is what it contain.

#Boole make algebra of true and false

Boole’s idea is small. Boole’s idea is huge. Both true.

Take some property. Say, “is a man”. Call it x. Take another property. Say, “is mortal”. Call it y. Now Boole say: treat x and y like algebra symbols. Multiply them together. xy means “select the things that are x, then from those select the things that are also y“. So xy mean “is a man AND is mortal”.

Multiplication is and.

Add them together. x + y mean “the things that are x, combined with the things that are y“. Boole’s plus is a little weird. He treat it as exclusive: it only works cleanly when x and y don’t overlap. Later big brain (Jevons, Peirce, Schröder) tidy this up so plus mean inclusive or, the or we use today. But Boole’s spirit is right.

Addition is or.

Now subtraction. Use the symbol 1 to mean “everything in the world we are talking about”. The whole universe of discourse. Then 1 − x mean “everything that is not x“. So if x is “is a man”, then 1 − x is “is not a man”.

One minus is not.

Three operations. Multiply for AND. Add for OR. One-minus for NOT. Boole now have algebra of logic.

Then Boole notice the law that make the whole thing work. If you multiply x by itself, you get xx, which is “select the x things, then from those select the x things again”. But selecting x from x just give you x back. So xx = x. Or, written like algebra, x² = x.

Boole call this the index law. It is the strangest equation in the book, because in ordinary algebra x² = x only have two solutions: x = 0 and x = 1. Everywhere else it false. And right there, Boole quietly point out: yes. That is the point. In this algebra, every variable is either 0 or 1. True or false. On or off. The law of the system forces it.

Two hundred winter before, Leibniz invent binary numbers and think they were a curiosity. Now Boole’s algebra of reasoning turn out to live in binary. Same 0 and 1. Coincidence, but big coincidence.

Boole now write down the laws of his system. Some of them are obvious from the algebra:

• x · 1 = x (everything that is x and also in the universe is just x).
• x(1 − x) = 0 (nothing is both x and not-x. Aristotle’s law of non-contradiction, now an equation).
• x + (1 − x) = 1 (everything is either x or not-x. Law of excluded middle, also now an equation).
• 1 − (1 − x) = x (not-not-x is just x. Double negation, trivial in this algebra).
• xy = yx (order of AND doesn’t matter).
• x(y + z) = xy + xz (AND distributes over OR).

Two thousand winter of Aristotle’s laws of thought. Boole reduce them to half a page of algebra.

His friend De Morgan, in Formal Logic the same November, contribute two more rules that Boole’s system needs and that nobody else had written down properly. The rules say: not (A and B) = (not A) or (not B), and not (A or B) = (not A) and (not B). We still call these De Morgan’s laws today. They are exactly what they look like: rules for pushing a NOT inside a parenthesis. De Morgan put them in his book. They have been called De Morgan’s laws ever since.

One thing Boole did not invent, and grug must be careful here: Boole did not invent truth tables. Modern reader who learn Boolean logic in school learn it by drawing little tables of T and F and filling in the result. These tables are not in Boole’s books. They were not in any book in 1847. Truth tables come about fifty winter later. Charles Sanders Peirce write one in a notebook in 1893 but never publish. Wittgenstein, Post, and Łukasiewicz invent and publish them on their own around 1921. Peirce had it first but kept it in his drawer. Wittgenstein make it famous. Boole did not have them. Boole prove things by manipulating equations.

So Boole’s Mathematical Analysis of Logic contain: the three operations (AND, OR, NOT), the index law, the laws of non-contradiction and excluded middle written as algebra, the algebraic method for solving syllogisms, and a fresh way to do every syllogism Aristotle had named in two thousand winter. In eighty-two pages.

Boole consider it a rough draft.

#Laws of Thought come later

Seven winter later, in 1854, Boole publish the version he consider proper. Title: An Investigation of the Laws of Thought, on Which are Founded the Mathematical Theories of Logic and Probabilities.

More careful. Add a calculus of probability on top of the calculus of logic. Boole notice that probability is just logic where the values are between 0 and 1 instead of being only 0 or 1. He prove a long list of theorems. He clean up the use of the plus sign. He give the system its mature face.

The famous line from the book, quoted by everyone after, is Boole’s declaration of where logic now belong:

We ought no longer to associate Logic and Metaphysics, but Logic and Mathematics.

Two thousand winter, logic was a branch of philosophy. Boole pull it across the line. Logic now mathematics. Logic now have rules you can compute with. Logic now is a kind of arithmetic. Arithmetic with only two numbers in it, but arithmetic.

This is the moment. From here on, true and false behave like 0 and 1. AND and OR behave like times and plus. NOT behave like one-minus. Reasoning is something you calculate.

Leibniz’s calculemus now have rules.

It still has no machine.

#everyone in same room, nobody connect dots

Now grug come to the part of the tale that hurt to tell.

In London and Cambridge in the 1840s and 1850s, the big brain of Britain who care about logic and machines all know each other. De Morgan is Babbage’s friend, write a paper in 1848 defending Babbage’s calculating machine. De Morgan is Boole’s friend, write letters for twenty-two winter, from 1842 until Boole gone to ancient spirits in 1864. De Morgan is Lovelace’s tutor. Yes. Same Lovelace from the last tale. He send her problems. She send him solutions. Lovelace’s copy of the calculus textbook still survive with thirty-five notes in her ink and eighteen in De Morgan’s pencil. Babbage and Lovelace meet in 1833. Babbage’s Saturday-evening parties draw half of London science: Faraday, Darwin, Dickens, Mary Somerville, the Carlyles.

The only two who never become friends, in all these winter, are Boole and Babbage. Boole in Cork, Babbage in London. They meet exactly once. Year 1862. International Exhibition in London. Boole travel from Cork. Babbage show him the working pieces of the Difference Engine. After the meeting Boole write Babbage one short thank-you letter, dated 15 October 1862:

I shall endeavour to acquaint myself with Menabrea’s paper and the principle of the Jacquard loom… it was a pleasure and an honour to me to meet you.

That is the whole correspondence. One meeting, one letter, no more.

Menabrea’s paper. The same paper Lovelace translated and wrote her Notes on, twenty winter earlier. Babbage tell Boole, in 1862: go read what my friend Lovelace wrote. Lovelace had been gone to ancient spirits already for ten winter by then.

Reader will remember from the last tale: Lovelace see in her Notes that the Analytical Engine could work on any thing made of symbol and rule, not just number. Boole’s algebra is exactly that: symbols and rules. Lovelace would have understood Boole’s book completely. The two pieces fit together. They needed only to be put in the same room.

They were in the same room. The room was empty of anyone who saw both at once.

This always make grug a bit sad. The man who turn logic into algebra and the man who design a machine that follow rules met for a few hours in 1862 and shook hands and parted, and Boole was sent to ancient spirits two winter later, and Babbage two winter after that. Then time demon eat the connection. Chew on it for ninety winter. Spit it out in the year 1937, into the hands of a twenty-one winter old at MIT, who would have to read Boole’s book and rediscover everything from scratch. Grug come to him in a few tales’ time.

The information was all there. The wiring was missing.

#Boole gone too young

November 1864. Boole walk three miles to lecture in heavy rain, give his lecture in wet clothes, take a chill. His wife, Mary Everest Boole, was a follower of homeopathy: like cures like. The rain that made him sick, she now applied to him as cure: cold water, wet sheets. Eighth of December. Boole go to ancient spirits. Forty-nine winter old.

Ten more winter at most of strong work in him, gone. The bridge from his algebra to a machine must wait seventy more winter, must be built by people who must discover his book all over again.

#Frege try once more

One last figure must enter the tale, briefly, because he set up the next tale.

Gottlob Frege, born 1848, German big brain, lived almost his whole working life at the University of Jena. Frege look at Boole’s work and at the two thousand winter of philosophy behind it and say: not enough. Boole give us an algebra of classes. Not enough. He want an algebra of all reasoning, including the kind of reasoning where you say “for every number n, there exists a prime greater than n“. For-every. There-exists. Boole’s algebra had no clean way to handle these.

Year 1879. Frege publish a small book called Begriffsschrift. The name mean “Concept Notation”. In it he invent, more or less single-handed, modern logic with quantifiers. The book look strange. Two-dimensional symbols. Almost nobody read it at first.

Then Frege start a much bigger project. He try to do something Leibniz had only dreamed of and Boole had not attempted: to build all of mathematics out of pure logic. Numbers, addition, the whole tower. Show that every mathematical truth is, when you look closely, a logical truth. The project is called logicism.

Volume one of his book, Grundgesetze der Arithmetik (Basic Laws of Arithmetic), appear in 1893. Volume two go to the printer in 1902. Frege is fifty-three winter old. He has been working on this for twenty-five winter. The foundation of all mathematics is about to be laid.

Then a letter arrive at his door. The letter break everything.

Grug come to the letter in the next tale.

#what grug learn

Boole take logic, two thousand winter old, and turn it into algebra. AND become times. OR become plus. NOT become one-minus. The variables are 0 or 1, true or false, nothing in between. And once it is algebra, you can manipulate it. You can prove things by moving symbols around, the way schoolchild move symbols around to solve for x.

Aristotle’s laws of thought become equations. x(1 − x) = 0 is non-contradiction. x + (1 − x) = 1 is excluded middle. x² = x is the strange law that force every variable to be 0 or 1. The law that quietly say this whole algebra lives in binary.

This is what Leibniz had dreamed of. This is calculemus. Two big brain disagree, sit at the algebra, manipulate, find the answer. No more shouting needed. (Of course, in real life the shouting never stops, because most disagreements are not actually about logic. But for the disagreements that are about logic, Boole now have the rules.)

Rules without a machine. Rules that rest on nothing. Both gaps will close eventually. They close slowly.

#what grug worry about next

Boole ask one question and answer it: can reasoning be made into algebra? Yes. Boole show how.

But this open up a bigger question. If reasoning is algebra, and all of mathematics rest on reasoning, then what can mathematics actually prove? Where is the edge? Are there true things no proof can reach? Are there questions even a perfect machine, with all of Boole’s algebra running clean, cannot settle?

Nobody know yet. Some big brain will try to nail mathematics down so tight that nothing escape. Other big brain will discover something terrible about the very idea of nailing things down.

Grug come to them next.