home | alphabetical index | |||||||

## Mathematical logicMathematical logic is a discipline within mathematics, studying formal systems in relation to the way they encode intuitive concepts of proof and computation. As a matter of history, it was developed to understand and present the work of Kurt Gödel on the foundations of mathematics. See the list of mathematical logic topics.
## The extent of mathematical logic
Although the layperson may think that mathematical logic is the
As a result of studies in mathematical logic one can have a rational discussion of many of the issues in the foundations of mathematics, though it would be misleading to say that the controversies that were alive in the period 1900-1925 have all been settled. While the traditional development of logic (see list of topics in logic) put heavy emphasis on Much of the subject relies on the existence of efficient proof-checking algorithms. This not emphasized in traditional treatments: this may change as software advances and exposition then starts to catch up. ## The founding resultsSome important results, all discovered during the 1930s, are:
- Putative proofs of universal validity of first-order formulas can be checked quickly for validity, algorithmically. In technical language, the set of proofs is primitive recursive. Essentially, this is Gödel's completeness theorem, although that theorem is usually stated in a way that does not make it obvious that it has anything to do with algorithms.
- The set of valid first-order formulas is
*not*computable, i.e., there is no algorithm for checking for universal validity. There is, however, an algorithm that behaves as follows: Given a first-order formula as its input, the algorithm eventually halts if the formula is universally valid, and runs forever otherwise. If the algorithm has been running for a trillion years, the answer remains unknown. In other words, this set is "recursively enumerable", or, as it is sometimes more suggestively put, "semi-decidable". - The set of all universally valid second-order formulas is not even recursively enumerable. This is a consequence of Gödel's incompleteness theorem.
## External links
| |||||||

copyright © 2004 FactsAbout.com |