Re: SUO: Theory Query
> As I have said many times before, I believe that we understand the
> technical issues in the same way.
Largely, yes, that is true.
> But we often disagree about the choice of terminology for expressing
> them.
Yes, sorry. I am pathologically peevish. How old do I have to be
before that turns to outright curmudgeonliness? Pat??
> To respond to your quibbles:
>
> JS> The set of all subsets of FOL sentences is a much bigger lattice.
> > What you need to do is to take the quotient space generated by the
> > provability relation |- of FOL (or the semantic entailment operator |=
> > which is equivalent to provability for FOL).
>
> CM> Actually, these lattices are the same size, so long as you've got at
> > least denumerably many predicates or constants in your language.
>
> Of course, both have the cardinality aleph0.
I'm sure you meant to say aleph_1 (and were assuming the continuum
hypothesis... ;-)
Also, we've covered this before (http://suo.iee.org/email/msg01744.html),
but I don't think that a Lindenbaum lattice is what you have in mind, as
that is just a partition of *sentences* -- equivalently, finite sets of
sentences -- into equivalence classes. Moreover, I don't think your
quotient space is what you want either. I think the nodes you want in
your lattice are *deductively closed* sets of sentences. The relation
that gives rise to your lattice is then simply the subset relation.
> But that measure of size, although useful for many purposes, is
> definitely misleading for many other purposes.
Of course.
> By a similar argument, you can define an ordering of the elements
> of the two lattices and look at the limits. By such an ordering,
> you can show that the limit of the ratio of the number of elements
> in the Lindenbaum lattice to the number of elements in the lattice
> of all subsets of formulas not only approaches zero -- it is zero
> for every theory in the Lindenbaum lattice.
You lost me here, but I'll take your word for it.
> I will, however, acknowledge that the term "bigger" is only acceptable
> in informal discussions, and in any formal presentation, I would be
> obligated to define what I mean by "bigger".
>
> > You mean "logical truths". Tautologies are the logical truths of
> > propositional logic.
>
> Usage varies among logicians.
Not in any of my texts.
> I agree most professional logicians
> today prefer to restrict the term to "the logical truths of
> propositional logic" and use the term "logical truth" for predicate
> logic. But earlier usage applied the term "tautology" to both.
>
> I have not seen any convincing reason why anyone should restrict the
> term in that way. And there are very good reasons why one should not
> make that distinction. For example,
>
> ~(p & ~p)
>
> is a tautology by your definition. And most current logicians would
> allow any substitution instance of a tautology to be called a tautology.
Correct.
> Therefore, the following formula would be called a tautology:
>
> ~((Ex)Q(x) & ~((Ex)Q(x))
>
> But a trivial reformulation of that formula by substituting the
> ~(Ax)~ for (Ex) and converting to prenex form would produce:
>
> (Ax)(Q(x) -> Q(x))
>
> which would not be considered a tautology, but a "logical truth
> of predicate calculus".
That is true.
> Such a distinction seems absolutely ridiculous.
Your argument might hold water if every logical truth were a matter of
doing a quantifier exchange on some tautology and converting it to
prenex. But it ain't so! (Simple example: (x)Fx -> Fa.) And anyway,
conversion to prenex is itself justified by the axioms of predicate
logic.
> I therefore prefer to use the same term "tautology" for the logical
> truths of both propositional and predicate calculus. And I would say
> that any attempt to avoid using the term for predicate calculus is
> frivolous, confusing, and not worthy of a serious logician.
Ha! Powerful rhetoric, John! You must sense your store of arguments is
running low! :-) Rhetoric or no, the distinction is sound and
substantive. Tautologies are logical truths that depend for their truth
value ultimately only on the meanings of their propositional
connectives. (This can be made as precise as you please.) Logical
truths include those that depend in addition upon on the meanings of
their quantifiers. Note also that the distinction is actually appealed
to in many standard presentations of predicate logic: rather than
providing an axiomatization for the propositional part, some logicians
simply include "all tautologies" as axioms.
Peevishly yours,
-chris