Re: SUO: Theory Query
Chris,
As I have said many times before, I believe that we understand the
technical issues in the same way. But we often disagree about the
choice of terminology for expressing them.
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. But that measure of size,
although useful for many purposes, is definitely misleading for many
other purposes.
For example, the cardinality of the integers is the same as the
cardinality of the prime numbers. But as you go farther and farther
out in the series of integers, the prime numbers become more and more
scarce. So if you use a definition of "bigger" by considering the
limit of the difference in size of the set of primes less than N
compared to the set of integers less than N, you will find that the
limit approaches 0.
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.
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. 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.
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".
Such a distinction seems absolutely ridiculous.
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.
John Sowa