Lesson 00

How to use this course

Augustus De Morgan proved no single famous theorem. His influence came through teaching, writing and argument. For nearly forty years he taught mathematics at University College London, to students who included James Joseph Sylvester, Isaac Todhunter, Edward Routh and William Stanley Jevons, and by letter to Ada Lovelace. He wrote some 700 encyclopaedia articles, named mathematical induction, set limits at the base of the calculus, and with George Boole turned logic into a branch of mathematics. His name survives in De Morgan’s laws, in the four-colour problem he spread, and in the London Mathematical Society he helped found.

Prerequisites for Part II

First-year calculus and series.
Basic set notation and propositional logic.
For Lesson 06, linear algebra (eigenvalues); for Lesson 10, the language of graphs.

Each technical lesson opens with a paragraph for the general reader, then gives precise statements, proofs and exercises with folded solutions. The lessons follow the chronology of his work: induction and calculus (1830s), algebra (1839–1849), logic (1846–1860), and the problems he passed on to others.

Reference

Timeline

1806	Born 27 June at Madura (now Madurai), Madras Presidency, India, son of Lieutenant-Colonel John De Morgan. Loses the sight of his right eye in infancy.
1816	His father dies.
1823	Enters Trinity College, Cambridge; taught by George Peacock and William Whewell.
1827	Fourth wrangler. Refuses the religious test required for an MA or fellowship.
1828	23 February: appointed first professor of mathematics at the new London University, aged 21. Fellow of the Astronomical Society.
1830	Elements of Arithmetic.
1831	Resigns his chair in protest at the dismissal of a colleague. Becomes secretary of the Astronomical Society (to 1839).
1836	Reappointed after his successor drowns. The Differential and Integral Calculus.
1837	Marries Sophia Elizabeth Frend, daughter of William Frend.
1838	Article “Induction (Mathematics)” in the Penny Cyclopaedia names mathematical induction. Essay on Probabilities.
1839–44	Four papers “On the foundation of algebra”.
1840–41	Teaches Ada Lovelace by correspondence.
1842	Begins a lifelong friendship and correspondence with George Boole.
1846–47	“On the structure of the syllogism”; priority dispute with the Edinburgh philosopher Sir William Hamilton. Formal Logic (1847).
1849	Trigonometry and Double Algebra.
1852	23 October: writes to William Rowan Hamilton about Francis Guthrie’s four-colour question.
1860	“On the syllogism, No. IV”: the logic of relations. Syllabus of a Proposed System of Logic.
1865	First president of the London Mathematical Society.
1866	Resigns from University College over a matter of religious freedom.
1871	Dies 18 March in London; buried at Kensal Green.
1872	A Budget of Paradoxes, edited by Sophia De Morgan.

Part I · Formation

Lesson 01

Madura to Cambridge, 1806–1827

Augustus De Morgan was born on 27 June 1806 at Madura, now Madurai in Tamil Nadu, where his father, John De Morgan, served as a lieutenant-colonel in the Madras Native Infantry. His mother was Elizabeth Dodson. An eye infection soon after birth left him blind in the right eye. The family returned to England when he was an infant, and his father died in 1816.

He was taught by a series of private teachers in Devon and Somerset, then at a school at Redland, near Bristol, which he left at sixteen. In February 1823 he entered Trinity College, Cambridge, where George Peacock and William Whewell taught him mathematics. Both became lifelong friends. Peacock was then developing a “symbolic algebra” in which the laws of operation come first and their meaning second, a view that shaped De Morgan’s later work (Lesson 06).

He read widely and played the flute. In the Mathematical Tripos of 1827 he was placed fourth wrangler. To proceed to the MA, or to hold a fellowship, a Cambridge graduate had to subscribe to the doctrines of the Church of England. De Morgan, who held that religion should be no condition of learning, refused. Cambridge was closed to him, and so was Oxford. He entered Lincoln’s Inn to read for the bar.

Lesson 02

The new university in London, 1828–1836

In 1826 a group of reformers founded the London University, later University College, on the principle that no student or teacher would face a religious test. De Morgan applied for its chair of mathematics and on 23 February 1828, aged 21, became its first professor. His inaugural lecture was on the study of mathematics. The same year he was elected a fellow of the Astronomical Society of London; he served as its secretary from 1831 to 1839 and again from 1847 to 1855, and declined its presidency.

He was a demanding, clear and popular teacher. He was also prickly about principle. In 1831 the university’s council dismissed the professor of anatomy, Granville Sharp Pattison, without, in De Morgan’s view, proper regard for the rights of the professors. He resigned on 24 July 1831. For five years he lived by private teaching, writing and actuarial work for life assurance companies.

