TransWikia.com

The difference between soundness and completeness

Philosophy Asked by user3741 on February 1, 2021

Is anyone able to articulate the difference between the properties of soundness and completeness insofar as they relate to the validity of the tree test?

3 Answers

Soundness, which states that provability implies validity

Γ ⊢ A    ⇒     Γ ⊨ A

means that the calculus doesn't prove nonsense: If a tree is closed, then that means that the inference also holds semantically; we won't find tree proofs for inferences that aren't actually valid.

Completeness, which states that validity implies provability

Γ ⊨ A    ⇒     Γ ⊢ A

means that the calculus is able to capture all inferences: If an inference holds semantically, then there is a closed tree for it; there will be no inferences that are semantically valid but can't be verified by the tree method.

While every reasonable calculus will be designed to be sound w.r.t. the semantics, completeness is (for FOL at least) a much less trivial and very powerful result: It means that cumbersome semantic considerations about truth in all conceivable structures can be replaced by a mechanical, easily verifiable procedure.

Note, though, that completeness dosen't imply decidability: Completeness means that we will detect all the inferences, but not necessarily all the non-inferences, as such.
In propositional logic, the truth tree test will give you a "yes" (all branches closed) for all inferences and a "no" (at least one branch open) for all non-inferences: Propositional logic is decidable. But in predicate logic, the truth tree test will give you a "yes" for all inferences, a "no" for some non-inferences, but on some non-inferences it will run forever and never come to an answer; and there is no other method that can do better: Predicate logic is undecidable.

Answered by lemontree on February 1, 2021

Taken from Restall's Logic:

  • The tree method is sound. If X ⊢ A then X ⊨ A. That is, if an argument is valid according to trees, it is valid according to truth tables too.
  • The tree method is complete. If X ⊨ A then X ⊢ A. That is, if an argument is valid according to truth tables, it is also valid according to trees.

Answered by Jonathan Scher on February 1, 2021

Some informal definitions first:

Soundness is the property of only being able to prove "true" things.

Completeness is the property of being able to prove all true things.

So a given logical system is sound if and only if the inference rules of the system admit only valid formulas. Or another way, if we start with valid premises, the inference rules do not allow an invalid conclusion to be drawn.

A system is complete if and only if all valid formula can be derived from the axioms and the inference rules. So there are no valid formula that we can't prove.

Truth trees seem to be a method of evaluating a logical proposition (they are new to me, so this is a first glance assessment), however the rules are really just graphical versions of the normal rules of inference, so should be sound as long as the inference rules are. Of course completeness depends on the logical system. So for propositional logic, you're fine.

Answered by Luke Mathieson on February 1, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP