hypothesis mathematical proof

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons

Margin Size

• Download Page (PDF)
• Download Full Book (PDF)
• Periodic Table
• Physics Constants
• Scientific Calculator
• Reference & Cite
• Tools expand_more
• Readability

selected template will load here

This action is not available.

9.1: Introduction to Hypothesis Testing

• Last updated
• Save as PDF
• Page ID 10211

• Kyle Siegrist
• University of Alabama in Huntsville via Random Services

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

Basic Theory

Preliminaries.

As usual, our starting point is a random experiment with an underlying sample space and a probability measure \(\P\). In the basic statistical model, we have an observable random variable \(\bs{X}\) taking values in a set \(S\). In general, \(\bs{X}\) can have quite a complicated structure. For example, if the experiment is to sample \(n\) objects from a population and record various measurements of interest, then \[ \bs{X} = (X_1, X_2, \ldots, X_n) \] where \(X_i\) is the vector of measurements for the \(i\)th object. The most important special case occurs when \((X_1, X_2, \ldots, X_n)\) are independent and identically distributed. In this case, we have a random sample of size \(n\) from the common distribution.

The purpose of this section is to define and discuss the basic concepts of statistical hypothesis testing . Collectively, these concepts are sometimes referred to as the Neyman-Pearson framework, in honor of Jerzy Neyman and Egon Pearson, who first formalized them.

A statistical hypothesis is a statement about the distribution of \(\bs{X}\). Equivalently, a statistical hypothesis specifies a set of possible distributions of \(\bs{X}\): the set of distributions for which the statement is true. A hypothesis that specifies a single distribution for \(\bs{X}\) is called simple ; a hypothesis that specifies more than one distribution for \(\bs{X}\) is called composite .

In hypothesis testing , the goal is to see if there is sufficient statistical evidence to reject a presumed null hypothesis in favor of a conjectured alternative hypothesis . The null hypothesis is usually denoted \(H_0\) while the alternative hypothesis is usually denoted \(H_1\).

An hypothesis test is a statistical decision ; the conclusion will either be to reject the null hypothesis in favor of the alternative, or to fail to reject the null hypothesis. The decision that we make must, of course, be based on the observed value \(\bs{x}\) of the data vector \(\bs{X}\). Thus, we will find an appropriate subset \(R\) of the sample space \(S\) and reject \(H_0\) if and only if \(\bs{x} \in R\). The set \(R\) is known as the rejection region or the critical region . Note the asymmetry between the null and alternative hypotheses. This asymmetry is due to the fact that we assume the null hypothesis, in a sense, and then see if there is sufficient evidence in \(\bs{x}\) to overturn this assumption in favor of the alternative.

An hypothesis test is a statistical analogy to proof by contradiction, in a sense. Suppose for a moment that \(H_1\) is a statement in a mathematical theory and that \(H_0\) is its negation. One way that we can prove \(H_1\) is to assume \(H_0\) and work our way logically to a contradiction. In an hypothesis test, we don't prove anything of course, but there are similarities. We assume \(H_0\) and then see if the data \(\bs{x}\) are sufficiently at odds with that assumption that we feel justified in rejecting \(H_0\) in favor of \(H_1\).

Often, the critical region is defined in terms of a statistic \(w(\bs{X})\), known as a test statistic , where \(w\) is a function from \(S\) into another set \(T\). We find an appropriate rejection region \(R_T \subseteq T\) and reject \(H_0\) when the observed value \(w(\bs{x}) \in R_T\). Thus, the rejection region in \(S\) is then \(R = w^{-1}(R_T) = \left\{\bs{x} \in S: w(\bs{x}) \in R_T\right\}\). As usual, the use of a statistic often allows significant data reduction when the dimension of the test statistic is much smaller than the dimension of the data vector.

The ultimate decision may be correct or may be in error. There are two types of errors, depending on which of the hypotheses is actually true.

Types of errors:

• A type 1 error is rejecting the null hypothesis \(H_0\) when \(H_0\) is true.
• A type 2 error is failing to reject the null hypothesis \(H_0\) when the alternative hypothesis \(H_1\) is true.

Similarly, there are two ways to make a correct decision: we could reject \(H_0\) when \(H_1\) is true or we could fail to reject \(H_0\) when \(H_0\) is true. The possibilities are summarized in the following table:

Of course, when we observe \(\bs{X} = \bs{x}\) and make our decision, either we will have made the correct decision or we will have committed an error, and usually we will never know which of these events has occurred. Prior to gathering the data, however, we can consider the probabilities of the various errors.

If \(H_0\) is true (that is, the distribution of \(\bs{X}\) is specified by \(H_0\)), then \(\P(\bs{X} \in R)\) is the probability of a type 1 error for this distribution. If \(H_0\) is composite, then \(H_0\) specifies a variety of different distributions for \(\bs{X}\) and thus there is a set of type 1 error probabilities.

The maximum probability of a type 1 error, over the set of distributions specified by \( H_0 \), is the significance level of the test or the size of the critical region.

The significance level is often denoted by \(\alpha\). Usually, the rejection region is constructed so that the significance level is a prescribed, small value (typically 0.1, 0.05, 0.01).

If \(H_1\) is true (that is, the distribution of \(\bs{X}\) is specified by \(H_1\)), then \(\P(\bs{X} \notin R)\) is the probability of a type 2 error for this distribution. Again, if \(H_1\) is composite then \(H_1\) specifies a variety of different distributions for \(\bs{X}\), and thus there will be a set of type 2 error probabilities. Generally, there is a tradeoff between the type 1 and type 2 error probabilities. If we reduce the probability of a type 1 error, by making the rejection region \(R\) smaller, we necessarily increase the probability of a type 2 error because the complementary region \(S \setminus R\) is larger.

The extreme cases can give us some insight. First consider the decision rule in which we never reject \(H_0\), regardless of the evidence \(\bs{x}\). This corresponds to the rejection region \(R = \emptyset\). A type 1 error is impossible, so the significance level is 0. On the other hand, the probability of a type 2 error is 1 for any distribution defined by \(H_1\). At the other extreme, consider the decision rule in which we always rejects \(H_0\) regardless of the evidence \(\bs{x}\). This corresponds to the rejection region \(R = S\). A type 2 error is impossible, but now the probability of a type 1 error is 1 for any distribution defined by \(H_0\). In between these two worthless tests are meaningful tests that take the evidence \(\bs{x}\) into account.

If \(H_1\) is true, so that the distribution of \(\bs{X}\) is specified by \(H_1\), then \(\P(\bs{X} \in R)\), the probability of rejecting \(H_0\) is the power of the test for that distribution.

Thus the power of the test for a distribution specified by \( H_1 \) is the probability of making the correct decision.

Suppose that we have two tests, corresponding to rejection regions \(R_1\) and \(R_2\), respectively, each having significance level \(\alpha\). The test with region \(R_1\) is uniformly more powerful than the test with region \(R_2\) if \[ \P(\bs{X} \in R_1) \ge \P(\bs{X} \in R_2) \text{ for every distribution of } \bs{X} \text{ specified by } H_1 \]

Naturally, in this case, we would prefer the first test. Often, however, two tests will not be uniformly ordered; one test will be more powerful for some distributions specified by \(H_1\) while the other test will be more powerful for other distributions specified by \(H_1\).

If a test has significance level \(\alpha\) and is uniformly more powerful than any other test with significance level \(\alpha\), then the test is said to be a uniformly most powerful test at level \(\alpha\).

Clearly a uniformly most powerful test is the best we can do.

\(P\)-value

In most cases, we have a general procedure that allows us to construct a test (that is, a rejection region \(R_\alpha\)) for any given significance level \(\alpha \in (0, 1)\). Typically, \(R_\alpha\) decreases (in the subset sense) as \(\alpha\) decreases.

The \(P\)-value of the observed value \(\bs{x}\) of \(\bs{X}\), denoted \(P(\bs{x})\), is defined to be the smallest \(\alpha\) for which \(\bs{x} \in R_\alpha\); that is, the smallest significance level for which \(H_0\) is rejected, given \(\bs{X} = \bs{x}\).

Knowing \(P(\bs{x})\) allows us to test \(H_0\) at any significance level for the given data \(\bs{x}\): If \(P(\bs{x}) \le \alpha\) then we would reject \(H_0\) at significance level \(\alpha\); if \(P(\bs{x}) \gt \alpha\) then we fail to reject \(H_0\) at significance level \(\alpha\). Note that \(P(\bs{X})\) is a statistic . Informally, \(P(\bs{x})\) can often be thought of as the probability of an outcome as or more extreme than the observed value \(\bs{x}\), where extreme is interpreted relative to the null hypothesis \(H_0\).

Analogy with Justice Systems

There is a helpful analogy between statistical hypothesis testing and the criminal justice system in the US and various other countries. Consider a person charged with a crime. The presumed null hypothesis is that the person is innocent of the crime; the conjectured alternative hypothesis is that the person is guilty of the crime. The test of the hypotheses is a trial with evidence presented by both sides playing the role of the data. After considering the evidence, the jury delivers the decision as either not guilty or guilty . Note that innocent is not a possible verdict of the jury, because it is not the point of the trial to prove the person innocent. Rather, the point of the trial is to see whether there is sufficient evidence to overturn the null hypothesis that the person is innocent in favor of the alternative hypothesis of that the person is guilty. A type 1 error is convicting a person who is innocent; a type 2 error is acquitting a person who is guilty. Generally, a type 1 error is considered the more serious of the two possible errors, so in an attempt to hold the chance of a type 1 error to a very low level, the standard for conviction in serious criminal cases is beyond a reasonable doubt .

Tests of an Unknown Parameter

