Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Define a formal tautology as a statement where by the nature of its atomic components there exists no truth-value assignment where it is not true. A contingent statement is a statement that is true by facts of the world. A statement is necessarily true if the statement is true in all possible worlds. A necessarily true statement is not contingent and a contingent statement is not necessarily true. A formal tautology is necessarily true. But a necessarily true statement is not always a formal tautology.

Are there mathematical theorems which are contingent? Are all mathematical theorems necessarily true?

share|improve this question
1  
I suspect that in proof theory, "tautology" might have a more restricted and precise meaning than the one you use here. Are you asking about the colloquial use of the word? Sometimes mathematicians say something is "merely a tautology", which might I guess be a misuse of language –  Yemon Choi Jan 28 '10 at 19:28
4  
I would say that the question does not make sense as stated. True statements mathematical do not stop being true, so 'always true' is mostly a pleonasm, and 'necessarily true'... well, it would need at least context to become meaningful. –  Mariano Suárez-Alvarez Jan 28 '10 at 19:33
3  
Stalyn: asking a bunch of mathematicians will probably not enlighten you on the question of "what is a necessary truth as opposed to a contingent truth?"; it would be much better to ask a local friendly philosophy student, or read Kripke's Naming and Necessity, or look on the Stanford Encyclopedia of Philosophy. –  John Goodrick Jan 28 '10 at 20:13
3  
I think your question is still a little vague from the strictly mathematical standpoint since it's unclear what the possible worlds might be. I think a reasonable answer to your question is given in Solovay's Provability interpretations of modal logic (Israel J. Math 25, 1976). However, I can't convince myself that this answer is correct in all possible worlds... –  François G. Dorais Jan 28 '10 at 20:44
8  
Stalyn/Paul: I still think that mathoverflow is not the place for this question. The last I heard, there was no consensus in the philosophical community as to what exactly a "possible world" is, or whether this is even a coherent notion, or whether "necessity" really does mean "true in all possible worlds." Unless you mean to ask a precise question about first-order modal logic, then you'd be better off asking this question to philosophers. –  John Goodrick Jan 28 '10 at 20:59

4 Answers 4

up vote 14 down vote accepted

Apart from the storm of comments, let me just try to answer the question.

There are several ways in a which a mathematical theorem can be contingent.

  • First, the independence phenomenon in set theory shows the striking ubiquity of contingency in mathematics. For example, the Continuum Hypothesis is true is some set-theoretic worlds and false in others (and we can control it exactly). There are hundreds of other examples of statements with the same independence status---they are true in some worlds and false in others. The method of forcing has been used to spectacular effect in proving many of these independence results.

  • The Incompleteness phenomenon of Goedel can be used to show that whether a statement is provable or not from a given axiom system (in classical logic) can be contingent. Specifically, the Incompleteness theorem says that no theory T, if consistent, can prove its own consistency. Thus, if ZFC is consistent, then there are models of ZFC in which ZFC is thought to be inconsistent. In such a model, ZFC is thought to prove any statement at all! But in our world, not all these statements will be theorems. Thus, in this sense, even the question of whether a given statement is a theorem or not can be contingent.

  • The large cardinal hierarchy in set theory provides numerous examples of statements transcending the consistency strength of weaker statements. If large cardinals are consistent, then there are some set-theoretical universes in which ZFC proves that there are no inaccessible cardinals and other universes where it does not.

There are also several ways in which contingency is ruled out.

  • First, one of the most important properties of a proof system is soundness, which means that any statement provable in the system from true hypotheses will remain true. Of course, this is an expected feature of any proof system worthy of the name. A theorem is a statement having a proof in such a system. Once we have adopted a given proof system that is sound, and the axioms are all necessarily true, then the theorems will also all be necessarily true. In this sense, there can be no contingent theorems.

  • Second, one of the profound achievements of Goedel was his Completeness theorem, which states that any statement that holds in all models of a given first order theory T, actually has a proof from the theory. For example, every statement in the language of group theory that happens to be true in all groups, actually has a finite proof from the group axioms (using any of several proof systems). This is far from obvious, and I find it profound. But it answers a dual version of a question you might have asked, which I find interesting, namely: Is every necessary truth a theorem? The answer is Yes, and this is just what the Completeness theorem expresses.

