As almost the last thing in almost my last lecture a week or so ago, one of the highlights was the Compactness Theorem for first-order logic together with some of its consequences (sucuh as the upward Löwenheim–Skolem theorem).

Some of the students who had met complactness in the Topology module were interested to know how the connection worked. There wasn’t time within the lectures to explain this in detail, so I will have a go here.

I will stick to propositional logic since the situation is simpler and clearer.

Logic: syntax and semantics

In propositional logic, we have a set P of propositional variables which can take the values T (true) or F (false). Formulae are built from propositional variables by combining them with connectives, typically → (implies) and ¬ (not). A valuation is an assignment of values to the variables; by the usual truth table rules, it assigns values to the formulae.

A set Σ of formulae is said to be satisfiable if there is a valuation which gives the value T to every formula in Σ.

There is also a deduction system for propositional logic, which comes into the argument. A set of formulae are designated as axioms; there is a single rule of inference, namely Modus Ponens (MP), which allows B to be deduced from A and (A→B).

A proof of a formula A from a set Σ in the deductive system is a sequence of formulae such that each formula in the sequence is an axiom, a member of Σ, or deduced from earlier formulae in the sequence by MP.

Now the set Σ of formulae is said to be consistent if no contradiction can be deduced from it.

The Soundness and Completeness Theorem asserts that a set of formulae is satisfiable if and only if it is consistent. The forward direction is easier; we only need to ensure that the axioms are tautologies (take the value T for all valuations) and that MP preserves the value T. The converse requires us to construct a valuation satisifying a consistent set of formula, which involves enlarging our set to a maximal consistent set Σ*, and showing that the function which is T on elements of Σ* is a valuation.

Clearly the truth of this theorem depends on the choice of deduction system. But it has consequences for the semantics, which make no mention of deduction,

There is a hidden difficulty here, which I will come to later.

Compactness

The Compactness Theorem for this logical system states the following:

Theorem A set of formulae is satisfiable if and only if every finite subset is satisfiable.

The proof uses the existence of a sound and complete deduction system: it suffices to prove that a set Σ of formulae is consistent if and only if every finite subset is consistent. The forward direction is clear, so suppose that every finite subset is consistent, but a contradiction could be deduced from Σ. Since proofs are finite strings of formulae, only finitely many formulae from Σ can be quoted in the proof, so there is an inconsistent finite subset of Σ, contrary to hypothesis.

This already has consequences for mathematics, for example the theorem that a graph can be properly coloured with a fixed finite number k of colours if and only if every finite subgraph can be properly coloured with k colours.

How is this connected with topology?

Our proof of compactness used soundness and completeness, but the statement does not refer to the deductive system at all. Is there a proof not depending on soundness and completeness?

Indeed there is, and it depends on Tychonoff’s Theorem in topology, according to which a product of compact topological spaces is compact. Now consider the set of all valuations of our first-order logic. Eacch valuation is determined by its values on the propositional variables, so the set of valuations is bijective with the Cartesian product over P of copies of {T,F}. So it is a topological space, with the product topology inherited from the discrete topology on {T,F}. The definition of this is that the basic open sets are sets of valuations taking prescribed values on finite subsets of P. By Tychonoff’s Theorem, this space V is compact.

Now suppose that Σ is an unsatisfiable set of formulae. For each formula A in Σ, let V(A) be the set of valuations giving A the value F. Since A only contains finitely many variables, this is an open set; and, by the assumption that Σ is unsatisfiable, V is the union of these open sets, which thus form an open cover. By compactness, there is a finite subcover; that is, a finite subset Σ₀ such that the corresponding open sets cover V. This means that every valuation gives some formula A in the set Σ₀ the value F. So some finite subset of Σ is not satisfiable. This proves the logical Compactness Theorem.

Set theory

If you have studied topology, I hope you are aware that the proof of Tychonoff’s Theorem uses the Axiom of Choice (AC). There was a hint of this in the observation that the proof of the Completeness Theorem involves choosing a set maximal with respect to some property.

But, as it turns out, the Propositional Compactness Theorem is strictly weaker than the Axiom of Choice. It is equivalent to a principle called the Boolean Prime Ideal Theorem (BPIT). (AC) is equivalent to the statement that every set can be well-ordered; on the other hand, (BPIT) implies the weaker statement that every set can be totally ordered. (Exercise: Prove this: translate the existence of a total order into a condition on a set of propositional variables indexed by distinct pairs of elements of the set.)

Boolean rings

Boolean rings (and the equivalent Boolean algebras) arose from George Boole’s program to turn logic into a branch of algebra.

