What do "soundness" and "completeness" mean?

Question

Soundness and completeness seem to occur in multiple scenarions:

1. In mathematical logic they are used to describe the relationship between syntax and semantics of logic systems.

2. In relational databases,

   The Armstrong's axioms are sound in generating only functional dependencies in the closure of a set of functional dependencies (denoted as $F^{+}$) when applied to that set (denoted as $ F$). They are also complete in that repeated application of these rules will generate all functional dependencies in the closure $F^+$.

3. In Baader's Term rewriting and all that, "soundness" and "completeness" appear multiple times, for example

   The popularity of measure functions into N is in part explained by the following completeness result:

   Lemma 2.3.3 A finitely branching reduction terminates iff there is a monotone embedding into (N, >).

   Proof The "if" direction follows from the soundness of the measure function approach. For the other direction, let —> be a terminating and finitely branching reduction.

I guess there are other examples of using the two words.

What do "soundness" and "completeness" mean?

Do they have different meanings outside mathematical logic?

Do they necessarily mean the two opposite directions of a "if and only if" proposition? If yes, which direction is soundness and which is completeness?

Where do they come from? (Not mathematical logic, since they may have different meanings outside it?)

Thanks.

Answer 1

As Henno Brandsma commented, soundness is a measure of health of the system (does it do anything we would not want it to?), and completeness is a measure of usefullness (could it do anything we may want it to?).

Basically:

• Sound: Anything we might get is something we would want. Nothing bad can happen.

• Complete: Anything we might want is something we could get. Anything good may happen.

So a logic system's rules of syntax are sound when nothing they derive will have invalid semantics and complete when they may derive anything with valid semantics.

So, Armstrong's axiom are sound because they generate only elements of $F^+$ when applied to $F$, and complete because they can generate all elements of $F^+$ when applied to $F$.

Answer 2

Here is my guess, which happens to be somehow similar to some replies and comments, or my misunderstanding.

Completeness and soundness apply (only?) to propositions that look like that given a set $T$ and another set $S$, $S=T$.

$T$ is usually a target, and $S$ is usually the result of a construction with a goal of matching $T$. In that sense, $S \subseteq T$ is soundness, and $S\supseteq T$ is completeness.