These last two points together explain that if one takes the possible worlds to be all models of a given theory, then the necessary truths are precisely the theorems of that theory.

share|improve this answer

John Goodrick writes, very much to the point: The last I heard, there was no consensus in the philosophical community as to what exactly a "possible world" is, or whether this is even a coherent notion, or whether "necessity" really does mean "true in all possible worlds. I think this is a problem with how the question is formulated, but if answers do not assume there is a fixed interpetation of these terms, maybe we can say something that is not entirely useless.

Robert Hanna (Kant's Theory of Judgment, SEP 2009, sect. 2.2.2) interprets Kant as saying that "logically possible worlds are nothing but maximal logically consistent sets of concepts". If we apply this by saying that the logically possible worlds that can contain the concepts as expressed by an axiomatisation are the models of that theory, then it follows that the theorems of an axiomatisation are necessarily true.

There are some issues we might have with this:

  1. Necessity on this interpretation is completely orthogonal to questions about what are the appropriate axiomatisations of given mathematical concepts are; and
  2. Some mathematical concepts appear to have no adequate axiomatisations.

But necessity has never seemed to be a very useful concept to me as it is put to use in philosophy. It is one of the concepts that seem to illuminate, but only dazzle.

share|improve this answer

Charles wrote:

Robert Hanna (Kant's Theory of Judgment, SEP 2009, sect. 2.2.2) interprets Kant as saying that "logically possible worlds are nothing but maximal logically consistent sets of concepts". If we apply this by saying that the logically possible worlds that can contain the concepts as expressed by an axiomatisation are the models of that theory, then it follows that the theorems of an axiomatisation are necessarily true.

The logical quantifiers interact in odd ways with this idea, and make "maximality" kind of a problematic notion. This is a familiar phenomenon for mathematicians and logicians, of course, but may be worth pointing out explicitly. So, if we have some set of atomic concepts or assertions about the world, then a model of a possible world is a Boolean algebra on this set. Then the basic logical connectives (conjunction, disjunction, negation) can be modelled by intersection, union and complement.

So far, so good. Now, if the set of atomic assertions is finite, then the Boolean algebra is finite, and so it is also a complete lattice, and so quantified statements also have interpretations in the model. But if the set of atomic assertions is not finite, then a Boolean algebra on this set doesn't have to be complete, and so quantified statements might not have interpretations! If we do demand that the Boolean algebra is complete, then what we consider to be "logically possible" depends upon what kinds of logical connectives we wish to consider. (For example, in probability theory the difference between the Kolmogorov and Bayesian axioms of probability is that the Bayesians don't demand countable additivity, which means that an existentially-quantified propositions might not have a Bayesian interpretation.)

share|improve this answer
    
It's quite true that, say, a maximal PA-consistent set of arithmetical formulae need not be omega consistent. In fact it is cases such as these where we don't have adequate axiomatisations. –  Charles Stewart Jan 29 '10 at 13:02

As I understand the word "tautology" from Mathematical Logic; a logic $L$ means a formal system of deductions $\Sigma \vdash_L \Phi$, satisfying some rules, where $\Sigma$ is a set of propositions and $\Phi$ is a single proposition. In this setting, an $L$-tautology is a deduction $\{\} \vdash_L \Phi $; there is a constructive theorem ("Compactness") about classical first-order logic $L_0$ that for every deduction $\Sigma \vdash_{L_0} \Phi$ there is a finite subset $S$ of $\Sigma$ such that $\{\} \vdash \bigwedge S \implies \Phi$; but consider classical first-order logic in the language of arrithmetic and augmented by just the deduction scheme $$ \{ \Phi[n] | n\in \mathbb{N}\} \vdash \forall n: \Phi[n] .$$ Then this can't be reduced to a tautological implication --- for instance, if $\Phi[n]$ says "$n$ is not the Goedel number of a proof of your favorite Goedel sentence". Then this logic has a theorem $$ PA \vdash \forall n:\Phi[n] $$ where $PA$ is is the (infinite) set of axioms for Peano arrithmetic. But even though first-order arithmetic can prove $\Phi[n]$ for all natural $n$, it can't use a single proof to cover all $n$, and in particular, it can't prove the universal generalization.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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