1
$\begingroup$

Is this accurate:

-Completeness is a property of a proof system / logical system. It says that if $\Gamma \vDash \phi \implies \Gamma \vdash \phi$ holds, the proof system is complete. In other words, "If we can show something is satisfied in all interpretations, then we can also write a syntactic proof of it." Otherwise it might be possible for something to be true but unreachable from our inference rules.

-Soundness is a property of a proof system / logical system. It says that if $\Gamma \vdash \phi \implies \Gamma \vDash \phi$ holds, the proof system is sound. In other words, "If we can write a proof of something, we can also show that it is true." Otherwise it might be possible to infer something false even if all our premises are true.

-Consistency is a property of a theory, or a set of assumptions / definitions that work with the logic. A theory is consistent iff it is not possible to prove $p \land \lnot p$ for some statement $p$. The underlying logic system can still be sound and complete, but possibly give you false conclusions if your assumptions are inconsistent.

-A statement is satisfied if it evaluates to true under some interpretation.

-A statement is valid if it is always satisfied under every interpretation. It's unsatisfiable if it is never satisfied under any interpretation. It's contingent if it's sometimes satisfied, sometimes not, depending on the interpretation.

$\endgroup$
1
$\begingroup$

This is definitely on the right track, but there are some things worth noting.

Completeness is a property of a proof system / logical system. It says that if Γ⊨𝜙⟹Γ⊢𝜙 holds, the proof system is complete. In other words, "If we can show something is satisfied in all interpretations, then we can also write a syntactic proof of it." Otherwise it might be possible for something to be true but unreachable from our inference rules.

That's an accurate assessment of what completeness is and what it's a property of. But in the last sentence, replace true' with 'true in all interpreations that satisfy $\Gamma$'.

Soundness is a property of a proof system / logical system. It says that if Γ⊢𝜙⟹Γ⊨𝜙 holds, the proof system is sound. In other words, "If we can write a proof of something, we can also show that it is true." Otherwise it might be possible to infer something false even if all our premises are true.

Ditto. Replace false with 'false in some interpretation that satisfies $\Gamma$' and true with 'true in all interpretations that satisfy $\Gamma$'.

Consistency is a property of a theory, or a set of assumptions / definitions that work with the logic. A theory is consistent iff it is not possible to prove 𝑝∧¬𝑝 for some statement 𝑝. The underlying logic system can still be sound and complete, but possibly give you false conclusions if your assumptions are inconsistent.

This is syntactic consistency, and is a correct definition (and you're right that it is a property of $\Gamma$ and not necessarily the underlying logic, in which the logical axioms are generally already shown to be consistent). We have to be careful about what 'false conclusions' means. (Non-logical) axioms can be consistent, but also false in a particular natural interpretation. For instance, most interesting first order theories (e.g. PA) are incomplete in the sense that there are sentences that they can't prove or refute. In this case it would be consistent to take either the sentence or its negation as an additional axiom, but only one of these can be true in a given interpretation (for instance, in the case of PA, the interpretation we might care about is $\mathbb N$.)

When we consider an inconsistent $\Gamma,$ what happens on the semantic side is that there are no interpretations at all that satisfy $\Gamma$ (provided that the deductive system is sound).

A statement is satisfied if it evaluates to true under some interpretation.

Either 'a statement is satisfiable if it is true under some interpretation' or 'a statement is satisfied in a given interpretation if it is true in that interpretation.'

A statement is valid if it is always satisfied under every interpretation. It's unsatisfiable if it is never satisfied under any interpretation. It's contingent if it's sometimes satisfied, sometimes not, depending on the interpretation.

Yep.

$\endgroup$
  • $\begingroup$ Can you explain about semantic and syntactic consistency and what you mean by "incomplete"? $\endgroup$ – user647147 Feb 24 at 5:05
  • $\begingroup$ syntactic means what you say: you cannot prove $p$ and $\lnot p$ from $\Gamma.$ Semantic consistency means there exists an interpretation that satisfies $\Gamma$. One way to interpret the completeness and soundness theorems is that completeness means syntactic consistency implies semantic, and soundness means semantic implies syntactic. By 'incomplete' I mean that there is a sentence $\phi$ such that neither $\Gamma\vdash \phi$ nor $\Gamma\vdash \lnot \phi.$ Note this is a syntactic notion (this can be confusing: it is quite different from 'complete' in the sense of the completeness theorem.) $\endgroup$ – spaceisdarkgreen Feb 24 at 5:36
  • $\begingroup$ Why is $\Gamma \vDash \varphi$ more important than "true"? $\endgroup$ – user647147 Feb 24 at 6:08
  • $\begingroup$ @user647147 Well, what does "true" mean? Truth is relative to a given interpretation, and it's not always clear that there's one particular interpretation we should favor. $\endgroup$ – spaceisdarkgreen Feb 24 at 6:53

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.