Hypothesis testing is a very general concept, but an important special class occurs when the distribution of the data variable \(\bs{X}\) depends on a parameter \(\theta\) taking values in a parameter space \(\Theta\). The parameter may be vector-valued, so that \(\bs{\theta} = (\theta_1, \theta_2, \ldots, \theta_n)\) and \(\Theta \subseteq \R^k\) for some \(k \in \N_+\). The hypotheses generally take the form \[ H_0: \theta \in \Theta_0 \text{ versus } H_1: \theta \notin \Theta_0 \] where \(\Theta_0\) is a prescribed subset of the parameter space \(\Theta\). In this setting, the probabilities of making an error or a correct decision depend on the true value of \(\theta\). If \(R\) is the rejection region, then the power function \( Q \) is given by \[ Q(\theta) = \P_\theta(\bs{X} \in R), \quad \theta \in \Theta \] The power function gives a lot of information about the test.

The power function satisfies the following properties:

• \(Q(\theta)\) is the probability of a type 1 error when \(\theta \in \Theta_0\).
• \(\max\left\{Q(\theta): \theta \in \Theta_0\right\}\) is the significance level of the test.
• \(1 - Q(\theta)\) is the probability of a type 2 error when \(\theta \notin \Theta_0\).
• \(Q(\theta)\) is the power of the test when \(\theta \notin \Theta_0\).

If we have two tests, we can compare them by means of their power functions.

Suppose that we have two tests, corresponding to rejection regions \(R_1\) and \(R_2\), respectively, each having significance level \(\alpha\). The test with rejection region \(R_1\) is uniformly more powerful than the test with rejection region \(R_2\) if \( Q_1(\theta) \ge Q_2(\theta)\) for all \( \theta \notin \Theta_0 \).

Most hypothesis tests of an unknown real parameter \(\theta\) fall into three special cases:

Suppose that \( \theta \) is a real parameter and \( \theta_0 \in \Theta \) a specified value. The tests below are respectively the two-sided test , the left-tailed test , and the right-tailed test .

• \(H_0: \theta = \theta_0\) versus \(H_1: \theta \ne \theta_0\)
• \(H_0: \theta \ge \theta_0\) versus \(H_1: \theta \lt \theta_0\)
• \(H_0: \theta \le \theta_0\) versus \(H_1: \theta \gt \theta_0\)

Thus the tests are named after the conjectured alternative. Of course, there may be other unknown parameters besides \(\theta\) (known as nuisance parameters ).

Equivalence Between Hypothesis Test and Confidence Sets

There is an equivalence between hypothesis tests and confidence sets for a parameter \(\theta\).

Suppose that \(C(\bs{x})\) is a \(1 - \alpha\) level confidence set for \(\theta\). The following test has significance level \(\alpha\) for the hypothesis \( H_0: \theta = \theta_0 \) versus \( H_1: \theta \ne \theta_0 \): Reject \(H_0\) if and only if \(\theta_0 \notin C(\bs{x})\)

By definition, \(\P[\theta \in C(\bs{X})] = 1 - \alpha\). Hence if \(H_0\) is true so that \(\theta = \theta_0\), then the probability of a type 1 error is \(P[\theta \notin C(\bs{X})] = \alpha\).

Equivalently, we fail to reject \(H_0\) at significance level \(\alpha\) if and only if \(\theta_0\) is in the corresponding \(1 - \alpha\) level confidence set. In particular, this equivalence applies to interval estimates of a real parameter \(\theta\) and the common tests for \(\theta\) given above .

In each case below, the confidence interval has confidence level \(1 - \alpha\) and the test has significance level \(\alpha\).

