Editing Foundations of mathematics (section)

== Foundational crisis<!-- 'Foundational crisis of mathematics' redirects here --> ==
The '''foundational crisis of mathematics'''<!-- boldface per WP:R#PLA -->
arose at the end of the 19th century and the beginning of the 20th century with the discovery of several [[paradox]]es or counter-intuitive results. 

The first one was the proof that the [[parallel postulate]] cannot be proved. This results from a construction of a [[non-Euclidean geometry]] inside [[Euclidean geometry]], whose [[inconsistency]] would imply the inconsistency of Euclidean geometry. A well known paradox is [[Russell's paradox]], which shows that the phrase "the set of all sets that do not contain themselves" is self-contradictory. Other philosophical problems were the proof of the existence of [[mathematical object]]s that cannot be computed or explicitly described, and the proof of the existence of theorems of [[arithmetic]] that cannot be proved with [[Peano arithmetic]]. 

Several schools of [[philosophy of mathematics]] were challenged with these problems in the 20th century, and are described below. 

These problems were also studied by mathematicians, and this led to establish [[mathematical logic]] as a new area of mathematics, consisting of providing mathematical definitions to logics (sets of [[inference rules]]), mathematical and logical theories, theorems, and proofs, and of using mathematical methods to prove theorems about these concepts. 

This led to unexpected results, such as [[Gödel's incompleteness theorems]], which, roughly speaking, assert that, if a theory contains the standard arithmetic, it cannot be used to prove that it itself is not [[consistent theory|self-contradictory]]; and, if it is not self-contradictory, there are theorems that cannot be proved inside the theory, but are nevertheless true in some technical sense. 

[[Zermelo–Fraenkel set theory]] with the [[axiom of choice]] (ZFC) is a logical theory established by [[Ernst Zermelo]] and [[Abraham Fraenkel]]. It became the standard foundation of modern mathematics, and, unless the contrary is explicitly specified, it is used in all modern mathematical texts, generally implicitly.

Simultaneously, the [[axiomatic method]] became a de facto standard: the proof of a theorem must result from explicit [[axiom]]s and previously proved theorems by the application of clearly defined inference rules. The axioms need not correspond to some reality. Nevertheless, it is an open philosophical problem to explain why the axiom systems that lead to rich and useful theories are those resulting from abstraction from the physical reality or other mathematical theory.

In summary, the foundational crisis is essentially resolved, and this opens new philosophical problems. In particular, it cannot be proved that the new foundation (ZFC) is not self-contradictory. It is a general consensus that, if this would happen, the problem could be solved by a mild modification of ZFC. 

=== Philosophical views ===
{{Main|Philosophy of mathematics}}

When the foundational crisis arose, there was much debate among mathematicians and logicians about what should be done for restoring confidence in mathematics. This involved philosophical questions about [[mathematical truth]], the relationship of mathematics with [[reality]], the reality of [[mathematical object]]s, and the nature of mathematics.

For the problem of foundations, there were two main options for trying to avoid paradoxes. The first one led to [[intuitionism]] and [[constructivism (mathematics)|constructivism]], and consisted to restrict the logical rules for remaining closer to intuition, while the second, which has been called [[formalism (mathematics)|formalism]], considers that a theorem is true if it can be deduced from [[axiom]]s by applying inference rules ([[formal proof]]), and that no "trueness" of the axioms is needed for the validity of a theorem.

==== Formalism ====
{{Main|Formalism (mathematics)}}

It has been claimed{{by whom|date=June 2024}} that formalists, such as [[David Hilbert]] (1862&ndash;1943), hold that mathematics is only a language and a series of games. Hilbert insisted that formalism, called "formula game" by him, is a fundamental part of mathematics, but that mathematics must not be reduced to formalism. Indeed, he used the words "formula game" in his 1927 response to [[L. E. J. Brouwer]]'s criticisms:

{{blockquote|And to what extent has the formula game thus made possible been successful? This formula game enables us to express the entire thought-content of the science of mathematics in a uniform manner and develop it in such a way that, at the same time, the interconnections between the individual propositions and facts become clear ... The formula game that Brouwer so deprecates has, besides its mathematical value, an important general philosophical significance. For this formula game is carried out according to certain definite rules, in which the ''technique of our thinking'' is expressed. These rules form a closed system that can be discovered and definitively stated.<ref name="ReferenceA">Hilbert 1927 ''The Foundations of Mathematics'' in van Heijenoort 1967:475</ref>}}

Thus Hilbert is insisting that mathematics is not an ''arbitrary'' game with ''arbitrary'' rules; rather it must agree with how our thinking, and then our speaking and writing, proceeds.<ref name="ReferenceA"/>

{{blockquote|We are not speaking here of arbitrariness in any sense. Mathematics is not like a game whose tasks are determined by arbitrarily stipulated rules. Rather, it is a conceptual system possessing internal necessity that can only be so and by no means otherwise.<ref>p. 14 in Hilbert, D. (1919–20), Natur und Mathematisches Erkennen: Vorlesungen, gehalten 1919–1920 in Göttingen. Nach der Ausarbeitung von Paul Bernays (Edited and with an English introduction by David E. Rowe), Basel, Birkhauser (1992).</ref>}}

The foundational philosophy of formalism, as exemplified by [[David Hilbert]], is a response to the paradoxes of [[set theory]], and is based on [[formal logic]]. Virtually all mathematical [[theorem]]s today can be formulated as theorems of set theory. The truth of a mathematical statement, in this view, is represented by the fact that the statement can be derived from the [[Zermelo–Fraenkel set theory|axioms of set theory]] using the rules of formal logic.

Merely the use of formalism alone does not explain several issues: why we should use the axioms we do and not some others, why we should employ the logical rules we do and not some others, why "true" mathematical statements (e.g., the [[Peano axioms|laws of arithmetic]]) appear to be true, and so on. [[Hermann Weyl]] posed these very questions to Hilbert:

{{blockquote|What "truth" or objectivity can be ascribed to this theoretic construction of the world, which presses far beyond the given, is a profound philosophical problem. It is closely connected with the further question: what impels us to take as a basis precisely the particular axiom system developed by Hilbert? Consistency is indeed a necessary but not a sufficient condition. For the time being we probably cannot answer this question ...<ref>Weyl 1927 ''Comments on Hilbert's second lecture on the foundations of mathematics'' in van Heijenoort 1967:484. Although Weyl the intuitionist believed that "Hilbert's view" would ultimately prevail, this would come with a significant loss to philosophy: "''I see in this a decisive defeat of the philosophical attitude of pure phenomenology'', which thus proves to be insufficient for the understanding of creative science even in the area of cognition that is most primal and most readily open to evidence{{snd}} mathematics" (ibid).</ref>}}

In some cases these questions may be sufficiently answered through the study of formal theories, in disciplines such as [[reverse mathematics]] and [[computational complexity theory]]. As noted by Weyl, [[formal logical system]]s also run the risk of [[consistency proof|inconsistency]]; in [[Peano axioms|Peano arithmetic]], this arguably has already been settled with several proofs of [[consistency proof|consistency]], but there is debate over whether or not they are sufficiently [[finitism|finitary]] to be meaningful. [[Gödel's incompleteness theorem|Gödel's second incompleteness theorem]] establishes that logical systems of arithmetic can never contain a valid proof of their own [[consistency proof|consistency]]. What Hilbert wanted to do was prove a logical system ''S'' was consistent, based on principles ''P'' that only made up a small part of ''S''. But Gödel proved that the principles ''P'' could not even prove ''P'' to be consistent, let alone ''S''.

==== Intuitionism ====
{{Main|Intuitionism|Constructivism (mathematics)}}

Intuitionists, such as [[L. E. J. Brouwer]] (1882–1966), hold that mathematics is a creation of the human mind. Numbers, like fairy tale characters, are merely mental entities, which would not exist if there were never any human minds to think about them.

The foundational philosophy of ''[[intuitionism]]'' or ''[[constructivism (mathematics)|constructivism]]'', as exemplified in the extreme by [[Luitzen Egbertus Jan Brouwer|Brouwer]] and [[Stephen Kleene]], requires proofs to be "constructive" in nature{{snd}} the existence of an object must be demonstrated rather than inferred from a demonstration of the impossibility of its non-existence. For example, as a consequence of this the form of proof known as [[reductio ad absurdum]] is suspect.

Some modern [[theory|theories]] in the philosophy of mathematics deny the existence of foundations in the original sense. Some theories tend to focus on [[mathematical practice]], and aim to describe and analyze the actual working of mathematicians as a [[social group]]. Others try to create a [[cognitive science of mathematics]], focusing on human cognition as the origin of the reliability of mathematics when applied to the real world. These theories would propose to find foundations only in human thought, not in any objective outside construct. The matter remains controversial.

==== Logicism ====
{{Main|Logicism}}

[[Logicism]] is a school of thought, and research programme, in the philosophy of mathematics, based on the thesis that mathematics is an extension of logic or that some or all mathematics may be derived in a suitable formal system whose axioms and rules of inference are 'logical' in nature. [[Bertrand Russell]] and [[Alfred North Whitehead]] championed this theory initiated by [[Gottlob Frege]] and influenced by [[Richard Dedekind]].

==== Set-theoretic Platonism ====
{{main|Set-theoretic Platonism}}
Many researchers in [[axiomatic set theory]] have subscribed to what is known as set-theoretic [[Platonism#Modern Platonism|Platonism]], exemplified by [[Kurt Gödel]].

Several set theorists followed this approach and actively searched for axioms that may be considered as true for heuristic reasons and that would decide the [[continuum hypothesis]]. Many [[large cardinal]] axioms were studied, but the hypothesis always remained [[Independence (mathematical logic)|independent]] from them and it is now considered unlikely that CH can be resolved by a new large cardinal axiom. Other types of axioms were considered, but none of them has reached consensus on the continuum hypothesis yet. Recent work by [[Joel David Hamkins|Hamkins]] proposes a more flexible alternative: a set-theoretic [[multiverse]] allowing free passage between set-theoretic universes that satisfy the continuum hypothesis and other universes that do not.

==== Indispensability argument for realism ====
{{Main|Quine–Putnam indispensability argument}}
This [[Quine–Putnam indispensability thesis|argument]] by [[Willard Quine]] and [[Hilary Putnam]] says (in Putnam's shorter words),

{{blockquote|...&nbsp;quantification over mathematical entities is indispensable for science&nbsp;... therefore we should accept such quantification; but this commits us to accepting the existence of the mathematical entities in question.}}

However, Putnam was not a Platonist.

==== Rough-and-ready realism ====
Few mathematicians are typically concerned on a daily, working basis over logicism, formalism or any other philosophical position. Instead, their primary concern is that the mathematical enterprise as a whole always remains productive. Typically, they see this as ensured by remaining open-minded, practical and busy; as potentially threatened by becoming overly-ideological, fanatically reductionistic or lazy.

Such a view has also been expressed by some well-known physicists.

For example, the Physics Nobel Prize laureate [[Richard Feynman]] said

{{blockquote|People say to me, "Are you looking for the ultimate laws of physics?" No, I'm not ... If it turns out there is a simple ultimate law which explains everything, so be it&nbsp;– that would be very nice to discover. If it turns out it's like an onion with millions of layers ... then that's the way it is. But either way there's Nature and she's going to come out the way She is. So therefore when we go to investigate we shouldn't predecide what it is we're looking for only to find out more about it.<ref name="fey1">Richard Feynman, ''The Pleasure of Finding Things Out'' p. 23</ref>}}

And [[Steven Weinberg]]:<ref name="weinberg">Steven Weinberg, chapter ''[http://libcom.org/library/unexpected-uselessness-philosophy Against Philosophy]'' wrote, in ''Dreams of a final theory''</ref>

{{blockquote|The insights of philosophers have occasionally benefited physicists, but generally in a negative fashion – by protecting them from the preconceptions of other philosophers. ... without some guidance from our preconceptions one could do nothing at all. It is just that philosophical principles have not generally provided us with the right preconceptions.}}

Weinberg believed that any undecidability in mathematics, such as the continuum hypothesis, could be potentially resolved despite the incompleteness theorem, by finding suitable further axioms to add to set theory.

==== Philosophical consequences of Gödel's completeness theorem ====
{{Main|Gödel's completeness theorem}}

Gödel's completeness theorem establishes an equivalence in first-order logic between the formal provability of a formula and its truth in all possible models. Precisely, for any consistent first-order theory it gives an "explicit construction" of a model described by the theory; this model will be countable if the language of the theory is countable. However this "explicit construction" is not algorithmic. It is based on an iterative process of completion of the theory, where each step of the iteration consists in adding a formula to the axioms if it keeps the theory consistent; but this consistency question is only semi-decidable (an algorithm is available to find any contradiction but if there is none this consistency fact can remain unprovable).

=== More paradoxes ===
{{See also|List of statements independent of ZFC|List of paradoxes}}

The following lists some notable results in metamathematics. [[Zermelo–Fraenkel set theory]] is the most widely studied axiomatization of set theory. It is abbreviated '''ZFC''' when it includes the [[axiom of choice]] and '''ZF''' when the axiom of choice is excluded.

*1920: [[Thoralf Skolem]] corrected [[Leopold Löwenheim]]'s proof of what is now called the [[downward Löwenheim–Skolem theorem]], leading to [[Skolem's paradox]] discussed in 1922, namely the existence of countable models of ZF, making infinite cardinalities a relative property.
*1922: Proof by [[Abraham Fraenkel]] that the axiom of choice cannot be proved from the axioms of [[Zermelo set theory]] with [[urelement]]s.
*1931: Publication of [[Gödel's incompleteness theorems]], showing that essential aspects of Hilbert's program could not be attained. It showed how to construct, for any sufficiently powerful and consistent recursively axiomatizable system{{snd}} such as necessary to axiomatize the elementary theory of [[arithmetic]] on the (infinite) set of natural numbers{{snd}} a statement that formally expresses its own unprovability, which he then proved equivalent to the claim of consistency of the theory; so that (assuming the consistency as true), the system is not powerful enough for proving its own consistency, let alone that a simpler system could do the job. It thus became clear that the notion of mathematical truth cannot be completely determined and reduced to a purely [[formal system]] as envisaged in Hilbert's program. This dealt a final blow to the heart of Hilbert's program, the hope that consistency could be established by finitistic means (it was never made clear exactly what axioms were the "finitistic" ones, but whatever axiomatic system was being referred to, it was a 'weaker' system than the system whose consistency it was supposed to prove).
*1936: [[Alfred Tarski]] proved his [[Tarski's undefinability theorem|truth undefinability theorem]].
*1936: [[Alan Turing]] proved that a general algorithm to solve the [[halting problem]] for all possible program-input pairs cannot exist.
*1938: Gödel proved the [[Constructible universe|consistency of the axiom of choice and of the generalized continuum hypothesis]].
*1936–1937: [[Alonzo Church]] and [[Alan Turing]], respectively, published independent papers showing that a general solution to the [[Entscheidungsproblem]] is impossible: the universal validity of statements in first-order logic is not decidable (it is only [[semi-decidable]] as given by the [[completeness theorem]]).
*1955: [[Pyotr Novikov]] showed that there exists a [[finitely presented group]] G such that the [[Word problem for groups|word problem]] for G is undecidable.
*1963: [[Paul Cohen (mathematician)|Paul Cohen]] showed that the Continuum Hypothesis is unprovable from [[Zermelo–Fraenkel set theory|ZFC]]. Cohen's proof developed the method of [[Forcing (mathematics)|forcing]], which is now an important tool for establishing [[Independence (mathematical logic)|independence]] results in set theory.
*1964: Inspired by the fundamental randomness in physics, [[Gregory Chaitin]] starts publishing results on [[algorithmic information theory]] (measuring incompleteness and randomness in mathematics).<ref>{{Citation |first=Gregory |last=Chaitin |author-link=Gregory Chaitin |url=https://www.cs.auckland.ac.nz/~chaitin/sciamer3.pdf |title=The Limits Of Reason |journal=Scientific American |volume=294 |issue=3 |pages=74–81 |year=2006 |access-date=2016-02-22 |archive-url=https://web.archive.org/web/20160304192140/https://www.cs.auckland.ac.nz/~chaitin/sciamer3.pdf |archive-date=2016-03-04 |url-status=dead |pmid=16502614 |doi=10.1038/scientificamerican0306-74 |bibcode=2006SciAm.294c..74C }}</ref>
*1966: Paul Cohen showed that the axiom of choice is unprovable in ZF even without [[urelements]].
*1970: [[Hilbert's tenth problem]] is proven unsolvable: there is no recursive solution to decide whether a [[Diophantine equation]] (multivariable polynomial equation) has a solution in integers.
*1971: [[Suslin's problem]] is proven to be independent from ZFC.