Re: Tautologies Then and Now

From: Stephen Harris (cyberguard1048-usenet_at_yahoo.com)
Date: 12/13/04 

Date: Mon, 13 Dec 2004 14:22:01 GMT

"Chris Menzel" <cmenzel@remove-this.tamu.edu> wrote in message
news:slrncrqso4.6h7.cmenzel@philebus.tamu.edu...
> On Mon, 13 Dec 2004 00:44:52 GMT, Stephen Harris said:
>> ...
>> I could have used Modal logic as another counter example; where the
>> term tautology is applied outside of propositional logic.
>
> Hm, nothing I saw in what you quoted supports this claim. Did I miss a
> quote where the validities of propositional modal logic are referred to
> as "tautologies" by someone?
>
> As you note, there is a limited use for truth tables -- of a sort -- in
> the case of the propositional modal logic S5, but this is directly
> analogous to their limited use in Monadic Predicate Logic (indeed, in a
> certain sense, it's identical). But because the modal operators
> function semantically as quantifiers over "possible worlds", a general
> truth table style semantics for propositional modal logic is not
> possible.
>

SH: Yes. Also I have become quite wary of using the word general.

> Chris Menzel

>SH wrote:
>> I could have used Modal logic as another counter example; where the
>> term tautology is applied outside of propositional logic.

Because Ed Zalta acknowledged your sage advice, I regarded him as a
good source. I didn't say that there was no relationship to propositional
logic when I mentioned sentential modal logic. I said that it was distinct
from propositional logic and that the term "tautological" comes up normally.
He mentions two approaches, the first uses infinity, and appears to have
three columns in the truth table which is enought to distinguish it IMO. The
second was finite (Enderton) and actually seemed closer to predicate logic,
but involves a different definition of tautology, meaning the term is
applied
normally outside of propositional logic with a different definition also.

http://mally.stanford.edu/notes.pdf by Ed Zalta (some of pages 18-23)

"The problem we face first is that we want to distinguish the tautologies
in some way from the rest of the formulas that are valid. We can't just
use the notion `true at every world in every model', for that is just
the notion of validity. So to prove that the tautologies, as a class,
are valid, we have to distinguish them in some way from the other valid
formulas. The basic idea we want to capture is that the tautologies have
the same form as tautologies in propositional logic. ...
[SH: This establishes their relatedness, IMO, now onto differences.]
...
Remark: These examples and exercises show that our definition of a
tautology allows us to prove that certain formulas are tautologies.
The definition is reasonably simple and serves us well in subsequent
work. But, for arbitrary @, there is no mechanical way of finding
arguments such as the one in the above Example that establish that @
is a tautology if indeed it is. Moreover, you can't mechanically use
the definition to show, for a given tautology, that indeed it is a
tautology, since you can't check every assignment f . Even if we start
with a language based on the set Omega = {p_1}, it would take a very
long time to even specify a basic assignment of the quasi-atomic
subformulas (since, as we have seen, Omega* will be an infinite set).

So the definition of `tautology' per se doesn't offer a mechanical
procedure to discover, for a given @, whether or not @ is a tautology,
since strictly speaking, you would have to check an infinite number of
assignments (none of which you can even specify completely).
[SH: This is the basics of modal logic and it keeps referring to tautology.]

** But we know from work in propositional logic that the truth table
method gives us a mechanical procedure by which we can discover
whether or not a given @ is a tautology. Have we lost anything in the
move to modal logic? Actually, we haven't, for there is a way to
construct such a decision procedure that tests for tautologyhood. **
[SH: This does not appear to be exactly the same as TT in prop. logic.]

Such a procedure will be described in the Digression that follows
(disinterested readers, or readers who don't wish to interrupt the train of
development of the concepts, may skip directly ahead to (14) ).
[SH: skipping most of the Digression which starts on page 20.]Digression:

... "Consequently, if for every i, each member f of F_i is such that
f (@) = T (i.e., if the value T appears in every row of the final
column of the truth table), then @ is a tautology. This is our
mechanical procedure for checking whether @ is a tautology. The
reader should check that T does appear in every row under the
column headed by @ in the above example.

Of course, this intuitive description of a decision procedure depends
on our having a precise way to delineate of the truth-functionally
relevant subformulas of @, and on a proof that whenever f and f' agree
on the relevant quasi-atomic formulas in @, then they agree on @. The
latter shall be an exercise." ...
[SH: This method seems different to me than the construction of the
propositional logic TT. There seems more to it and more column(s).]

Alternative Section2: Tautologies are Valid (following Enderton)

In some developments of propositional logic (Enderton's, for example),
the notion of tautology is: @ is a tautology iff @ is true in all the
extensions of basic assignments of its atomic subformulas. The difference
here is that instead of being defined for all the atomic formulas in the
language, basic assignments f* are defined relative to arbitrary sets of
atomic formulas.

The basic assignments for a given formula @ will be functions that assign
truth values to every member of the set of atomic subformulas in @. An
extended assignment f is then defined relative to a basic assignment f*,
and extends f* to all the formulas that can be constructed out of the set
of atomic formulas over which f* is defined. So, for a given formula @,
f extends a given basic assignment f* by being defined on all the formulas
that can be constructed out of the set of atomic subformulas in @. Such fs
will therefore be defined on all of the subformulas in @, including @
itself. The definition of a tautology, then, is: @ is a tautology iff for
every basic assignment f* (of the atomic subformulas in @), the extended
assignment f (based on f*) assigns @ the value T .

One advantage of doing things this way is that for any given formula
@, there will be only a finite number of basic assignments, since there
will always be a finite number of atomic subformulas in @. Whenever
there are n atomic subformulas of @, there will be 2^n basic assignment
functions. Thus, our decision procedure for determining whether an
arbitrary @ is a tautology will simply be: check all the basic
assignments f* to see whether f assigns @ the value T .

In this section, we redevelop the definitions of the previous section
for those readers who prefer Enderton's definition of tautology. The
twist is that we have to define basic assignments relative to a given
set of quasi-atomic formulas. So for any given @, the basic assignments
f* will be defined on the set of quasi-atomic subformulas in @. Then we
extend those basic assignments to total assignments defined on all the
formulas constructible from such sets of quasi-atomics (these will there-
fore be defined for the subformulas of @ and @ itself). To accomplish all
of this, we need to define the notions of subformula, quasi-atomic formula,
and basic truth assignment to a set of quasi-atomic formulas, and then,
finally, extended assignment, before we can define the notion of a
tautology. Readers who are not familiar with Enderton's method, or who
have little interest in seeing how the method is adapted to our modal
setting, should simply skip ahead to section3. ....

Remark: Not only does our definition allow us to prove that a given
formula @ is a tautology, it gives us a decision procedure for
determining, for an arbitrary @, whether or not @ is a tautology. The
set of quasi-atomic subformulas of @ (Omega*_@) is finite. Suppose it
has n members. Then we have only to check 2^n basic assignments f* and
determine, in each case, whether f assigns @ the value T . So our modal
logic has not lost any of the special status that propositional logic has
with regard to the tautologies. **Indeed, there is a simple way to show that
tautologies in our modal language correspond with tautologies in
propositional language."**
[SH: This second method seems closer to propositional logic.]

SH: This is my evidence that "tautology" is normally used in Modal logic,
which is outside of sentential logic, which disuptes paul's contention.

paul wrote:
>>original) ... "that support what I said --
>>that the term "tautology" is not applied outside propositional logic"

which paul revised to:
>new) "My question is why is "tautology"
> not normally used outside sentential logic? There must be a reason."