• Suppose that \(\left[L(\bs{X}, U(\bs{X})\right]\) is a two-sided confidence interval for \(\theta\). Reject \(H_0: \theta = \theta_0\) versus \(H_1: \theta \ne \theta_0\) if and only if \(\theta_0 \lt L(\bs{X})\) or \(\theta_0 \gt U(\bs{X})\).
• Suppose that \(L(\bs{X})\) is a confidence lower bound for \(\theta\). Reject \(H_0: \theta \le \theta_0\) versus \(H_1: \theta \gt \theta_0\) if and only if \(\theta_0 \lt L(\bs{X})\).
• Suppose that \(U(\bs{X})\) is a confidence upper bound for \(\theta\). Reject \(H_0: \theta \ge \theta_0\) versus \(H_1: \theta \lt \theta_0\) if and only if \(\theta_0 \gt U(\bs{X})\).

Pivot Variables and Test Statistics

Recall that confidence sets of an unknown parameter \(\theta\) are often constructed through a pivot variable , that is, a random variable \(W(\bs{X}, \theta)\) that depends on the data vector \(\bs{X}\) and the parameter \(\theta\), but whose distribution does not depend on \(\theta\) and is known. In this case, a natural test statistic for the basic tests given above is \(W(\bs{X}, \theta_0)\).

www.springer.com The European Mathematical Society

• StatProb Collection
• Recent changes
• Current events
• Random page
• Project talk
• Request account
• What links here
• Related changes
• Special pages
• Printable version
• Permanent link
• Page information
• View source

Proof theory

A branch of mathematical logic which deals with the concept of a proof in mathematics and with the applications of this concept in various branches of science and technology.

In the wide meaning of the term, a proof is a manner of justification of the validity of some given assertion. To what extent a proof is convincing will mainly depend on the means employed to substantiate the truth. Thus, in exact sciences certain conditions have been established under which a certain experimental fact may be considered to have been proven (constant reproducibility of the experiment, clear description of the experimental technique, the experimental accuracy, the equipment employed, etc.). In mathematics, where the axiomatic method of study is characteristic, the means of proof were sufficiently precisely established at an early stage of its development. In mathematics, a proof consists of a succession of derivations of assertions from previously derived assertions, and the means of such derivation can be exactly analyzed.

The origin of proof theory can be traced to Antiquity (the deductive method of reasoning in elementary geometry, Aristotelian syllogistics, etc.), but the modern stage in its development begins at the turn of the 19th century with the studies of G. Frege, B. Russell, A.N. Whitehead, E. Zermelo, and, in particular, D. Hilbert. At that time, G. Cantor's research in the theory of sets gave rise to antinomies (cf. Antinomy ) which cast doubt on the validity of even the simplest considerations concerning arbitrary sets. L.E.J. Brouwer severely criticized certain classical methods of proof of the existence of objects in mathematics, and proposed a radical reconstruction of mathematics in the spirit of intuitionism . Problems concerning the foundations of mathematics became especially timely. Hilbert proposed to separate out the part of practical mathematics known as finitary mathematics, which is unobjectionable as regards both the appearance of antinomies and intuitionistic criticism. Finitary mathematics deals solely with constructive objects (cf. Constructive object ) such as, say, the natural numbers, and with methods of reasoning that agree with the abstraction of potential realizability but are not concerned with the abstraction of actual infinity . In particular, the use of the law of the excluded middle is restricted. In finitary mathematics, no antinomies have been noted and there is no reason for expecting them to appear. Philosophically, the methods of reasoning of finitary mathematics reflect the constructive processes of real activity much more satisfactorily than those in general set-theoretic mathematics. It was the idea of Hilbert to use the solid ground of finitary mathematics as the foundation of all main branches of classical mathematics. He accordingly presented his formalization method, which is one of the basic methods in proof theory.

In general outline, the formalization method may be described as follows. One formulates a logico-mathematic language (an object language) $ L $ in terms of which the assertions of a given mathematical theory $ T $ are written as formulas. One then describes a certain class $ A $ of formulas of $ L $, known as the axioms of the theory, and describes the derivation rules (cf. Derivation rule ) with the aid of which transitions may be made from given formulas to other formulas. The general term postulates applies to both axioms and derivation rules. The formal theory $ T ^ {*} $( a calculus according to a different terminology) is defined by a description of the postulates. Formulas which are obtainable from the axioms of the formal theory by its derivation rules are said to be deducible or provable in that theory. The deduction process itself may be formulated as a derivation tree. (See Derivation tree .) $ T ^ {*} $ is of special interest as regards the contents of the mathematical theory $ T $ if the axioms of $ T ^ {*} $ are records of true statements of $ T $ and if the derivation rules lead from true statements to true statements. In such a case $ T ^ {*} $ may be considered as a precision of a fragment of $ T $, while the concept of a derivation in $ T ^ {*} $ may be considered as a more precise form of the informal idea of a proof in $ T $, at least within the framework formalized by the calculus $ T ^ {*} $. Thus, in constructing the calculus $ T ^ {*} $, one must specify, in the first place, which postulates are to be considered suitable from the point of view of the theory $ T $. However, this does not mean that a developed semantics of $ T $ must be available at this stage; rather, it is permissible to employ practical habits, to include the most useful or the most theoretically interesting facts among the postulates, etc. The exact nature of the description of derivations in the calculus $ T ^ {*} $ makes it possible to apply mathematical methods in their study, and thus to give statements on the content and the properties of the theory $ T $.

Proof theory comprises standard methods of formalization of the content of mathematical theories. Axioms and derivation rules of the calculus are usually divided into logical and applied ones. Logical postulates serve to produce statements which are valid by virtue of their form itself, irrespective of the formalized theory. Such postulates define the logic of the formal theory and are formulated in the form of a propositional calculus or predicate calculus (see also Logical calculus ; Mathematical logic ; Intuitionism ; Constructive logic ; Strict implication calculus ). Applied postulates serve to describe truths related to the special features of a given mathematical theory. Examples are: the axiom of choice in axiomatic set theory; the scheme of induction in elementary arithmetic (cf. Mathematical induction ); and bar induction in intuitionistic analysis.

The Hilbert program for the foundations of mathematics may be described as follows. It may be hoped that any mathematical theory $ T $, no matter how involved or how abstract (e.g. the essential parts of set theory), may be formalized as a calculus $ T ^ {*} $ and that the formulation of the calculus itself requires finitary mathematics alone. Further, by analyzing the conclusions of $ T ^ {*} $ by purely finitary means, one tries to establish the consistency of $ T ^ {*} $ and, consequently, to establish the absence of antinomies in $ T $, at least in that part of it which is reflected in the postulates of $ T ^ {*} $. It immediately follows, as far as ordinary formalization methods are concerned, that certain very simple statements (in Hilbert's terminology — real statements) are deducible in $ T ^ {*} $ only if they are true in the finitary sense. It was initially hoped that practically all of classical mathematics could be described in a finitary way, after which its consistency could be demonstrated by finitary means. That this program could not be completed was shown in 1931 by K. Gödel, who proved that, on certain natural assumptions, it is not possible to demonstrate the consistency of $ T ^ {*} $ even by the powerful tools formalized in $ T ^ {*} $. Nevertheless, the study of various formal calculi remains a very important method in the foundations of mathematics. In the first place, it is of interest to construct calculi which reproduce important branches of modern mathematics, with consistency as the guideline, even if it is not yet possible to prove the consistency of such calculi in a manner acceptable to all mathematicians. An example of a calculus of this kind is the Zermelo–Fraenkel system of set theory, in which practically all results of modern set-theoretic mathematics can be deduced. Proofs of non-deducibility, in this theory, of several fundamental hypotheses obtained on the assumption that the theory is consistent (cf. Axiomatic set theory ; Forcing method ) indicate that these hypotheses are independent of the set-theoretic principles accepted in mathematics. This in turn may be regarded as a confirmation of the view according to which the existing concepts are insufficient to prove or disprove the hypotheses under consideration. It is in this sense that the independence of Cantor's continuum hypothesis has been established by P. Cohen.

Secondly, extensive study is made of the class of calculi whose consistency can be established by finitary means. Thus Gödel in 1932 proposed a translation converting formulas deducible by classical arithmetical calculus into formulas deducible by intuitionistic arithmetical calculus (i.e. an interpretation of the former calculus into the latter). If the latter is considered consistent (e.g. by virtue of its natural finitary interpretation), it follows that classical arithmetical calculus is self-consistent as well.

Finally, it may be promising to study more extensive methods than Hilbert's traditional finitism which are satisfactory from some other point of view. Thus, remaining in the framework of potential realizability, one may use so-called general inductive definitions. This makes it possible to use semi-formal theories in which some of the derivation rules have an infinite (but constructively generated) set of premises, and to transfer to finitary mathematics many semantic results. This procedure yielded the results obtained by P.S. Novikov (1943), who established the consistency of classical arithmetic using effective functionals of finite type; by C. Spector (1961), who proved the consistency of classical analysis by extending the natural intuitionistic methods of proof to include intuitionistic effective functionals of finite type; and by A.A. Markov (1971), on constructive semantics involving the use of general inductive definitions. In addition, many important problems on calculi may also be considered out of the context of the foundations of mathematics. These include problems of completeness and solvability of formal theories, the problem of independence of certain statements of a given formal theory, etc. It is then unnecessary to impose limitations of definite methods in the reasoning, and it is permissible to develop the theory of proofs as an ordinary mathematical theory, while using any mathematical means of proof that is convincing for the researcher.

A rigorously defined semantics for the formulas of the language under consideration, i.e. a strict definition of the meaning of the statements expressed in that language, serves as an instrument in the study of calculi, and sometimes even as a motivation for the introduction of new calculi. Thus, such a semantics is well-known in classical propositional calculus: Tautologies and only tautologies are deducible in such a calculus. In the general case, in order to prove that a certain formula $ A $ is not deducible in a calculus $ T ^ {*} $ under consideration, it is sufficient to construct a semantics for the formulas of the language of this theory such that all deducible formulas in $ T ^ {*} $ are true in this semantics, while $ A $ is false. A semantics can be classical, intuitionistic or of some other type, depending on the logical postulates it has to agree with. Non-classical semantics are successfully employed in the study of classical calculi — e.g. Cohen's forcing relationship can naturally be regarded as a modification of intuitionistic semantics. In another variant of Cohen's theory, multi-valued semantics are employed; these are models with truth values in a complete Boolean algebra. On the other hand, semantics of the type of Kripke models , defined by a classical set-theoretic method, make it possible to clarify many properties of modal and non-standard logics, including intuitionistic logic.

Proof theory makes extensive use of algebraic methods in the form of model theory . An algebraic system which brings each initial symbol of the language into correspondence with some algebraic objects forms a natural definition of some classical semantics of the language. An algebraic system is said to be a model of the formal theory $ T ^ {*} $ if all deducible formulas in $ T ^ {*} $ are true in the semantics generated by the algebraic system. Gödel showed in 1931 that any consistent calculus (with a classical logic) has a model. It was independently shown by A.I. Mal'tsev at a later date that if any finite fragment of a calculus has a model, then the calculus as a whole has a model (the so-called compactness theorem of first-order logic). These two theorems form the foundation of an entire trend in mathematical logic.

A survey of non-standard models of arithmetic established that the concept of the natural numbers is not axiomatizable in the framework of a first-order theory, and that the principle of mathematical induction is independent of the other axioms of arithmetical calculus. The relative nature of the concept of the cardinality of a set in classical mathematics was revealed during the study of countable models for formal theories, the interpretation of which is exclusively based on trivially uncountable models (the so-called Skolem's paradox). Many syntactic results were initially obtained from model-theoretic considerations. In terms of constructions of model theory it is possible to give simple criteria for many concepts of interest to proof theory. Thus, according to Scott's criterion, a class $ K $ of algebraic systems of a given language is axiomatizable if and only if it is closed with respect to ultra-products, isomorphisms and taking of elementary subsystems.

A formal theory is said to be decidable if there exists an algorithm which determines for an arbitrary formula $ A $ whether or not it is deducible in that theory. It is known that no formal theory containing a certain fragment of the theory of recursive functions (cf. Recursive function ) is decidable. It follows that elementary arithmetic, the Zermelo–Fraenkel system and many other theories are undecidable as well. Proof theory disposes of powerful methods for the interpretation of theories in terms of other theories; such interpretations may also be used to establish the undecidability of several very simple calculi in which recursive calculi are not interpreted directly. Examples are elementary group theory, the theory of two equivalence relations, an elementary theory of fractional order, etc. On the other hand, examples are available of interesting decidable theories such as elementary geometry, the elementary theory of real numbers, and the theory of sets of natural numbers with a unique successor operation. The decidability of a theory is demonstrated by model-theoretic and syntactic methods. Syntactic methods often yield simpler decidability algorithms. For instance, the decidability of the elementary theory of $ p $- adic numbers was first established by model-theoretic methods. Subsequently a primitive-recursive algorithm was found for the recognition of decidability of this theory by a certain modification of the syntactic method of quantifier elimination. Estimates of the complexity of decidability algorithms of theories are of importance. As a rule, a primitive-recursive solution algorithm is available for decidable theories, and the problem is to find more exact complexity bounds. A promising direction in such studies is the decidability of real fragments of known formal theories. In this connection classical predicate calculus has been studied in much detail, where an effective description has been given of all decidable and undecidable classes of formulas, in terms of the position of quantifiers in the formula and the form of the predicate symbols appearing in the formula. A number of decidable fragments of arithmetical calculus and of elementary set theory have been described.

Methods for estimating the complexity of derivations have attracted the attention of researchers. This area of research comprises problems such as finding relatively short formulas that are derivable in a complex manner, or formulas yielding a large number of results in a relatively simple manner. Such formulas must be regarded as expressing the "depth" of the facts in the theory. Natural measures of the complexity of a proof are studied: the length of the proof; the time needed to find a solution; the complexity of the formulas used in the proof, etc. This is the domain of contact between proof theory and the methods of theoretical cybernetics.

• This page was last edited on 6 June 2020, at 08:08.
• Privacy policy
• About Encyclopedia of Mathematics
• Disclaimers
• Impressum-Legal

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Difference between axioms, theorems, postulates, corollaries, and hypotheses

I've heard all these terms thrown about in proofs and in geometry, but what are the differences and relationships between them? Examples would be awesome! :)

• terminology

• 3 $\begingroup$ Go read this Wikipedia article and the articles it links to. $\endgroup$ –  kahen Commented Oct 24, 2010 at 20:22
• 10 $\begingroup$ One difficulty is that, for historical reasons, various results have a specific term attached (Parallel postulate, Zorn's lemma, Riemann hypothesis, Collatz conjecture, Axiom of determinacy). These do not always agree with the the usual usage of the words. Also, some theorems have unique names, for example Hilbert's Nullstellensatz. Since the German word there incorporates "satz", which means "theorem", it is not typical to call this the "Nullstellensatz theorem". These things make it harder to pick up the general usage. $\endgroup$ –  Carl Mummert Commented Oct 24, 2010 at 23:15

5 Answers 5

In Geometry, " Axiom " and " Postulate " are essentially interchangeable. In antiquity, they referred to propositions that were "obviously true" and only had to be stated, and not proven. In modern mathematics there is no longer an assumption that axioms are "obviously true". Axioms are merely 'background' assumptions we make. The best analogy I know is that axioms are the "rules of the game". In Euclid's Geometry, the main axioms/postulates are:

• Given any two distinct points, there is a line that contains them.
• Any line segment can be extended to an infinite line.
• Given a point and a radius, there is a circle with center in that point and that radius.
• All right angles are equal to one another.
• If a straight line falling on two straight lines makes the interior angles on the same side less than two right angles, the two straight lines, if produced indefinitely, meet on that side on which are the angles less than the two right angles. (The parallel postulate ).

A theorem is a logical consequence of the axioms. In Geometry, the "propositions" are all theorems: they are derived using the axioms and the valid rules. A "Corollary" is a theorem that is usually considered an "easy consequence" of another theorem. What is or is not a corollary is entirely subjective. Sometimes what an author thinks is a 'corollary' is deemed more important than the corresponding theorem. (The same goes for " Lemma "s, which are theorems that are considered auxiliary to proving some other, more important in the view of the author, theorem).

A " hypothesis " is an assumption made. For example, "If $x$ is an even integer, then $x^2$ is an even integer" I am not asserting that $x^2$ is even or odd; I am asserting that if something happens (namely, if $x$ happens to be an even integer) then something else will also happen. Here, "$x$ is an even integer" is the hypothesis being made to prove it.

See the Wikipedia pages on axiom , theorem , and corollary . The first two have many examples.

• 2 $\begingroup$ Arturo, I hope you don't mind if I edged your already excellent answer a little bit nearer to perfection. $\endgroup$ –  J. M. ain't a mathematician Commented Oct 25, 2010 at 0:26
• $\begingroup$ @J.M.: Heh. Not at all; thanks for the corrections! You did miss the single quotation mark after "propositions" in the second paragraph, though. (-: $\endgroup$ –  Arturo Magidin Commented Oct 25, 2010 at 0:33
• $\begingroup$ Great answer. Clear and informal, while still accurate. Better than wikipedia's, in my opinion. $\endgroup$ –  7hi4g0 Commented Feb 8, 2014 at 0:47
• $\begingroup$ Why is Bertrand's postulate considered a postulate? I don't think it would be obvious to anybody except to extraordinary geniuses like Euler, Gauss or Ramanujan.. $\endgroup$ –  AvZ Commented Feb 14, 2015 at 5:54
• 1 $\begingroup$ @gen-zreadytoperish: People don’t use usually use “postulate” anymore outside of historical contexts (e.g., “Bertrand’s postulate”). $\endgroup$ –  Arturo Magidin Commented Apr 12, 2020 at 20:26

Based on logic, an axiom or postulate is a statement that is considered to be self-evident. Both axioms and postulates are assumed to be true without any proof or demonstration. Basically, something that is obvious or declared to be true and accepted but have no proof for that, is called an axiom or a postulate. Axioms and postulate serve as a basis for deducing other truths.

The ancient Greeks recognized the difference between these two concepts. Axioms are self-evident assumptions, which are common to all branches of science, while postulates are related to the particular science.

Aristotle by himself used the term “axiom”, which comes from the Greek “axioma”, which means “to deem worth”, but also “to require”. Aristotle had some other names for axioms. He used to call them as “the common things” or “common opinions”. In Mathematics, Axioms can be categorized as “Logical axioms” and “Non-logical axioms”. Logical axioms are propositions or statements, which are considered as universally true. Non-logical axioms sometimes called postulates, define properties for the domain of specific mathematical theory, or logical statements, which are used in deduction to build mathematical theories. “Things which are equal to the same thing, are equal to one another” is an example for a well-known axiom laid down by Euclid.

The term “postulate” is from the Latin “postular”, a verb which means “to demand”. The master demanded his pupils that they argue to certain statements upon which he could build. Unlike axioms, postulates aim to capture what is special about a particular structure. “It is possible to draw a straight line from any point to any other point”, “It is possible to produce a finite straight continuously in a straight line”, and “It is possible to describe a circle with any center and any radius” are few examples for postulates illustrated by Euclid.

What is the difference between Axioms and Postulates?

• An axiom generally is true for any field in science, while a postulate can be specific on a particular field.

• It is impossible to prove from other axioms, while postulates are provable to axioms.

• $\begingroup$ Hmmm. This isn't a bad explanation, and thanks for attempting to explain the difference, but I'm still a bit fuzzy on the historical distinction as used by Aristotle and Euclid. $\endgroup$ –  Wildcard Commented Dec 10, 2016 at 2:53
• $\begingroup$ The historical part is interesting but at the end your statements are not correct. It is not the way the words "axiom" and "postulate" are being used in math and logic. $\endgroup$ –  LoMaPh Commented Jun 18, 2017 at 9:16

Technically Axioms are self-evident or self-proving, while postulates are simply taken as given. However really only Euclid and really high end theorists and some poly-maths make such a distinction. See http://www.friesian.com/space.htm

Theorems are then derived from the "first principles" i.e. the axioms and postulates.

• 3 $\begingroup$ No, that "technical" division really leads nowhere, and nowadays no one follows it. $\endgroup$ –  Andrés E. Caicedo Commented Nov 23, 2014 at 17:58
• 2 $\begingroup$ From a purely epistemological standpoint this is an excellent distinction, and I am extremely glad you took the time to contribute this simple answer. This fully clarified the historical difference for me. While @AndrésE.Caicedo is correct that this distinction doesn't form a part of modern mathematical practice, that doesn't make it wholly valueless. $\endgroup$ –  Wildcard Commented Dec 10, 2016 at 3:03

Axiom: Not proven and known to be unprovable using other axioms

Postulate: Not proven but not known if it can be proven from axioms (and theorems derived only from axioms)

Theorem: Proved using axioms and postulates

For example -- the parallel postulate of Euclid was used unproven but for many millennia a proof was thought to exist for it in terms of other axioms. Later is was definitively shown that it could not (by e.g. showing consistent other geometries). At that point it could be converted to axiom status for the Euclidean geometric system.

I think everything being marked as postulates is a bit of a disservice, but also reflect it would be almost impossible to track if any nontrivial theorem does not somewhere depend on a postulate rather than an axiom, also, standards for what constitutes 'proof' changes over time.

But I do think the triple structure is helpful for teaching beginning students. E.g. you can prove congruence of triangles via SSS with some axioms but it can be damnably hard and confusing/circular/nit-picky, so it makes sense to teach it as a postulate at first, use it, and then come back and show a proof.

• $\begingroup$ I think that the common usage does not require that an axiom is "known to be unprovable using other axioms." This would mean that there is no such thing as "an axiom", only "an axiom relative to other statements"; and it would mean that many common presentations of axioms actually don't consist of axioms. (For example, the axioms of a ring include left and right distributivity of multiplication over addition; the axioms of a commutative ring include commutativity of multiplication; but suddenly that means that we must (arbitrarily) pick only left or right distributivity as an axiom.) $\endgroup$ –  LSpice Commented Mar 6, 2018 at 14:39

Since it is not possible to define everything, as it leads to a never ending infinite loop of circular definitions, mathematicians get out of this problem by imposing "undefined terms". Words we never define. In most mathematics that two undefined terms are set and element of .

We would like to be able prove various things concerning sets. But how can we do so if we never defined what a set is? So what mathematicians do next is impose a list of axioms . An axiom is some property of your undefined object. So even though you never define your undefined terms you have rules about them. The rules that govern them are the axioms . One does not prove an axiom, in fact one can choose it to be anything he wishes (of course, if it is done mindlessly it will lead to something trivial).

Now that we have our axioms and undefined terms we can form some main definitions for what we want to work with.

After we defined some stuff we can write down some basic proofs. Usually known as propositions . Propositions are those mathematical facts that are generally straightforward to prove and generally follow easily form the definitions.

Deep propositions that are an overview of all your currently collected facts are usually called Theorems . A good litmus test, to know the difference between a Proposition and Theorem, as somebody once remarked here, is that if you are proud of a proof you call it a Theorem, otherwise you call it a Proposition. Think of a theorem as the end goals we would like to get, deep connections that are also very beautiful results.

Sometimes in proving a Proposition or a Theorem we need some technical facts. Those are called Lemmas . Lemmas are usually not useful by themselves. They are only used to prove a Proposition/Theorem, and then we forget about them.

The net collection of definitions, propositions, theorems, form a mathematical theory .

• 1 $\begingroup$ Please don't propound the falsehood that "it is not possible to define everything." I understand what you mean by it, but the result is only pedagogical disaster. (See my answer here.) The truth is that a concept or thought is a distinct entity from a symbolic representation, and when a concept is grasped directly, total understanding is possible in spite of the apparent circularity of defining words using other words. $\endgroup$ –  Wildcard Commented Dec 10, 2016 at 2:58

You must log in to answer this question.

Not the answer you're looking for browse other questions tagged terminology ..

• Upcoming Events
• 2024 Community Moderator Election ends in 6 days
• Featured on Meta
• We've made changes to our Terms of Service & Privacy Policy - July 2024
• Bringing clarity to status tag usage on meta sites
• Upcoming Moderator Election
• 2024 Community Moderator Election

Hot Network Questions

• As a resident of a Schengen country, do I need to list every visit to other Schengen countries in my travel history in visa applications?
• The minimal Anti-Sudoku
• Why didn't Walter White choose to work at Gray Matter instead of becoming a drug lord in Breaking Bad?
• Secret super people
• Sharing course material from a previous lecturer with a new lecturer
• A burning devil shape rises into the sky like a sun
• Is there any point "clean-installing" on a brand-new MacBook?
• Isn't an appeal to emotions in fact necessary to validate our ethical decisions?
• Is there a plurality of persons in the being of king Artaxerxes in his use of the pronoun "us" in Ezra 4:18?
• Is groff ignoring `.nh` command?
• Vim macro to mapping
• Specified data directory does not exist - but it does
• Are there rules of when there is linking-sound compound words?
• A post-apocalyptic short story where very sick people from our future save people in our timeline that would be killed in plane crashes
• How can I obscure branding on the side of a pure white ceramic sink?
• Why would Space Colonies even want to secede?
• Shift right by half a trit
• Is there an integer that serves as the short leg of a primitive Pythagorean triple, the long leg of another, and the hypotenuse of a third?
• What are those bars in subway train or bus called?
• How to declutter a mobile app home screen with a floating “Create Video” component?
• Fallacy of special significance of eigenvalues and eigenvectors of density operator
• Would it be possible for humans to be alive to witness the beginning of a runaway greenhouse effect on Earth?
• I submitted a paper and later realised one reference was missing, although I had written the authors in the body text. What could happen?
• Short story about a committee planning to eliminate 1 in 10 people

Mathematical Induction

Mathematical induction for summation.

The proof by mathematical induction (simply known as induction) is a fundamental proof technique that is as important as the direct proof, proof by contraposition, and proof by contradiction . It is usually useful in proving that a statement is true for all the natural numbers [latex]\mathbb{N}[/latex]. In this case, we are going to prove summation statements that depend on natural numbers [latex]\mathbb{N}[/latex] or the positive integers [latex]\mathbb{Z}^+[/latex].

My other lesson on mathematical induction deals with proving divisibility statements .

Believe me, the steps of proving using mathematical induction can be challenging at first. But when you actually start doing it, you will realize that it is very intuitive and simple. After going through the examples below, you will gain good insights and confidence to tackle much more challenging mathematical induction problems that deal with summations.

Steps to Prove by Mathematical Induction

• Show the basis step is true. It means the statement is true for [latex]n=1[/latex].
• Assume true for [latex]n=k[/latex]. This step is called the induction hypothesis .
• Prove the statement is true for [latex]n=k+1[/latex]. This step is called the induction step .

Diagram of Mathematical Induction using Dominoes

Examples of Proving Summation Statements by Mathematical Induction

Example 1: Use the mathematical to prove that the formula is true for all natural numbers [latex]\mathbb{N}[/latex].

[latex]3 + 7 + 11 + … + \left( {4n – 1} \right) = n\left( {2n + 1} \right)[/latex]

a) Check the basis step [latex]n=1[/latex] if it is true.

[latex]3= n\left( {2n + 1} \right)[/latex]

[latex]3 = 1\left[ {2\left( 1 \right) + 1} \right][/latex]

[latex]3 = 1\left( 3 \right)[/latex]

[latex]3 = 3[/latex]

Yes, it is true!

b) Assume the statement is true for [latex]n=k[/latex].

[latex]\color{red}3 + 7 + 11 + … + \left( {4k – 1} \right) = k\left( {2k + 1} \right)[/latex]

c) Now, we are going to prove that it is true for [latex]n=k+1[/latex].

[latex]3 + 7 + 11 + … + \left( {4k – 1} \right) + \left[ {4\left( {k + 1} \right) – 1} \right] = \left( {k + 1} \right)\left[ {2\left( {k + 1} \right) + 1} \right][/latex]

Notice that we can greatly simplify the equation using part b) .

[latex]{\color{red}3 + 7 + 11 + … + \left( {4k – 1} \right)} + \left[ {4\left( {k + 1} \right) – 1} \right] = \left( {k + 1} \right)\left[ {2\left( {k + 1} \right) + 1} \right][/latex]

[latex]{\color{red}k\left( {2k + 1} \right)} + \left[ {4\left( {k + 1} \right) – 1} \right] = \left( {k + 1} \right)\left[ {2\left( {k + 1} \right) + 1} \right][/latex]

The next obvious step is to simplify both sides of the equation. But here’s the thing. We want to simplify the left-hand side (LHS) as much as possible while the right-hand side (RHS) with the least number of steps when simplifying.

There’s nothing wrong if we are heavy on simplifications on both sides as long as we can show that both sides are equal. But it is more elegant that we keep the least amount of simplification on the right side with the most on the left. You will understand this better the more you practice with mathematical induction.

Without touching the left side of the equation, we are going to simplify the right side a bit. Distribute [latex]2[/latex] into the binomial inside the parenthesis then add the numbers.

[latex]k\left( {2k + 1} \right) + \left[ {4\left( {k + 1} \right) – 1} \right] = \left( {k + 1} \right)\left( {2k + 2 + 1} \right)[/latex]

[latex]k\left( {2k + 1} \right) + \left[ {4\left( {k + 1} \right) – 1} \right] = \left( {k + 1} \right)\left( {2k + 3} \right)[/latex]

Now, it’s time to manipulate the left-hand side so it looks the same as the right-hand side. Apply the Distributive Property twice then combine like terms. Finally, factor out the trinomial. We are done!

[latex]2{k^2} + k + 4k + 3= \left( {k + 1} \right)\left( {2k + 3} \right)[/latex]

[latex]2{k^2} + 5k + 3= \left( {k + 1} \right)\left( {2k + 3} \right)[/latex]

[latex]\left( {k + 1} \right)\left( {2k + 3} \right)= \left( {k + 1} \right)\left( {2k + 3} \right)[/latex] ✔︎

We have shown that if the statement is true for [latex]n=k[/latex], then it is also true for [latex]n=k+1[/latex]. Therefore, the statement is true for all natural numbers.◾️

Example 2: Use the mathematical induction to prove that the formula is true for all natural numbers [latex]\mathbb{N}[/latex].

[latex] – 1 + 2 + 5 + … + \left( {3n – 4} \right) = {\Large{{n \over 2}}}\left( {3n – 5} \right)[/latex]

a) Verify the basis step; [latex]n=1[/latex] is true.

