GetWiki
Mathematical logic
ARTICLE SUBJECTS
being →
database →
ethics →
fiction →
history →
internet →
language →
linux →
logic →
method →
news →
policy →
purpose →
religion →
science →
software →
truth →
unix →
wiki →
ARTICLE TYPES
essay →
feed →
help →
system →
wiki →
ARTICLE ORIGINS
critical →
forked →
imported →
original →
Mathematical logic
please note:
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
{{for|Quine's theory sometimes called "Mathematical Logic"|New Foundations}}{{Citation style|date=July 2019|details=In particular, use Harvard (parenthetical) referencing}}{{Use Harvard referencing|date=July 2019}}{{short description|Subfield of mathematics}}Mathematical logic is a subfield of mathematics exploring the applications of formal logic to mathematics. It bears close connections to metamathematics, the foundations of mathematics, and theoretical computer science.Undergraduate texts include Boolos, Burgess, and Jeffrey (2002), Enderton (2001), and Mendelson (1997). A classic graduate text by Shoenfield (2001) first appeared in 1967. The unifying themes in mathematical logic include the study of the expressive power of formal systems and the deductive power of formal proof systems.
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
Subfields and scope
The Handbook of Mathematical Logic {{harv|Barwise|1989}} makes a rough division of contemporary mathematical logic into four areas:- set theory
- model theory
- recursion theory, and
- proof theory and constructive mathematics (considered as parts of a single area).
History
Mathematical logic emerged in the mid-19th century as a subfield of mathematics, reflecting the confluence of two traditions: formal philosophical logic and mathematics (FerreirÃ³s 2001, p. 443). "Mathematical logic, also called 'logistic', 'symbolic logic', the 'algebra of logic', and, more recently, simply 'formal logic', is the set of logical theories elaborated in the course of the last [nineteenth] century with the aid of an artificial notation and a rigorously deductive method."Jozef Maria Bochenski, A Precis of Mathematical Logic (1959), rev. and trans., Albert Menne, ed. and trans., Otto Bird, Dordrecht, South Holland: Reidel, Sec. 0.1, p. 1. Before this emergence, logic was studied with rhetoric, with calculationes,Richard Swineshead (1498), Calculationes Suiseth Anglici, Papie: Per Franciscum Gyrardengum. through the syllogism, and with philosophy. The first half of the 20th century saw an explosion of fundamental results, accompanied by vigorous debate over the foundations of mathematics.Early history
{{Further|History of logic}}Theories of logic were developed in many cultures in history, including China, India, Greece and the Islamic world. Greek methods, particularly Aristotelian logic (or term logic) as found in the Organon, found wide application and acceptance in Western science and mathematics for millennia.Boehner p. xiv The Stoics, especially Chrysippus, began the development of predicate logic. In 18th-century Europe, attempts to treat the operations of formal logic in a symbolic or algebraic way had been made by philosophical mathematicians including Leibniz and Lambert, but their labors remained isolated and little known.19th century
In the middle of the nineteenth century, George Boole and then Augustus De Morgan presented systematic mathematical treatments of logic. Their work, building on work by algebraists such as George Peacock, extended the traditional Aristotelian doctrine of logic into a sufficient framework for the study of foundations of mathematics (Katz 1998, p. 686).Charles Sanders Peirce built upon the work of Boole to develop a logical system for relations and quantifiers, which he published in several papers from 1870 to 1885.Gottlob Frege presented an independent development of logic with quantifiers in his Begriffsschrift, published in 1879, a work generally considered as marking a turning point in the history of logic. Frege's work remained obscure, however, until Bertrand Russell began to promote it near the turn of the century. The two-dimensional notation Frege developed was never widely adopted and is unused in contemporary texts.From 1890 to 1905, Ernst SchrÃ¶der published Vorlesungen Ã¼ber die Algebra der Logik in three volumes. This work summarized and extended the work of Boole, De Morgan, and Peirce, and was a comprehensive reference to symbolic logic as it was understood at the end of the 19th century.Foundational theories
Concerns that mathematics had not been built on a proper foundation led to the development of axiomatic systems for fundamental areas of mathematics such as arithmetic, analysis, and geometry.In logic, the term arithmetic refers to the theory of the natural numbers. Giuseppe Peano (1889) published a set of axioms for arithmetic that came to bear his name (Peano axioms), using a variation of the logical system of Boole and SchrÃ¶der but adding quantifiers. Peano was unaware of Frege's work at the time. Around the same time Richard Dedekind showed that the natural numbers are uniquely characterized by their induction properties. Dedekind (1888) proposed a different characterization, which lacked the formal logical character of Peano's axioms. Dedekind's work, however, proved theorems inaccessible in Peano's system, including the uniqueness of the set of natural numbers (up to isomorphism) and the recursive definitions of addition and multiplication from the successor function and mathematical induction.In the mid-19th century, flaws in Euclid's axioms for geometry became known (Katz 1998, p. 774). In addition to the independence of the parallel postulate, established by Nikolai Lobachevsky in 1826 (Lobachevsky 1840), mathematicians discovered that certain theorems taken for granted by Euclid were not in fact provable from his axioms. Among these is the theorem that a line contains at least two points, or that circles of the same radius whose centers are separated by that radius must intersect. Hilbert (1899) developed a complete set of axioms for geometry, building on previous work by Pasch (1882). The success in axiomatizing geometry motivated Hilbert to seek complete axiomatizations of other areas of mathematics, such as the natural numbers and the real line. This would prove to be a major area of research in the first half of the 20th century.The 19th century saw great advances in the theory of real analysis, including theories of convergence of functions and Fourier series. Mathematicians such as Karl Weierstrass began to construct functions that stretched intuition, such as nowhere-differentiable continuous functions. Previous conceptions of a function as a rule for computation, or a smooth graph, were no longer adequate. Weierstrass began to advocate the arithmetization of analysis, which sought to axiomatize analysis using properties of the natural numbers. The modern (Îµ, Î´)-definition of limit and continuous functions was already developed by Bolzano in 1817 (Felscher 2000), but remained relatively unknown.Cauchy in 1821 defined continuity in terms of infinitesimals (see Cours d'Analyse, page 34). In 1858, Dedekind proposed a definition of the real numbers in terms of Dedekind cuts of rational numbers (Dedekind 1872), a definition still employed in contemporary texts.Georg Cantor developed the fundamental concepts of infinite set theory. His early results developed the theory of cardinality and proved that the reals and the natural numbers have different cardinalities (Cantor 1874). Over the next twenty years, Cantor developed a theory of transfinite numbers in a series of publications. In 1891, he published a new proof of the uncountability of the real numbers that introduced the diagonal argument, and used this method to prove Cantor's theorem that no set can have the same cardinality as its powerset. Cantor believed that every set could be well-ordered, but was unable to produce a proof for this result, leaving it as an open problem in 1895 (Katz 1998, p. 807).20th century
In the early decades of the 20th century, the main areas of study were set theory and formal logic. The discovery of paradoxes in informal set theory caused some to wonder whether mathematics itself is inconsistent, and to look for proofs of consistency.In 1900, Hilbert posed a famous list of 23 problems for the next century. The first two of these were to resolve the continuum hypothesis and prove the consistency of elementary arithmetic, respectively; the tenth was to produce a method that could decide whether a multivariate polynomial equation over the integers has a solution. Subsequent work to resolve these problems shaped the direction of mathematical logic, as did the effort to resolve Hilbert's Entscheidungsproblem, posed in 1928. This problem asked for a procedure that would decide, given a formalized mathematical statement, whether the statement is true or false.Set theory and paradoxes
Ernst Zermelo (1904) gave a proof that every set could be well-ordered, a result Georg Cantor had been unable to obtain. To achieve the proof, Zermelo introduced the axiom of choice, which drew heated debate and research among mathematicians and the pioneers of set theory. The immediate criticism of the method led Zermelo to publish a second exposition of his result, directly addressing criticisms of his proof (Zermelo 1908a). This paper led to the general acceptance of the axiom of choice in the mathematics community.Skepticism about the axiom of choice was reinforced by recently discovered paradoxes in naive set theory. Cesare Burali-Forti (1897) was the first to state a paradox: the Burali-Forti paradox shows that the collection of all ordinal numbers cannot form a set. Very soon thereafter, Bertrand Russell discovered Russell's paradox in 1901, and Jules Richard (1905) discovered Richard's paradox.Zermelo (1908b) provided the first set of axioms for set theory. These axioms, together with the additional axiom of replacement proposed by Abraham Fraenkel, are now called Zermeloâ€“Fraenkel set theory (ZF). Zermelo's axioms incorporated the principle of limitation of size to avoid Russell's paradox.In 1910, the first volume of Principia Mathematica by Russell and Alfred North Whitehead was published. This seminal work developed the theory of functions and cardinality in a completely formal framework of type theory, which Russell and Whitehead developed in an effort to avoid the paradoxes. Principia Mathematica is considered one of the most influential works of the 20th century, although the framework of type theory did not prove popular as a foundational theory for mathematics (FerreirÃ³s 2001, p. 445).Fraenkel (1922) proved that the axiom of choice cannot be proved from the axioms of Zermelo's set theory with urelements. Later work by Paul Cohen (1966) showed that the addition of urelements is not needed, and the axiom of choice is unprovable in ZF. Cohen's proof developed the method of forcing, which is now an important tool for establishing independence results in set theory.See also {{harvnb|Cohen|2008}}.Symbolic logic
Leopold LÃ¶wenheim (1915) and Thoralf Skolem (1920) obtained the LÃ¶wenheimâ€“Skolem theorem, which says that first-order logic cannot control the cardinalities of infinite structures. Skolem realized that this theorem would apply to first-order formalizations of set theory, and that it implies any such formalization has a countable model. This counterintuitive fact became known as Skolem's paradox.In his doctoral thesis, Kurt GÃ¶del (1929) proved the completeness theorem, which establishes a correspondence between syntax and semantics in first-order logic. GÃ¶del used the completeness theorem to prove the compactness theorem, demonstrating the finitary nature of first-order logical consequence. These results helped establish first-order logic as the dominant logic used by mathematicians.In 1931, GÃ¶del published On Formally Undecidable Propositions of Principia Mathematica and Related Systems, which proved the incompleteness (in a different meaning of the word) of all sufficiently strong, effective first-order theories. This result, known as GÃ¶del's incompleteness theorem, establishes severe limitations on axiomatic foundations for mathematics, striking a strong blow to Hilbert's program. It showed the impossibility of providing a consistency proof of arithmetic within any formal theory of arithmetic. Hilbert, however, did not acknowledge the importance of the incompleteness theorem for some time.In the foreword to the 1934 first edition of "Grundlagen der Mathematik" {{harv|Hilbert|Bernays|1934}}, Bernays wrote the following, which is reminiscent of the famous note by Frege when informed of Russell's paradox."Die AusfÃ¼hrung dieses Vorhabens hat eine wesentliche VerzÃ¶gerung dadurch erfahren, daÃŸ in einem Stadium, in dem die Darstellung schon ihrem AbschuÃŸ nahe war, durch das Erscheinen der Arbeiten von Herbrand und von GÃ¶del eine verÃ¤nderte Situation im Gebiet der Beweistheorie entstand, welche die BerÃ¼cksichtigung neuer Einsichten zur Aufgabe machte. Dabei ist der Umfang des Buches angewachsen, so daÃŸ eine Teilung in zwei BÃ¤nde angezeigt erschien." Translation: "Carrying out this plan [by Hilbert for an exposition on proof theory for mathematical logic] has experienced an essential delay because, at the stage at which the exposition was already near to its conclusion, there occurred an altered situation in the area of proof theory due to the appearance of works by Herbrand and GÃ¶del, which necessitated the consideration of new insights. Thus the scope of this book has grown, so that a division into two volumes seemed advisable." So certainly Hilbert was aware of the importance of GÃ¶del's work by 1934. The second volume in 1939 included a form of Gentzen's consistency proof for arithmetic.GÃ¶del's theorem shows that a consistency proof of any sufficiently strong, effective axiom system cannot be obtained in the system itself, if the system is consistent, nor in any weaker system. This leaves open the possibility of consistency proofs that cannot be formalized within the system they consider. Gentzen (1936) proved the consistency of arithmetic using a finitistic system together with a principle of transfinite induction. Gentzen's result introduced the ideas of cut elimination and proof-theoretic ordinals, which became key tools in proof theory. GÃ¶del (1958) gave a different consistency proof, which reduces the consistency of classical arithmetic to that of intuitionistic arithmetic in higher types.Beginnings of the other branches
Alfred Tarski developed the basics of model theory.Beginning in 1935, a group of prominent mathematicians collaborated under the pseudonym Nicolas Bourbaki to publish a series of encyclopedic mathematics texts. These texts, written in an austere and axiomatic style, emphasized rigorous presentation and set-theoretic foundations. Terminology coined by these texts, such as the words bijection, injection, and surjection, and the set-theoretic foundations the texts employed, were widely adopted throughout mathematics.The study of computability came to be known as recursion theory, because early formalizations by GÃ¶del and Kleene relied on recursive definitions of functions.A detailed study of this terminology is given by Soare (1996). When these definitions were shown equivalent to Turing's formalization involving Turing machines, it became clear that a new concept – the computable function – had been discovered, and that this definition was robust enough to admit numerous independent characterizations. In his work on the incompleteness theorems in 1931, GÃ¶del lacked a rigorous concept of an effective formal system; he immediately realized that the new definitions of computability could be used for this purpose, allowing him to state the incompleteness theorems in generality that could only be implied in the original paper.Numerous results in recursion theory were obtained in the 1940s by Stephen Cole Kleene and Emil Leon Post. Kleene (1943) introduced the concepts of relative computability, foreshadowed by Turing (1939), and the arithmetical hierarchy. Kleene later generalized recursion theory to higher-order functionals. Kleene and Kreisel studied formal versions of intuitionistic mathematics, particularly in the context of proof theory.Formal logical systems {{anchor|Formal logic}}
At its core, mathematical logic deals with mathematical concepts expressed using formal logical systems. These systems, though they differ in many details, share the common property of considering only expressions in a fixed formal language. The systems of propositional logic and first-order logic are the most widely studied today, because of their applicability to foundations of mathematics and because of their desirable proof-theoretic properties.FerreirÃ³s (2001) surveys the rise of first-order logic over other formal logics in the early 20th century. Stronger classical logics such as second-order logic or infinitary logic are also studied, along with nonclassical logics such as intuitionistic logic.First-order logic
First-order logic is a particular formal system of logic. Its syntax involves only finite expressions as well-formed formulas, while its semantics are characterized by the limitation of all quantifiers to a fixed domain of discourse.Early results from formal logic established limitations of first-order logic. The LÃ¶wenheimâ€“Skolem theorem (1919) showed that if a set of sentences in a countable first-order language has an infinite model then it has at least one model of each infinite cardinality. This shows that it is impossible for a set of first-order axioms to characterize the natural numbers, the real numbers, or any other infinite structure up to isomorphism. As the goal of early foundational studies was to produce axiomatic theories for all parts of mathematics, this limitation was particularly stark.GÃ¶del's completeness theorem (GÃ¶del 1929) established the equivalence between semantic and syntactic definitions of logical consequence in first-order logic. It shows that if a particular sentence is true in every model that satisfies a particular set of axioms, then there must be a finite deduction of the sentence from the axioms. The compactness theorem first appeared as a lemma in GÃ¶del's proof of the completeness theorem, and it took many years before logicians grasped its significance and began to apply it routinely. It says that a set of sentences has a model if and only if every finite subset has a model, or in other words that an inconsistent set of formulas must have a finite inconsistent subset. The completeness and compactness theorems allow for sophisticated analysis of logical consequence in first-order logic and the development of model theory, and they are a key reason for the prominence of first-order logic in mathematics.GÃ¶del's incompleteness theorems (GÃ¶del 1931) establish additional limits on first-order axiomatizations. The first incompleteness theorem states that for any consistent, effectively given (defined below) logical system that is capable of interpreting arithmetic, there exists a statement that is true (in the sense that it holds for the natural numbers) but not provable within that logical system (and which indeed may fail in some non-standard models of arithmetic which may be consistent with the logical system). For example, in every logical system capable of expressing the Peano axioms, the GÃ¶del sentence holds for the natural numbers but cannot be proved.Here a logical system is said to be effectively given if it is possible to decide, given any formula in the language of the system, whether the formula is an axiom, and one which can express the Peano axioms is called "sufficiently strong." When applied to first-order logic, the first incompleteness theorem implies that any sufficiently strong, consistent, effective first-order theory has models that are not elementarily equivalent, a stronger limitation than the one established by the LÃ¶wenheimâ€“Skolem theorem. The second incompleteness theorem states that no sufficiently strong, consistent, effective axiom system for arithmetic can prove its own consistency, which has been interpreted to show that Hilbert's program cannot be completed.Other classical logics
Many logics besides first-order logic are studied. These include infinitary logics, which allow for formulas to provide an infinite amount of information, and higher-order logics, which include a portion of set theory directly in their semantics.The most well studied infinitary logic is L_{omega_1,omega}. In this logic, quantifiers may only be nested to finite depths, as in first-order logic, but formulas may have finite or countably infinite conjunctions and disjunctions within them. Thus, for example, it is possible to say that an object is a whole number using a formula of L_{omega_1,omega} such as
(x = 0) lor (x = 1) lor (x = 2) lor cdots.
Higher-order logics allow for quantification not only of elements of the domain of discourse, but subsets of the domain of discourse, sets of such subsets, and other objects of higher type. The semantics are defined so that, rather than having a separate domain for each higher-type quantifier to range over, the quantifiers instead range over all objects of the appropriate type. The logics studied before the development of first-order logic, for example Frege's logic, had similar set-theoretic aspects. Although higher-order logics are more expressive, allowing complete axiomatizations of structures such as the natural numbers, they do not satisfy analogues of the completeness and compactness theorems from first-order logic, and are thus less amenable to proof-theoretic analysis.Another type of logics are {{vanchor|fixed-point logic}}s that allow inductive definitions, like one writes for primitive recursive functions.One can formally define an extension of first-order logic — a notion which encompasses all logics in this section because they behave like first-order logic in certain fundamental ways, but does not encompass all logics in general, e.g. it does not encompass intuitionistic, modal or fuzzy logic. LindstrÃ¶m's theorem implies that the only extension of first-order logic satisfying both the compactness theorem and the Downward LÃ¶wenheimâ€“Skolem theorem is first-order logic.Nonclassical and modal logic
Modal logics include additional modal operators, such as an operator which states that a particular formula is not only true, but necessarily true. Although modal logic is not often used to axiomatize mathematics, it has been used to study the properties of first-order provability (Solovay 1976) and set-theoretic forcing (Hamkins and LÃ¶we 2007).Intuitionistic logic was developed by Heyting to study Brouwer's program of intuitionism, in which Brouwer himself avoided formalization. Intuitionistic logic specifically does not include the law of the excluded middle, which states that each sentence is either true or its negation is true. Kleene's work with the proof theory of intuitionistic logic showed that constructive information can be recovered from intuitionistic proofs. For example, any provably total function in intuitionistic arithmetic is computable; this is not true in classical theories of arithmetic such as Peano arithmetic.Algebraic logic
Algebraic logic uses the methods of abstract algebra to study the semantics of formal logics. A fundamental example is the use of Boolean algebras to represent truth values in classical propositional logic, and the use of Heyting algebras to represent truth values in intuitionistic propositional logic. Stronger logics, such as first-order logic and higher-order logic, are studied using more complicated algebraic structures such as cylindric algebras.Set theory
Set theory is the study of sets, which are abstract collections of objects. Many of the basic notions, such as ordinal and cardinal numbers, were developed informally by Cantor before formal axiomatizations of set theory were developed. The first such axiomatization, due to Zermelo (1908b), was extended slightly to become Zermeloâ€“Fraenkel set theory (ZF), which is now the most widely used foundational theory for mathematics.Other formalizations of set theory have been proposed, including von Neumannâ€“Bernaysâ€“GÃ¶del set theory (NBG), Morseâ€“Kelley set theory (MK), and New Foundations (NF). Of these, ZF, NBG, and MK are similar in describing a cumulative hierarchy of sets. New Foundations takes a different approach; it allows objects such as the set of all sets at the cost of restrictions on its set-existence axioms. The system of Kripkeâ€“Platek set theory is closely related to generalized recursion theory.Two famous statements in set theory are the axiom of choice and the continuum hypothesis. The axiom of choice, first stated by Zermelo (1904), was proved independent of ZF by Fraenkel (1922), but has come to be widely accepted by mathematicians. It states that given a collection of nonempty sets there is a single set C that contains exactly one element from each set in the collection. The set C is said to "choose" one element from each set in the collection. While the ability to make such a choice is considered obvious by some, since each set in the collection is nonempty, the lack of a general, concrete rule by which the choice can be made renders the axiom nonconstructive. Stefan Banach and Alfred Tarski (1924{{Citation not found|date=July 2019}}) showed that the axiom of choice can be used to decompose a solid ball into a finite number of pieces which can then be rearranged, with no scaling, to make two solid balls of the original size. This theorem, known as the Banachâ€“Tarski paradox, is one of many counterintuitive results of the axiom of choice.The continuum hypothesis, first proposed as a conjecture by Cantor, was listed by David Hilbert as one of his 23 problems in 1900. GÃ¶del showed that the continuum hypothesis cannot be disproven from the axioms of Zermeloâ€“Fraenkel set theory (with or without the axiom of choice), by developing the constructible universe of set theory in which the continuum hypothesis must hold. In 1963, Paul Cohen showed that the continuum hypothesis cannot be proven from the axioms of Zermeloâ€“Fraenkel set theory (Cohen 1966). This independence result did not completely settle Hilbert's question, however, as it is possible that new axioms for set theory could resolve the hypothesis. Recent work along these lines has been conducted by W. Hugh Woodin, although its importance is not yet clear (Woodin 2001).Contemporary research in set theory includes the study of large cardinals and determinacy. Large cardinals are cardinal numbers with particular properties so strong that the existence of such cardinals cannot be proved in ZFC. The existence of the smallest large cardinal typically studied, an inaccessible cardinal, already implies the consistency of ZFC. Despite the fact that large cardinals have extremely high cardinality, their existence has many ramifications for the structure of the real line. Determinacy refers to the possible existence of winning strategies for certain two-player games (the games are said to be determined). The existence of these strategies implies structural properties of the real line and other Polish spaces.Model theory
Model theory studies the models of various formal theories. Here a theory is a set of formulas in a particular formal logic and signature, while a model is a structure that gives a concrete interpretation of the theory. Model theory is closely related to universal algebra and algebraic geometry, although the methods of model theory focus more on logical considerations than those fields.The set of all models of a particular theory is called an elementary class; classical model theory seeks to determine the properties of models in a particular elementary class, or determine whether certain classes of structures form elementary classes.The method of quantifier elimination can be used to show that definable sets in particular theories cannot be too complicated. Tarski (1948) established quantifier elimination for real-closed fields, a result which also shows the theory of the field of real numbers is decidable. (He also noted that his methods were equally applicable to algebraically closed fields of arbitrary characteristic.) A modern subfield developing from this is concerned with o-minimal structures.Morley's categoricity theorem, proved by Michael D. Morley (1965), states that if a first-order theory in a countable language is categorical in some uncountable cardinality, i.e. all models of this cardinality are isomorphic, then it is categorical in all uncountable cardinalities.A trivial consequence of the continuum hypothesis is that a complete theory with less than continuum many nonisomorphic countable models can have only countably many. Vaught's conjecture, named after Robert Lawson Vaught, says that this is true even independently of the continuum hypothesis. Many special cases of this conjecture have been established.Recursion theory
Recursion theory, also called computability theory, studies the properties of computable functions and the Turing degrees, which divide the uncomputable functions into sets that have the same level of uncomputability. Recursion theory also includes the study of generalized computability and definability. Recursion theory grew from the work of RÃ³zsa PÃ©ter, Alonzo Church and Alan Turing in the 1930s, which was greatly extended by Kleene and Post in the 1940s.WEB, Soare, Robert Irving, Computability Theory and Applications: The Art of Classical Computability,weblink Department of Mathematics, University of Chicago, 23 August 2017, 22 December 2011, Classical recursion theory focuses on the computability of functions from the natural numbers to the natural numbers. The fundamental results establish a robust, canonical class of computable functions with numerous independent, equivalent characterizations using Turing machines, λ calculus, and other systems. More advanced results concern the structure of the Turing degrees and the lattice of recursively enumerable sets.Generalized recursion theory extends the ideas of recursion theory to computations that are no longer necessarily finite. It includes the study of computability in higher types as well as areas such as hyperarithmetical theory and α-recursion theory.Contemporary research in recursion theory includes the study of applications such as algorithmic randomness, computable model theory, and reverse mathematics, as well as new results in pure recursion theory.Algorithmically unsolvable problems
An important subfield of recursion theory studies algorithmic unsolvability; a decision problem or function problem is algorithmically unsolvable if there is no possible computable algorithm that returns the correct answer for all legal inputs to the problem. The first results about unsolvability, obtained independently by Church and Turing in 1936, showed that the Entscheidungsproblem is algorithmically unsolvable. Turing proved this by establishing the unsolvability of the halting problem, a result with far-ranging implications in both recursion theory and computer science.There are many known examples of undecidable problems from ordinary mathematics. The word problem for groups was proved algorithmically unsolvable by Pyotr Novikov in 1955 and independently by W. Boone in 1959. The busy beaver problem, developed by Tibor RadÃ³ in 1962, is another well-known example.Hilbert's tenth problem asked for an algorithm to determine whether a multivariate polynomial equation with integer coefficients has a solution in the integers. Partial progress was made by Julia Robinson, Martin Davis and Hilary Putnam. The algorithmic unsolvability of the problem was proved by Yuri Matiyasevich in 1970 (Davis 1973).Proof theory and constructive mathematics
Proof theory is the study of formal proofs in various logical deduction systems. These proofs are represented as formal mathematical objects, facilitating their analysis by mathematical techniques. Several deduction systems are commonly considered, including Hilbert-style deduction systems, systems of natural deduction, and the sequent calculus developed by Gentzen.The study of constructive mathematics, in the context of mathematical logic, includes the study of systems in non-classical logic such as intuitionistic logic, as well as the study of predicative systems. An early proponent of predicativism was Hermann Weyl, who showed it is possible to develop a large part of real analysis using only predicative methods (Weyl 1918){{Citation not found|date=July 2019}}.Because proofs are entirely finitary, whereas truth in a structure is not, it is common for work in constructive mathematics to emphasize provability. The relationship between provability in classical (or nonconstructive) systems and provability in intuitionistic (or constructive, respectively) systems is of particular interest. Results such as the GÃ¶delâ€“Gentzen negative translation show that it is possible to embed (or translate) classical logic into intuitionistic logic, allowing some properties about intuitionistic proofs to be transferred back to classical proofs.Recent developments in proof theory include the study of proof mining by Ulrich Kohlenbach and the study of proof-theoretic ordinals by Michael Rathjen.Applications
"Mathematical logic has been successfully applied not only to mathematics and its foundations (G. Frege, B. Russell, D. Hilbert, P. Bernays, H. Scholz, R. Carnap, S. Lesniewski, T. Skolem), but also to physics (R. Carnap, A. Dittrich, B. Russell, C. E. Shannon, A. N. Whitehead, H. Reichenbach, P. Fevrier), to biology (J. H. Woodger, A. Tarski), to psychology (F. B. Fitch, C. G. Hempel), to law and morals (K. Menger, U. Klug, P. Oppenheim), to economics (J. Neumann, O. Morgenstern), to practical questions (E. C. Berkeley, E. Stamm), and even to metaphysics (J. [Jan] Salamucha, H. Scholz, J. M. Bochenski). Its applications to the history of logic have proven extremely fruitful (J. Lukasiewicz, H. Scholz, B. Mates, A. Becker, E. Moody, J. Salamucha, K. Duerr, Z. Jordan, P. Boehner, J. M. Bochenski, S. [Stanislaw] T. Schayer, D. Ingalls)."Jozef Maria Bochenski, A Precis of Mathematical Logic, rev. and trans., Albert Menne, ed. and trans., Otto Bird, Dordrecht, South Holland: Reidel, Sec. 0.3, p. 2. "Applications have also been made to theology (F. Drewnowski, J. Salamucha, I. Thomas)."Jozef Maria Bochenski, A Precis of Mathematical Logic, rev. and trans., Albert Menne, ed. and trans., Otto Bird, Dordrecht, South Holland: Reidel, Sec. 0.3, p. 2.Connections with computer science
The study of computability theory in computer science is closely related to the study of computability in mathematical logic. There is a difference of emphasis, however. Computer scientists often focus on concrete programming languages and feasible computability, while researchers in mathematical logic often focus on computability as a theoretical concept and on noncomputability.The theory of semantics of programming languages is related to model theory, as is program verification (in particular, model checking). The Curry–Howard isomorphism between proofs and programs relates to proof theory, especially intuitionistic logic. Formal calculi such as the lambda calculus and combinatory logic are now studied as idealized programming languages.Computer science also contributes to mathematics by developing techniques for the automatic checking or even finding of proofs, such as automated theorem proving and logic programming.Descriptive complexity theory relates logics to computational complexity. The first significant result in this area, Fagin's theorem (1974) established that NP is precisely the set of languages expressible by sentences of existential second-order logic.Foundations of mathematics
In the 19th century, mathematicians became aware of logical gaps and inconsistencies in their field. It was shown that Euclid's axioms for geometry, which had been taught for centuries as an example of the axiomatic method, were incomplete. The use of infinitesimals, and the very definition of function, came into question in analysis, as pathological examples such as Weierstrass' nowhere-differentiable continuous function were discovered.Cantor's study of arbitrary infinite sets also drew criticism. Leopold Kronecker famously stated "God made the integers; all else is the work of man," endorsing a return to the study of finite, concrete objects in mathematics. Although Kronecker's argument was carried forward by constructivists in the 20th century, the mathematical community as a whole rejected them. David Hilbert argued in favor of the study of the infinite, saying "No one shall expel us from the Paradise that Cantor has created."Mathematicians began to search for axiom systems that could be used to formalize large parts of mathematics. In addition to removing ambiguity from previously naive terms such as function, it was hoped that this axiomatization would allow for consistency proofs. In the 19th century, the main method of proving the consistency of a set of axioms was to provide a model for it. Thus, for example, non-Euclidean geometry can be proved consistent by defining point to mean a point on a fixed sphere and line to mean a great circle on the sphere. The resulting structure, a model of elliptic geometry, satisfies the axioms of plane geometry except the parallel postulate.With the development of formal logic, Hilbert asked whether it would be possible to prove that an axiom system is consistent by analyzing the structure of possible proofs in the system, and showing through this analysis that it is impossible to prove a contradiction. This idea led to the study of proof theory. Moreover, Hilbert proposed that the analysis should be entirely concrete, using the term finitary to refer to the methods he would allow but not precisely defining them. This project, known as Hilbert's program, was seriously affected by GÃ¶del's incompleteness theorems, which show that the consistency of formal theories of arithmetic cannot be established using methods formalizable in those theories. Gentzen showed that it is possible to produce a proof of the consistency of arithmetic in a finitary system augmented with axioms of transfinite induction, and the techniques he developed to do so were seminal in proof theory.A second thread in the history of foundations of mathematics involves nonclassical logics and constructive mathematics. The study of constructive mathematics includes many different programs with various definitions of constructive. At the most accommodating end, proofs in ZF set theory that do not use the axiom of choice are called constructive by many mathematicians. More limited versions of constructivism limit themselves to natural numbers, number-theoretic functions, and sets of natural numbers (which can be used to represent real numbers, facilitating the study of mathematical analysis). A common idea is that a concrete means of computing the values of the function must be known before the function itself can be said to exist. In the early 20th century, Luitzen Egbertus Jan Brouwer founded intuitionism as a philosophy of mathematics. This philosophy, poorly understood at first, stated that in order for a mathematical statement to be true to a mathematician, that person must be able to intuit the statement, to not only believe its truth but understand the reason for its truth. A consequence of this definition of truth was the rejection of the law of the excluded middle, for there are statements that, according to Brouwer, could not be claimed to be true while their negations also could not be claimed true. Brouwer's philosophy was influential, and the cause of bitter disputes among prominent mathematicians. Later, Kleene and Kreisel would study formalized versions of intuitionistic logic (Brouwer rejected formalization, and presented his work in unformalized natural language). With the advent of the BHK interpretation and Kripke models, intuitionism became easier to reconcile with classical mathematics.See also
- Argument
- Informal logic
- Knowledge representation and reasoning
- Logic
- List of computability and complexity topics
- List of first-order theories
- List of logic symbols
- List of mathematical logic topics
- List of set theory topics
Notes
{{Reflist}}References
Undergraduate texts
- BOOK,weblink Formal logic: Classical problems and proofs, Luis M., Augusto, College Publications, London, 2019, 978-1-84890-317-3,
- {hide}Citation
|last1=Walicki
|first1=MichaÅ‚
|title=Introduction to Mathematical Logic
|publisher=World Scientific Publishing
|location=Singapore
|isbn=978-981-4343-87-9
|year=2011{edih}.
|first1=MichaÅ‚
|title=Introduction to Mathematical Logic
|publisher=World Scientific Publishing
|location=Singapore
|isbn=978-981-4343-87-9
|year=2011{edih}.
- {hide}Citation
|last1=Boolos
|first1=George
|author1-link=George Boolos
|last2=Burgess
|first2=John
|last3=Jeffrey
|first3=Richard
|author3-link=Richard Jeffrey
|title=Computability and Logic
|publisher=Cambridge University Press
|location=Cambridge
|edition=4th
|isbn=978-0-521-00758-0
|year=2002{edih}.
|first1=George
|author1-link=George Boolos
|last2=Burgess
|first2=John
|last3=Jeffrey
|first3=Richard
|author3-link=Richard Jeffrey
|title=Computability and Logic
|publisher=Cambridge University Press
|location=Cambridge
|edition=4th
|isbn=978-0-521-00758-0
|year=2002{edih}.
- {{citation | last1=Crossley | first1=J.N. | last2=Ash | first2=C.J. | last3=Brickhill | first3=C.J. | last4=Stillwell | first4=J.C. | last5=Williams | first5=N.H. | title=What is mathematical logic? | zbl=0251.02001 | location=London-Oxford-New York | publisher=Oxford University Press | year=1972 | isbn=978-0-19-888087-5 }}.
- {hide}Citation
|last1=Enderton
|first1=Herbert
|title=A mathematical introduction to logic
|publisher=Academic Press
|location=Boston, MA
|edition=2nd
|isbn=978-0-12-238452-3
|year=2001
{edih}. |first1=Herbert
|title=A mathematical introduction to logic
|publisher=Academic Press
|location=Boston, MA
|edition=2nd
|isbn=978-0-12-238452-3
|year=2001
- {hide}Citation
|last1=Fisher
|first1=Alec
|title=Formal Number Theory and Computability: A Workbook
|publisher=Oxford University Press
|location=USA
|edition=1st
|isbn=978-0-19-853188-3
|year=1982
{edih}. Suitable as a first course for independent study. |first1=Alec
|title=Formal Number Theory and Computability: A Workbook
|publisher=Oxford University Press
|location=USA
|edition=1st
|isbn=978-0-19-853188-3
|year=1982
- {{Citation
|last1=Hamilton
|first1=A.G.
|title=Logic for Mathematicians
|publisher=Cambridge University Press
|location=Cambridge
|edition=2nd
|isbn=978-0-521-36865-0
|year=1988}}.
|first1=A.G.
|title=Logic for Mathematicians
|publisher=Cambridge University Press
|location=Cambridge
|edition=2nd
|isbn=978-0-521-36865-0
|year=1988}}.
- {{Citation
|last1=Ebbinghaus
|first1=H.-D.
|last2=Flum
|first2=J.
|last3=Thomas
|first3=W.
|doi=
|title=Mathematical Logic
|url=https://www.springer.com/mathematics/book/978-0-387-94258-2
|publisher=Springer
|location=New York
|edition=2nd
|isbn=978-0-387-94258-2
|year=1994
}}. |first1=H.-D.
|last2=Flum
|first2=J.
|last3=Thomas
|first3=W.
|doi=
|title=Mathematical Logic
|url=https://www.springer.com/mathematics/book/978-0-387-94258-2
|publisher=Springer
|location=New York
|edition=2nd
|isbn=978-0-387-94258-2
|year=1994
- {{Citation
|last1=Katz
|first1=Robert
|title=Axiomatic Analysis
|publisher=D. C. Heath and Company
|location=Boston, MA
|year=1964}}.
|first1=Robert
|title=Axiomatic Analysis
|publisher=D. C. Heath and Company
|location=Boston, MA
|year=1964}}.
- {hide}Citation
|last1=Mendelson
|first1=Elliott
|author1link=Elliott Mendelson
|title=Introduction to Mathematical Logic
|publisher=Chapman & Hall
|location=London
|edition=4th
|isbn=978-0-412-80830-2
|year=1997
{edih}. |first1=Elliott
|author1link=Elliott Mendelson
|title=Introduction to Mathematical Logic
|publisher=Chapman & Hall
|location=London
|edition=4th
|isbn=978-0-412-80830-2
|year=1997
- {{Citation
|last=Rautenberg
|first=Wolfgang
|authorlink=Wolfgang Rautenberg
|doi=10.1007/978-1-4419-1221-3
|title=A Concise Introduction to Mathematical Logic
|url=http://www.springerlink.com/content/978-1-4419-1220-6/
|publisher=Springer Science+Business Media
|location=New York
|edition=3rd
|isbn=978-1-4419-1220-6
|year=2010
}}. |first=Wolfgang
|authorlink=Wolfgang Rautenberg
|doi=10.1007/978-1-4419-1221-3
|title=A Concise Introduction to Mathematical Logic
|url=http://www.springerlink.com/content/978-1-4419-1220-6/
|publisher=Springer Science+Business Media
|location=New York
|edition=3rd
|isbn=978-1-4419-1220-6
|year=2010
- {{Citation
|last1=Schwichtenberg
|author-link=Helmut Schwichtenberg
|first1=Helmut
|title=Mathematical Logic
|publisher=Mathematisches Institut der UniversitÃ¤t MÃ¼nchen
|location=Munich, Germany
|url=http://www.mathematik.uni-muenchen.de/~schwicht/lectures/logic/ws03/ml.pdf
|year=2003â€“2004
|accessdate=2016-02-24
}}. |author-link=Helmut Schwichtenberg
|first1=Helmut
|title=Mathematical Logic
|publisher=Mathematisches Institut der UniversitÃ¤t MÃ¼nchen
|location=Munich, Germany
|url=http://www.mathematik.uni-muenchen.de/~schwicht/lectures/logic/ws03/ml.pdf
|year=2003â€“2004
|accessdate=2016-02-24
- Shawn Hedman, A first course in logic: an introduction to model theory, proof theory, computability, and complexity, Oxford University Press, 2004, {{isbn|0-19-852981-3}}. Covers logics in close relation with computability theory and complexity theory
- {{Citation
|last1=van Dalen
|first1=Dirk
|title=Logic and Structure
|publisher=Springer-Verlag
|location=Berlin
|year=2013
|isbn=978-1-4471-4557-8
|doi=10.1007/978-1-4471-4558-5
|series=Universitext
}}.
|first1=Dirk
|title=Logic and Structure
|publisher=Springer-Verlag
|location=Berlin
|year=2013
|isbn=978-1-4471-4557-8
|doi=10.1007/978-1-4471-4558-5
|series=Universitext
}}.
Graduate texts
- {{Citation
| last1=Andrews
| first1=Peter B.
| title=An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof
| publisher=Kluwer Academic Publishers
| location=Boston
| edition=2nd
| isbn=978-1-4020-0763-7
| year=2002
}}. | first1=Peter B.
| title=An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof
| publisher=Kluwer Academic Publishers
| location=Boston
| edition=2nd
| isbn=978-1-4020-0763-7
| year=2002
- BOOK, harv, Barwise
, Jon
, Jon Barwise
, Handbook of Mathematical Logic
, Elsevier, North Holland
, Studies in Logic and the Foundations of Mathematics
, 978-0-444-86388-1
, 1989
, . , Jon Barwise
, Handbook of Mathematical Logic
, Elsevier, North Holland
, Studies in Logic and the Foundations of Mathematics
, 978-0-444-86388-1
, 1989
- {hide}Citation
| last1=Hodges
| first1=Wilfrid
| author1-link=Wilfrid Hodges
| title=A shorter model theory
| publisher=Cambridge University Press
| location=Cambridge | isbn=978-0-521-58713-6 | year=1997{edih}.
| first1=Wilfrid
| author1-link=Wilfrid Hodges
| title=A shorter model theory
| publisher=Cambridge University Press
| location=Cambridge | isbn=978-0-521-58713-6 | year=1997{edih}.
- {hide}Citation
| last1=Jech
| first1=Thomas
| author1-link=Thomas Jech
| title=Set Theory: Millennium Edition
| publisher=Springer-Verlag
| location=Berlin, New York
| series=Springer Monographs in Mathematics
| isbn=978-3-540-44085-7
| year=2003
{edih}. | first1=Thomas
| author1-link=Thomas Jech
| title=Set Theory: Millennium Edition
| publisher=Springer-Verlag
| location=Berlin, New York
| series=Springer Monographs in Mathematics
| isbn=978-3-540-44085-7
| year=2003
- Kleene, Stephen Cole.(1952), Introduction to Metamathematics. New York: Van Nostrand. (Ishi Press: 2009 reprint).
- Kleene, Stephen Cole. (1967), Mathematical Logic. John Wiley. Dover reprint, 2002. {{isbn|0-486-42533-9}}.
- {{Citation
| last1=Shoenfield
| first1=Joseph R.
| author1link=Joseph R. Shoenfield
| title=Mathematical Logic
| origyear=1967
| publisher=A K Peters
| edition=2nd
| isbn=978-1-56881-135-2
| year=2001
}}. | first1=Joseph R.
| author1link=Joseph R. Shoenfield
| title=Mathematical Logic
| origyear=1967
| publisher=A K Peters
| edition=2nd
| isbn=978-1-56881-135-2
| year=2001
- {{Citation
| last1=Troelstra
| first1=Anne Sjerp
| author1-link=A. S. Troelstra
| last2=Schwichtenberg
| first2=Helmut
| title=Basic Proof Theory
| publisher=Cambridge University Press
| location=Cambridge
| edition=2nd
| series=Cambridge Tracts in Theoretical Computer Science
| isbn=978-0-521-77911-1
| year=2000
}}.| first1=Anne Sjerp
| author1-link=A. S. Troelstra
| last2=Schwichtenberg
| first2=Helmut
| title=Basic Proof Theory
| publisher=Cambridge University Press
| location=Cambridge
| edition=2nd
| series=Cambridge Tracts in Theoretical Computer Science
| isbn=978-0-521-77911-1
| year=2000
Research papers, monographs, texts, and surveys
- BOOK,weblink Logical consequences. Theory and applications: An introduction, Luis M., Augusto, College Publications, London, 2017, 978-1-84890-236-7,
- Boehner, Philotheus, Medieval Logic, Manchester 1950.
- {{Citation
| last1=Cohen
| first1=P. J.
| author1link=Paul Cohen
| title=Set Theory and the Continuum Hypothesis
| publisher=W. A. Benjamin
| location=Menlo Park, CA
| year=1966
}}. | first1=P. J.
| author1link=Paul Cohen
| title=Set Theory and the Continuum Hypothesis
| publisher=W. A. Benjamin
| location=Menlo Park, CA
| year=1966
- BOOK, harv, Cohen, Paul Joseph, Paul Cohen (mathematician), Set theory and the continuum hypothesis, 2008, 1966, Dover Publications, Mineola, New York, 978-0-486-46921-8, .
- J.D. Sneed, The Logical Structure of Mathematical Physics. Reidel, Dordrecht, 1971 (revised edition 1979).
- {{Citation
| last1=Davis
| first1=Martin
| author1-link=Martin Davis (mathematician)
| title=Hilbert's tenth problem is unsolvable
| year=1973
| journal=The American Mathematical Monthly
| volume=80
| pages=233â€“269
| doi=10.2307/2318447
| issue=3
| jstor=2318447
}}, reprinted as an appendix in Martin Davis, Computability and Unsolvability, Dover reprint 1982. | first1=Martin
| author1-link=Martin Davis (mathematician)
| title=Hilbert's tenth problem is unsolvable
| year=1973
| journal=The American Mathematical Monthly
| volume=80
| pages=233â€“269
| doi=10.2307/2318447
| issue=3
| jstor=2318447
- {{Citation
| title=Bolzano, Cauchy, Epsilon, Delta
| first1=Walter
| last1=Felscher
|journal=The American Mathematical Monthly
| volume = 107
| year = 2000
| pages = 844–862
| doi=10.2307/2695743
| issue = 9
| jstor=2695743
}}. | first1=Walter
| last1=Felscher
|journal=The American Mathematical Monthly
| volume = 107
| year = 2000
| pages = 844–862
| doi=10.2307/2695743
| issue = 9
| jstor=2695743
- {{Citation
| last1=FerreirÃ³s
| first1=JosÃ©
| title=The Road to Modern Logic-An Interpretation
|journal=Bulletin of Symbolic Logic
|volume=7
|year=2001
|pages=441–484
| doi=10.2307/2687794
|issue=4
| jstor=2687794|url=https://idus.us.es/xmlui/bitstream/11441/38373/1/The%20road%20to%20modern%20logic.pdf
| hdl=11441/38373
}}.
| first1=JosÃ©
| title=The Road to Modern Logic-An Interpretation
|journal=Bulletin of Symbolic Logic
|volume=7
|year=2001
|pages=441–484
| doi=10.2307/2687794
|issue=4
| jstor=2687794|url=https://idus.us.es/xmlui/bitstream/11441/38373/1/The%20road%20to%20modern%20logic.pdf
| hdl=11441/38373
}}.
- {{Citation
| last1 = Hamkins
| first1 = Joel David
| last2 = LÃ¶we
| first2 = Benedikt
| title = The modal logic of forcing
| journal = Transactions of the American Mathematical Society
| doi = 10.1090/s0002-9947-07-04297-3
| arxiv = math/0509616
| volume=360
| issue = 4
| year=2007
| pages=1793â€“1818
}} | first1 = Joel David
| last2 = LÃ¶we
| first2 = Benedikt
| title = The modal logic of forcing
| journal = Transactions of the American Mathematical Society
| doi = 10.1090/s0002-9947-07-04297-3
| arxiv = math/0509616
| volume=360
| issue = 4
| year=2007
| pages=1793â€“1818
- {{Citation
| last1=Katz
| first1=Victor J.
| title = A History of Mathematics
| year = 1998
| publisher = Addisonâ€“Wesley
| isbn = 978-0-321-01618-8
}}. | first1=Victor J.
| title = A History of Mathematics
| year = 1998
| publisher = Addisonâ€“Wesley
| isbn = 978-0-321-01618-8
- {{Citation
| last1=Morley
| first1=Michael
| author1-link=Michael D. Morley
| title=Categoricity in Power
| doi=10.2307/1994188
| year=1965
| journal=Transactions of the American Mathematical Society
| volume=114
| issue=2
| pages=514â€“538
| jstor=1994188
}}. | first1=Michael
| author1-link=Michael D. Morley
| title=Categoricity in Power
| doi=10.2307/1994188
| year=1965
| journal=Transactions of the American Mathematical Society
| volume=114
| issue=2
| pages=514â€“538
| jstor=1994188
- {{Citation
| last1 = Soare
| first1 = Robert I.
| title = Computability and recursion
| journal = Bulletin of Symbolic Logic
| volume = 2
| pages = 284â€“321
| doi = 10.2307/420992
| year = 1996
| issue = 3
| jstor = 420992| citeseerx = 10.1.1.35.5803
}}.
| first1 = Robert I.
| title = Computability and recursion
| journal = Bulletin of Symbolic Logic
| volume = 2
| pages = 284â€“321
| doi = 10.2307/420992
| year = 1996
| issue = 3
| jstor = 420992| citeseerx = 10.1.1.35.5803
}}.
- {{Citation
| last1=Solovay
| first1= Robert M.
| author-link = Robert M. Solovay
| title = Provability Interpretations of Modal Logic
| journal = Israel Journal of Mathematics
| volume = 25
| year = 1976
| pages=287–304
| doi=10.1007/BF02757006
| issue=3â€“4
}}. | first1= Robert M.
| author-link = Robert M. Solovay
| title = Provability Interpretations of Modal Logic
| journal = Israel Journal of Mathematics
| volume = 25
| year = 1976
| pages=287–304
| doi=10.1007/BF02757006
| issue=3â€“4
- {{Citation
| last1=Woodin
| first1=W. Hugh
| author1-link=W. Hugh Woodin
| title=The Continuum Hypothesis, Part I
|journal=Notices of the American Mathematical Society
|volume=48
|year=2001
|issue=6
}}. PDF| first1=W. Hugh
| author1-link=W. Hugh Woodin
| title=The Continuum Hypothesis, Part I
|journal=Notices of the American Mathematical Society
|volume=48
|year=2001
|issue=6
Classical papers, texts, and collections
- {hide}Citation
| first1=Cesare
| last1=Burali-Forti
| year=1897|title = A question on transfinite numbers
{edih}, reprinted in van Heijenoort 1976, pp. 104–111. | last1=Burali-Forti
| year=1897|title = A question on transfinite numbers
- {hide}citation
| first1=Richard
| last1=Dedekind
| author1-link=Richard Dedekind
| year=1872
| title=Stetigkeit und irrationale Zahlen
{edih}. English translation of title: "Consistency and irrational numbers". | last1=Dedekind
| author1-link=Richard Dedekind
| year=1872
| title=Stetigkeit und irrationale Zahlen
- {hide}Citation
| first1=Richard
| last1=Dedekind
| author1-link=Richard Dedekind
| year=1888
| title=Was sind und was sollen die Zahlen?''
{edih} Two English translations: | last1=Dedekind
| author1-link=Richard Dedekind
| year=1888
| title=Was sind und was sollen die Zahlen?''
- 1963 (1901). Essays on the Theory of Numbers. Beman, W. W., ed. and trans. Dover.
- 1996. In From Kant to Hilbert: A Source Book in the Foundations of Mathematics, 2 vols, Ewald, William B., ed., Oxford University Press: 787â€“832.
- {{citation
| first1=Abraham A.
| last1=Fraenkel
| author1-link=Abraham Fraenkel
| year=1922
| contribution=Der Begriff 'definit' und die UnabhÃ¤ngigkeit des Auswahlsaxioms
| title=Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physikalisch-mathematische Klasse
| pages=253–257
}} (German), reprinted in English translation as "The notion of 'definite' and the independence of the axiom of choice", van Heijenoort 1976, pp. 284–289. | last1=Fraenkel
| author1-link=Abraham Fraenkel
| year=1922
| contribution=Der Begriff 'definit' und die UnabhÃ¤ngigkeit des Auswahlsaxioms
| title=Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physikalisch-mathematische Klasse
| pages=253–257
- Frege, Gottlob (1879), Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle a. S.: Louis Nebert. Translation: Concept Script, a formal language of pure thought modelled upon that of arithmetic, by S. Bauer-Mengelberg in Jean Van Heijenoort, ed., 1967. From Frege to GÃ¶del: A Source Book in Mathematical Logic, 1879â€“1931. Harvard University Press.
- Frege, Gottlob (1884), Die Grundlagen der Arithmetik: eine logisch-mathematische Untersuchung Ã¼ber den Begriff der Zahl. Breslau: W. Koebner. Translation: J. L. Austin, 1974. The Foundations of Arithmetic: A logico-mathematical enquiry into the concept of number, 2nd ed. Blackwell.
- {{citation
| author1-link=Gerhard Gentzen
| first1=Gerhard
| last1=Gentzen
| year=1936
| title=Die Widerspruchsfreiheit der reinen Zahlentheorie
| journal=Mathematische Annalen
| volume=112
| pages=132–213
| doi=10.1007/BF01565428
}}, reprinted in English translation in Gentzen's Collected works, M. E. Szabo, ed., North-Holland, Amsterdam, 1969. | first1=Gerhard
| last1=Gentzen
| year=1936
| title=Die Widerspruchsfreiheit der reinen Zahlentheorie
| journal=Mathematische Annalen
| volume=112
| pages=132–213
| doi=10.1007/BF01565428
- {hide}Citation
| last1=GÃ¶del
| first1=Kurt
| author1-link=Kurt GÃ¶del
| year = 1929
| title = Ãœber die VollstÃ¤ndigkeit des LogikkalkÃ¼ls
| series = doctoral dissertation
| publisher = University Of Vienna
{edih}. English translation of title: "Completeness of the logical calculus". | first1=Kurt
| author1-link=Kurt GÃ¶del
| year = 1929
| title = Ãœber die VollstÃ¤ndigkeit des LogikkalkÃ¼ls
| series = doctoral dissertation
| publisher = University Of Vienna
- {{Citation
| last1=GÃ¶del
| first1=Kurt
| author1-link=Kurt GÃ¶del
| year = 1930
| title = Die VollstÃ¤ndigkeit der Axiome des logischen Funktionen-kalkÃ¼ls
| journal = Monatshefte fÃ¼r Mathematik und Physik
| volume = 37
| pages = 349–360
| doi=10.1007/BF01696781
}}. English translation of title: "The completeness of the axioms of the calculus of logical functions". | first1=Kurt
| author1-link=Kurt GÃ¶del
| year = 1930
| title = Die VollstÃ¤ndigkeit der Axiome des logischen Funktionen-kalkÃ¼ls
| journal = Monatshefte fÃ¼r Mathematik und Physik
| volume = 37
| pages = 349–360
| doi=10.1007/BF01696781
- {{Citation
| last1=GÃ¶del
| first1=Kurt
| author1-link=Kurt GÃ¶del
| title=Ãœber formal unentscheidbare SÃ¤tze der Principia Mathematica und verwandter Systeme I
| year=1931
| journal=Monatshefte fÃ¼r Mathematik und Physik
| volume=38
| issue=1
| pages=173â€“198
| doi=10.1007/BF01700692
}}, see On Formally Undecidable Propositions of Principia Mathematica and Related Systems for details on English translations. | first1=Kurt
| author1-link=Kurt GÃ¶del
| title=Ãœber formal unentscheidbare SÃ¤tze der Principia Mathematica und verwandter Systeme I
| year=1931
| journal=Monatshefte fÃ¼r Mathematik und Physik
| volume=38
| issue=1
| pages=173â€“198
| doi=10.1007/BF01700692
- {{Citation
| last1=GÃ¶del
| first1=Kurt
| author1-link=Kurt GÃ¶del
| title=Ãœber eine bisher noch nicht benÃ¼tzte Erweiterung des finiten Standpunktes
| year=1958
| journal=Dialectica. International Journal of Philosophy
| volume=12
| pages=280â€“287
| doi=10.1111/j.1746-8361.1958.tb01464.x
| issue=3â€“4
}}, reprinted in English translation in GÃ¶del's Collected Works, vol II, Solomon Feferman et al., eds. Oxford University Press, 1990.{{Specify|date=September 2009}} | first1=Kurt
| author1-link=Kurt GÃ¶del
| title=Ãœber eine bisher noch nicht benÃ¼tzte Erweiterung des finiten Standpunktes
| year=1958
| journal=Dialectica. International Journal of Philosophy
| volume=12
| pages=280â€“287
| doi=10.1111/j.1746-8361.1958.tb01464.x
| issue=3â€“4
- {{citation
| editor-first=Jean
| editor-last=van Heijenoort
| editor-link=Jean van Heijenoort
| title = From Frege to GÃ¶del: A Source Book in Mathematical Logic, 1879â€“1931
| edition = 3rd
| publisher = Harvard University Press
| location = Cambridge, Mass
| orig-year = 1967
| year = 1976
| id = (pbk.)
| isbn=978-0-674-32449-7
}} | editor-last=van Heijenoort
| editor-link=Jean van Heijenoort
| title = From Frege to GÃ¶del: A Source Book in Mathematical Logic, 1879â€“1931
| edition = 3rd
| publisher = Harvard University Press
| location = Cambridge, Mass
| orig-year = 1967
| year = 1976
| id = (pbk.)
| isbn=978-0-674-32449-7
- {hide}citation
| last1=Hilbert
| first1=David
| author1-link=David Hilbert
| year = 1899
| title = Grundlagen der Geometrie
| publisher = Teubner
| location = Leipzig
{edih}, English 1902 edition (The Foundations of Geometry) republished 1980, Open Court, Chicago. | first1=David
| author1-link=David Hilbert
| year = 1899
| title = Grundlagen der Geometrie
| publisher = Teubner
| location = Leipzig
- {{Citation
|first1=Hilbert
|last1=David
|author1-link=David Hilbert
|year=1929
|title=Probleme der Grundlegung der Mathematik
|journal=Mathematische Annalen|volume=102|pages=1–9
|url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002273500&L=1
|doi=10.1007/BF01782335
}}. Lecture given at the International Congress of Mathematicians, 3 September 1928. Published in English translation as "The Grounding of Elementary Number Theory", in Mancosu 1998, pp. 266–273. |last1=David
|author1-link=David Hilbert
|year=1929
|title=Probleme der Grundlegung der Mathematik
|journal=Mathematische Annalen|volume=102|pages=1–9
|url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002273500&L=1
|doi=10.1007/BF01782335
- BOOK, harv, Hilbert, David, David Hilbert, Bernays, Paul, Paul Bernays, Grundlagen der Mathematik. I, Springer-Verlag, Berlin, New York, Die Grundlehren der mathematischen Wissenschaften, 978-3-540-04134-4, 1934, 40, 0237246, 60.0017.02,
- {{Citation
| last1=Kleene
| first1=Stephen Cole
| author1-link=Stephen Kleene
| title=Recursive Predicates and Quantifiers
| year=1943
| journal=American Mathematical Society Transactions
| volume=54
| issue=1
| pages=41â€“73
| doi=10.2307/1990131
| jstor=1990131
}}. | first1=Stephen Cole
| author1-link=Stephen Kleene
| title=Recursive Predicates and Quantifiers
| year=1943
| journal=American Mathematical Society Transactions
| volume=54
| issue=1
| pages=41â€“73
| doi=10.2307/1990131
| jstor=1990131
- {hide}Citation
| first1 = Nikolai
| last1 = Lobachevsky
| authorlink = Nikolai Lobachevsky
| title = Geometrishe Untersuchungen zur Theorie der Parellellinien
| year = 1840
{edih} (German). Reprinted in English translation as "Geometric Investigations on the Theory of Parallel Lines" in Non-Euclidean Geometry, Robert Bonola (ed.), Dover, 1955. {{isbn|0-486-60027-0}} | last1 = Lobachevsky
| authorlink = Nikolai Lobachevsky
| title = Geometrishe Untersuchungen zur Theorie der Parellellinien
| year = 1840
- {{Citation
| last1=LÃ¶wenheim
| first1=Leopold
| author1-link=Leopold LÃ¶wenheim
| title=Ãœber MÃ¶glichkeiten im RelativkalkÃ¼l
| year=1915
| journal=Mathematische Annalen
| issn=0025-5831
| volume=76
| pages=447â€“470
| url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002266121&L=1
| doi=10.1007/BF01458217
| issue=4}} (German). Translated as "On possibilities in the calculus of relatives" in Jean van Heijenoort, 1967. A Source Book in Mathematical Logic, 1879â€“1931. Harvard Univ. Press: 228â€“251.
| first1=Leopold
| author1-link=Leopold LÃ¶wenheim
| title=Ãœber MÃ¶glichkeiten im RelativkalkÃ¼l
| year=1915
| journal=Mathematische Annalen
| issn=0025-5831
| volume=76
| pages=447â€“470
| url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002266121&L=1
| doi=10.1007/BF01458217
| issue=4}} (German). Translated as "On possibilities in the calculus of relatives" in Jean van Heijenoort, 1967. A Source Book in Mathematical Logic, 1879â€“1931. Harvard Univ. Press: 228â€“251.
- {{Citation
|editor-last=Mancosu
|editor-first=Paolo
|editor-link=Paolo Mancosu
|year=1998
|title=From Brouwer to Hilbert. The Debate on the Foundations of Mathematics in the 1920s
|publisher=Oxford University Press|location=Oxford
}}. |editor-first=Paolo
|editor-link=Paolo Mancosu
|year=1998
|title=From Brouwer to Hilbert. The Debate on the Foundations of Mathematics in the 1920s
|publisher=Oxford University Press|location=Oxford
- {hide}citation
|last1=Pasch
|first1=Moritz
|author1-link=Moritz Pasch
|title=Vorlesungen Ã¼ber neuere Geometrie
|year=1882
{edih}. |first1=Moritz
|author1-link=Moritz Pasch
|title=Vorlesungen Ã¼ber neuere Geometrie
|year=1882
- {hide}citation
|first1=Giuseppe
|last1=Peano
|author1-link=Giuseppe Peano
|year=1889
|title=Arithmetices principia, nova methodo exposita|title-link=Arithmetices principia, nova methodo exposita
{edih} (Latin), excerpt reprinted in English translation as "The principles of arithmetic, presented by a new method", van Heijenoort 1976, pp. 83 97.
|last1=Peano
|author1-link=Giuseppe Peano
|year=1889
|title=Arithmetices principia, nova methodo exposita|title-link=Arithmetices principia, nova methodo exposita
{edih} (Latin), excerpt reprinted in English translation as "The principles of arithmetic, presented by a new method", van Heijenoort 1976, pp. 83 97.
- {hide}Citation
|first1=Jules
|last1=Richard
|year=1905
|title=Les principes des mathÃ©matiques et le problÃ¨me des ensembles
|journal=Revue GÃ©nÃ©rale des Sciences Pures et AppliquÃ©es
|volume=16
|page=541
{edih} (French), reprinted in English translation as "The principles of mathematics and the problems of sets", van Heijenoort 1976, pp. 142–144. |last1=Richard
|year=1905
|title=Les principes des mathÃ©matiques et le problÃ¨me des ensembles
|journal=Revue GÃ©nÃ©rale des Sciences Pures et AppliquÃ©es
|volume=16
|page=541
- {{Citation
| last1=Skolem
| first1=Thoralf
| author1-link=Thoralf Skolem
| title=Logisch-kombinatorische Untersuchungen Ã¼ber die ErfÃ¼llbarkeit oder Beweisbarkeit mathematischer SÃ¤tze nebst einem Theoreme Ã¼ber dichte Mengen
| year=1920
| journal=Videnskapsselskapet Skrifter, I. Matematisk-naturvidenskabelig Klasse
| volume=6
| pages=1â€“36}}.
| first1=Thoralf
| author1-link=Thoralf Skolem
| title=Logisch-kombinatorische Untersuchungen Ã¼ber die ErfÃ¼llbarkeit oder Beweisbarkeit mathematischer SÃ¤tze nebst einem Theoreme Ã¼ber dichte Mengen
| year=1920
| journal=Videnskapsselskapet Skrifter, I. Matematisk-naturvidenskabelig Klasse
| volume=6
| pages=1â€“36}}.
- {hide}Citation
| last1=Tarski
| first1=Alfred
| author1-link=Alfred Tarski
| title=A decision method for elementary algebra and geometry
| publisher=RAND Corporation
| location=Santa Monica, California
| year=1948{edih}
| first1=Alfred
| author1-link=Alfred Tarski
| title=A decision method for elementary algebra and geometry
| publisher=RAND Corporation
| location=Santa Monica, California
| year=1948{edih}
- {{Citation
| last1=Turing
| first1=Alan M.
| author1-link=A. M. Turing
| title=Systems of Logic Based on Ordinals
| year=1939
| journal=Proceedings of the London Mathematical Society
| volume=45
| issue=2
| pages=161â€“228
| doi=10.1112/plms/s2-45.1.161| hdl=21.11116/0000-0001-91CE-3
}}
| first1=Alan M.
| author1-link=A. M. Turing
| title=Systems of Logic Based on Ordinals
| year=1939
| journal=Proceedings of the London Mathematical Society
| volume=45
| issue=2
| pages=161â€“228
| doi=10.1112/plms/s2-45.1.161| hdl=21.11116/0000-0001-91CE-3
}}
- {{Citation
|first1=Ernst
|last1=Zermelo
|author1-link=Ernst Zermelo
|year=1904
|title=Beweis, daÃŸ jede Menge wohlgeordnet werden kann
|journal=Mathematische Annalen|volume=59|pages=514–516
|url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002260018&L=1
|doi=10.1007/BF01445300
|issue=4
}} (German), reprinted in English translation as "Proof that every set can be well-ordered", van Heijenoort 1976, pp. 139–141. |last1=Zermelo
|author1-link=Ernst Zermelo
|year=1904
|title=Beweis, daÃŸ jede Menge wohlgeordnet werden kann
|journal=Mathematische Annalen|volume=59|pages=514–516
|url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002260018&L=1
|doi=10.1007/BF01445300
|issue=4
- {{Citation
|first1=Ernst
|last1=Zermelo
|author1-link=Ernst Zermelo
|year=1908a
|title=Neuer Beweis fÃ¼r die MÃ¶glichkeit einer Wohlordnung
|journal=Mathematische Annalen
|volume=65
|pages=107â€“128
|url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002261952&L=1
|doi=10.1007/BF01450054
|issn=0025-5831
}} (German), reprinted in English translation as "A new proof of the possibility of a well-ordering", van Heijenoort 1976, pp. 183–198. |last1=Zermelo
|author1-link=Ernst Zermelo
|year=1908a
|title=Neuer Beweis fÃ¼r die MÃ¶glichkeit einer Wohlordnung
|journal=Mathematische Annalen
|volume=65
|pages=107â€“128
|url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002261952&L=1
|doi=10.1007/BF01450054
|issn=0025-5831
- {{Citation
| last1=Zermelo
| first1=Ernst
| author1-link=Ernst Zermelo
| year=1908b
| title=Untersuchungen Ã¼ber die Grundlagen der Mengenlehre
| journal=Mathematische Annalen
| volume=65
| pages=261â€“281
| url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0065&DMDID=DMDLOG_0018&L=1
| doi=10.1007/BF01449999
| issue=2
}}.| first1=Ernst
| author1-link=Ernst Zermelo
| year=1908b
| title=Untersuchungen Ã¼ber die Grundlagen der Mengenlehre
| journal=Mathematische Annalen
| volume=65
| pages=261â€“281
| url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0065&DMDID=DMDLOG_0018&L=1
| doi=10.1007/BF01449999
| issue=2
External links
- {{Springer |title=Mathematical logic |id=p/m062660}}
- Polyvalued logic and Quantity Relation Logic
- forall x: an introduction to formal logic, a free textbook by {{nowrap|P. D. Magnus}}.
- A Problem Course in Mathematical Logic, a free textbook by Stefan Bilaniuk.
- Detlovs, Vilnis, and Podnieks, Karlis (University of Latvia), Introduction to Mathematical Logic. (hyper-textbook).
- In the Stanford Encyclopedia of Philosophy:
- : Classical Logic by Stewart Shapiro.
- : First-order Model Theory by Wilfrid Hodges.
- In the London Philosophy Study Guide:
- : Mathematical Logic
- : Set Theory & Further Logic
- : Philosophy of Mathematics
- content above as imported from Wikipedia
- "Mathematical logic" does not exist on GetWiki (yet)
- time: 10:32pm EDT - Mon, Sep 16 2019
- "Mathematical logic" does not exist on GetWiki (yet)
- time: 10:32pm EDT - Mon, Sep 16 2019
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 09 JUL 2019
Eastern Philosophy
History of Philosophy
History of Philosophy
GETWIKI 09 MAY 2016
GetMeta:About
GetWiki
GetWiki
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
Biographies
GETWIKI 20 AUG 2014
GetMeta:News
GetWiki
GetWiki
GETWIKI 19 AUG 2014
© 2019 M.R.M. PARROTT | ALL RIGHTS RESERVED