ONT Re: Model Theory
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
John Collier wrote (JC):
Jon Awbrey wrote (JA):
Let's look at that example again. The first time that I read it,
I thought that you were merely weakening the inference rule, but
now I'm not so sure that's what you intended. I did not want to
spend this kind of time on these kinds of proof systems, since
everything is so much clearer in a Peircean framework, but let
me retrieve C&K's text as being the clearest of this brand.
(I will change the Attic character @S@ to a Latin L.)
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
| 1.2 Model Theory for Sentential Logic (cont.)
|
| Let us now introduce the notion of a formal deduction in our logic $S$.
|
| The 'Rule of Detachment' (or 'Modus Ponens') states:
|
| From r and (r => q) infer q.
|
| We say that q is 'inferred' from r, s by detachment
| iff s is the sentence (r => q).
|
| Now consider a finite or infinite set L of $S$.
|
| A sentence q is 'deducible' from L, in symbols, L |- q,
| iff there is a finite sequence r_0, r_1, ..., r_n of sentences
| such that q = r_n, and each sentence r_m is either a tautology,
| belongs to L, or is inferred from two earlier sentences of the
| sequence by detachment. The sequence r_0, r_1, ..., r_n is called
| a 'deduction' of q from L. Note that q is deducible from the
| empty set of sentences if and only if q is a tautology.
|
| We shall say that L is 'inconsistent'
| iff we have L |- q for all sentences q.
| Otherwise, we say that L is 'consistent'.
|
| Finally, we say that L is 'maximal consistent'
| iff L is consistent, but the only consistent
| set of sentences which includes L is L itself.
| The proposition below contains facts which
| can be found in most elementary logic texts.
|
| Proposition 1.2.8 [Deductive Closure Properties of Consistent Sets]
|
| 1. If L is consistent and L is the set
| of all sentences deducible from L,
| then L is consistent.
|
| 2. If L is maximal consistent and L |- q,
| then q is an element of the set L.
|
| 3. L is inconsistent if and only if
| L |- (S & (~S)) for any S in $S$.
|
| 4. Deduction Theorem.
| If L |_| {r} |- q, then L |- (r => q).
|
| C.C. Chang & H.J. Keisler, 'Model Theory',
| North-Holland, Amsterdam, Netherlands, 1973,
| pages 9-10.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
JA, citing EFT:
| 4.7 Consistency
|
| The syntactic concept |- of derivability corresponds to
| the semantic concept |= of consequence. As a syntactic
| counterpart to satisfiability we define the concept of
| 'consistency'.
|
| 4.7.1 Definition.
|
| a. Q is 'consistent' (written: Con Q) if and only if
| there is no formula q such that Q |- q and Q |- ~q.
|
| b. Q is 'inconsistent' (written: Inc Q) if and only if
| Q is not consistent (that is, if there is a formula q
| such that Q |- q and Q |- ~q).
|
| First we show that from an inconsistent set one can derive any formula.
|
| 4.7.2 Lemma. For a set of formulas Q the following are equivalent:
|
| a. Inc Q.
| b. For all q, Q |- q.
|
| EFT, page 72.
|
| Ebbinghaus, H.-D., Flum, J., & Thomas, W.,
|'Mathematical Logic',
| Springer-Verlag, New York, NY, 1984
JC: Consider the following system: sentential logic
restricted to conjunction and disjunction, but with
all atomic sentences (informally, a, ~a, b, ~b, ...)
as axioms. Call it U. U is not a theory, technically,
but this doesn't bother Zeus.
JC: Now, U is intuitively inconsistent, but no inconsistency
can be derived in U. However all sentences of U can be
derived in U.
If you are given modus ponens and all tautologies, as in C&K,
then L = {a, ~a} |- (a & ~a).
This is so because ((a & ~a) => (a & ~a)) is a tautology, but this is
truth-table equivalent to (a => (~a => (a & ~a))), and so two uses of
detachment will do the trick, that is, give us the proof of (a & ~a).
Jon Awbrey
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