Re: ? Completeness Quantification ?

From: Chris Menzel (cmenzel_at_remove-this.tamu.edu)
Date: 11/20/04 

Date: 20 Nov 2004 08:50:01 GMT

On Sat, 20 Nov 2004 20:30:50 +1300, Barb Knox <see@sig.below> said:
> In article <fa8tp0hp86ei7hm1heje75k33c9g4djudl@4ax.com>,
> num num <num@num.num> wrote:
>
>>I'm told that in the completeness theorem of classical logic
>>
>> P |- g <=> P |= g

Actually, the completeness theorem proper is the <= direction. The =>
direction is the soundness theorem, which says, in effect, that your
logical axioms are all valid and your rules of inference are
truth-preserving.

>>(where P is a set of formulae and g is a formula) the statement of
>>syntactic entailment 'P |- g' is existentially quantified and the
>>statement of semantic entailment 'P |= g' is universally quantified.
>>Can someone explain to me why that's the case?
>
> That is (IMO) a rather odd way to put it,

But really, isn't it exactly right, if we take "P |= g" and "P |- g" to
be mere notational abbreviations?

> but it can be seen as being true by unwinding some of the notation:
> 'P |= g' is really an abbreviation for
> For all models M, if M |= P then M |= g

<pedantry>
Granted, "model" is often used to mean "interpretation (of some given
language L)", but I think it's a little more common to use "model" to
indicate an interpretation in which all the members of some given set of
sentences are true. So understood, where L is the language in question,
"P |= g" means "for all interpretations M of L, if M is a model of P,
then g is true in M".
</pedantry>

Chris Menzel

Relevant Pages

  • Re: Semantics of First-Order Languages
    ... and an interpretation of this language such that it would not possible ... We also know that there are infinitely many sentences in the language ... in the naturals, while, in fact, the sentence is true when interpreted ... I think I am never going to understand the completeness theorem, ...
    (sci.logic)
  • Re: Proof and entailment
    ... One sense is that for every sentence P in the language of the theory, ... But that is 'complete' in a sense not meant in this context. ... (i.e., as you mentioned, negation complete). ... of the completeness theorem EXCEPT just to use the TITLE 'the ...
    (sci.logic)
  • Re: Semantics of First-Order Languages
    ... But classical first-order proof is ... so you are ALWAYS computing something. ... on the COMPLETENESS theorem?? ... can be proved is that they are true IRrespective of interpretation! ...
    (sci.logic)
  • Re: Semantics of First-Order Languages
    ... But classical first-order proof is ... so you are ALWAYS computing something. ... on the COMPLETENESS theorem?? ... can be proved is that they are true IRrespective of interpretation! ...
    (sci.logic)
  • Re: Confusion about gödels proof for con(ZF+CH)
    ... But doesn't the completeness theorem say that "If a formula is true ... for every interpretation then it is provable". ... I thought that relativization was about inner models, ... structure M was a inner model of a theory if the relativised formulae ...
    (sci.logic)