## The Limitations of Logic & Reason

### Theoretic Limits to Deductive Reasoning

At the same time as Hilbert was proclaiming "We must know. We will know." a mathematician named Kurt Godel was developing his "incompleteness" theorems. When a mathematician proves a new theorem it involves the use of previously proved theorems or assumed axioms. Each new addition to the body of logical, mathematical knowledge builds upon what was previously established. The question is whether this will continue until every mathematical truth is established by proof.

Completeness is the concept that a logical, mathematical system can be used to prove every scientific truth. Naturally, incompleteness means the opposite, the inability of a logical, mathematical system to ultimately prove everything. An apt metaphor is a puzzle. Completeness would refer to a puzzle with all the pieces being present and all of them being capable of fitting together into a final, cohesive image. On the other hand, incompleteness would be a puzzle that is missing pieces or contains pieces that do not fit with any piece.

Kurt Godel is considered to be one of the greatest mathematicians of the twentieth century, if not the greatest. His proof of incompleteness of mathematics involves a brilliant trick, he expressed the process of mathematical theorem proving within mathematics itself. He used the axiomatic system of mathematics devised by Bertrand Russell, which was intended to be a universal framework for all mathematical and scientific knowledge. Obviously all mathematical truth had not been discovered, but Russell's system was the starting point. It was to serve as a scaffold and foundation on which to assemble discovered truth.

Each theorem in Russell's system depends on previously discovered theorems and possibly some axioms. Since a number (integer) can be uniquely factored into primes, Godel devised a way of mapping each theorem to a number. That way when he made a proof using numbers, he was actually making a proof about mathematics itself. His proof involved introducing theorems, in the form of numbers, that were true but could not be connected to any other theorem or axiom via proof within Russell's system. Worse yet for Russell’s system, if an updated version of Russell's system was created with that unprovable theorem included as an axiom, a starting assumption, Godel's proof still holds and there would be yet another unprovable theorem. This recurrence would continue on forever, new systems created with unprovable theorems which in turn would produce unprovable theorems. Only this infinite recurrence of systems could contain everything that is true mathematically. Further, Godel proved this incompleteness was not specific to Russell's system, but any axiomatic mathematical system. Finally, this is not some kind of abstract limitation, examples of theorems that are true without the possibility of proof have been found, one such example is called Goodstein's theorem.

Godel went further, he proved that any axiomatic mathematical system could not be guaranteed to be "consistent." Returning to the metaphor of the puzzle, an "inconsistent" puzzle would be a bunch of pieces that are actually two or more smaller puzzles that cannot be connected with each other. In other words, an inconsistent mathematical system would be one that produces theorems that are contradictory. The individual theorems themselves may have a perfectly logical proof and yet they are incompatible with each other.

The significance of Godel's work is that it proves that there is truth without any hope of proof. Prior to his theorems it was natural to believe that the progress of mathematics would eventually lead to the discovery of every mathematical truth. At the very least this belief could have been imagined to be theoretically possible. However, Godel's theorems have shown that there exists a limit on mathematical and logic thought. For further insight, the book Godel, Escher, Bach: An Eternal Golden Braid covers the proof in greater depth.

### Computational Limits to Deductive Reasoning

Part of Russell and Hilbert's motivation to formalize mathematics into an axiomatic system was to make the process of scientific discovery more mechanical and deliberate. Then with the invention of the digital computer, the natural question was whether logical deduction and the creation of mathematical proofs could be automated. In fact, mathematical and logical theorem proving can be framed as a computer science problem called "satisfiability." There is a problem however, not all computer science problems are created equal.

Many problems are solvable with computers, the issue is how long the computer will take to solve the problem. For example, consider sorting a list of numbers e.g. reordering 4, 6, -1, 5, 3, 2 into -1, 2, 3, 4, 5, 6. The amount of time it takes to solve a sorting problem in general depends on the length of the list. If "n" is the length of the list a naive solution will take about $$n^2$$ time, while a more efficient algorithm would take about n log(n) time. Sorting a list of numbers is a tractable problem because the time required is roughly speaking polynomial. As the length of the list increases so does the time it takes to sort it, but only by a reasonable (polynomial) amount of time.

There are many computer science problems that are known, or least very widely believed, to not be tractable. An intractable problem makes more than polynomial time, e.g. exponential, $$2^n$$. One example of an intractable type of problem is the traveling salesman problem. Imagine being a salesman that travels from city to city selling your wares. You have a list of cities that you would like to visit once on your trip and you would like to start and end in your hometown. Naturally you would like to make your trip as short as possible. This problem sounds innocuous but is quite difficult. Even a clever algorithm can in general take $$n^2 \; 2^n$$ time. That means as more destinations are added to the list of cities to visit, the time it takes to find the optimal tour of all the cities increases exponentially. What this means is there is a "limit" to the size of the optimal tour that can be found. For example, for a particular computer, it can calculate the optimal tour for 100 cities in a couple minutes, for 101 cities it takes hours, and for 1000 cities it would take a billion years.

The problem inherently resists being split into smaller problems, there is no known way to solve the problem more efficiently. For example, the optimal tour of all the major cities in North America cannot be found by combining the solution for the USA and solution for Canada because the optimal tour for North America may cross the border. There is no way to efficiently combine the solutions for the USA and Canada to create the North American solution.

Though computers are generally getting faster year after year, it is not clear that this trend will continue forever. The larger issue is that the increase in computer processing power is slower than the rate that intractable problems like the traveling salesman problem grow. This means a doubling of processing power means a small increase in the size of problem that can be solved e.g. optimal tours of 1 or 2 more cities can be found.

The problem of automatic theorem proving i.e. "satisfiability" is just as difficult as the traveling salesman problem. Just as time required to solve the traveling salesman problem increases exponentially as the number of cities increases, the time required to prove a theorem is exponential in the size of axioms, facts, and deductive rules involved. What this means is that there are theorems that are true that cannot be feasibly proved. The plan of Russell and Hilbert to systematize mathematics and continually build a body of scientific knowledge ultimately collapses under its own weight due to the volume of knowledge. At the very least, there is no practical way to deduce everything that is logically and mathematically true due the limitations of computational power and time.

The idea of systematizing logic and mathematics into a universal collection of scientific truth is simply not possible. There are real limitations from both above and below: Godel's incompleteness theorems proved that there are theoretic limits to what is knowable logically and computational intractability limits the ability of performing deduction in general. In short, there are real theoretic and computational limits to what is knowable mathematically and logically.