# Mathematical logic

For Quine's theory sometimes called "Mathematical Logic", see New Foundations. Mathematical logic_sentence_0

Mathematical logic is a subfield of mathematics exploring the applications of formal logic to mathematics. Mathematical logic_sentence_1

It bears close connections to metamathematics, the foundations of mathematics, and theoretical computer science. Mathematical logic_sentence_2

The unifying themes in mathematical logic include the study of the expressive power of formal systems and the deductive power of formal proof systems. Mathematical logic_sentence_3

Mathematical logic is often divided into the fields of set theory, model theory, recursion theory, and proof theory. Mathematical logic_sentence_4

These areas share basic results on logic, particularly first-order logic, and definability. Mathematical logic_sentence_5

In computer science (particularly in the ACM Classification) mathematical logic encompasses additional topics not detailed in this article; see Logic in computer science for those. Mathematical logic_sentence_6

Since its inception, mathematical logic has both contributed to, and has been motivated by, the study of foundations of mathematics. Mathematical logic_sentence_7

This study began in the late 19th century with the development of axiomatic frameworks for geometry, arithmetic, and analysis. Mathematical logic_sentence_8

In the early 20th century it was shaped by David Hilbert's program to prove the consistency of foundational theories. Mathematical logic_sentence_9

Results of Kurt Gödel, Gerhard Gentzen, and others provided partial resolution to the program, and clarified the issues involved in proving consistency. Mathematical logic_sentence_10

Work in set theory showed that almost all ordinary mathematics can be formalized in terms of sets, although there are some theorems that cannot be proven in common axiom systems for set theory. Mathematical logic_sentence_11

Contemporary work in the foundations of mathematics often focuses on establishing which parts of mathematics can be formalized in particular formal systems (as in reverse mathematics) rather than trying to find theories in which all of mathematics can be developed. Mathematical logic_sentence_12

## Subfields and scope Mathematical logic_section_0

The Handbook of Mathematical Logic in 1977 makes a rough division of contemporary mathematical logic into four areas: Mathematical logic_sentence_13

Mathematical logic_ordered_list_0

1. set theoryMathematical logic_item_0_0
2. model theoryMathematical logic_item_0_1
3. recursion theory, andMathematical logic_item_0_2
4. proof theory and constructive mathematics (considered as parts of a single area).Mathematical logic_item_0_3

Each area has a distinct focus, although many techniques and results are shared among multiple areas. Mathematical logic_sentence_14

The borderlines amongst these fields, and the lines separating mathematical logic and other fields of mathematics, are not always sharp. Mathematical logic_sentence_15

Gödel's incompleteness theorem marks not only a milestone in recursion theory and proof theory, but has also led to Löb's theorem in modal logic. Mathematical logic_sentence_16

The method of forcing is employed in set theory, model theory, and recursion theory, as well as in the study of intuitionistic mathematics. Mathematical logic_sentence_17

The mathematical field of category theory uses many formal axiomatic methods, and includes the study of categorical logic, but category theory is not ordinarily considered a subfield of mathematical logic. Mathematical logic_sentence_18

Because of its applicability in diverse fields of mathematics, mathematicians including Saunders Mac Lane have proposed category theory as a foundational system for mathematics, independent of set theory. Mathematical logic_sentence_19

These foundations use toposes, which resemble generalized models of set theory that may employ classical or nonclassical logic. Mathematical logic_sentence_20

## History Mathematical logic_section_1

Mathematical logic emerged in the mid-19th century as a subfield of mathematics, reflecting the confluence of two traditions: formal philosophical logic and mathematics (, p. 443). Mathematical logic_sentence_21

"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." Mathematical logic_sentence_22

Before this emergence, logic was studied with rhetoric, with calculationes, through the syllogism, and with philosophy. Mathematical logic_sentence_23

The first half of the 20th century saw an explosion of fundamental results, accompanied by vigorous debate over the foundations of mathematics. Mathematical logic_sentence_24

### Early history Mathematical logic_section_2

Further information: History of logic Mathematical logic_sentence_25

Theories of logic were developed in many cultures in history, including China, India, Greece and the Islamic world. Mathematical logic_sentence_26

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. Mathematical logic_sentence_27

The Stoics, especially Chrysippus, began the development of predicate logic. Mathematical logic_sentence_28

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. Mathematical logic_sentence_29

