What is the difference between Completeness and Soundness in first order logic?

Question

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

Answer 1

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.

Answer 2

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.)

Answer 3

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.

Answer 4

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.