The writing was prodigious. He published Elements of Arithmetic (1830), still in use decades later, On the Study and Difficulties of Mathematics (1831), and textbooks on algebra and trigonometry. He began contributing to the Penny Cyclopaedia of the Society for the Diffusion of Useful Knowledge, eventually writing 712 articles for it. In 1836 his successor at London, George White, drowned in a boating accident, and De Morgan was invited back. He held the chair for another thirty years.

Lesson 03

Teacher, writer, correspondent, 1836–1850

On 3 August 1837 he married Sophia Elizabeth Frend, daughter of William Frend, a Cambridge mathematician and religious dissenter. They married in a registry office, without a church ceremony. They had seven children, three sons and four daughters, including the potter and novelist William De Morgan, the writer Mary De Morgan, and George Campbell De Morgan, an able mathematician. Sophia De Morgan was a reformer and writer in her own right, and after his death edited his memoir and his Budget of Paradoxes.

The decade after 1836 was his most productive. The Differential and Integral Calculus (1836) made limits the foundation of the subject (Lesson 05). His 1838 Penny Cyclopaedia article “Induction (Mathematics)” gave the method its name (Lesson 04). His Essay on Probabilities (1838) applied probability to insurance (Lesson 09). Four papers “On the foundation of algebra” (1839–1844) and Trigonometry and Double Algebra (1849) asked what the laws of algebra are and what they apply to (Lesson 06).

His students at University College included Sylvester, Todhunter, Routh, Jevons, the economist Walter Bagehot and the physicist Frederick Guthrie. From 1840 to 1841 he taught Ada Lovelace calculus by letter; in 1844 he told her mother, in confidence, that her daughter’s power of thought was quite exceptional. From 1842 he corresponded with George Boole, then an unknown schoolmaster in Lincoln, and they remained friends for life. In 1846 his paper on the syllogism provoked a bitter priority dispute with the Edinburgh philosopher Sir William Hamilton over the “quantification of the predicate”. The quarrel prompted Boole to write The Mathematical Analysis of Logic, which appeared in 1847 within weeks of De Morgan’s Formal Logic.

Part II · The mathematics

Lesson 04

Mathematical induction

For the general reader. To prove that a statement holds for every whole number, prove it for 1, then prove that whenever it holds for one number it holds for the next. The method is old: Pascal used it, and earlier writers came close. De Morgan gave it a name, “mathematical induction”, in 1838, and stated it as a general principle of proof, distinct from the inductive reasoning of the natural sciences.

Goals

State ordinary and strong induction precisely.
Prove their equivalence with the well-ordering principle.
Use induction to prove identities and inequalities.

Principle of mathematical induction

Let \(P(n)\) be a statement about natural numbers \(n\ge n_0\). If \(P(n_0)\) holds, and \(P(k)\Rightarrow P(k+1)\) for every \(k\ge n_0\), then \(P(n)\) holds for every \(n\ge n_0\).

Theorem

The following are equivalent as properties of \(\mathbb N=\{0,1,2,\dots\}\) with its usual order: (1) the principle of induction; (2) strong induction: if \(P(m)\) for all \(m<k\) implies \(P(k)\), for every \(k\), then \(P(n)\) for all \(n\); (3) well-ordering: every non-empty subset of \(\mathbb N\) has a least element.

Proof

(3)⇒(2): if \(P\) failed somewhere, the set of failures would have a least element \(k\); then \(P(m)\) holds for all \(m<k\), so \(P(k)\) holds, a contradiction. (2)⇒(1): ordinary induction hypotheses imply the strong ones, since \(P(k-1)\) is among the \(P(m)\), \(m<k\). (1)⇒(3): let \(S\) have no least element, and let \(Q(n)\) say that no \(m\le n\) lies in \(S\). \(Q(0)\) holds, since otherwise 0 would be least. If \(Q(k)\) holds and \(k+1\in S\), then \(k+1\) would be least; so \(Q(k+1)\). By induction \(Q(n)\) for all \(n\), so \(S\) is empty.

In De Morgan’s 1838 article the method was presented as a way to pass from a law verified in particular cases to the general law, with the step from one case to the next carrying the proof. Today induction is one of Peano’s axioms for the natural numbers, or a theorem of set theory.

Exercise 4.1Prove \(1+3+5+\cdots+(2n-1)=n^2\) by induction.

Show solution

For \(n=1\), both sides are 1. If the sum up to \(2k-1\) is \(k^2\), adding \(2k+1\) gives \(k^2+2k+1=(k+1)^2\).

Exercise 4.2Prove that \(2^n>n^2\) for all \(n\ge5\). Why does the induction step need \(k\ge3\)?

Show solution