### 19th century Mathematical logic_section_3

In the middle of the nineteenth century, George Boole and then Augustus De Morgan presented systematic mathematical treatments of logic. Mathematical logic_sentence_30

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 (, p. 686). Mathematical logic_sentence_31

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. Mathematical logic_sentence_32

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. Mathematical logic_sentence_33

Frege's work remained obscure, however, until Bertrand Russell began to promote it near the turn of the century. Mathematical logic_sentence_34

The two-dimensional notation Frege developed was never widely adopted and is unused in contemporary texts. Mathematical logic_sentence_35

From 1890 to 1905, Ernst Schröder published Vorlesungen über die Algebra der Logik in three volumes. Mathematical logic_sentence_36

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. Mathematical logic_sentence_37

#### Foundational theories Mathematical logic_section_4

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. Mathematical logic_sentence_38

In logic, the term arithmetic refers to the theory of the natural numbers. Mathematical logic_sentence_39

Giuseppe Peano () 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. Mathematical logic_sentence_40

Peano was unaware of Frege's work at the time. Mathematical logic_sentence_41

Around the same time Richard Dedekind showed that the natural numbers are uniquely characterized by their induction properties. Mathematical logic_sentence_42

Dedekind () proposed a different characterization, which lacked the formal logical character of Peano's axioms. Mathematical logic_sentence_43

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. Mathematical logic_sentence_44

In the mid-19th century, flaws in Euclid's axioms for geometry became known (, p. 774). Mathematical logic_sentence_45

In addition to the independence of the parallel postulate, established by Nikolai Lobachevsky in 1826 (), mathematicians discovered that certain theorems taken for granted by Euclid were not in fact provable from his axioms. Mathematical logic_sentence_46

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. Mathematical logic_sentence_47

Hilbert () developed a complete set of axioms for geometry, building on previous work by Pasch (). Mathematical logic_sentence_48

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. Mathematical logic_sentence_49

This would prove to be a major area of research in the first half of the 20th century. Mathematical logic_sentence_50

The 19th century saw great advances in the theory of real analysis, including theories of convergence of functions and Fourier series. Mathematical logic_sentence_51

Mathematicians such as Karl Weierstrass began to construct functions that stretched intuition, such as nowhere-differentiable continuous functions. Mathematical logic_sentence_52

Previous conceptions of a function as a rule for computation, or a smooth graph, were no longer adequate. Mathematical logic_sentence_53

Weierstrass began to advocate the arithmetization of analysis, which sought to axiomatize analysis using properties of the natural numbers. Mathematical logic_sentence_54

The modern (ε, δ)-definition of limit and continuous functions was already developed by Bolzano in 1817 (), but remained relatively unknown. Mathematical logic_sentence_55

