Re: Empty algebras

[Vaughan Pratt <pratt@cs.stanford.edu>]

On 10/23/2011 2:11 PM, Dusko Pavlovic wrote:
>> variable a. To avoid the vacuity and get a falsehood you have to
>>>  quantify out the free variable, as
>>>
>>>     ((all) a. P(a)) -->  ((exists) x. P(x))
> here is a proof of this apparent falsehood:

As long as "true" and "valid" are used interchangeably one is going to
encounter repeated confusions.

I don't know what Steve had in mind in his passage from
P(a) --> (exists) x. P(x)
to
((all) a. P(a)) -->  ((exists) x. P(x))
given that these say different things.  The first says that if P holds
of a it holds of some x, for example x = a.  The second says that if P
is the constantly true predicate then it must hold of some x.

But what does the latter mean?  Steve says it's false in the empty
universe, which is to say (exists) x. TRUE(x) is false there.  We can
confirm this by taking the meaning of this formula in the universe {a_1,
a_2, ...} to be TRUE(a_1) v TRUE(a_2) v ..., which in the empty universe
is the empty disjunction, by convention false.

But could it still be valid, meaning true in all interpretations?  The
possible interpretations of a set V of variables form the set D^V.  When
D = 0, D^V can be thought of as the (intuitionistic) negation of V:
there are interpretations iff there are no variables.

So if there are variables there are no interpretations whence Steve's
formula is vacuously valid, consistent with you (Dusko) having a proof
of the formula.

Conversely no variables implies not valid, consistent with what Steve
seems to have in mind.

In the case of a formula with free variables, there is no question there
are variables.  But this particular formula is a (closed) sentence, so
no free variables, so there exist interpretations, whence the formula is
not valid.

But it is just as reasonable to say there are variables even when they
don't occur free in the formula, e.g. when they occur bound, and the
opposite result then obtains.  The wffs of propositional calculus, L_0,
don't even contain bound variables.  Since this convention seems to
create fewer problems I'm inclined to prefer it.  It justifies Dusko's
proof, while arguing against Steve's position that the formula is not
valid.  There is no question however that the formula is not true, and
given that Steve has not yet made a sharp distinction between truth and
validity, it is perhaps not unreasonable to defend Steve's position by
interpreting him as talking about the truth of
((all) a. P(a)) -->  ((exists) x. P(x))
rather than its validity.

Vaughan


[For admin and other information see: http://www.mta.ca/~cat-dist/ ]