\(2^5=32>25\). If \(2^k>k^2\) then \(2^{k+1}>2k^2\), and \(2k^2\ge(k+1)^2\) iff \(k^2-2k-1\ge0\) iff \(k\ge1+\sqrt2\), so for \(k\ge3\). The base case must still be checked separately: the statement fails for \(n=2,3,4\).

Exercise 4.3Use strong induction to prove that every integer \(n\ge2\) is a product of primes.

Show solution

If \(n\) is prime, done. Otherwise \(n=ab\) with \(2\le a,b<n\). By the strong hypothesis \(a\) and \(b\) are products of primes, hence so is \(n\).

Exercise 4.4Find the flaw: “All horses have the same colour. True for one horse. If any \(k\) horses share a colour, take \(k+1\) horses; the first \(k\) share a colour and so do the last \(k\), and these groups overlap, so all \(k+1\) do.”

Show solution

The step from \(k=1\) to \(k=2\) fails: the first horse and the last horse form groups with no common member. The implication \(P(k)\Rightarrow P(k+1)\) must hold for every \(k\ge n_0\), and here it fails at \(k=1\).

Lesson 05

Limits and the convergence of series

For the general reader. An infinite sum may settle to a value or may not. The simplest check, comparing each term with the one before, often fails to decide. De Morgan proposed a ladder of finer and finer tests, each able to decide cases the previous one could not. His textbook of 1836 also insisted that calculus rest on limits alone.

Goals

Prove the comparison lemma for ratios.
State and prove the ratio, Raabe and Bertrand tests as rungs of De Morgan’s hierarchy.
Apply each test where the earlier ones fail.

Comparing ratios

Lemma

Let \(a_n,b_n>0\). If \(\dfrac{a_{n+1}}{a_n}\le\dfrac{b_{n+1}}{b_n}\) for all large \(n\) and \(\sum b_n\) converges, then \(\sum a_n\) converges. If \(\dfrac{a_{n+1}}{a_n}\ge\dfrac{b_{n+1}}{b_n}\) for all large \(n\) and \(\sum b_n\) diverges, so does \(\sum a_n\).

Proof: the hypothesis says \(a_n/b_n\) is eventually non-increasing, so \(a_n\le Cb_n\); in the second case it is non-decreasing, so \(a_n\ge cb_n\) with \(c>0\). Each rung of the ladder uses a comparison series that converges or diverges more slowly than the last: geometric series, then \(\sum n^{-p}\), then \(\sum 1/(n(\ln n)^p)\).

De Morgan’s hierarchy (first three rungs)

Let \(a_n>0\) and \(r_n=a_n/a_{n+1}\).

(Ratio test) If \(r_n\to\rho\), the series converges for \(\rho>1\) and diverges for \(\rho<1\).
(Raabe’s test) If \(n(r_n-1)\to\rho\), the series converges for \(\rho>1\) and diverges for \(\rho<1\).
(Bertrand’s test, found independently by De Morgan) If \(\ln n\,\big(n(r_n-1)-1\big)\to\rho\), the series converges for \(\rho>1\) and diverges for \(\rho<1\).

Each test is inconclusive when \(\rho=1\), and the next rung may then decide.

Proof of Raabe’s test

Suppose \(n(r_n-1)\to\rho>1\) and choose \(1<p<q<\rho\). For \(b_n=n^{-p}\), \(b_n/b_{n+1}=(1+\tfrac1n)^p=1+\tfrac pn+O(n^{-2})\). Eventually \(r_n>1+\tfrac qn>b_n/b_{n+1}\), so \(a_{n+1}/a_n\le b_{n+1}/b_n\), and \(\sum n^{-p}\) converges. For \(\rho<1\), compare with \(b_n=1/n\) in the same way. Bertrand’s test is proved identically with \(b_n=1/(n(\ln n)^p)\), for which

\[ \frac{b_n}{b_{n+1}}=\Big(1+\frac1n\Big)\Big(\frac{\ln(n+1)}{\ln n}\Big)^p=1+\frac1n+\frac{p}{n\ln n}+O\Big(\frac1{n^2}\Big), \]

and \(\sum 1/(n(\ln n)^p)\) converges exactly when \(p>1\), by the integral test.

Exercise 5.1Let \(a_n=\Big(\dfrac{1\cdot3\cdots(2n-1)}{2\cdot4\cdots(2n)}\Big)^s\) with \(s>0\). Show that the ratio test fails and Raabe’s test gives convergence for \(s>2\), divergence for \(s<2\).

Show solution

\(r_n=\big(\frac{2n+2}{2n+1}\big)^s\to1\), so the ratio test is silent. \(r_n=\big(1+\frac1{2n+1}\big)^s=1+\frac{s}{2n+1}+O(n^{-2})\), so \(n(r_n-1)\to s/2\). Raabe: convergent for \(s>2\), divergent for \(s<2\).