Cauchy in 1821 defined continuity in terms of infinitesimals (see Cours d'Analyse, page 34). Mathematical logic_sentence_56

In 1858, Dedekind proposed a definition of the real numbers in terms of Dedekind cuts of rational numbers , a definition still employed in contemporary texts. Mathematical logic_sentence_57

Georg Cantor developed the fundamental concepts of infinite set theory. Mathematical logic_sentence_58

His early results developed the theory of cardinality and proved that the reals and the natural numbers have different cardinalities (Cantor 1874). Mathematical logic_sentence_59

Over the next twenty years, Cantor developed a theory of transfinite numbers in a series of publications. Mathematical logic_sentence_60

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. Mathematical logic_sentence_61

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 (). Mathematical logic_sentence_62

### 20th century Mathematical logic_section_5

In the early decades of the 20th century, the main areas of study were set theory and formal logic. Mathematical logic_sentence_63

The discovery of paradoxes in informal set theory caused some to wonder whether mathematics itself is inconsistent, and to look for proofs of consistency. Mathematical logic_sentence_64

In 1900, Hilbert posed a famous list of 23 problems for the next century. Mathematical logic_sentence_65

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. Mathematical logic_sentence_66

Subsequent work to resolve these problems shaped the direction of mathematical logic, as did the effort to resolve Hilbert's Entscheidungsproblem, posed in 1928. Mathematical logic_sentence_67

This problem asked for a procedure that would decide, given a formalized mathematical statement, whether the statement is true or false. Mathematical logic_sentence_68

#### Set theory and paradoxes Mathematical logic_section_6

Ernst Zermelo () gave a proof that every set could be well-ordered, a result Georg Cantor had been unable to obtain. Mathematical logic_sentence_69

To achieve the proof, Zermelo introduced the axiom of choice, which drew heated debate and research among mathematicians and the pioneers of set theory. Mathematical logic_sentence_70

The immediate criticism of the method led Zermelo to publish a second exposition of his result, directly addressing criticisms of his proof (). Mathematical logic_sentence_71

This paper led to the general acceptance of the axiom of choice in the mathematics community. Mathematical logic_sentence_72

Skepticism about the axiom of choice was reinforced by recently discovered paradoxes in naive set theory. Mathematical logic_sentence_73

Cesare Burali-Forti () was the first to state a paradox: the Burali-Forti paradox shows that the collection of all ordinal numbers cannot form a set. Mathematical logic_sentence_74

Very soon thereafter, Bertrand Russell discovered Russell's paradox in 1901, and Jules Richard () discovered Richard's paradox. Mathematical logic_sentence_75

Zermelo () provided the first set of axioms for set theory. Mathematical logic_sentence_76

These axioms, together with the additional axiom of replacement proposed by Abraham Fraenkel, are now called Zermelo–Fraenkel set theory (ZF). Mathematical logic_sentence_77

Zermelo's axioms incorporated the principle of limitation of size to avoid Russell's paradox. Mathematical logic_sentence_78

In 1910, the first volume of Principia Mathematica by Russell and Alfred North Whitehead was published. Mathematical logic_sentence_79

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. Mathematical logic_sentence_80

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 (, p. 445). Mathematical logic_sentence_81

Fraenkel () proved that the axiom of choice cannot be proved from the axioms of Zermelo's set theory with urelements. Mathematical logic_sentence_82

Later work by Paul Cohen () showed that the addition of urelements is not needed, and the axiom of choice is unprovable in ZF. Mathematical logic_sentence_83

Cohen's proof developed the method of forcing, which is now an important tool for establishing independence results in set theory. Mathematical logic_sentence_84

#### Symbolic logic Mathematical logic_section_7

Leopold Löwenheim () and Thoralf Skolem () obtained the Löwenheim–Skolem theorem, which says that first-order logic cannot control the cardinalities of infinite structures. Mathematical logic_sentence_85

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. Mathematical logic_sentence_86

This counterintuitive fact became known as Skolem's paradox. Mathematical logic_sentence_87

In his doctoral thesis, Kurt Gödel () proved the completeness theorem, which establishes a correspondence between syntax and semantics in first-order logic. Mathematical logic_sentence_88

Gödel used the completeness theorem to prove the compactness theorem, demonstrating the finitary nature of first-order logical consequence. Mathematical logic_sentence_89

These results helped establish first-order logic as the dominant logic used by mathematicians. Mathematical logic_sentence_90

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. Mathematical logic_sentence_91

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. Mathematical logic_sentence_92

It showed the impossibility of providing a consistency proof of arithmetic within any formal theory of arithmetic. Mathematical logic_sentence_93

Hilbert, however, did not acknowledge the importance of the incompleteness theorem for some time. Mathematical logic_sentence_94

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. Mathematical logic_sentence_95

This leaves open the possibility of consistency proofs that cannot be formalized within the system they consider. Mathematical logic_sentence_96

Gentzen () proved the consistency of arithmetic using a finitistic system together with a principle of transfinite induction. Mathematical logic_sentence_97

Gentzen's result introduced the ideas of cut elimination and proof-theoretic ordinals, which became key tools in proof theory. Mathematical logic_sentence_98

Gödel () gave a different consistency proof, which reduces the consistency of classical arithmetic to that of intuitionistic arithmetic in higher types. Mathematical logic_sentence_99

#### Beginnings of the other branches Mathematical logic_section_8

Alfred Tarski developed the basics of model theory. Mathematical logic_sentence_100

Beginning in 1935, a group of prominent mathematicians collaborated under the pseudonym Nicolas Bourbaki to publish Éléments de mathématique, a series of encyclopedic mathematics texts. Mathematical logic_sentence_101

These texts, written in an austere and axiomatic style, emphasized rigorous presentation and set-theoretic foundations. Mathematical logic_sentence_102

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. Mathematical logic_sentence_103

The study of computability came to be known as recursion theory or computability theory, because early formalizations by Gödel and Kleene relied on recursive definitions of functions. Mathematical logic_sentence_104

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. Mathematical logic_sentence_105

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. Mathematical logic_sentence_106

Numerous results in recursion theory were obtained in the 1940s by Stephen Cole Kleene and Emil Leon Post. Mathematical logic_sentence_107

Kleene () introduced the concepts of relative computability, foreshadowed by Turing (), and the arithmetical hierarchy. Mathematical logic_sentence_108

Kleene later generalized recursion theory to higher-order functionals. Mathematical logic_sentence_109

Kleene and Georg Kreisel studied formal versions of intuitionistic mathematics, particularly in the context of proof theory. Mathematical logic_sentence_110

## Formal logical systems Mathematical logic_section_9

At its core, mathematical logic deals with mathematical concepts expressed using formal logical systems. Mathematical logic_sentence_111

These systems, though they differ in many details, share the common property of considering only expressions in a fixed formal language. Mathematical logic_sentence_112

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. Mathematical logic_sentence_113

Stronger classical logics such as second-order logic or infinitary logic are also studied, along with Non-classical logics such as intuitionistic logic. Mathematical logic_sentence_114

### First-order logic Mathematical logic_section_10

Main article: First-order logic Mathematical logic_sentence_115

First-order logic is a particular formal system of logic. Mathematical logic_sentence_116

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. Mathematical logic_sentence_117

Early results from formal logic established limitations of first-order logic. Mathematical logic_sentence_118

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. Mathematical logic_sentence_119

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. Mathematical logic_sentence_120

As the goal of early foundational studies was to produce axiomatic theories for all parts of mathematics, this limitation was particularly stark. Mathematical logic_sentence_121

Gödel's completeness theorem () established the equivalence between semantic and syntactic definitions of logical consequence in first-order logic. Mathematical logic_sentence_122

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. Mathematical logic_sentence_123

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. Mathematical logic_sentence_124

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. Mathematical logic_sentence_125

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. Mathematical logic_sentence_126

Gödel's incompleteness theorems () establish additional limits on first-order axiomatizations. Mathematical logic_sentence_127

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). Mathematical logic_sentence_128

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. Mathematical logic_sentence_129

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." Mathematical logic_sentence_130

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. Mathematical logic_sentence_131

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 reached. Mathematical logic_sentence_132

