Re: SUO: RE: Re: Peirce's MS 514

["John F. Sowa" <sowa@bestweb.net>]

Matthew West wrote:

>I'm glad you posted this, because I have been puzzled by the 
>difference between inference (provability) and entailment 
>for some time.
>
>Below you give the difference by:
>
>>  1. Provability:  p is said to be _provable_ from A in some
>>     logical system L iff there are rules of inference that
>>     allow p to be derived by performing some operations on
>>     the statements of A to generate the statement p.
>> 
>>  2. Entailment:  p is said to be _semantically entailed_ by
>>     A iff in any state of affairs (or universe of discourse,
>>     or possible world) for which all the statements of A are
>>     true, the statement p is also true.
>
>Well I can see some difference, and that entailment should be
>stronger, but I don't really understand the difference.

The basic point is that semantic entailment depends on the
subject matter, but provability depends on your choice of
notation for logic and the rules of inference associated with
it.  Provability can be defined in terms of the syntax of the
notation, but entailment depends on the semantics of whatever
subject is under consideration.

>Presumably there are cases where something can be proved through
>inference, but is not entailed. Could you give an example of
>that please?

There are two terms that are used to characterize inference
methods:

  1. Soundness:  A proof procedure is said to be _sound_
     iff everything that is provable from some starting
     set of statements A is also semantically entailed by A.
     This point is often summarized by saying that a rule of
     inference is sound, if it preserves truth:  if you start
     from true statements all the deductions will also be true.

  2. Completeness:  A proof procedure is said to be _complete_
     iff every statement that is semantically entailed by a
     set of statements A is provable from A by that procedure.
     This point may be summarized by saying that everything
     that is true by semantic entailment is also provable.

First-order logic has the very nice property of being both
sound and complete:  everything that is provable is also true
by semantic entailment, and everything that is semantically
entailed is also provable.

With his famous incompleteness theorem, Kurt Goedel proved that
higher-order logic is not complete:  there are true statements
of arithmetic that are not provable.  He gave some examples
of such statements, including an encoding of a statement of
the following form into an arithmetical proposition:

   "This statement is not provable."

It turns out that statements of this form (in arithmetic)
can be true, but there is no way to prove them.

For most purposes, soundness is extremely desirable, since
one would not like to have a logic whose conclusions are
unreliable.  However, there are some systems of plausible
reasoning (called "nonmonotonic logics") for which inference
rules are allowed that are usually, but not always correct.
Such logics are "unsound", and their conclusions must be
used with caution.  Sometimes, it is better to have plausible
information that is more likely right than wrong; however,
it is wise to be prepared for possible surprises.

John