Take P to be a set of propositional variables. Call two formulae equivalent if their truth values under every valuation are equivalent. Let R(P) be the set of equivalence classes of formulae.

Now define two operations + and · on R(P) by the rules that [A]+[B] = [(AB)] and [A]·[B] = [(A∧B)]. These operations make R(P) into a ring satisfying the equation x² = x. Such a ring is called a Boolean ring. Any quotient is also a Boolean ring. So if (Σ) denotes the ideal generated by a set Σ of formulae, then R(P)/(Σ) is a Boolean ring. It can be shown that, if every finite subset of Σ is satisfiable, then the element 1 (corresponding to a contradiction) cannot be expressed as a finite combination of elements in Σ. If we assume that every Boolean ring has a prime (or maximal) ideal, then Σ is contained in such an ideal. Now it is not hard to prove that, if I is a maximal ideal, then for any formula A, either [A] or (1+[A]) belongs to I; so mapping formula in I to T and the others to F is a valuation, and clearly it makes all formulae in Σ true.

The statement that every Boolean ring has a maximal ideal is (BPIT). So this set-theoretic principle, weaker than (AC), suffices to prove the propositional compactness theorem.

Final note

We noted that some set-theoretic principle is required to prove propositional compactness. One can work more locally.

If the set P of propositional variables can be well-ordered (in particular, if it is finite or countable), then the proof of the soundness and completeness theorem goes through, and so propositional compactness holds for P.

I assume that a weaker condition on P suffices for propositional compactness over P. But I have not thought about this, and have gone on long enough.

Today is my official last day, after 50 years, as a University lecturer, made up of

• half a year at the University of Michigan;
• a year and a bit at Bedford College, London;
• eleven years at Merton College, Oxford;
• 26 years at what began as Queen Mary College, University of London, and ended up dropping the “College” and the comma;
• 12 years at the University of St Andrews;
• and in the middle of this, some remote teaching at Universidade Aberta in Portugal.

During that time I have taught courses from multivariate calculus to operational research, from mathematical logic to algebraic structures.

I suppose the course of which I am most proud is Mathematical Structures for all first-semester students on mathematics or joint degrees at Queen Mary; you can watch my LMS/Gresham College lecture about it here.

And, of course, it is not over yet; I will be teaching classes and marking exam scripts on Set Theory and Mathematical Logic for the rest of this semester.

I hope that research will carry on as usual, that the occasional bit of teaching will come my way (I very much enjoy dealing with students), and that I can avoid the less enjoyable bits of admin.

I should become Professor Emeritus tomorrow. There was some difficulty between Human Resources and the academic side of the University, which may not be fully resolved yet; I will only discover this when I can see whether my access card still works, whether I can still read email, and so on. They had threatened to remove all these things tomorrow, and I am not sure yet that they really understand, since they describe my status from tomorrow as a “new contract” and my last pay slip includes “redundancy pay”. Ah well, we shall see.

I’m afraid this is the sort of news I have to report all too often.

The University of Cardiff, one of the leading universities in Wales, is in financial trouble. They are proposing re-structuring, which will involve merging mathematics with computer science and “data science” and making half of the mathematics staff redundant. I have no idea who is staying and who is being sent away under their plans; it may be (though I have no evidence for this) that only mathematicians whose work is thought to be relevant to computer science and “data science” will be allowed to remain.

Jens Marklof, President of the London Mathematical Society, has drawn up an open letter to management at the University about why this is not a good idea. You can view the open letter at https://tinyurl.com/2vjxurb9, and sign it at https://forms.gle/bqwZXMkajEVbucWe7 .

You are welcome to stop reading here and go to the open letter or the signing page. What follows is not really relevant, but appears to me to be related.

All this comes at a time when both the British university system and many other aspects of life in Wales are in serious trouble. The Principality is well known for music, especially vocal music, but funding to opera companies there is being seriously cut back to the point where some may have to close.

At the same time, rumour has it that a trade deal between the UK and the USA would entail American tech billionaires paying even less tax on their businesses here than they currently do.

I went to London on Wednesday for the second in the series of Simon Norton memorial lectures, endowed by his family in memory of this remarkable mathematician.

The lecture was given by Leonard Soicher; I gave the first in the series last year. Here are the first two lecturers, with Yang He, the organiser of the series, in LIMS (in Michael Faraday’s rooms in the Royal Institution).

I don’t want to compare our lectures, but I will briefly contrast our approaches.

Leonard began, more or less, with the axioms for a group, and explained how groups describe symmetry (with an example, the projective plane of order 3, which came into his talk later). He then described some of the excitement of being around while the properties of the sporadic simple groups were being investigated (he was too late to take part in their discovery), and some of Simon’s technical work on the Monster.

