The Problem
From at least the time of Leibniz (Ishiguro, 1990; Kemerling, 2011; Shabel, 2005), logicians and mathematicians have had a dream of representing both information and thought in logic, and using that to deduce the truth and resolve conflicts. In line with attempts by Frege (Frege, 1950; Wikipedia, n.d.f)1 and Russell & Whitehead (Whitehead & Russell, 1912; Wikipedia, n.d.p) to create complete logical models for mathematics (Demopoulos & Clark, 2005; Franzén, 2005), David Hilbert in his 1900 address to the International Conference of Mathematicians in Paris (Hilbert, 1900) challenged mathematicians with a list of 23 problems (Browder, 1976). For this chapter, the most relevant are the Second Problem, asking whether arithmetic could be proved consistent, and the Tenth Problem, asking for a general solution technique for Diophantine equations. (See (Hawking, 2007) for a discussion of and excerpts from the work of Diophantus of Alexandria, who first studied the class of equations now known as Diophantine equations.) Hilbert’s First Problem, on the Continuum Hypothesis (Martin, 1976), is also mentioned in Applications of Modal Logic, below.
By the middle of the 20th century, however, it had become clear:
- •
That constructs such as “the set of all sets” lead to a contradiction (“Russell’s Paradox”) (Ellenberg, 2015; Stanford Encyclopedia of Philosophy, 2014)—see Undecidability and Rice’s Theorem, below;
- •
That even physical information is inherently imprecise (the Heisenberg Principle (Eisberg, 1961; Hilgevoord & Uffink, 2016; Perry, 2012) and dependent on the observer’s frame of reference (relativity (Wald, 2010));
- •
That quantifying cause-and-effect may rely on arbitrarily precise representation of information (chaos theory (Gleick, 2011)), may undergo rapid or even instantaneous transitions to different response regimes (for example, catastrophe theory (Poston & Stewart, 2014)), and may entail probabilistically random events (for example, atomic decays or random mutations) (Acín, 2014; Bryn, 2015);
- •
That statistical information is needed in discussing human reactions and characteristics, unless a very large number of independent factors can be observed and encoded, and possibly not even then—part of the motivation behind Big Data, for which see for example (Moorthy et al., 2015);
- •
And that, perhaps most surprisingly, there are inherent limitations to logic and computation, so that the Leibniz program can never be realized in its entirety, even in principle.
Due to these limitations, and also for several other major purposes—to understand human cognition and reasoning, to develop artificial intelligence/expert systems to assist in problem solving (and because it is fun) (Wikipedia, n.d.o), and to explore the boundaries of mathematical and logical reasoning—the past 200 years have seen a renewed interest in both the foundations and the frontiers of logic and its relatives, mathematics and computer science.
The significance of such studies has only increased with the pervasiveness and ubiquity of computation in the modern world, impacted by not only the practice but also the theory of computing (Copeland, Posy & Shagrir, 2013). Below, we consider at some of those frontiers, and in particular several extensions and limitations.