[latex] – 1 = {\Large{{n \over 2}}}\left( {3n – 5} \right)[/latex]

[latex] – 1 = {\Large{{1 \over 2}}}\left[ {3\left( 1 \right) – 5} \right] [/latex]

[latex] – 1 = {\Large{{1 \over 2}}}\left[ {3 – 5} \right][/latex]

[latex] – 1 = {\Large{{1 \over 2}}}\left( { – 2} \right)[/latex]

[latex] – 1 = – 1[/latex]

[latex]\color{red} – 1 + 2 + 5 + … + \left( {3k – 4} \right) = {\Large{{k \over 2}}}\left( {3k – 5} \right)[/latex]

c) Now, we are going to show that it holds true for [latex]n=k+1[/latex].

[latex] – 1 + 2 + 5 + … + \left( {3k – 4} \right) + \left[ {3\left( {k + 1} \right) – 4} \right] = {\Large{{{k + 1} \over 2}}}\left[ {3\left( {k + 1} \right) – 5} \right][/latex]

We will use part b) to substitute it into the equation.

[latex]{\color{red} – 1 + 2 + 5 + … + \left( {3k – 4} \right)} + \left[ {3\left( {k + 1} \right) – 4} \right] = {\Large{{{k + 1} \over 2}}}\left[ {3\left( {k + 1} \right) – 5} \right][/latex]