Exercise 5.2Settle the case \(s=2\) of Exercise 5.1 with Bertrand’s test.

Show solution

\(r_n-1=\frac2{2n+1}+\frac1{(2n+1)^2}\), so \(n(r_n-1)-1=\frac{2n}{2n+1}+\frac{n}{(2n+1)^2}-1=\frac{-(n+1)}{(2n+1)^2}\sim-\frac1{4n}\). Multiplying by \(\ln n\) gives a limit of \(0<1\): the series diverges. Indeed \(a_n\sim\frac1{\pi n}\) by Wallis’s product.

Exercise 5.3Show that for \(a_n=1/(n(\ln n)^p)\) Raabe’s test gives \(\rho=1\) and Bertrand’s test gives \(\rho=p\).

Show solution

From the displayed expansion, \(n(r_n-1)=1+\frac{p}{\ln n}+O(\frac1n)\to1\), so Raabe is inconclusive. Then \(\ln n\,(n(r_n-1)-1)=p+O(\frac{\ln n}{n})\to p\). For \(p=1\) even Bertrand is inconclusive, and the next rung, with \(\ln\ln n\), is needed. No rung of the ladder decides every series.

Lesson 06

Double algebra and the search for a triple

For the general reader. Peacock had taught that algebra is a game of symbols whose rules come first. De Morgan pushed the question further: which rules, and what do the symbols stand for? A “double algebra” has symbols made of two parts, like complex numbers, which he interpreted as directed lines in the plane. He and William Rowan Hamilton both tried to build a triple algebra for space. Hamilton found that he needed four parts, the quaternions. Modern algebra explains why three cannot work.

Goals

Describe complex numbers as a double algebra of directed lines.
Check the laws that De Morgan required of an algebra.
Prove that no real division algebra has odd dimension greater than 1.

Directed lines

In Trigonometry and Double Algebra (1849) a symbol denotes a line of given length \(r\) and direction \(\theta\), written \(r(\cos\theta+\sqrt{-1}\sin\theta)\). Lines add by the parallelogram rule. They multiply by multiplying lengths and adding angles:

\[ r(\cos\theta+i\sin\theta)\cdot s(\cos\varphi+i\sin\varphi)=rs\big(\cos(\theta+\varphi)+i\sin(\theta+\varphi)\big). \]

De Morgan checked that these operations obey the familiar laws: addition and multiplication are associative and commutative, multiplication distributes over addition, and every non-zero line has an inverse. In his view an algebra was defined by such laws, and an interpretation was a separate question. This separation, shared with Peacock and Boole, prepared the ground for the abstract algebra of rings and fields.

Why there is no triple algebra

A real division algebra is a finite-dimensional real vector space \(D\) with a bilinear product, an identity element \(1\), and no zero divisors: \(xy=0\) implies \(x=0\) or \(y=0\). Associativity is not assumed.

Theorem

If \(D\) is a real division algebra of odd dimension, then \(\dim D=1\) and \(D=\mathbb R\).

Proof. Let \(x\in D\) and let \(L_x(y)=xy\). This is a linear map of a real vector space of odd dimension, so its characteristic polynomial has odd degree and a real root \(\lambda\). Choose \(y\ne0\) with \(xy=\lambda y\). Then \((x-\lambda1)y=0\), and since there are no zero divisors, \(x=\lambda1\). Every element is a real multiple of 1.

So no multiplication on \(\mathbb R^3\) extending the real numbers can avoid zero divisors. Hamilton escaped by moving to four dimensions in 1843. Later results go much further: Frobenius showed in 1877 that the associative ones are only \(\mathbb R,\mathbb C\) and the quaternions, and topology shows that the dimension must be 1, 2, 4 or 8.

Exercise 6.1Show that \(|zw|=|z|\,|w|\) for complex numbers, both from the directed-line rule and algebraically.

Show solution

Geometrically the lengths multiply by definition. Algebraically, with \(z=a+bi\), \(w=c+di\): \(|zw|^2=(ac-bd)^2+(ad+bc)^2=a^2c^2+b^2d^2+a^2d^2+b^2c^2=(a^2+b^2)(c^2+d^2)\).

Exercise 6.2The cross product on \(\mathbb R^3\) is bilinear. Exhibit zero divisors, and explain why it has no identity element.

Show solution

\(\mathbf u\times\mathbf u=0\) for every \(\mathbf u\ne0\). An identity \(\mathbf e\) would need \(\mathbf e\times\mathbf e=\mathbf e\), but \(\mathbf e\times\mathbf e=0\). It is also anticommutative and not associative.

Exercise 6.3Try the rule \((a,b,c)(a',b',c')=(aa'-bb'-cc',\ ab'+ba',\ ac'+ca')\) on \(\mathbb R^3\). Find a pair of zero divisors.

