10
$\begingroup$

For a long time now I've been confused about the difference between truth and provability. I've also read questions like this but I still don't understand it. A typical example of my confusion is the following sentence (which I read on the linked page):

$17$ is a prime number. That is true. But if there are no deduction rules, then of course you cannot prove it.

I kind of get the idea here, but at the same time I do not really get it.

The fact that $17$ is a prime number must be specified in some way. If this way is not by it being provable, then how IS it specified? Is $17$ just defined to be a prime? But in that case '$17$ is prime' is basically an axiom, so then it IS provable.

I feel like my main confusion stems from the fact that I don't understand where/how the 'true' sentences are defined. Apparently they are not defined as 'everything that can be proven', so how ARE they defined?

Thanks

$\endgroup$
3
  • $\begingroup$ I'm assuming you mean "true" as in axiomatic, is this what you mean? $\endgroup$
    – Aleksandar
    Jun 24, 2015 at 11:46
  • $\begingroup$ @Aleksandar I mean true in the way it is used in for example Gödel's incompleteness theorems $\endgroup$ Jun 24, 2015 at 11:49
  • $\begingroup$ Would "proven" be a better word than "provable" for the purposes of this question? $\endgroup$ Jun 24, 2015 at 12:00

2 Answers 2

5
$\begingroup$

The usual way to define truth is due to Tarski. Given a structure $M$ (i.e. a set with operations and relations), we recursively define $M \models \phi$, meaning $\phi$ is true in $M$. For concreteness, let's consider the natural numbers $N = (\mathbb N, +, \times, 0, 1, <)$:

  • $N \models a + b = c$ if it the output of the binary function $+$ on input $(a,b)$ is $c$. Similarly for $N \models a \times b = c$.

    • $N \models a < b$ if $(a,b)$ is in the set $\mathord< \mathbin{\subseteq} \mathbb N^2$.

    • $N \models \phi \land \psi$ if $N \models \phi$ and $N \models \psi$ and $N \models \phi \lor \psi$ if $N \models \phi$ or $N \models \psi$.

    • $N \models \neg \phi$ if it is not the case that $N \models \phi$.

    • $N \models \exists x \phi(x)$ if there is some $a \in \mathbb N$ so that $N \models \phi(a)$ and $N \models \forall x \phi(x)$ if for all $a \in \mathbb N$ we have $N \models \phi(a)$.

In other words, truth is defined exactly how you would expect; symbols in the language correspond to certain constants, functions, and relations in the structure and truth is based upon that connection.

Provability, on the other hand, isn't a property of structures. Instead, it's a property of theories. If $T$ is a theory, meaning a set of sentences in some fixed language, then we can define a provability relation $T \vdash \phi$. There are many ways to do the details here to match with our intuitive notion of provability. But the important things are that the provability relation should be closed under valid inference rules (e.g. if $T \vdash \phi$ and $T \vdash \phi \rightarrow \psi$, then $T \vdash \psi$), that the axioms of $T$ are provable (if $\phi \in T$ then $T \vdash \phi$), and that logical validities (statements true in any structure) are provable.

We can now ask about how provability and truth relate. Any definition of provability worth a damn will be sound. This means that if $M$ is a model of $T$ (i.e. every axiom of $T$ is true in $M$, when interpreted appropriately), then $T \vdash \phi$ implies $M \models \phi$. In other other words, if we have proved something, then we know it is true. Moreover, as Gödel showed, first-order logic is complete. This means that if every model $M$ of $T$ has $M \models \phi$, then $T \vdash \phi$.

On a final note, it's very common to see people refer to truth without indicating a structure they are working in or refer to provability without indicating a theory they are working from. In the former situation, it's usually clear what structure is implicitly being used. For instance, the statement "17 is prime" is referring to the natural numbers, and can be translated to a formal statement something like $N \models \forall x < 17\, \exists y \le 17 \ (x \times y = 17 \rightarrow x = 1)$.

In the latter situation, when referring to provability, some implicit background of commonly accepted mathematics is assumed. When we say that the intermediate value theorem is provable, we mean that there is a proof of the IVT from some commonly accepted basic principles.