[latex]{\color{red}{\Large{k \over 2}}\left( {3k – 5} \right)} + \left[ {3\left( {k + 1} \right) – 4} \right] = {\Large{{k + 1} \over 2}}\left[ {3\left( {k + 1} \right) – 5} \right][/latex]

Let’s focus on simplifying the right side of the equation first.

[latex]{\Large{k \over 2}}\left( {3k – 5} \right) + \left[ {3\left( {k + 1} \right) – 4} \right] = {\Large{{k + 1} \over 2}}\left[ {3\left( {k + 1} \right) – 5} \right][/latex]

[latex]{\Large{k \over 2}}\left( {3k – 5} \right) + \left[ {3\left( {k + 1} \right) – 4} \right] = {\Large{{k + 1} \over 2}}\left[ {3k + 3 – 5} \right][/latex]

[latex]{\Large{k \over 2}}\left( {3k – 5} \right) + \left[ {3\left( {k + 1} \right) – 4} \right] = {\Large{{k + 1} \over 2}}\left( {3k – 2} \right)[/latex]

It is time to simplify and manipulate the left-hand side to make it appear the same as the right side of the equation.

Example 3: Prove the equation using the mathematical induction that it is true for all natural numbers [latex]\mathbb{N}[/latex].

[latex]\large{1 + 2 + {2^2} + … + {2^{n – 1}} = {2^n} – 1 }[/latex]

a) Inspect the basis step; [latex]n=1[/latex] is true.

[latex]\large1 = {2^n} – 1[/latex]

[latex]\large 1 = {2^1} – 1[/latex]

[latex]\large1 = 2 – 1[/latex]

[latex]\large1 = 1 [/latex]

It is true!

[latex]\color{red}\large{1 + 2 + {2^2} + … + {2^{k – 1}} = {2^k} – 1 }[/latex]

c) If it is true for [latex]n=k[/latex], then it must be true for [latex]n=k+1[/latex].

[latex] \large1 + 2 + {2^2} + … + {2^{k – 1}} + {2^{\left( {k + 1} \right) – 1}} = {2^{k + 1}} – 1[/latex]

Use part b) to perform a substitution. This is the use of the assumption.

[latex] \large {\color{red}1 + 2 + {2^2} + … + {2^{k – 1}}} + {2^{\left( {k + 1} \right) – 1}} = {2^{k + 1}} – 1[/latex]

[latex] \large {\color{red} 2^{k}-1} + {2^{\left( {k + 1} \right) – 1}} = {2^{k + 1}} – 1[/latex]

There is no need to simplify the right-hand side. We will simplify and manipulate the left side of the equation so that it looks like the right side of the equation.

[latex] \large 2^{k}-1 + {2^{\left( {k + 1} \right) – 1}} = {2^{k + 1}} – 1[/latex]

Here we go!

Example 4: Prove the equation using the mathematical induction that it is true for all positive integers [latex]\mathbb{Z}^+[/latex].

[latex]4 + 9 + 14 + 19 + … + \left( {5n – 1} \right) ={\Large{ {n \over 2}}}\left( {5n + 3} \right)[/latex]

a) Show the basis step; [latex]n=1[/latex] is true.

[latex]4 = {\Large{{n \over 2}}}\left( {5n + 3} \right)[/latex]

[latex]4 ={ \Large{{1 \over 2}}}\left[ {5\left( 1 \right) + 3} \right] [/latex]

[latex] 4 = {\Large{{1 \over 2}}}\left[ {5 + 3} \right][/latex]

[latex]4 ={ \Large{{1 \over 2}}}\left( 8 \right) [/latex]

[latex]4 = 4 [/latex]

b) Assume true for [latex]n=k[/latex].

[latex]\color{red}4 + 9 + 14 + 19 + … + \left( {5k – 1} \right) = {\Large{{k \over 2}}}\left( {5k + 3} \right)[/latex]

c) If it is true for [latex]n=k[/latex], then [latex]n=k+1[/latex] must also be true.

[latex]4 + 9 + 14 + 19 + … + \left( {5k – 1} \right) + \left[ {5\left( {k + 1} \right) – 1} \right] = {\Large{{{k + 1} \over 2}}}\left[ {5\left( {k + 1} \right) + 3} \right][/latex]

Perform a substitution using the information in part b) . The seemingly complicated equation is going to be further simplified.

[latex]{\color{red}4 + 9 + 14 + 19 + … + \left( {5k – 1} \right)} + \left[ {5\left( {k + 1} \right) – 1} \right] = {\Large{{{k + 1} \over 2}}}\left[ {5\left( {k + 1} \right) + 3} \right][/latex]