Show solution

Take \(x=(0,1,1)\), \(y=(0,1,-1)\): first coordinate \(0-1+1=0\), second \(0\), third \(0\). So \(xy=0\) with both factors non-zero, as the theorem predicts.

Lesson 07

Formal logic and De Morgan’s laws

For the general reader. “It is not true that it is cold or wet” means “it is not cold and it is not wet.” Medieval logicians knew such rules in words. De Morgan stated them as laws of a calculus of terms in his Formal Logic of 1847, using a letter for a term and another for its contrary. Together with Boole’s algebra, published the same year, his work began the transformation of logic into mathematics.

Goals

State De Morgan’s laws for propositions, sets and quantifiers.
Prove them by truth tables and by element-chasing.
Use them to transform formulas and circuits.

Terms and contraries

De Morgan wrote \(X\) for a term and \(x\) for its contrary, everything in the universe under consideration that is not \(X\). He insisted that the universe be specified: “not man” means not man among animals, or among things, depending on the discussion. The idea of a limited universe of discourse, usually credited to his 1846 paper, became standard through Boole. The contrary of “\(X\) or \(Y\)” is “\(x\) and \(y\)”; the contrary of “\(X\) and \(Y\)” is “\(x\) or \(y\)”.

De Morgan’s laws

For propositions: \(\neg(p\lor q)\equiv\neg p\land\neg q\) and \(\neg(p\land q)\equiv\neg p\lor\neg q\).

For subsets of a universe \(U\), with \(A^c=U\setminus A\), and for any family \((A_i)_{i\in I}\):

\[ \Big(\bigcup_{i\in I}A_i\Big)^c=\bigcap_{i\in I}A_i^c,\qquad \Big(\bigcap_{i\in I}A_i\Big)^c=\bigcup_{i\in I}A_i^c . \]

For quantifiers: \(\neg\forall x\,P(x)\equiv\exists x\,\neg P(x)\) and \(\neg\exists x\,P(x)\equiv\forall x\,\neg P(x)\).

Proof

For propositions, check the four rows of the truth table. For sets, \(u\in(\bigcup A_i)^c\) iff \(u\) lies in no \(A_i\) iff \(u\in A_i^c\) for every \(i\) iff \(u\in\bigcap A_i^c\). The second law follows by applying the first to the complements \(A_i^c\) and complementing both sides. The quantifier laws are the same statement with \(A_i=\{x: P(x)\}\) read pointwise.

Duality

The laws show that complement exchanges union and intersection. Consequently every identity of Boolean algebra has a dual, obtained by swapping \(\cup\) with \(\cap\) and \(\varnothing\) with \(U\). In circuit design they let any logic function be built from NAND gates alone, as Claude Shannon’s switching algebra later made practical.

Exercise 7.1Simplify \(\neg\big(\neg p\land(q\lor\neg r)\big)\).

Show solution

\(\neg\neg p\lor\neg(q\lor\neg r)=p\lor(\neg q\land r)\).

Exercise 7.2Express \(p\lor q\) and \(\neg p\) using only NAND, \(p\uparrow q=\neg(p\land q)\).

Show solution

\(\neg p=p\uparrow p\). By De Morgan, \(p\lor q=\neg(\neg p\land\neg q)=(p\uparrow p)\uparrow(q\uparrow q)\).

Exercise 7.3Negate the definition of continuity: \(\forall\varepsilon>0\ \exists\delta>0\ \forall x\ (|x-a|<\delta\Rightarrow|f(x)-f(a)|<\varepsilon)\).

Show solution

Push the negation inward with the quantifier laws, and use \(\neg(A\Rightarrow B)\equiv A\land\neg B\): \(\exists\varepsilon>0\ \forall\delta>0\ \exists x\ (|x-a|<\delta\land|f(x)-f(a)|\ge\varepsilon)\).

Lesson 08

The logic of relations

For the general reader. Traditional logic handled statements like “all men are mortal”, which relate a subject to a class. It could not handle “every man is the son of some man”, where the reasoning depends on a relation between two things. In 1860 De Morgan showed how to calculate with relations: combine them, reverse them, negate them. Charles Sanders Peirce called this the logic of relatives and developed it further; it is now relation algebra, part of the foundations of databases and program semantics.

Goals

Define composition, converse and complement of relations.
Prove De Morgan’s Theorem K.
Compute with relations as Boolean matrices.

Operations

A relation on a set \(U\) is a subset \(R\subseteq U\times U\); write \(xRy\) for \((x,y)\in R\). Define

\[ \begin{aligned} x\,(R;S)\,z &\iff \exists y\ (xRy\ \text{and}\ ySz) &&\text{(composition)}\\ x\,R^{\smile}\,y &\iff yRx &&\text{(converse)}\\ x\,\overline R\,y &\iff \text{not}\ xRy &&\text{(complement)} \end{aligned} \]