### Other classical logics Mathematical logic_section_11

Many logics besides first-order logic are studied. Mathematical logic_sentence_133

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. Mathematical logic_sentence_134

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. Mathematical logic_sentence_135

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. Mathematical logic_sentence_136

The logics studied before the development of first-order logic, for example Frege's logic, had similar set-theoretic aspects. Mathematical logic_sentence_137

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. Mathematical logic_sentence_138

Another type of logics are fixed-point logics that allow inductive definitions, like one writes for primitive recursive functions. Mathematical logic_sentence_139

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. Mathematical logic_sentence_140

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. Mathematical logic_sentence_141

### Nonclassical and modal logic Mathematical logic_section_12

Main article: Non-classical logic Mathematical logic_sentence_142

Modal logics include additional modal operators, such as an operator which states that a particular formula is not only true, but necessarily true. Mathematical logic_sentence_143

Although modal logic is not often used to axiomatize mathematics, it has been used to study the properties of first-order provability () and set-theoretic forcing (). Mathematical logic_sentence_144

Intuitionistic logic was developed by Heyting to study Brouwer's program of intuitionism, in which Brouwer himself avoided formalization. Mathematical logic_sentence_145

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. Mathematical logic_sentence_146

Kleene's work with the proof theory of intuitionistic logic showed that constructive information can be recovered from intuitionistic proofs. Mathematical logic_sentence_147

For example, any provably total function in intuitionistic arithmetic is computable; this is not true in classical theories of arithmetic such as Peano arithmetic. Mathematical logic_sentence_148

### Algebraic logic Mathematical logic_section_13

Algebraic logic uses the methods of abstract algebra to study the semantics of formal logics. Mathematical logic_sentence_149

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. Mathematical logic_sentence_150

Stronger logics, such as first-order logic and higher-order logic, are studied using more complicated algebraic structures such as cylindric algebras. Mathematical logic_sentence_151

## Set theory Mathematical logic_section_14

Main article: Set theory Mathematical logic_sentence_152

