Maria is either at home or in the office. She’s not at home. Where is she? You might wonder why I started with such an unpuzzling puzzle. But in solving it, you already used logic. You reasoned correctly from the premises ‘Maria is either at home or in the office’ and ‘She’s not at home’ to the conclusion ‘Maria is in the office.’ That might not seem like a big deal, but someone who couldn’t make that move would be in trouble. We need logic to put together different pieces of information, sometimes from different sources, and to extract their consequences. By linking together many small steps of logical reasoning, we can solve much harder problems, as in mathematics.
Another angle on logic is that it’s about inconsistency. Imagine someone making all three statements ‘Maria is either at home or in the office’, ‘She’s not at home’, and ‘She’s not in the office’ (about the same person at the same time). Those statements are jointly inconsistent; they can’t all be true together. Any two of them can be true, but they exclude the third. When we spot an inconsistency in what someone is saying, we tend to stop believing them. Logic is crucial for our ability to detect inconsistency, even when we can’t explain exactly what has gone wrong. Often, it is much more deeply hidden than in that example. Spotting inconsistencies in what is said can enable us to work out that a relative is confused, or that a public figure is lying. Logic is one basic check on what politicians say.
To put your pattern of reasoning in the simplest form, you went from premises ‘A or B’ and ‘Not A’ to the conclusion ‘B’. The deductive action was all in the two short words ‘or’ and ‘not’. How you fill in ‘A’ and ‘B’ doesn’t matter logically, as long as you don’t introduce ambiguities. If ‘A or B’ and ‘Not A’ are both true, so is ‘B’. In other words, that form of argument is logically valid. The technical term for it is disjunctive syllogism. You have been applying disjunctive syllogism most of your life, whether you knew it or not.
Except for a few special cases, logic can’t tell you whether the premises or conclusion of an argument are true. It can’t tell you whether Maria is at home, or whether she’s in the office, or whether she’s in neither of those places. What it tells you about is the connection between them; in a valid argument, logic rules out the combination where the premises are all true while the conclusion is false. Even if your premises are false, you can still reason from them in logically valid ways – perhaps my initial statement about Maria was quite wrong, and she is actually on a train.
The logical validity of forms of argument depends on logical words: as well as ‘or’ and ‘not’, they include ‘and’, ‘if’, ‘some’, ‘all’, and ‘is’. For instance, reasoning from ‘All toadstools are poisonous’ and ‘This is a toadstool’ to ‘This is poisonous’ illustrates a valid form of argument, one that we use when we apply our general knowledge or belief to particular cases. A mathematical instance of another form of argument is the move from ‘x is less than 3’ and ‘y isn’t less than 3’ to ‘x is not y’, which involves the logical principle that things are identical only if they have the same properties.
In everyday life and even in much of science, we pay little or no conscious attention to the role of logical words in our reasoning because they don’t express what we are interested in reasoning about. We care about where Maria is, not about disjunction, the logical operation expressed by ‘or’. But without those logical words, our reasoning would fall apart; swapping ‘some’ and ‘all’ turns many valid arguments into invalid ones. Logicians’ interests are the other way round; they care about how disjunction works, not where Maria is.
Philosophers have sometimes fallen into that trap, thinking that logic had nothing left to discover
Logic was already studied in the ancient world, in Greece, India and China. To recognise valid or invalid forms of argument in ordinary reasoning is hard. We must stand back, and abstract from the very things we usually find of most interest. But it can be done. That way, we can uncover the logical microstructure of complex arguments.
For example, here are two arguments:
‘All politicians are criminals, and some criminals are liars, so some politicians are liars.’
‘Some politicians are criminals, and all criminals are liars, so some politicians are liars.’
The conclusion follows logically from the premises in one of these arguments but not the other. Can you work out which is which?
When one just looks at such ordinary cases, one can get the impression that logic has only a limited number of argument forms to deal with, so that once they have all been correctly classified as valid or as invalid, logic has completed its task, except for teaching its results to the next generation. Philosophers have sometimes fallen into that trap, thinking that logic had nothing left to discover. But it is now known that logic can never complete its task. Whatever problems logicians solve, there will always be new problems for them to tackle, which cannot be reduced to the problems already solved. To understand how logic emerged as this open-ended field for research, we need to look back at how its history has been intertwined with that of mathematics.
The most sustained and successful tradition of logical reasoning in human history is mathematics. Its results are applied in the natural and social sciences too, so those sciences also ultimately depend on logic.
The idea that a mathematical statement needs to be proved from first principles goes back at least to Euclid’s geometry. Although mathematicians typically care more about the mathematical pay-offs of their reasoning than its abstract structure, to reach those pay-offs they had to develop logical reasoning to unprecedented power.
From Oliver Byrne’s The First Six Books of the Elements of Euclid (1867). Public Domain
An example is the principle of reductio ad absurdum. This is what one uses in proving a result by supposing that it does not hold, and deriving a contradiction. For instance, to prove that there are infinitely many prime numbers, one starts by supposing the opposite, that there is a largest prime, and then derives contradictory consequences from that supposition. In a complex proof, one may have to make suppositions within suppositions within suppositions; keeping track of that elaborate dialectical structure requires a secure logical grasp of what is going on.
There was a trend to rigorise mathematics by reducing it to logical constructions out of arithmetic
As mathematics grew ever more abstract and general in the 19th century, logic developed accordingly. George Boole developed what is now called ‘Boolean algebra’, which is basically the logic of ‘and’, ‘or’ and ‘not’, but equally of the operations of intersection, union, and complementation on classes. It also turns out to model the building blocks for electronic circuits, AND gates, OR gates and NOT gates, and has played a fundamental role in the history of digital computing.
Boolean logic has its limits. In particular, it doesn’t cover the logic of ‘some’ and ‘all’. Yet complex combinations of such words played an increasing role in rigorous mathematical definitions, for instance of what it means for a mathematical function to be ‘continuous’, and of what it means to be a ‘function’ anyway, issues that had led to confusion and inconsistency in early 19th-century mathematics.
The later 19th century witnessed an increasing trend to rigorise mathematics by reducing it to logical constructions out of arithmetic, the theory of the natural numbers – those reached from 0 by repeatedly adding 1 – under operations like addition and multiplication. Then the mathematician Richard Dedekind showed how arithmetic itself could be reduced to the general theory of all sequences generated from a given starting point by repeatedly applying a given operation (0, 1, 2, 3, …). That theory is very close to logic. He imposed two constraints on the operation: first, it never outputs the same result for different inputs; second, it never outputs the original starting point. Given those constraints, the resulting sequence cannot loop back on itself, and so must be infinite.
The trickiest part of Dedekind’s project was showing that there is even one such infinite sequence. He did not want to take the natural numbers for granted, since arithmetic was what he was trying to explain. Instead, he proposed the sequence whose starting point (in place of 0) was his own self and whose generating operation (in place of adding 1) constructed from any thinkable input the thought that he could think about that input. The reference in his proof to his own self and to thoughts about thinkability was unexpected, to say the least. It does not feel like regular mathematics. But could anyone else do better, to make arithmetic fully rigorous?
A natural idea was to reduce arithmetic, and perhaps the rest of mathematics, to pure logic. Some partial reductions are easy. For example, take the equation 2 + 2 = 4. Applied to the physical world, it corresponds to arguments like this (about a bowl of fruit):
There are exactly two apples.
There are exactly two oranges.
No apple is an orange.
Therefore:
There are exactly four apples and oranges.
Phrases like ‘exactly two’ can be translated into purely logical terms: ‘There are exactly two apples’ is equivalent to ‘There is an apple, and another apple, and no further apple.’ Once the whole argument has been translated into such terms, the conclusion can be rigorously deduced from the premises by purely logical reasoning. This procedure can be generalised to any arithmetical equation involving particular numerals like ‘2’ and ‘4’, even very large ones. Such simple applications of mathematics are reducible to logic.
However, that easy reduction does not go far enough. Mathematics also involves generalisations, such as ‘If m and n are any natural numbers, then m + n = n + m’. The easy reduction cannot handle such generality. Some much more general method would be needed to reduce arithmetic to pure logic.
A key contribution was made by Gottlob Frege, in work slightly earlier than Dedekind’s, though with a much lower profile at the time. Frege invented a radically new symbolic language in which to write logical proofs, and a system of formal deductive rules for it, so the correctness of any alleged proof in the system could be rigorously checked. His artificial language could express much more than any previous logical symbolism. For the first time, the structural complexity of definitions and theorems in advanced mathematics could be articulated in purely formal terms. Within this formal system, Frege showed how to understand natural numbers as abstractions from sets with equally many members. For example, the number 2 is what all sets with exactly two members have in common. Two sets have equally many members just when there is a one-one correspondence between their members. Actually, Frege talked about ‘concepts’ rather than ‘sets’, but the difference is not crucial for our purposes.
Is R a set that is not a member of itself? If it is, it isn’t, and if it isn’t, it is: an inconsistency!
Frege’s language for logic has turned out to be invaluable for philosophers and linguists as well as mathematicians. For instance, take the simple argument ‘Every horse is an animal, so every horse’s tail is an animal’s tail.’ It had been recognised as valid long before Frege, but Fregean logic was needed to analyse its underlying structure and properly explain its validity. Today, philosophers routinely use it for analysing much trickier arguments. Linguists use an approach that goes back to Frege to explain how the meaning of a complex sentence is determined by the meanings of its constituent words and how they are put together.
Frege contributed more than anyone else to the attempted reduction of mathematics to logic. By the start of the 20th century, he seemed to have succeeded. Then a short note arrived from Bertrand Russell, pointing out a hidden inconsistency in the logical axioms from which Frege had reconstructed mathematics. The news could hardly have been worse.
The contradiction is most easily explained in terms of sets, but its analogue in Fregean terms is equally fatal. To understand it, we need to take a step back.
In mathematics, once it is clear what we mean by ‘triangle’, we can talk about the set of all triangles: its members are just the triangles. Similarly, since it is equally clear what we mean by ‘non-triangle’, we should be able to talk about the set of all non-triangles: its members are just the non-triangles. One difference between these two sets is that the set of all triangles is not a member of itself, since it is not a triangle, whereas the set of all non-triangles is a member of itself, since it is a non-triangle. More generally, whenever it is clear what we mean by ‘X’, there is the set of all Xs. This natural principle about sets is called ‘unrestricted comprehension’. Frege’s logic included an analogous principle.
Since it is clear what we mean by ‘set that is not a member of itself’, we can substitute it for ‘X’ in the unrestricted comprehension principle. Thus, there is the set of all sets that are not members of themselves. Call that set ‘R’ (for ‘Russell’). Is R a member of itself? In other words, is R a set that is not a member of itself? Reflection quickly shows that if R is a member of itself, it isn’t, and if it isn’t, it is: an inconsistency!
That contradiction is Russell’s paradox. It shows that something must be wrong with unrestricted comprehension. Although many sets are not members of themselves, there is no set of all sets that are not members of themselves. That raises the general question: when can we start talking about the set of all Xs? When is there a set of all Xs? The question matters for contemporary mathematics, because set theory is its standard framework. If we can never be sure whether there is a set for us to talk about, how are we to proceed?
Logicians and mathematicians have explored many ways of restricting the comprehension principle enough to avoid contradictions but not so much as to hamper normal mathematical investigations. In their massive work Principia Mathematica (1910-13), Russell and Alfred North Whitehead imposed very tight restrictions to restore consistency, while still preserving enough mathematical power to carry through a variant of Frege’s project, reducing most of mathematics to their consistent logical system. However, it is too cumbersome to work in for normal mathematical purposes. Mathematicians now prefer a simpler and more powerful system, devised around the same time as Russell’s by Ernst Zermelo and later enhanced by Abraham Fraenkel. The underlying conception is called ‘iterative’, because the Zermelo-Fraenkel axioms describe how more and more sets are reached by iterating set-building operations. For example, given any set, there is the set of all its subsets, which is a bigger set.
Set theory is classified as a branch of mathematical logic, not just of mathematics. That is apt for several reasons.
First, the meanings of core logical words like ‘or’, ‘some’ and ‘is’ have a kind of abstract structural generality; in that way, the meanings of ‘set’ and ‘member of’ are similar.
Second, much of set theory concerns logical questions of consistency and inconsistency. One of its greatest results is the independence of the continuum hypothesis (CH), which reveals a major limitation of current axioms and principles for logic and mathematics. CH is a natural conjecture about the relative sizes of different infinite sets, first proposed in 1878 by Georg Cantor, the founder of set theory. In 1938, Kurt Gödel showed that CH is consistent with standard set theory (assuming the latter is itself consistent). But in 1963 Paul Cohen showed that the negation of CH is also consistent with standard set theory (again, assuming the latter is consistent). Thus, if standard set theory is consistent, it can neither prove nor disprove CH; it is agnostic on the question. Some set theorists have searched for plausible new axioms to add to set theory to settle CH one way or the other, so far with little success. Even if they found one, the strengthened set theory would still be agnostic about some further hypotheses, and so on indefinitely.
A proof in a framework of formal logic is still the gold standard, even if you never see a bar of gold
A working mathematician may use sets without worrying about the risk of inconsistency or checking whether their proofs can be carried out in standard set theory. Fortunately, they normally can. Those mathematicians are like people who live their lives without worrying about the law, but whose habits are in practice law-abiding.
Kurt Gödel in 1925. Courtesy Wikipedia
Although set theory is not the only conceivable framework in which to do mathematics, analogous issues arise for any alternative framework: restrictions will be needed to block analogues of Russell’s paradox, and its rigorous development will involve intricate questions of logic.
By examining the relation between mathematical proof and formal logic, we can start to understand some deeper connections between logic and computer science: another way in which logic matters.
Most proofs in mathematics are semi-formal; they are presented in a mix of mathematical and logical notation, diagrams, and English or another natural language. The underlying axioms and first principles are left unmentioned. Nevertheless, if competent mathematicians question a point in the proof, they challenge the author(s) to fill in the missing steps, until it is clear that the reasoning is legitimate. The assumption is that any sound proof can in principle be made fully formal and logically rigorous, although in practice full formalisation is hardly ever required, and might involve a proof thousands of pages long. A proof in a framework of formal logic is still the gold standard, even if you personally never see a bar of gold.
The standard of formal proof is closely related to the checking of mathematical proofs by computer. An ordinary semi-formal proof cannot be mechanically checked as it stands, since the computer cannot assess the prose narrative holding the more formal pieces together (current AI would be insufficiently reliable). What is needed instead is an interactive process between the proof-checking program and human mathematicians: the program repeatedly asks the humans to clarify definitions and intermediate steps, until it can find a fully formal proof, or the humans find themselves at a loss. All this can take months. Even the finest mathematicians may use the interactive process to check the validity of a complicated semi-formal proof, because they know cases where a brilliant, utterly convincing proof strategy turned out to depend on a subtle mistake.
Historically, connections between logic and computing go much deeper than that. In 1930, Gödel published a demonstration that there is a sound and complete proof system for a large part of logic, first-order logic. For many purposes, first-order logic is all one needs. The system is sound in the sense that any provable formula is valid (true in all models). The system is also complete in the sense that any valid formula is provable. In principle, the system provides an automatic way of listing all the valid formulas of the language, even though there are infinitely many, since all proofs in the system can be listed in order. Although the process is endless, any given valid formula will show up sooner or later (perhaps not in our lifetimes). That might seem to give us an automatic way of determining in principle whether any given formula is valid: just wait to see whether it turns up on the list. That works fine for valid formulas, but what about invalid ones? You sit there, waiting for the formula. But if it hasn’t shown up yet, how do you know whether it will show up later, or will never show up? The big open question was the Decision Problem: is there a general algorithm that, given any formula of the language, will tell you whether it is valid or not?
Almost simultaneously in 1935-36, Alonzo Church in the US and Alan Turing in the UK showed that such an algorithm is impossible. To do that, they first had to think very hard and creatively about what exactly it is to be an algorithm, a purely mechanical way of solving a problem step by step that leaves no room for discretion or judgment. To make it more concrete, Turing came up with a precise description of an imaginary kind of universal computing machine, which could in principle execute any algorithm. He proved that no such machine could meet the challenge of the Decision Problem. In effect, he had invented the computer (though at the time the word ‘computer’ was used for humans whose job was to do computations; one philosopher liked to point out that he had married a computer). A few years later, Turing built an electronic computer to break German codes in real time during the Second World War, which made a major contribution to defeating German U-boats in the North Atlantic. The programs on your laptop are one practical answer to the question ‘Why does logic matter?’
Alternative logicians are far more rational than the average conspiracy theorist
Logic and computing have continued to interact since Turing. Programming languages are closely related in structure to logicians’ formal languages. A flourishing branch of logic is computational complexity theory, which studies not just whether there is an algorithm for a given class, but how fast the algorithm can be, in terms of how many steps it involves as a function of the size of the input. If you look at a logic journal, you will see that the contributors typically come from a mix of academic disciplines – mathematics, computer science, and philosophy.
Since logic is the ultimate go-to discipline for determining whether deductions are valid, one might expect basic logical principles to be indubitable or self-evident – so philosophers used to think. But in the past century, every principle of standard logic was rejected by some logician or other. The challenges were made on all sorts of grounds: paradoxes, infinity, vagueness, quantum mechanics, change, the open future, the obliterated past – you name it. Many alternative systems of logic were proposed. Contrary to prediction, alternative logicians are not crazy to the point of unintelligibility, but far more rational than the average conspiracy theorist; one can have rewarding arguments with them about the pros and cons of their alternative systems. There are genuine disagreements in logic, just as there are in every other science. That does not make logic useless, any more than it makes other sciences useless. It just makes the picture more complicated, which is what tends to happen when one looks closely at any bit of science. In practice, logicians agree about enough for massive progress to be made. Most alternative logicians insist that classical logic works well enough in ordinary cases. (In my view, all the objections to classical logic are unsound, but that is for another day.)
What is characteristic of logic is not a special standard of certainty, but a special level of generality. Beyond its role in policing deductive arguments, logic discerns patterns in reality of the most abstract, structural kind. A trivial example is this: everything is self-identical. The various logical discoveries mentioned earlier reflect much deeper patterns. Contrary to what some philosophers claim, these patterns are not just linguistic conventions. We cannot make something not self-identical, however hard we try. We could mean something else by the word ‘identity’, but that would be like trying to defeat gravity by using the word ‘gravity’ to mean something else. Laws of logic are no more up to us than laws of physics.