“Parent of a parent” is the composite of parent with itself; “child of” is the converse of “parent of”. De Morgan observed that ordinary syllogisms are composition of relations in disguise, and found the rule that governs composition and negation together.

Theorem K (De Morgan, 1860)

For relations \(R,S,T\) on \(U\), the following are equivalent:

\[ R;S\subseteq T,\qquad R^{\smile};\overline T\subseteq\overline S,\qquad \overline T;S^{\smile}\subseteq\overline R . \]

Proof. Each inclusion says the same thing: there are no \(x,y,z\) with \(xRy\), \(ySz\) and not \(xTz\). For the first, this is the definition. For the second, \(R^{\smile};\overline T\subseteq\overline S\) says that if \(yR^{\smile}x\) and \(x\overline Tz\) then not \(ySz\); that is, no triple with \(xRy\), not \(xTz\), and \(ySz\). The third is similar. Tarski later took this equivalence as one of the axioms of relation algebra.

Relations as matrices

On a finite set \(\{1,\dots,n\}\), represent \(R\) by the 0–1 matrix \(M_R\) with \((M_R)_{ij}=1\) iff \(iRj\). Then \(M_{R;S}=M_R\odot M_S\), the matrix product computed with OR for addition and AND for multiplication; the converse is the transpose; the complement swaps 0 and 1.

Exercise 8.1On \(\{1,2,3\}\) let \(R=\{(1,2),(2,3)\}\). Compute \(R;R\), \(R;R^{\smile}\) and \(R^{\smile};R\).

Show solution

\(R;R=\{(1,3)\}\). \(R;R^{\smile}=\{(x,z):\exists y,\ xRy,\ zRy\}=\{(1,1),(2,2)\}\). \(R^{\smile};R=\{(y,w):\exists x,\ xRy,\ xRw\}=\{(2,2),(3,3)\}\).

Exercise 8.2Show that \(R\) is transitive iff \(R;R\subseteq R\), and use Theorem K to give an equivalent condition involving \(\overline R\).

Show solution

Transitivity says \(xRy\), \(yRz\) imply \(xRz\), which is \(R;R\subseteq R\). Theorem K with \(S=T=R\) gives \(R^{\smile};\overline R\subseteq\overline R\): if \(yRx\) and not \(xRz\), then not \(yRz\).

Exercise 8.3Express “every man is the son of some man” as an inclusion between relations, using the identity relation on men \(I_M\) and the relation “son of”, \(S\).

Show solution

For every man \(x\) there is a man \(y\) with \(xSy\): \(I_M\subseteq S;I_M;S^{\smile}\). Indeed \(x\,(S;I_M;S^{\smile})\,x\) says exactly that \(x\) is the son of some \(y\) who is a man. Syllogistic logic, which handles only one-place terms, cannot express this.

Lesson 09

Probability and life contingencies

For the general reader. An insurance company must decide today what to charge for a promise to pay in the future, when payment depends on who is still alive. De Morgan earned part of his living as a consulting actuary, and his Essay on Probabilities and on their Application to Life Contingencies and Insurance Offices (1838) explained the mathematics to the profession. Two ideas carry it: discounting money for time, and weighting each payment by the probability that it is made.

Goals

Derive the present value of a certain annuity.
Define a life annuity using survival probabilities.
Compute expected present values for simple life tables.

Certain annuities

At interest rate \(i\) per year, a payment of 1 due in \(t\) years is worth \(v^t\) today, where \(v=1/(1+i)\). An annuity of 1 at the end of each of \(n\) years has present value

\[ a_{\overline{n}|}=\sum_{t=1}^{n}v^t=\frac{1-v^n}{i}. \]

Life annuities

Let \({}_tp_x\) be the probability that a person aged \(x\) survives \(t\) more years. A life annuity of 1 at the end of each year while the person lives has expected present value

Proposition \[ a_x=\sum_{t\ge1}v^t\,{}_tp_x . \]

If \(T\) is the number of complete future years lived, then \(a_x=\mathbb E\big[a_{\overline{T}|}\big]\). If survival beyond \(n\) more years is impossible, then \(a_x\le a_{\overline{n}|}\), with equality only if survival for exactly \(n\) years is certain.

Proof. The annuity pays \(\sum_{t=1}^{T}v^t=\sum_{t\ge1}v^t\,\mathbf 1[T\ge t]\). Take expectations, using \(\mathbb P(T\ge t)={}_tp_x\). The comparison follows because \({}_tp_x\le1\) for \(t\le n\) and \({}_tp_x=0\) for \(t>n\).

Exercise 9.1Find the present value of 10 annual payments of 100 at 4% interest.