Set theory is the study of sets, which are abstract collections of objects. Mathematical logic_sentence_153

Many of the basic notions, such as ordinal and cardinal numbers, were developed informally by Cantor before formal axiomatizations of set theory were developed. Mathematical logic_sentence_154

The first such axiomatization, due to Zermelo (), was extended slightly to become Zermelo–Fraenkel set theory (ZF), which is now the most widely used foundational theory for mathematics. Mathematical logic_sentence_155

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). Mathematical logic_sentence_156

Of these, ZF, NBG, and MK are similar in describing a cumulative hierarchy of sets. Mathematical logic_sentence_157

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. Mathematical logic_sentence_158

The system of Kripke–Platek set theory is closely related to generalized recursion theory. Mathematical logic_sentence_159

Two famous statements in set theory are the axiom of choice and the continuum hypothesis. Mathematical logic_sentence_160

The axiom of choice, first stated by Zermelo (), was proved independent of ZF by Fraenkel (), but has come to be widely accepted by mathematicians. Mathematical logic_sentence_161

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. Mathematical logic_sentence_162

The set C is said to "choose" one element from each set in the collection. Mathematical logic_sentence_163

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. Mathematical logic_sentence_164

Stefan Banach and Alfred Tarski () 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. Mathematical logic_sentence_165

This theorem, known as the Banach–Tarski paradox, is one of many counterintuitive results of the axiom of choice. Mathematical logic_sentence_166

The continuum hypothesis, first proposed as a conjecture by Cantor, was listed by David Hilbert as one of his 23 problems in 1900. Mathematical logic_sentence_167

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. Mathematical logic_sentence_168

In 1963, Paul Cohen showed that the continuum hypothesis cannot be proven from the axioms of Zermelo–Fraenkel set theory (). Mathematical logic_sentence_169

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. Mathematical logic_sentence_170

Recent work along these lines has been conducted by W. Mathematical logic_sentence_171 Hugh Woodin, although its importance is not yet clear (). Mathematical logic_sentence_172

Contemporary research in set theory includes the study of large cardinals and determinacy. Mathematical logic_sentence_173

Large cardinals are cardinal numbers with particular properties so strong that the existence of such cardinals cannot be proved in ZFC. Mathematical logic_sentence_174

The existence of the smallest large cardinal typically studied, an inaccessible cardinal, already implies the consistency of ZFC. Mathematical logic_sentence_175

Despite the fact that large cardinals have extremely high cardinality, their existence has many ramifications for the structure of the real line. Mathematical logic_sentence_176

Determinacy refers to the possible existence of winning strategies for certain two-player games (the games are said to be determined). Mathematical logic_sentence_177

The existence of these strategies implies structural properties of the real line and other Polish spaces. Mathematical logic_sentence_178

## Model theory Mathematical logic_section_15

Main article: Model theory Mathematical logic_sentence_179

Model theory studies the models of various formal theories. Mathematical logic_sentence_180

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. Mathematical logic_sentence_181

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. Mathematical logic_sentence_182

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. Mathematical logic_sentence_183

The method of quantifier elimination can be used to show that definable sets in particular theories cannot be too complicated. Mathematical logic_sentence_184

Tarski () established quantifier elimination for real-closed fields, a result which also shows the theory of the field of real numbers is decidable. Mathematical logic_sentence_185

(He also noted that his methods were equally applicable to algebraically closed fields of arbitrary characteristic.) Mathematical logic_sentence_186

A modern subfield developing from this is concerned with o-minimal structures. Mathematical logic_sentence_187

Morley's categoricity theorem, proved by Michael D. Morley (), 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. Mathematical logic_sentence_188

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. Mathematical logic_sentence_189

Vaught's conjecture, named after Robert Lawson Vaught, says that this is true even independently of the continuum hypothesis. Mathematical logic_sentence_190

Many special cases of this conjecture have been established. Mathematical logic_sentence_191

## Recursion theory Mathematical logic_section_16

Main article: Recursion theory Mathematical logic_sentence_192

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. Mathematical logic_sentence_193

Recursion theory also includes the study of generalized computability and definability. Mathematical logic_sentence_194

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. Mathematical logic_sentence_195

Classical recursion theory focuses on the computability of functions from the natural numbers to the natural numbers. Mathematical logic_sentence_196

The fundamental results establish a robust, canonical class of computable functions with numerous independent, equivalent characterizations using Turing machines, λ calculus, and other systems. Mathematical logic_sentence_197