[latex]{\color{red}{\Large{{k \over 2}}}\left( {5k + 3} \right)} + \left[ {5\left( {k + 1} \right) – 1} \right] = {\Large{{{k + 1} \over 2}}}\left[ {5\left( {k + 1} \right) + 3} \right][/latex]

Ignore the left side of the equation for now. We are going to clean up the right-hand side of the equation first by simplifying it.

[latex]{\Large{{k \over 2}}}\left( {5k + 3} \right) + \left[ {5\left( {k + 1} \right) – 1} \right] = {\Large{{{k + 1} \over 2}}}\left[ {5\left( {k + 1} \right) + 3} \right][/latex]

[latex]{\Large{{k \over 2}}}\left( {5k + 3} \right) + \left[ {5\left( {k + 1} \right) – 1} \right] = {\Large{{{k + 1} \over 2}}}\left( {5k + 5 + 3} \right)[/latex]

[latex]{\Large{{k \over 2}}}\left( {5k + 3} \right) + \left[ {5\left( {k + 1} \right) – 1} \right] = {\Large{{{k + 1} \over 2}}}\left( {5k + 8} \right)[/latex]

Our final step is to algebraically manipulate the left-hand side of the equation so that it becomes equal to the right-hand side.

We have shown that if the statement is true for [latex]n=k[/latex], then it is also true for [latex]n=k+1[/latex]. Therefore, the statement is true for all positive integers.◾️

Example 5: Use the mathematical induction to prove that the formula is true for all positive integers [latex]\mathbb{Z}^+[/latex].

[latex]\Large{1 \over {1 \cdot 2}} + {1 \over {2 \cdot 3}} + {1 \over {3 \cdot 4}} + … + {1 \over {n\left( {n + 1} \right)}} = {n \over {n + 1}} [/latex]

a) Show that the basis step is true for [latex]n=1[/latex].

[latex]\Large{1 \over {1 \cdot 2}} = {n \over {n + 1}}[/latex]

[latex]\Large{1 \over 2} = {n \over {n + 1}}[/latex]

[latex]\Large{1 \over 2} = {1 \over {1 + 1}} [/latex]

[latex]\Large{1 \over 2} = {1 \over 2}[/latex]

[latex]\color{red}\Large{1 \over {1 \cdot 2}} + {1 \over {2 \cdot 3}} + {1 \over {3 \cdot 4}} + … + {1 \over {k\left( {k + 1} \right)}} = {k \over {k + 1}}[/latex]

c) Now, we are going to show that it will hold true for [latex]n=k+1[/latex].

[latex]\Large{1 \over {1 \cdot 2}} + {1 \over {2 \cdot 3}} + {1 \over {3 \cdot 4}} + … + {1 \over {k\left( {k + 1} \right)}} + {1 \over {\left( {k + 1} \right)\left[ {\left( {k + 1} \right) + 1} \right]}} = {{k + 1} \over {\left( {k + 1} \right) + 1}}[/latex]

Use the assumption written in part b) to perform a substitution. This will greatly simplify the equation we are working on.

[latex]\Large{\color{red}{1 \over {1 \cdot 2}} + {1 \over {2 \cdot 3}} + {1 \over {3 \cdot 4}} + … + {1 \over {k\left( {k + 1} \right)}}} + {1 \over {\left( {k + 1} \right)\left[ {\left( {k + 1} \right) + 1} \right]}} = {{k + 1} \over {\left( {k + 1} \right) + 1}}[/latex]

[latex]\Large{\color{red}{k \over {k + 1}}} + {1 \over {\left( {k + 1} \right)\left[ {\left( {k + 1} \right) + 1} \right]}} = {{k + 1} \over {\left( {k + 1} \right) + 1}}[/latex]

Without paying attention to the left side of the equation, let’s simplify the right side.

[latex]\Large{k \over {k + 1}} + {1 \over {\left( {k + 1} \right)\left[ {\left( {k + 1} \right) + 1} \right]}} = {{k + 1} \over {\left( {k + 1} \right) + 1}}[/latex]

[latex]\Large{k \over {k + 1}} + {1 \over {\left( {k + 1} \right)\left[ {\left( {k + 1} \right) + 1} \right]}} = {{k + 1} \over {k + 1 + 1}}[/latex]

[latex]\Large{k \over {k + 1}} + {1 \over {\left( {k + 1} \right)\left[ {\left( {k + 1} \right) + 1} \right]}} = {{k + 1} \over {k + 2}}[/latex]

To finish this off, we will manipulate the left-hand side of the equation such that it equals the right-hand side.

Example 6: Use the mathematical induction to prove that the formula is true for all positive integers [latex]\mathbb{Z}^+[/latex].

[latex]\LARGE{1 \over 2} + {1 \over 4} + {1 \over 8} + … + {1 \over {{2^n}}} = {{{2^n} – 1} \over {{2^n}}} [/latex]

a) Check the basis step if [latex]n=1[/latex] is true.

[latex]\LARGE{1 \over 2} = {{{2^n} – 1} \over {{2^n}}}[/latex]

[latex]\LARGE{1 \over 2} = {{{2^1} – 1} \over {{2^1}}}[/latex]

[latex]\LARGE{1 \over 2} = {{2 – 1} \over 2}[/latex]

[latex]\LARGE{1 \over 2} = {1 \over 2}[/latex]

[latex]\LARGE\color{red}{1 \over 2} + {1 \over 4} + {1 \over 8} + … + {1 \over {{2^k}}} = {{{2^k} – 1} \over {{2^k}}}[/latex]

c) Prove that it is true for [latex]n=k+1[/latex].

[latex]\LARGE{1 \over 2} + {1 \over 4} + {1 \over 8} + … + {1 \over {{2^k}}} + {1 \over {{2^{k + 1}}}} = {{{2^{k + 1}} – 1} \over {{2^{k + 1}}}}[/latex]

Use the assumption to make a substitution in order to simplify the equation.

[latex]\LARGE{\color{red}{1 \over 2} + {1 \over 4} + {1 \over 8} + … + {1 \over {{2^k}}}} + {1 \over {{2^{k + 1}}}} = {{{2^{k + 1}} – 1} \over {{2^{k + 1}}}}[/latex]

[latex]\LARGE{\color{red}{{{2^k} – 1} \over {{2^k}}}} + {1 \over {{2^{k + 1}}}} = {{{2^{k + 1}} – 1} \over {{2^{k + 1}}}}[/latex]

We will keep the right-hand side unchanged because it is simplified enough. We will work on the left-hand side to make it look the same as the one on the right.

You might also like these tutorials:

• Mathematical Induction (Divisibility)

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons

Margin Size

• Download Page (PDF)
• Download Full Book (PDF)
• Periodic Table
• Physics Constants
• Scientific Calculator
• Reference & Cite
• Tools expand_more
• Readability

selected template will load here

This action is not available.

3.1: Proof by Induction

• Last updated
• Save as PDF
• Page ID 23859

• Pamini Thangarajah
• Mount Royal University

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

Inductive reasoning is the process of drawing conclusions after examining particular observations. This reasoning is very useful when studying number patterns. In many situations, inductive reasoning strongly suggests that the statement is valid, however, we have no way to present whether the statement is true or false, for example, Goldbach conjecture. But, in this class, we will deal with problems that are more accessible and we can often apply mathematical induction to prove our guess based on particular observations. For example, when we predict a \(n^{th}\) term for a given sequence of numbers, mathematics induction is useful to prove the statement, as it involves positive integers.

Process of Proof by Induction

There are two types of induction: regular and strong. The steps start the same but vary at the end. Here are the steps. In mathematics, we start with a statement of our assumptions and intent:

Let \(p(n), \forall n \geq n_0, \, n, \, n_0 \in \mathbb{Z_+}\) be a statement. We would show that p(n) is true for all possible values of n.

• Show that p(n) is true for the smallest possible value of n: In our case \(p(n_0)\). AND
• For Regular Induction: Assume that the statement is true for \(n = k,\) for some integer \(k \geq n_0\). Show that the statement is true for n = k + 1.

For Strong Induction: Assume that the statement p(r) is true for all integers r, where \(n_0 ≤ r ≤ k \) for some \(k ≥ n_0\). Show that p(k+1) is true.

If these steps are completed and the statement holds, we are saying that, by mathematical induction, we can conclude that the statement is true for all values of \(n \geq n_0.\)

We shall use the following template for proof by induction:

Template for proof by induction

In order to prove a mathematical statement involving integers, we may use the following template:

Suppose \(p(n), \forall n \geq n_0, \, n, \, n_0 \in \mathbb{Z_+}\) be a statement.

For regular Induction:

• Base Case: We need to s how that p(n) is true for the smallest possible value of n: In our case show that \(p(n_0)\) is true.
• Induction Hypothesis : Assume that the statement \(p(n)\) is true for any positive integer \(n = k,\) for s \(k \geq n_0\).
• Inductive Step: Show tha t the statement \(p(n)\) is true for \(n=k+1.\).

For strong Induction:

• Base Case: Show that p(n) is true for the smallest possible value of n: In our case \(p(n_0)\).
• Induction Hypothesis : Assume that the statement \(p(n)\) is true for all integers r, where \(n_0 ≤ r ≤ k \) for some \(k ≥ n_0\).

If these steps are completed and the statement holds, by mathematical induction, we can conclude that the statement is true for all values of \( n\geq n_0.\)

Example \(\PageIndex{1}\)

Exercise \(\PageIndex{1}\)

P rove that \(n < 2^n \) for \(n\in \mathbb{N}\).

Hint: \(k+1 < 2^k(1+1)\).

Example \(\PageIndex{2}\)

Prove that \(1 + 2 + ... + n = \displaystyle \frac{n(n + 1)}{2}, \, \forall n \in \mathbb{Z}\).

Base step : Choose \(n = 1\). Then L.H.S =\(1\). and R.H.S \( = \frac{(1)(1 + 1)}{2}=1\)

