2
$\begingroup$

Mathematicians frequently speak of a theorem being stronger than another. But on its face, this does not make sense, since all theorems in a formal system imply each other, hence are equivalent. Is there some paper or text where this notion is made precise, where there is defined a preorder on theorems that is stronger than equivalence but weaker than strict identity? I would like a link to such a paper.

$\endgroup$
  • 1
    $\begingroup$ You can see Axiom of choice for several examples of statement that are consequences of AC but not equivalent to it; in this case, we say that these statements are "weaker than" AC. $\endgroup$ – Mauro ALLEGRANZA Apr 2 '15 at 13:41
  • 3
    $\begingroup$ You can see also this post. $\endgroup$ – Mauro ALLEGRANZA Apr 2 '15 at 14:39
  • $\begingroup$ The key to understanding what mathematicians mean when they say things like this is to think of a theorem not as a proposition $P$ but rather an implication $H \to C$. ($H$ stands for hypothesis, $C$ stands for conclusion.) Usually, what we mean when we say that $H \to C$ is stronger that $H' \to C'$ is that $H'$ implies $H$ and $C$ implies $C'$. Obviously, this is not truth-functional, and it even depends on the precise decomposition of the theorem into hypotheses and conclusions. $\endgroup$ – Zhen Lin Apr 2 '15 at 15:10
  • $\begingroup$ @Zhen Lin: as in my comment on Peter Smith's answer, I claim that the prime number theorem is a strengthening of the theorem that there are infinitely many primes. How does your analysis explain that? $\endgroup$ – Rob Arthan Apr 2 '15 at 20:51
  • $\begingroup$ That is harder to analyse, yes. One possibility is to look at families/generalisations. For your example, we could consider the statement $P (R)$ obtained by replacing $\mathbb{Z}$ in the prime number theorem with any infinite normed commutative ring. Then $P (R)$ is only conditionally true. But the statement "$P (R)$ implies $R$ has infinitely many prime elements" remains true. $\endgroup$ – Zhen Lin Apr 2 '15 at 21:02
1
$\begingroup$

Yes, there is a way of making this notion precise. Namely, for two theorems $A$ and $B$ of a theory $T$, one can fix a subtheory $T_0$ of $T$ and ask whether or not $T_0 \cup \{A\} \vdash B$. The idea is that the "base theory" $T_0$ has only some basic axioms that we take for granted (and which axioms we wish to take for granted can depend on the context.)

For example, both the Boolean Prime Ideal Theorem and the Hahn–Banach Theorem are provable in $\mathsf{ZFC}$; however, it is often said that the Hahn–Banach Theorem is weaker than the Boolean Prime Ideal Theorem because it can be proved from the $\mathsf{ZF}$ axioms plus the Boolean Prime Ideal Theorem, whereas the Boolean Prime Ideal Theorem cannot be proved from the $\mathsf{ZF}$ axioms plus the Hahn–Banach Theorem.

Naturally, the meaning of "weaker than" depends on the base theory (here it is $\mathsf{ZF}$.)

Besides consequences of $\mathsf{AC}$, another context in which this notion has been studied extensively is subsystems of second order arithmetic — see the book by Stephen G. Simpson by this name. Here the theory $T$ is second-order arithmetic (instead of $\mathsf{ZFC}$) and the base theory $T_0$ is a weak subtheory called $\mathsf{RCA}_0$.

$\endgroup$
4
$\begingroup$

"All theorems in a formal system imply each other".

Not so.

Suppose $T \vdash_S A$ and $T \vdash_S B$ where $T$ is some theory whose deductive apparatus is $S$ [e.g. first-order logic], and $\vdash_S$ is syntactic entailment in $S$. Nothing whatsoever follows about whether $A \vdash_S B$ or $B \vdash_S A$. So the claim doesn't apply to theoremhood and implication understood in terms syntactic entailment.

Suppose $T \vDash_L A$ and $T \vDash_L B$ where $T$ is some theory in language $L$, and $\vDash_L$ is the notion of semantical entailment appropriate to the language $L$. Nothing whatsoever follows about whether $A \vDash_L B$ or $B \vDash_L A$. So the claim doesn't apply to theorem hood and implication understood in terms of semantic entailment either.

(Perhaps you think "implies" in the sense relevant to talk about one theorem implying more than another is well captured by material implication, i.e. the truth-functional conditional. Well, it isn't. And anyway even if $T \supset A$ and $T \supset B$, nothing as yet follows about whether $A \supset B$ or $B \supset A$ either.)

$\endgroup$
  • 1
    $\begingroup$ However, if $T = \emptyset$, e.g. because all the axioms have been folded into the deductive system $S$, ... $\endgroup$ – Zhen Lin Apr 2 '15 at 15:05
  • $\begingroup$ I suspect that most mathematicians make statements about the strength of theorems that are much harder to formalise. E.g., I don't think it would be exceptional to state that the prime number theorem is stronger than the theorem that there are infinitely many primes. How would you apply your analysis to a statement like that? $\endgroup$ – Rob Arthan Apr 2 '15 at 16:46
  • $\begingroup$ @RobArthan I didn't give an analysis -- I was just trying to get out of the way that claim that all theorems in a formal system imply each other, which was supposed to show that that talk about one theorem being stronger than another doesn't even make sense. $\endgroup$ – Peter Smith Apr 2 '15 at 21:27
  • $\begingroup$ @Peter Smith: sorry, I thought you were trying to answer the question. $\endgroup$ – Rob Arthan Apr 3 '15 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.