1
$\begingroup$

I recently started reading an introductory logic textbook, and I haven't got yet to the chapter that talks about completeness theorem, but I just couldn't wait to read about it using shortcuts. I just read Completeness Theorem and had the below question.

So in the link above, there is a proof for "every true statement is provable" by using Henkin's Theorem: if $T$ is syntactically consistent, then $T$ has a model.

But I am wondering what would be the proof for the converse: every provable statement is true.

Intuitively, this sounds obvious because if $T$ is provable, then in any model, we should be able to use the proof that $T$ is provable. This implies $T$ is provable in any model, (which implies there exists a proof of $T$ in any model???)$\leftarrow$ not sure.

Also, let's say we have a proof that every provable statement is true. But then that just tells me "every provable statement is true" is provable, not necessarily true???

Please assist me!

$\endgroup$
2
  • 1
    $\begingroup$ You are conflating a few things here. Provability and truth are relative concepts and they are relative to different things. Provability is relative to a deductive system, whereas truth is relative to an interpretation (/structure/model). In particular, there is no such thing as "provable in a model". (Though one might prove (in the metatheory) that a statement is true in a given model, just as one might prove (in the metatheory) that a statement is provable in a given formal system.) $\endgroup$ Oct 22, 2021 at 3:35
  • $\begingroup$ The correct reading of Completeness Th is twofold: (i) every theorem of a theory T is true in every model of T, where T is a set of axioms and a model of T is a "universe" satisfying the axioms. (ii) every theorem of a logical calculus, like e.g. predicate calculus, is valid, i.e. always true. $\endgroup$ Oct 22, 2021 at 6:47

2 Answers 2

5
$\begingroup$

The completeness theorem is a result about the traditional systems of proof that states $$ (T\vDash \phi) \Rightarrow (T \vdash \phi). $$ That is, if $\phi$ holds in every model where $T$ holds, then there exists a proof of $\phi$ from $T$. Conversely, the soundness theorem states $$ (T\vdash \phi) \Rightarrow (T\vDash \phi), $$ so that if you can prove $\phi$ from $T$ then in every model where $T$ holds, $\phi$ must also hold. The proof of the soundness theorem is considered elementary and goes like this:

(1) First prove that the proof system's laws of inference are truth-preserving. That is, any result deduced from statements true in model are also true in that model.

(2) Use induction on proof length to show that the last line of any finite length proof must be true in a model if the assumptions are true in that model.

My final comment is that you seem to be confusing theory with metatheory. When we carry out the proof sketched above we are trusting our metatheory, the set of assumptions we use when performing formal deductions on logical systems, to make true statements about our theory. But we can't expect the metatheory to logically vindicate itself, because at some point we have to just trust our assumptions.

$\endgroup$
2
  • $\begingroup$ I may misunderstood, but did you mean that we are 'believing' that if $P$ holds in arbitrary model, then $P$ holds in every model? I think your outlined proof shows that when we can prove $\phi$ from $T$, then if $M$ is an arbitrary model where $T$ holds, then $\phi$ holds. How would I deduce that this is true for every model $M$ where $T$ holds? $\endgroup$ Oct 22, 2021 at 3:32
  • $\begingroup$ @mathlearner98 If something is true for arbitrary $M$ then it's true for all $M$. This is known as universal generalization and is part of the metatheory. $\endgroup$
    – subrosar
    Oct 22, 2021 at 4:00
3
$\begingroup$

If the axioms you start with are true, and the logical inference rules you use are valid, then every statement you derive from those axioms and using those inference rules (which is to say: every provable statement) will be true as well.

$\endgroup$
2
  • $\begingroup$ I think I understand your answer, but also have some questions. So I get that if $P$ is provable, then $P$ is true. Does this imply every provable statement is true? $\endgroup$ Oct 22, 2021 at 3:14
  • $\begingroup$ @mathlearner98 Again, it depends on the axioms and inference rules you use. If the axioms are true, and the inference rules are valid, then yes: all statements that are provable from those axioms using those inference rules are true. But you cannot in general say that all provable statements are true: if you start with false axioms, or use inference rules that are not sound, then you can end up proving statements that are false. $\endgroup$
    – Bram28
    Oct 22, 2021 at 4:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .