Re: completeness what is it exactly

On Jul 7, 10:47 pm, Chris Menzel <cmen...@xxxxxxxxxxxxxxxxxxxx> wrote:
On Mon, 07 Jul 2008 19:03:55 +0200, Jan Burse <janbu...@xxxxxxxxxxx> said:





translogi schrieb:
Hello

following another discussion

http://groups.google.com/group/sci.logic/browse_frm/thread/06c1ca6e6a....

What is completeness exactly?

what kind of completeness are there?
(I remember long ago having read somewhere about strong completeness
and weak completeness but I  forgot what the difference was.)

can anybody refresh my memory?

A theory T is complete :<=> forall "A" (T |- A v T |- ~A)

A theory T is complete and has witnesses :<=> T is complete
    and forall "exists A" (T |- exists A => exists t T |- A[x/t])

That's often referred to as "negation" completeness.  There is also a
notion of completeness -- often referred to as "semantic" completeness
-- that applies to logics rather than theories.  Say that a logic is a
language L together with a semantics and a proof theory.  A logic is
*complete* if every logical truth of L (i.e., every sentence that is
true in every interpretation of L according to the semantics) is a
theorem of the proof theory.  This is sometimes referred to as "weak"
(semantic) completeness.  A logic is strongly complete if, whenever a
set S of sentences of L entails a sentence A of L, there is a proof of A
from S.  (S entails A if every interpretation that makes all the
sentences in S true also makes A true.)- Hide quoted text -

- Show quoted text -

So, let's distinguish for logics between 'logical truth
completeness' (LTC) and 'logical consequence completeness' (LCC). You
say LCC is called 'strong' while LTC is called 'weak'.

I see that LCC entails LTC. But not vice versa? Are there any counter-
examples?

Thanks
.

Relevant Pages

  • Re: completeness what is it exactly
    ... At least two different kinds of completeness. ... A is a well formed formula ... negation completeness has nothing whatever to do with truth. ... of logics. ...
    (sci.logic)
  • Re: Godels Incompleteness and Nonmonotonic Logic
    ... The two incompleteness theorems of Godel refer to what ... > cannot have both completeness and consistency. ... For non-monotonic logics with a perfect weak negation, ... The incompleteness that he probably means is 'the logics are not ...
    (comp.lang.prolog)
  • Re: Godels Incompleteness and Nonmonotonic Logic
    ... The two incompleteness theorems of Godel refer to what ... > cannot have both completeness and consistency. ... For non-monotonic logics with a perfect weak negation, ... The incompleteness that he probably means is 'the logics are not ...
    (sci.logic)
  • Re: completeness what is it exactly
    ... What is completeness exactly? ... and weak completeness but I forgot what the difference was.) ... -- that applies to logics rather than theories. ... language L together with a semantics and a proof theory. ...
    (sci.logic)
  • Re: completeness what is it exactly
    ... What is completeness exactly? ... A theory is descriptively complete with respect to a certain semantics ... propositional calculus and for the first-order predicate calculus. ... The "weak completeness ...
    (sci.logic)