More advanced results concern the structure of the Turing degrees and the lattice of recursively enumerable sets. Mathematical logic_sentence_198

Generalized recursion theory extends the ideas of recursion theory to computations that are no longer necessarily finite. Mathematical logic_sentence_199

It includes the study of computability in higher types as well as areas such as hyperarithmetical theory and α-recursion theory. Mathematical logic_sentence_200

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. Mathematical logic_sentence_201

### Algorithmically unsolvable problems Mathematical logic_section_17

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. Mathematical logic_sentence_202

The first results about unsolvability, obtained independently by Church and Turing in 1936, showed that the Entscheidungsproblem is algorithmically unsolvable. Mathematical logic_sentence_203

Turing proved this by establishing the unsolvability of the halting problem, a result with far-ranging implications in both recursion theory and computer science. Mathematical logic_sentence_204

There are many known examples of undecidable problems from ordinary mathematics. Mathematical logic_sentence_205

The word problem for groups was proved algorithmically unsolvable by Pyotr Novikov in 1955 and independently by W. Boone in 1959. Mathematical logic_sentence_206

The busy beaver problem, developed by Tibor Radó in 1962, is another well-known example. Mathematical logic_sentence_207

Hilbert's tenth problem asked for an algorithm to determine whether a multivariate polynomial equation with integer coefficients has a solution in the integers. Mathematical logic_sentence_208

Partial progress was made by Julia Robinson, Martin Davis and Hilary Putnam. Mathematical logic_sentence_209

The algorithmic unsolvability of the problem was proved by Yuri Matiyasevich in 1970 (). Mathematical logic_sentence_210

## Proof theory and constructive mathematics Mathematical logic_section_18

Main article: Proof theory Mathematical logic_sentence_211

Proof theory is the study of formal proofs in various logical deduction systems. Mathematical logic_sentence_212

These proofs are represented as formal mathematical objects, facilitating their analysis by mathematical techniques. Mathematical logic_sentence_213

Several deduction systems are commonly considered, including Hilbert-style deduction systems, systems of natural deduction, and the sequent calculus developed by Gentzen. Mathematical logic_sentence_214

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. Mathematical logic_sentence_215

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 (). Mathematical logic_sentence_216

Because proofs are entirely finitary, whereas truth in a structure is not, it is common for work in constructive mathematics to emphasize provability. Mathematical logic_sentence_217

The relationship between provability in classical (or nonconstructive) systems and provability in intuitionistic (or constructive, respectively) systems is of particular interest. Mathematical logic_sentence_218

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. Mathematical logic_sentence_219

Recent developments in proof theory include the study of proof mining by Ulrich Kohlenbach and the study of proof-theoretic ordinals by Michael Rathjen. Mathematical logic_sentence_220

## Applications Mathematical logic_section_19

"Mathematical logic has been successfully applied not only to mathematics and its foundations (G. Mathematical logic_sentence_221 Frege, B. Mathematical logic_sentence_222 Russell, D. Mathematical logic_sentence_223 Hilbert, P. Mathematical logic_sentence_224 Bernays, H. Mathematical logic_sentence_225 Scholz, R. Mathematical logic_sentence_226 Carnap, S. Mathematical logic_sentence_227 Lesniewski, T. Mathematical logic_sentence_228 Skolem), but also to physics (R. Carnap, A. Dittrich, B. Russell, C. Mathematical logic_sentence_229 E. Shannon, A. Mathematical logic_sentence_230 N. Whitehead, H. Mathematical logic_sentence_231 Reichenbach, P. Fevrier), to biology (J. Mathematical logic_sentence_232 H. Woodger, A. Mathematical logic_sentence_233 Tarski), to psychology (F. Mathematical logic_sentence_234 B. Fitch, C. Mathematical logic_sentence_235 G. Hempel), to law and morals (K. Mathematical logic_sentence_236 Menger, U. Klug, P. Oppenheim), to economics (J. Mathematical logic_sentence_237 Neumann, O. Mathematical logic_sentence_238 Morgenstern), to practical questions (E. Mathematical logic_sentence_239 C. Berkeley, E. Stamm), and even to metaphysics (J. [Jan] Salamucha, H. Scholz, J. Mathematical logic_sentence_240 M. Bochenski). Mathematical logic_sentence_241

Its applications to the history of logic have proven extremely fruitful (J. Mathematical logic_sentence_242 Lukasiewicz, H. Scholz, B. Mathematical logic_sentence_243 Mates, A. Becker, E. Mathematical logic_sentence_244 Moody, J. Salamucha, K. Duerr, Z. Jordan, P. Mathematical logic_sentence_245 Boehner, J. M. Bochenski, S. [Stanislaw] T. Schayer, D. Mathematical logic_sentence_246 Ingalls)." Mathematical logic_sentence_247

"Applications have also been made to theology (F. Drewnowski, J. Salamucha, I. Mathematical logic_sentence_248

Thomas)." Mathematical logic_sentence_249

## Connections with computer science Mathematical logic_section_20

Main article: Logic in computer science Mathematical logic_sentence_250

The study of computability theory in computer science is closely related to the study of computability in mathematical logic. Mathematical logic_sentence_251

There is a difference of emphasis, however. Mathematical logic_sentence_252

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. Mathematical logic_sentence_253

The theory of semantics of programming languages is related to model theory, as is program verification (in particular, model checking). Mathematical logic_sentence_254

The Curry–Howard isomorphism between proofs and programs relates to proof theory, especially intuitionistic logic. Mathematical logic_sentence_255

Formal calculi such as the lambda calculus and combinatory logic are now studied as idealized programming languages. Mathematical logic_sentence_256

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. Mathematical logic_sentence_257

Descriptive complexity theory relates logics to computational complexity. Mathematical logic_sentence_258

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. Mathematical logic_sentence_259

## Foundations of mathematics Mathematical logic_section_21

Main article: Foundations of mathematics Mathematical logic_sentence_260

In the 19th century, mathematicians became aware of logical gaps and inconsistencies in their field. Mathematical logic_sentence_261

It was shown that Euclid's axioms for geometry, which had been taught for centuries as an example of the axiomatic method, were incomplete. Mathematical logic_sentence_262

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. Mathematical logic_sentence_263

Cantor's study of arbitrary infinite sets also drew criticism. Mathematical logic_sentence_264

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. Mathematical logic_sentence_265

Although Kronecker's argument was carried forward by constructivists in the 20th century, the mathematical community as a whole rejected them. Mathematical logic_sentence_266

David Hilbert argued in favor of the study of the infinite, saying "No one shall expel us from the Paradise that Cantor has created." Mathematical logic_sentence_267

Mathematicians began to search for axiom systems that could be used to formalize large parts of mathematics. Mathematical logic_sentence_268

In addition to removing ambiguity from previously naive terms such as function, it was hoped that this axiomatization would allow for consistency proofs. Mathematical logic_sentence_269

In the 19th century, the main method of proving the consistency of a set of axioms was to provide a model for it. Mathematical logic_sentence_270

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. Mathematical logic_sentence_271

The resulting structure, a model of elliptic geometry, satisfies the axioms of plane geometry except the parallel postulate. Mathematical logic_sentence_272

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. Mathematical logic_sentence_273

This idea led to the study of proof theory. Mathematical logic_sentence_274

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. Mathematical logic_sentence_275

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. Mathematical logic_sentence_276

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. Mathematical logic_sentence_277

A second thread in the history of foundations of mathematics involves nonclassical logics and constructive mathematics. Mathematical logic_sentence_278

The study of constructive mathematics includes many different programs with various definitions of constructive. Mathematical logic_sentence_279

At the most accommodating end, proofs in ZF set theory that do not use the axiom of choice are called constructive by many mathematicians. Mathematical logic_sentence_280

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). Mathematical logic_sentence_281

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. Mathematical logic_sentence_282

In the early 20th century, Luitzen Egbertus Jan Brouwer founded intuitionism as a part of philosophy of mathematics . Mathematical logic_sentence_283

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. Mathematical logic_sentence_284

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. Mathematical logic_sentence_285

Brouwer's philosophy was influential, and the cause of bitter disputes among prominent mathematicians. Mathematical logic_sentence_286

Later, Kleene and Kreisel would study formalized versions of intuitionistic logic (Brouwer rejected formalization, and presented his work in unformalized natural language). Mathematical logic_sentence_287

With the advent of the BHK interpretation and Kripke models, intuitionism became easier to reconcile with classical mathematics. Mathematical logic_sentence_288