35
$\begingroup$

Completeness is defined as if given $\Sigma\models\Phi$ then $\Sigma\vdash\Phi$. Meaning if for every truth placement $Z$ in $\Sigma$ we would get $T$, then $\Phi$ also would get $T$. If the previous does indeed exists, then we can prove $\Phi$ using the rules in $\Sigma$.

Soundness is defined as: when given that $\Sigma\vdash\Phi$ then $\Sigma\models\Phi$ , which is the opposite.

Can you please explain the basic difference between the two of them ?

Thanks ,Ron

7 Answers 7

66

In brief:

Soundness means that you cannot prove anything that's wrong.

Completeness means that you can prove anything that's right.

In both cases, we are talking about a some fixed system of rules for proof (the one used to define the relation $\vdash$ ).

In more detail: Think of $\Sigma$ as a set of hypotheses, and $\Phi$ as a statement we are trying to prove. When we say $\Sigma \models \Phi$, we are saying that $\Sigma$ logically implies $\Phi$, i.e., in every circumstance in which $\Sigma$ is true, then $\Phi$ is true. Informally, $\Phi$ is "right" given $\Sigma$.

When we say $\Sigma \vdash \Phi$, on the other hand, we must have some set of rules of proof (sometimes called "inference rules") in mind. Usually these rules have the form, "if you start with some particular statements, then you can derive these other statements". If you can derive $\Phi$ starting from $\Sigma$, then we say that $\Sigma \vdash \Phi$, or that $\Phi$ is provable from $\Sigma$.

We are thinking of a proof as something used to convince others, so it's important that the rules for $\vdash$ are mechanical enough so that another person or a computer can check a purported proof (this is different from saying that the other person/computer could create the proof, which we do not require).

Soundness states: $\Sigma \vdash \Phi$ implies $\Sigma \models \Phi$. If you can prove $\Phi$ from $\Sigma$, then $\Phi$ is true given $\Sigma$. Put differently, if $\Phi$ is not true (given $\Sigma$), then you can't prove $\Phi$ from $\Sigma$. Informally: "You can't prove anything that's wrong."

Completeness states: $\Sigma \models \Phi$ imples $\Sigma \vdash \Phi$. If $\Phi$ is true given $\Sigma$, then you can prove $\Phi$ from $\Sigma$. Informally: "You can prove anything that's right."

Ideally, a proof system is both sound and complete.

  • 0
    @Doug I say that because that is the intuition behind the formal definition which you give.2012-02-05
9

From the perspective of trying to write down axioms for first-order logic that satisfy both completeness and soundness, soundness is the easy direction: all you have to do is make sure that all of your axioms are true and that all of your inference rules preserve truth. Completeness is the hard direction: you need to write down strong enough axioms to capture semantic truth, and it's not obvious from the outset that this is even possible in a non-trivial way.

(A trivial way would be to admit all truths as your axioms, but the problem with this logical system is that you can't recognize what counts as a valid proof.)

  • 0
    @Carl: I mean a hypothetical set of axioms describing first-order logic which is capable of proving every semantically true statement but is also capable of proving semantically false statements.2012-09-03
3

Let me characterize soundness and completeness using a silly example. Suppose you are in the business of making machines which make widgets, and suppose that someone comes to you and says "I need a machine which makes red widgets which are either round or square". You go off and build a widget producing machine, and show it to your potential customer. To convert her from a potential to an actual customer, you must convince her of two things: first, that your widget machine will only produce square or round red widgets, and not blue widgets, and second, that your machine will produce both round red and square red widgets, and not only square red ones. If your machine satisfies the first requirement, then it is sound. If you machine satisfies the second requirement, then it is complete.

1

I cannot write comments so I post is as an answer. Matt in his answer changes meaning of "complete" while saying that group theory is incomplete. The OP asked about semantical completeness, Matt writes about negation completeness, that is:

A theory $T$ is negation complete iff for every formula $A$ of $T$, either $T\vdash A$ or $T\vdash\neg A$.

As such group theory is indeed not complete (see Matt's example). But it is still semantically complete, that is whatever that is true in every group (in every structure which is a model of group axioms) is provable from the axioms for groups.

1

Not sure if my following informal understanding is correct:

Imagine I have a box and many crystal balls with color either black or white but not both.

  • Soundness: Every balls inside the box are black, but does not mean all outside balls are white. (Soundness only accepts black but not always)
  • Completeness: Every balls outside the box are white, but does not mean all inside balls are black. (Completeness always accepts black but not only)

By combining Soundness and Completeness, I am sure that: All black balls are inside the box and all white ones are outside

0

You can have a theory $T$ that is sound but incomplete. As an example consider group theory where $T$ are the three properties of groups. Then you cannot prove or disprove $\forall x,y: xy = yx$ since not all groups are abelian but some are.

  • 0
    This is $a$ pointer to the answer $b$y Steve. The $c$oncept of "completeness" for a logic, such as first-or$d$er logic, is sem$a$ntic completeness, and this is the notion defined in the question. It is also common to talk a$b$out a theory being $c$omplete, which me$a$ns negation complete, $b$ut I b$e$li$e$v$e$ that is not what the question is asking about.2012-09-02
0
  • A system of logic is sound if it can prove only true statements.
    • i.e. A system of logic is sound if it cannot prove any false statements.
  • A system of logic is complete if it can prove all true statements.

Source: https://blog.inf.ed.ac.uk/da18/files/2018/03/da18-t7-notes.pdf