Show solution

\(v=1/1.04\), \(v^{10}\approx0.6756\). \(100\cdot\frac{1-0.6756}{0.04}\approx811.09\).

Exercise 9.2A person survives each year with probability 0.9, independently, forever. Find \(a_x\) at interest \(i\), and its value for \(i=5\%\).

Show solution

\({}_tp_x=0.9^t\), so \(a_x=\sum_{t\ge1}(0.9v)^t=\frac{0.9v}{1-0.9v}=\frac{0.9}{1+i-0.9}=\frac{0.9}{0.1+i}\). At 5% this is \(6\). The same answer arises as a certain perpetuity at the higher “interest” rate \((1+i)/0.9-1\).

Exercise 9.3A life insurance pays 1 at the end of the year of death. Show that its expected present value is \(A_x=1-(1-v)(1+a_x)\).

Show solution

With \(K=T+1\) the year of death, the payment is \(v^{K}\). Since \(\sum_{t=0}^{K-1}v^t=\frac{1-v^K}{1-v}\), we have \(v^K=1-(1-v)\sum_{t=0}^{T}v^t\). Taking expectations, \(\mathbb E\sum_{t=0}^{T}v^t=1+a_x\), so \(A_x=1-(1-v)(1+a_x)\).

Lesson 10

The four-colour problem

For the general reader. In October 1852 Frederick Guthrie, one of De Morgan’s students, brought him a question from his brother Francis, who had been colouring a map of the counties of England. Can every map be coloured with four colours so that neighbouring regions differ? De Morgan could not answer and wrote the same day to William Rowan Hamilton, who replied that he would not take it up soon. De Morgan kept asking others. The question was answered only in 1976, with the help of a computer.

Goals

Translate maps into planar graphs.
Prove that \(K_5\) is not planar, and why that does not prove the four-colour theorem.
Prove the six-colour theorem and outline the history to 1976.

From maps to graphs

Put a vertex in each region and join two vertices when their regions share a border of positive length. The result is a planar graph, and colouring the map is colouring the vertices so that adjacent vertices differ. Four mutually adjacent regions, as in the figure at the top of this page, force four colours.

Theorem (Euler’s formula and its consequence)

A connected plane graph with \(V\) vertices, \(E\) edges and \(F\) faces has \(V-E+F=2\). If it is simple with \(V\ge3\), then \(E\le3V-6\), and so some vertex has degree at most 5.

Each face is bounded by at least 3 edges and each edge borders at most 2 faces, so \(3F\le2E\); substituting into Euler’s formula gives \(E\le3V-6\). The average degree is \(2E/V<6\).

For \(K_5\), five mutually adjacent vertices, \(E=10>3\cdot5-6=9\): five regions cannot all touch each other. De Morgan’s published remarks of 1860 turn on this kind of observation, which does not settle the question: a graph can need many colours without containing many mutually adjacent vertices.

Theorem (six colours suffice)

Every planar graph can be properly coloured with 6 colours.

Proof. Induction on \(V\). Remove a vertex \(w\) of degree at most 5, colour the rest by induction, and give \(w\) a colour not used by its at most 5 neighbours. Alfred Kempe published a proof of four colours in 1879 by refining this argument; Percy Heawood found the error in 1890 and salvaged the five-colour theorem. Kenneth Appel and Wolfgang Haken proved the four-colour theorem in 1976 by reducing it to a large set of configurations checked by computer. In his 1879 paper on the problem, Arthur Cayley attributed the question to De Morgan.

Exercise 10.1The wheel \(W_5\) is a cycle of 5 vertices plus a hub joined to all of them. Show that it is planar, contains no \(K_4\), and still needs 4 colours.

Show solution

Draw the cycle as a pentagon with the hub inside. Any 4 vertices include at least 3 rim vertices, two of which are non-adjacent, so there is no \(K_4\). The 5-cycle needs 3 colours, and the hub, adjacent to all of them, needs a fourth. So “no five mutually adjacent regions” cannot by itself imply four colours suffice.

Exercise 10.2Show that \(K_{3,3}\) is not planar, using the fact that it has no triangles.

Show solution

Without triangles each face has at least 4 edges, so \(4F\le2E\) and Euler gives \(E\le2V-4\). For \(K_{3,3}\), \(E=9>2\cdot6-4=8\).

Exercise 10.3Use \(E\le3V-6\) to show that a planar graph with all degrees at least 5 has at least 12 vertices of degree exactly 5.

Show solution

Let \(n_d\) be the number of vertices of degree \(d\). Then \(\sum_d d\,n_d=2E\le6V-12=\sum_d 6n_d-12\), so \(\sum_d(6-d)n_d\ge12\). With all \(d\ge5\), only \(d=5\) contributes positively, so \(n_5\ge12\). The icosahedron shows this is sharp.

Part III · Life and legacy

Lesson 11

The London Mathematical Society and the last years, 1850–1871

In the 1850s and 1860s De Morgan remained the centre of mathematics teaching at University College. He reviewed books for the weekly Athenaeum, a column that became the basis of his Budget of Paradoxes. In 1860 he published the fourth of his papers on the syllogism, with the logic of relations (Lesson 08), and a Syllabus of a Proposed System of Logic. He corresponded at length with William Rowan Hamilton for more than twenty-five years, and with Boole until Boole’s death in 1864, after which he helped secure a government pension for Boole’s widow and children.

In 1864 his son George Campbell De Morgan and a friend, Arthur Cowper Ranyard, proposed a society for mathematics in London. De Morgan suggested the name, and on 16 January 1865, at University College, he gave the opening address as first president of the London Mathematical Society; his son was its first secretary. De Morgan himself never became a Fellow of the Royal Society. He refused to let his name go forward and declined an honorary degree from Edinburgh.

In 1866 University College declined to appoint the Unitarian minister James Martineau to its chair of mental philosophy and logic. De Morgan believed the decision was made on religious grounds, the very principle the college had been founded to reject, and resigned his chair. His health declined in his last years. He died in London on 18 March 1871, aged 64, and was buried at Kensal Green Cemetery.

Lesson 12

Paradoxes, principles, legacy

A Budget of Paradoxes, published by Sophia De Morgan in 1872, collects his reviews of books by circle-squarers, angle-trisectors, perpetual-motion inventors and other “paradoxers”, mixed with anecdotes, puns and anagrams. It remains one of the funniest books written by a mathematician, and a serious study of how expertise and crankery differ. In the same spirit he took part in the controversy of 1867–69 over the forged letters, presented by Michel Chasles to the Paris Academy, which claimed that Pascal had discovered universal gravitation before Newton.

He loved numerical curiosities. Asked his age, he liked to say that he was \(x\) years old in the year \(x^2\).

Legacy

Logic: De Morgan’s laws; the explicit role of the universe of discourse; the logic of relations, developed by Peirce, Ernst Schröder and Alfred Tarski into relation algebra.
Analysis and algebra: the name and formulation of mathematical induction; limits as the base of calculus; a hierarchy of convergence tests; the law-based view of algebra that led to abstract structures.
Problems: the four-colour problem, which he circulated for twenty years and which shaped graph theory.
Institutions: the first chair of mathematics in London, the London Mathematical Society, whose highest honour, the De Morgan Medal, has been awarded since 1884, and a generation of students who taught British mathematics.

Exercise 12.1Solve De Morgan’s age riddle: he was \(x\) years old in the year \(x^2\), and he lived in the nineteenth century. Check against his birth year.

Show solution

Need \(1800\le x^2\le1899\): \(x=43\) gives 1849 (and \(42^2=1764\), \(44^2=1936\) are out of range). So he was 43 in 1849, born in 1806 (he turned 43 in June 1849).

Final projectChoose one of De Morgan’s ideas from Part II (induction, the convergence hierarchy, double algebra, Theorem K, or the four-colour problem). Write a two-page account for a strong undergraduate that states the idea as De Morgan had it, states it as it is known today, and works one example in full.

Reference

Sources and further reading

Biography

J. J. O’Connor and E. F. Robertson, Augustus De Morgan, MacTutor.
Augustus De Morgan, Wikipedia.
S. E. De Morgan, Memoir of Augustus De Morgan, Longmans, Green, 1882.
C. Hollings, U. Martin, A. Rice, The Lovelace–De Morgan mathematical correspondence: a critical re-appraisal, Historia Mathematica 44 (2017), 202–231.

Mathematics

A. De Morgan, Induction (Mathematics), Penny Cyclopaedia (1838).
A. De Morgan, The Differential and Integral Calculus, London, 1836–42.
A. De Morgan, Trigonometry and Double Algebra, London, 1849.
A. De Morgan, Formal Logic, or the Calculus of Inference, Necessary and Probable, London, 1847.
A. De Morgan, On the syllogism, No. IV, and on the logic of relations, Transactions of the Cambridge Philosophical Society 10 (1864; read 1860).
A. De Morgan, A Budget of Paradoxes, London, 1872.
De Morgan’s laws and Ratio test (including the De Morgan hierarchy), Wikipedia.
B. D. McKay, A note on the history of the four-colour conjecture, arXiv:1201.2852.
R. Wilson, Four Colors Suffice, Princeton University Press, 2002.
R. D. Maddux, Relation Algebras, Elsevier, 2006.
T. J. I’A. Bromwich, An Introduction to the Theory of Infinite Series, Macmillan, 1908.