$\endgroup$
7
  • $\begingroup$ Oke so if I understand this correctly: you have a model for which you DEFINE the true statements. You can then consider some theory consisting of axioms and rules of inference (same as deduction?). If you can now somehow relate the axiom of your theory to some of the true sentences in the model (say using some function $f$), in such a way that $T \vdash \phi \Rightarrow M \models f(\phi)$ then you can consider the model to be 'an instance' of the theory, and can prove things about it using the theory. Oke this makes sense to me. Except! (see next comment) $\endgroup$ Jun 24, 2015 at 13:06
  • $\begingroup$ What's the point of the theory?! We have a model about which we want to say stuff, and we already defined everything there is to know about it when we constructed it! why would we want to take the round-about way of using theories (which are apparently full of flaws according to Godel) to say stuff about models? $\endgroup$ Jun 24, 2015 at 13:08
  • $\begingroup$ It's too hard to get at truth directly from the model. For example, consider the statement that there are infinitely many primes. In order to directly check that this is true, we'd have to look at each $n \in \mathbb N$ and find $m > n$ which is prime. This would require looking at infinitely many objects, which isn't feasible. On the other other, proofs are finite objects. Making finitely many deductions we can prove that there are infinitely many primes. $\endgroup$ Jun 24, 2015 at 13:25
  • 1
    $\begingroup$ @user2520938 I would agree with you. For most of mathematics, truth is what we care about and provability is a tool to get at that. $\endgroup$ Jun 24, 2015 at 13:34
  • 1
    $\begingroup$ There is an interesting video on YouTube discussing truth and provability: youtube.com/watch?v=HeQX2HjkcNo $\endgroup$
    – pmdci
    Jun 9, 2021 at 9:21
2
$\begingroup$

In math you need to start with a language with which to describe the objects of study. You can use set theory, type theory, etc. Then there will be a rigorous way to define "prime number". For example, "A number $x$ is prime if whenever $y$ divides $x$, $y$ must be $1$ or $x$." Then it is true that $17$ is prime. But, if we don't have a formalization of rules for deduction, we cannot prove that the number $17$ satisfies the definition we have for "prime".

Moreover, there are things we can state using the language of math that cannot be proven even given a formalized system of deduction. Since we can state them using the language of math, they must be true or false. We just can't deduce that truth value.

$\endgroup$
4
  • $\begingroup$ But isn't it strange to on the one hand claim you need 'rules for deduction' to conclude that $17$ is prime, while on the hand claiming that you already KNOW that it is true that $17$ is prime. How can you say 'then it is true that $17$ is prime' without the need to invoke some set of 'rules for deduction'? $\endgroup$ Jun 24, 2015 at 12:00
  • $\begingroup$ @user2520938 The reason we know that $17$ is prime is because there exist rules of deduction from which we can conclude it is prime. The point is that we can state a lot of things in math, but cannot prove anything without a system of deduction. We can state "$17$ is prime", but have no way of showing it without such a system. But, either $17$ is prime or it is not, regardless of whether we can prove it. Thankfully we have a system of deduction (several really) that can show it is indeed prime. $\endgroup$
    – J126
    Jun 24, 2015 at 12:09
  • 3
    $\begingroup$ "But, either 17 is prime or it is not, regardless of whether we can prove it." This I don't understand. Isn't all of mathematics done w.r.t. some system of axioms and rules of deduction? I always thought there's no such thing as 'absolute truth' but that we are always working within some system. Also, according to your logic, something is 'absolutely true' if there is SOME system in which we can prove it. But that's nonsense, because I can always work in a system that just assumes it as an axiom and claim it to be proven, thus true. $\endgroup$ Jun 24, 2015 at 12:17
  • $\begingroup$ @user2520938 You are losing sight of the intent of what you read. The original statement is just to show that truth and proof are different. You can have some facts that you want to be true, but have no way to prove them if you don't have the right deduction system. You are correct, we can add anything we want as an axiom and consider it proven. But, if you add some statement $P$ and the negation of $P$ is provable, you tend to run into problems. Again, this points out the difference between "truth" and "proof", at least as defined in mathematical systems. $\endgroup$
    – J126
    Jun 24, 2015 at 15:44

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.