Induction Assumption : Assume that \( 1 + 2 + ... +k= \displaystyle\frac{k(k + 1)}{2}\), for \(k \in \mathbb{Z}\).

We shall show that \(1 + 2 + ... + k + (k + 1) = \displaystyle\frac{(k + 1)[(k + 1) + 1]}{2} = \frac{(k + 1)(k + 2)}{2}\)

Consider \(1 + 2 + ... + k + (k + 1) \)

\(= \displaystyle \frac{k(k + 1)}{2} + (k + 1)\)

\(= (k + 1) \left( \displaystyle\frac{k}{2} + \displaystyle\frac{1}{1}\right)\)

\(= (k + 1) \left( \displaystyle\frac{k + 2}{2}\right)\)

\(= \displaystyle \frac{(k + 1)(k + 2)}{2}\).

Thus, by induction we have \(1 + 2 + ... + n = \displaystyle\frac{n(n + 1)}{2}, \, \forall n \in \mathbb{Z}\).

We will explore examples that are related to number patterns in the next section.

• Comment Comments
• Save Article Read Later Read Later

Why Mathematical Proof Is a Social Compact

August 31, 2023

Andrew Granville on the campus of the University of Montreal.

Alex Tran for Quanta Magazine

Introduction

In 2012, the mathematician Shinichi Mochizuki claimed he had solved the abc conjecture, a major open question in number theory about the relationship between addition and multiplication. There was just one problem: His proof, which was more than 500 pages long, was completely impenetrable. It relied on a snarl of new definitions, notation, and theories that nearly all mathematicians found impossible to make sense of. Years later, when two mathematicians translated large parts of the proof into more familiar terms, they pointed to what one called a “ serious, unfixable gap ” in its logic — only for Mochizuki to reject their argument on the basis that they’d simply failed to understand his work.

The incident raises a fundamental question: What is a mathematical proof? We tend to think of it as a revelation of some eternal truth, but perhaps it is better understood as something of a social construct.

Andrew Granville , a mathematician at the University of Montreal, has been thinking about that a lot recently. After being contacted by a philosopher about some of his writing, “I got to thinking about how we arrive at our truths,” he said. “And once you start pushing at that door, you find it’s a vast subject.”

Granville enjoyed arithmetic from an early age, but he never considered a career in mathematics research because he didn’t know such a thing existed. “My father left school at 14, my mother at 15 or 16,” he said. “They were born in what was then the working-class area of London, and university was just beyond what they saw as possible. So we had no clue.”

After graduating from the University of Cambridge, where he studied math, he started adapting The Rachel Papers , a novel by Martin Amis, into a screenplay. While working on and seeking funding for the project, he wanted to avoid taking a desk job — he’d worked at an insurance company during a gap year between high school and college and didn’t want to return to it — “so I went to grad school,” he said. The film never got off the ground (the novel was later independently made into a movie), but Granville got a master’s degree in math and then moved to Canada to complete his doctorate. He never looked back.

Video : Andrew Granville muses on how artificial intelligence could profoundly change math.

Video: Emily Buder/ Quanta Magazine; Photo: Alex Tran for Quanta Magazine

“It was an adventure, really,” he said. “I didn’t really go in expecting much. I didn’t really know what a Ph.D. was.”

In the decades since, he has authored more than 175 papers, mostly in number theory. He’s also become well known for writing about math for a popular audience: In 2019, he co-authored a graphic novel about prime numbers and related concepts with his older sister, Jennifer, a screenwriter. Last month, one of his papers on “how we arrive at our truths” was published in the Annals of Mathematics and Philosophy. And along with other mathematicians, computer scientists and philosophers, he is planning to publish a collection of articles in next year’s Bulletin of the American Mathematical Society about how machines might change mathematics.

Quanta spoke with Granville about the nature of mathematical proof — from how proofs work in practice to popular misconceptions about them, to how proof-writing might evolve in the age of artificial intelligence. The interview has been edited and condensed for clarity.

You recently published a paper on the nature of mathematical proof. Why did you decide that this was important to write about?

How mathematicians go about research isn’t generally portrayed well in popular media. People tend to see mathematics as this pure quest, where we just arrive at great truths by pure thought alone. But mathematics is about guesses — often wrong guesses. It’s an experimental process. We learn in stages.

For example, when the Riemann hypothesis first appeared in a paper in 1859, it was like magic: Here’s this amazing conjecture, out of nowhere. For 70 years, people talked about what a great thinker can do by pure thought alone. Then the mathematician Carl Siegel found Riemann’s scratch notes in the Göttingen archives. Riemann had actually done pages of calculations of zeros of the Riemann zeta function. Siegel’s famous words were, “So much for pure thought alone.”

So there is this tension in the way people write about mathematics — some philosophers and historians in particular. They seem to think that we’re some pure magical creature, some unicorn of science. But we’re not, typically. It’s rarely pure thought alone.

Granville flipping through a copy of Prime Suspects, a math-themed murder mystery graphic novel he co-wrote with his older sister.

How would you characterize what mathematicians do?

The culture of mathematics is all about proof. We sit around and think, and 95% of what we do is proof. A lot of the understanding we gain is from struggling with proofs and interpreting the issues that come up when we struggle with them.

We often think of a proof as a mathematical argument. Through a series of logical steps, it demonstrates that a given statement is true. But you write that this shouldn’t be mistaken for pure, objective truth. What do you mean by that?

The main point of a proof is to persuade the reader of the truth of an assertion. That means verification is key. The best verification system we have in mathematics is that lots of people look at a proof from different perspectives, and it fits well in a context that they know and believe. In some sense, we’re not saying we know it’s true. We’re saying we hope it’s correct, because lots of people have tried it from different perspectives. Proofs are accepted by these community standards.

Then there’s this notion of objectivity — of being sure that what is claimed is right, of feeling like you have an ultimate truth. But how can we know we’re being objective? It’s hard to take yourself out of the context in which you’ve made a statement — to have a perspective outside of the paradigm that has been put in place by society. This is just as true for scientific ideas as it is for anything else.

One can also ask what is objectively interesting or important in mathematics. But this is also clearly subjective. Why do we consider Shakespeare to be a good writer? Shakespeare wasn’t as popular in his own time as he is today. There are obviously social conventions around what’s interesting, what’s important. And that depends on the current paradigm.

Granville inherited this copy of a 19th-cenutry mathematical text, the 1811 Cribrum Arithméticum by Ladislaud Chernac, when a colleague passed it to him in his will.

In math, what does that look like?

One of the most famous examples of a change in paradigm is calculus. When calculus was invented, it involved dividing something that’s going toward zero by something else that’s going toward zero — leading to zero divided by zero, which doesn’t have any meaning. Initially, Newton and Leibniz came up with objects called infinitesimals. It made their equations work, but by today’s standards it wasn’t sensible or rigorous.

We now have the epsilon-delta formulation, which was introduced at the end of the 19th century. This modern formulation is so stunningly, obviously good for getting these concepts right that when you look at the old formulations, you’re like, what were they thinking? But at the time, that was considered the only way you could do it. To be fair to Leibniz and Newton, they probably would have loved the modern way. They didn’t think to do it, because of the paradigms of their era. So it just took an awfully long time to get there.

The problem is, we don’t know when we’re behaving like that. We’re entrapped in the society we’re in. We don’t have an outside perspective to say what assumptions we’re making. One of the dangers in mathematics is that you can conceive of something as not being important because it’s not easily expressed or discussed in the language you’ve chosen to use. It doesn’t mean you’re right.

I really like this quote by Descartes, where he essentially says: “I think I know everything there is to know about a triangle, but who’s to say I do? I mean, somebody in the future might come up with a radically different perspective, leading to a much better way of thinking about a triangle.” And I think he’s right. You see that in mathematics.

As you wrote in your paper, you can think of a proof as a social compact — a sort of mutual agreement between the author and their mathematical community. We’ve seen an extreme example of this not working, with Mochizuki’s claimed proof of the abc conjecture.

It’s extreme, because Mochizuki did not want to play the game in the way it’s played. He has made this choice to be obscure. When people make big breakthroughs, with really new and difficult ideas, I feel it’s incumbent on them to try and include other people by explaining their ideas in as accessible a way as possible. And he was more like, well, if you don’t want to read it the way I wrote it, that’s not my problem. He has the right to play the game he wants to play. But it’s nothing to do with community. It’s nothing to do with the ways that we make progress.

“We get on and try to prove what we can,” said Granville.

If proofs exist in a social context, how have they changed over time?

It all starts with Aristotle. He said that there needs to be some sort of deductive system — that you can only prove new things by basing them on things you already know and are certain of, going back to certain “primitive statements,” or axioms.

So then the question is: What are those basic things that you know to be true? For a very long time, people just said, well, a line is a line, a circle is a circle; there are a few things that are simple and obvious, and those should be the assumptions we start from.

That perspective has lasted forever. It’s still around today to a large extent. But the Euclidean axiomatic system that developed — “a line is a line” — had its problems. There were these paradoxes discovered by Bertrand Russell based on the notion of a set. Moreover, one could play word games with the mathematical language, creating problematic statements like “this statement is false” (if it’s true, then it’s false; if it’s false, then it’s true) that indicated there were problems with the axiomatic system.

So Russell and Alfred Whitehead tried to create a new system of doing math that could avoid all these problems. But it was ludicrously complicated, and it was hard to believe that these were the right primitives to start from. Nobody was comfortable with it. Something like proving 2 + 2 = 4 took a vast amount of space from the starting point. What’s the point of such a system?

Then David Hilbert came along and had this amazing idea: that maybe we shouldn’t be telling anyone what’s the right thing to start with at all. Instead, anything that works — a starting point that’s simple, coherent and consistent — is worth exploring. You can’t deduce two things from your axioms that contradict each other, and you should be able to describe most of mathematics in terms of the selected axioms. But you shouldn’t a priori say what they are.

This, too, seems to fit into our earlier discussion of objective truth in math. So at the turn of the 20th century, mathematicians were realizing that there could be a plurality of axiomatic systems — that one given set of axioms shouldn’t be taken as a universal or self-evident truth?

