1
$\begingroup$

I have some doubts regarding this concept.

DEF1: Given a formal language L, an interpretation of L is a mechanism that allow the ascription of a truth value to every sentence of L. If E is a set of formulas of L, a model of E is an interpretation of L that makes true every sentence in E. If T is a formal system, a model of T is a model of the set of theorems in T.

DEF2: A formal system is semantically complete when all its valid formulas (that is, formulas that are true under every interpretation of the language of the system) are theorems.

DEF3: A formal system is semantically complete when formulas true in every model of the system are theorems.

The first definition is informal and needs to be formalized differently for each "type" of language under consideration. My question is about DEF2 and DEF3, which to me don't look equivalent.

My question is: which one (between DEF2 and DEF3) is the correct (or more accepted) definition of semantic completeness?

A bit of formalization should make more clear why I think it's not obvious that DEF2 and DEF3 are equivalent:

T = Formal System , L = Language of T , Σ = Sentences of L

I = Set of Possible Interpretations of L

K = Set of Theorems of T

For i ∈ I, S(i) = { s ∈ Σ | i(s) = true}

V = Set of Validities = {s ∈ Σ | i ∈ I ⇒ i(s) = true}

M = Set of Models = {i ∈ I | k ∈ K ⇒ i(k) = true}

DEF2 completeness says V = ∩{S(i) | i ∈ I} ⊆ K

DEF3 completeness says ∩{S(i) | i ∈ M} = ∩{S(i) | (i ∈ I) & (k ∈ K ⇒ i(k) = true)} ⊆ K

It looks like DEF2 takes the intersection of a bigger family of sets.

$\endgroup$
  • 1
    $\begingroup$ What is your definition of "formal system"? Semantic completeness is usually defined for theories (i.e. collections of axioms in a language), and in that case the two definitions looks exactly the same to me $\endgroup$ – TheMadcapLaughs Aug 14 '18 at 10:09
  • $\begingroup$ @TheMadcapLaughs To me a formal system is a formal language plus a deductive apparatus. The same definition I give for theory (although I’ve heard the term theory used with other meanings). I edited the OP to make more clear the question (I hope). $\endgroup$ – Markus Steiner Aug 14 '18 at 12:22
  • $\begingroup$ You are right, there's is a missing part in DEF2: "all its valid formulas" indicates "formulas that are true under every interpretation of the language" that makes true all formulas in T. $\endgroup$ – TheMadcapLaughs Aug 14 '18 at 12:28
  • $\begingroup$ (Notice that a priori the collection $I$ of all possible interpretations is not a set itself: think about groups, which are the models for the theory of groups but their collection is not a set) $\endgroup$ – TheMadcapLaughs Aug 14 '18 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.