Chris wrote:
> Hm, nothing I saw in what you quoted supports this claim. Did I miss a
> quote where the validities of propositional modal logic are referred to
> as "tautologies" by someone?

Ed Zalta wrote in introducing the basics of modal logic (91 pages!):
"Basic Concepts in Modal Logic" by Edward N. Zalta

"The problem we face first is that we want to distinguish the tautologies
in some way from the rest of the formulas that are valid. We can't just
use the notion `true at every world in every model', for that is just
the notion of validity. So to prove that the tautologies, as a class,
are valid, we have to distinguish them in some way from the other valid
formulas. The basic idea we want to capture is that the tautologies have
the same form as tautologies in propositional logic. ... Ed also wrote:

"I am also indebted to Chris Menzel, Kees van Deemter, Nathan Tawil,
Greg O'Hair, and Peter Apostoli. Finally, I am indebted to the Center
for the Study of Language and Information, which has provided me with
offce space and and various other kinds of support over the past years."
[SH: I didn't think I had to quote this again since you had already read
it.]

SH wrote: Did Ed falsely claim you reviewed his draft of this paper?! :-)
Sometimes I leave the living room to get something from the bathroom
and by the time I get to the bedroom, I've forgotten my mission.
Really, I'm just kidding around with this. It was over 9 years ago, besides
maybe he ignored your red ink! In reading Ed's description, Modal TT
may not be exactly general, but requires some finesse. I had a little
trouble
with the paper. If propositional logic TT are quite mechanical and general,
and Modal TT are less so, then that is a distinction between them, which
did not prevent the usage of tautology several times in Zalta's paper.

Best regards,
Stephen