Re: "Theorem" in Mendelson ?

On Thu, 15 Jun 2006 23:21:01 -0400, Question <question@xxxxxxxxxxxxx>
said:
Here are a couple exaples of proofs in propositional logic from
another text that do NOT derive from axioms or tautologies AND that do
not conclude in theorems of propositional logic:

1. A -> (B v C) hypothesis
2. ~B hypothesis
3. ~C hypothesis
4. ~B & ~C 2,3, conjugation
5. ~(B v C) 4, De Morgan
6. ~A 1,5, modus tollens

1. ~A hypothesis
2. A v B hypothesis
3. ~~A v B 2, double negation
4. ~A -> B 3, implication
5. B 1,4, modus ponens

No lines in those proofs are axioms, tautologies, or theorems. They're
from the answers section of "Mathematical Structures for Computer
Science," (Gerstring, 2003, page 655). I could draw from numerous
other texts, but this is time consuming and really pretty silly since
anyone who's taken a logic course should know that proofs do not
necessarily derive from axioms or tautologies or conclude in theorems.

In fact, in many logic texts, one finds two related notions of proof,
one of which does allow you to draw only from axioms. Specifically,
there is the notion of a proof in a formal system S, and the slightly
more complex notion of a proof *from a set of sentences* of the language
of S. Proofs in the latter sense are sometimes referred to as
"deductions" or the like to distinguish them from proofs in the former
sense. The first notion of proof involves only axioms and rules of
inference: a proof in a given system S is a sequence of sentences in the
language of S such that each member of the sequence is either an axiom
of S or follows from previous sentences in the sequence by a rule of
inference. A sentence T is a theorem of S, then, if there is a proof in
S of which T is the last element.

A proof in the second sense, or deduction, in a formal system S, by
contrast, is defined *relative to* a given set A of sentences in the
language of S: a deduction from A in S is a sequence of sentences in
the language of S such that each member of the sequence is either an
axiom, a member of A, or follows from previous sentences in the sequence
by a rule of inference. (This of course is the more general notion, as
every proof in the first sense is a deduction from the empty set.)

What you've got above are proofs in the second sense, i.e., deductions
from the sets comprising the given hypotheses.

.

Relevant Pages
Quantcast