On the other hand, I “explained” groups using the Rubik cube, and “explained” Norton algebras using the football. (Griess constructed the Monster as the group of symmetries of a Norton algebra in 196883 dimensions.)

This leads to a little puzzle. Of what is the group of the Rubik cube the symmetry group? I think this question does need a bit of thought, but I leave it to you.

The ADE book now has a webpage where you can pre-order it, though it won’t actually be published until August.

The ISBN for the paperback version is 9781009335980 and the link is https://www.cambridge.org/9781009335980.

You will see that it contains much more than just what I discussed in the ADE series of posts.

From Chuang Tzu, as quoted by Aldous Huxley:

The ruler of the Southern Ocean was Shu, the ruler of the Northern Ocean was Hu, and the ruler of the Centre was Chaos. Shu and Hu were continually meeting in the land of Chaos, who treated them very well. They consulted together how they might repay his kindness, and said: “Men all have seven orifices for the purpose of seeing, hearing, eating and breathing, while this ruler alone has not a single one. Let us try to make them for him.” Accordingly they dug one orifice in him every day. At the end of seven days Chaos died.

Take a look at this web page.

Put the dates in your diary, and please come if you possibly can!

In her memoir about her father André, the famous mathematician, and her aunt Simone, the even more famous saint, Sophie Weil says the following:

My father often said that Jews could be divided into two categories: merchants or rabbis. Naturally he classified himself, along with his sister, in the latter category, shich did not keep him from taking pride in almost always selling what he called his “modest merchandise,” or mathematical insight, at a respectable price.

I am not a mathematician in Weil’s class, but this seems a good principle to me, so I have decided to start charging a fee for giving an on-line talk.

The problem with an on-line talk is that I may know very few people in the audience, and they probably have their cameras off while I am talking, so I have no idea who I am talking to or how it is going over. It occurred to me that if I at least had a picture of the place where I am speaking, I would feel a bit more connected to it. So I decided to request that organisers of on-line seminars or conferences who invite me should send me a picture of their university, town, or surroundings.

This new policy was implemented for a talk at a hybrid conference in Tezpur, Assam, India, on Mathematical Sciences and Applications. The local organiser, Rajat Kanti Nath, enthusiastically agreed and sent me a number of pictures of the university and its surroundings. I found that it really did work: I have never been there, and have no prospect of going in the immediate future, but it did feel more like a real place, just after viewing a few carefully chosen pictures.

Somebody pointed out an added advantage of this system: the fee is not taxable!

Happy new year!

2025 is the square of a triangular number, somethiing that won’t happen again for a thousand years (literally).

Indeed, the square of the triangle is an interesting graph, being one of only two finite homogeneous graphs (the other is the pentagon). Indeed, I don’t have to say whether I mean the Cartesian square or the categorical square, since for the triangle they happen to be isomorphic: the graph is self-complementary.

So what will 2025 bring? For me, at least, it will bring retirement, or maybe that is redundancy. The Head of School believes that on 1 March I will become Professor Emeritus and continue to have the use of my office, the library, the computer network, and so on; but Human Resources think that, after a month’s grace I will be out on my ear. It is a bit stressful not knowing with just two months to go; but either way it will be softer than leaving QMUL, when I was given two weeks over Christmas and New Year to clear my office, with no advance warning.

Looking wider, it is certainly difficult to be hopeful about the world at present. I was born two years after the Second World War, and it is hard for me to remember a bleaker time. Aldous Huxley’s recipe for saving the world was to persuade people to open their eyes and see who and where they were; that is not going to happen, with so many people finding the echo chamber of social media more attractive than the “real world”.

Bob Dylan said,

Life is sad,
Life is a bust.
All you can do is
Do what you must.
Do what you must do
And do it well.

That will be my aim in 2025.

Mathematicians’ perspective on problem solving is not unique to us. The following is from At home in the world by Vietnamese monk Thich Nhat Hanh:

“One day when I was a child, I looked into the large clay water jar in the front yard that we used for collecting water and I saw a very beautiful leaf at the bottom. It had so many colors. I wanted to take it out and play with it, but my arm was too short to reach the bottom. So I used a stick to try to get it out. It was so difficult I became impatient. I stirred twenty times, thirty times, and yet the leaf didn’t come up to the surface. So I gave up and threw the stick away.

When I came back a few minutes later, I was surprised to see the leaf floating on the surface of the water, and I picked it up. While I was away the water had continued to turn, and had brought the leaf up to the surface. This is how our unconscious mind works. When we have a problem to solve, or when we want more insight into a situation, we need to entrust the task of finding a solution to the deeper level of our consciousness. Struggling with our thinking mind will not help.”