Right. And I should say, Hilbert didn’t start off doing this for abstract reasons. He was very interested in different notions of geometry: non-Euclidean geometry. It was very controversial. People at the time were like, if you give me this definition of a line that goes around the corners of a box, why on earth should I listen to you? And Hilbert said that if he could make it coherent and consistent, you should listen, because this may be another geometry that we need to understand. And this change in viewpoint — that you can allow any axiomatic system — didn’t just apply to geometry; it applied to all of mathematics.

But of course, some things are more useful than others. So most of us work with the same 10 axioms, a system called ZFC.

Which leads to the question of what can and can’t be deduced from it. There are statements, like the continuum hypothesis, which cannot be proved using ZFC. There must be an 11th axiom. And you can resolve it either way, because you can choose your axiomatic system. It’s pretty cool. We continue with this sort of plurality. It’s not clear what’s right, what’s wrong. According to Kurt Gödel, we still need to make choices based on taste, and we hopefully have good taste. We should do things that make sense. And we do.

Speaking of Gödel, he plays a pretty big role here, too.

To discuss mathematics, you need a language, and a set of rules to follow in that language. In the 1930s, Gödel proved that no matter how you select your language, there are always statements in that language that are true but that can’t be proved from your starting axioms. It’s actually more complicated than that, but still, you have this philosophical dilemma immediately: What is a true statement if you can’t justify it? It’s crazy.

So there’s a big mess. We are limited in what we can do.

Professional mathematicians largely ignore this. We focus on what’s doable. As Peter Sarnak likes to say, “We’re working people.” We get on and try to prove what we can.

“One of the dangers in mathematics is that you can conceive of something as not being important because it’s not easily expressed or discussed in the language you’ve chosen to use. It doesn’t mean you’re right,” said Granville.

Now, with the use of not just computers but even AI, how is the notion of proof changing?

We’ve moved to a different place, where computers can do some wild things. Now people say, oh, we’ve got this computer, it can do things people can’t. But can it? Can it actually do things people can’t? Back in the 1950s, Alan Turing said that a computer is designed to do what humans can do, just faster. Not much has changed.

For decades, mathematicians have been using computers — to make calculations that can help guide their understanding, for instance. What AI can do that’s new is to verify what we believe to be true. Some terrific developments have happened with proof verification. Like [the proof assistant] Lean, which has allowed mathematicians to verify many proofs, while also helping the authors better understand their own work, because they have to break down some of their ideas into simpler steps to feed into Lean for verification.

But is this foolproof? Is a proof a proof just because Lean agrees it’s one? In some ways, it’s as good as the people who convert the proof into inputs for Lean. Which sounds very much like how we do traditional mathematics. So I’m not saying that I believe something like Lean is going to make a lot of errors. I’m just not sure it’s any more secure than most things done by humans.

I’m afraid I have a lot of skepticism about the role of computers. They can be a very valuable tool for getting things right — particularly for verifying mathematics that rests heavily on new definitions that are not easy to analyze at first sight. There’s no debate that it’s helpful to have new perspectives, new tools and new technology in our armory. But what I shy away from is the concept that we’re now going to have perfect logical machines that produce correct theorems.

You have to acknowledge that we can’t be sure things are correct with computers. Our future has to rely on the sense of community that we have relied on throughout the history of science: that we bounce things off one another. That we talk to people who look at the same thing from a completely different perspective. And so on.

Where do you see this going in the future, though, as these technologies get more sophisticated?

Perhaps it could assist in creating a proof. Maybe in five years’ time, I’ll be saying to an AI model like ChatGPT, “I’m pretty sure I’ve seen this somewhere. Would you check it out?” And it’ll come back with a similar statement that’s correct.

And then once it gets very, very good at that, perhaps you could go one step further and say, “I don’t know how to do this, but is there anybody who’s done something like this?” Perhaps eventually an AI model could find skilled ways to search the literature to bring tools to bear that have been used elsewhere — in a way that a mathematician might not foresee.

However, I don’t understand how ChatGPT can go beyond a certain level to do proofs in a way that outstrips us. ChatGPT and other machine learning programs are not thinking. They are using word associations based on many examples. So it seems unlikely that they will transcend their training data. But if that were to happen, what will mathematicians do? So much of what we do is proof. If you take proofs away from us, I’m not sure who we become.

Regardless, when we think about where we’re going to take computer assistance, we need to take into account all the lessons we’ve learned from human endeavor: the importance of using different languages, working together, carrying different perspectives. There’s a robustness, a health, in how different communities come together to work on and understand a proof. If we’re going to have computer assistance in mathematics, we need to enrich it in the same way.

Get highlights of the most important news delivered to your email inbox

Comment on this article

Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation. Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected. Moderators are staffed during regular business hours (New York time) and can only accept comments written in English. 

Next article

Grab your spot at the free arXiv Accessibility Forum

Help | Advanced Search

Mathematics > Logic

Title: the theory of maximal hardy fields.

Abstract: We show that all maximal Hardy fields are elementarily equivalent as differential fields to the differential field $\mathbb T$ of transseries, and give various applications of this result and its proof.

Submission history

Access paper:.

• HTML (experimental)
• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

BibTeX formatted citation

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .

Progress towards a grand unified theory of mathematics

In mathematics new results do not displace older ones but are absorbed into an ever-widening nexus.

Science advances by overturning theories, replacing them by better ones. Sometimes the old theories continue to serve as valuable approximations, as with Newton’s laws of motion.

Sometimes the older theories become redundant and are forgotten. The theory of phlogiston, a fire-like element released during combustion, and the luminiferous aether beloved of 19th century physicists and believed to transmit light through space have no role in modern science.

By contrast, the theorem of Pythagoras, still valid after several millenniums, is more important than ever. Mathematics has staying power. Unlike the physical, biological and medical sciences, mathematical theorems once proved remain valid forever. Mathematics is agglutinative: new results do not displace older ones but are absorbed into an ever-widening nexus.

Mathematical knowledge is growing so fast that no one can master it all. There is a risk of the subject fracturing into many fields that are mutually incomprehensible and apparently unrelated. Two opposing trends are at work here, fragmentation and unification. Things fall apart but the centre holds when, from time to time, sweeping simplifications arise and disparate fields are shown to be closely entangled.

Ireland’s housing crisis ‘on a different level’ with population growing at nearly four people for every new home built

MrBeast, one of YouTube’s richest stars, may have shown his true colours. Can his empire survive?

Trump’s ‘conversation’ with Musk reveals dangers that were not made explicit until now

An example of this unification was the merger of algebra and geometry by the great French philosopher René Descartes. His co-ordinate geometry enabled geometric objects such as lines and circles to be expressed using algebraic equations. Ultimately Descartes’ co-ordinates carried us far beyond two or three dimensions to multidimensional and even infinite dimensional spaces, which play a central role in modern theoretical physics.

There are concerted efforts under way to establish connections between number theory and topology, the global geometry of smooth surfaces. An ambitious programme was set down about 50 years ago by Robert Langlands of the Institute for Advanced Study in Princeton. This followed a visionary ambition, described by André Weil in a letter to his sister, the noted philosopher Simone Weil, to link three distinct areas of mathematics.

Weil described his idea for translating between fields as a Rosetta stone for mathematics, drawing an analogy with the famous engraving, now in the British Museum, that led to the decoding of Egyptian hieroglyphs. Weil’s Rosetta stone linked three fields of mathematics: number theory, geometry and finite fields.

Substantial strides have been made in the ensuing decades but many of the conjectures of the Langlands Programme remain to be proved. The programme has been called the Grand Unified Theory of Mathematics. It is also intimately related to modern physics, which seeks to reconcile quantum field theory and general relativity.

In 1798 the brilliant French mathematician Joseph Fourier was scientific adviser to Napoleon Bonaparte on his Egyptian expedition. Somewhat later, in a bravura development, Fourier established the link between the smooth sine waves of analysis and their discrete arithmetic spectra, foreshadowing the wave-particle duality of quantum physics.

A similar, if more complex, connection between the wave-like and spectral aspects of geometry was envisaged by Langlands. Earlier this year the last of a series of five papers appeared, authored by a team of nine mathematicians led by Dennis Gaitsgory of the Max Planck Institute. They proved the Geometric Langlands Conjecture.

The papers extend to more than 800 pages so, echoing Fermat, I conclude that the proof will not fit in the margin of The Irish Times. A recent article in the online Quanta Magazine tells the story in more detail.

Peter Lynch is emeritus professor at the school of mathematics & statistics, University College Dublin. He blogs at thatsmaths.com

• Sign up for push alerts and have the best news, analysis and comment delivered directly to your phone
• Join The Irish Times on WhatsApp and stay up to date
• Listen to our Inside Politics podcast for the best political chat and analysis

IN THIS SECTION

Will 200-year-old maps help inform decisions on crucial habitat restoration and future land use, multivitamin supplements are little more than expensive placebos, 'putting back nature that man eliminated': white-tailed sea eagles return to ireland, study raises hope of finding life on mars after indication of water, scientists say, flaming tennis balls, drones and corrupt guards make drug smuggling rife within irish prisons, garda assigned to protect cabinet member allegedly left gun in ted baker changing room, the myth of passport-free flying between britain and ireland under the common travel area, latest stories, ireland facing worsening shortage of gps as retirements loom, representative body warns.

What is mpox, why has it been declared a global emergency and is it in Ireland?

Russia’s Glushkov district to be evacuated as Ukrainian forces advance

Your top stories on Thursday: Ireland’s population growth outstrips housing delivery; and Olympic swimming pool sits in storage in Cork

Charlie versus Garret part two: Grotesque! Unbelievable! Bizarre! Unprecedented!

Woman (53) jailed over ‘blow the mosque up’ Facebook post after Southport riots

C&C ‘confident’ of full-year earnings growth despite consumer headwinds

• Terms & Conditions
• Privacy Policy
• Cookie Information
• Cookie Settings
• Community Standards