[FOM] Mathematician in the street

Vaughan Pratt pratt at cs.stanford.edu
Fri Aug 28 21:25:58 EDT 2009



Bill Taylor wrote:
> Just a small quibble here, for Vaughn Pratt:
> 
>>             I would first ask the "street mathematician"
>> whether they regarded the concept of set as necessarily tied to
>> a particular formulation of mathematical language or whether sets
>> had an existence of their own independent of language.  
> 
> Isn't there a third plausible option?
> 
> They may take it that the universe of sets does indeed have a fixed
> "Platonic" existence, but that nevertheless any attempt to deal with it 
> necessarily requires one to view them as tied to a particular language.

This may be, but how would you go about arguing necessity here?

> Much in the same way that there is really only one concept of
> "effective computability", or of "a universal machine", or of
> Chaitin's constant; but that the particular implementation of it
> may seem quite different according to the technical substrate,
> which is essentialy unimportant, as they all lead to "the same thing".

Each of those examples admit sharpening with one or another theorem. 
What theorem did you have in mind here?

Any given formulation of the interaction of word and object that 
exhibits any interdependencies between them comes with some limitations, 
otherwise word and object would be independent and it would be a theory 
of noninteraction.  As a simple example, let L be a set of assertions, W 
a set of possible worlds, and |= a binary relation of satisfiability 
defined as a subset of W x L, namely the set of pairs (w,p) such that p 
holds in w.

Now with no other information about the detailed structure of L and W, 
it is conceivable that there could be a proposition which is true in 
every world, or that there could be a world falsifying every 
proposition.  However there could not be both, by the 
irresistible-force-immovable-object paradox if you will.

Are the following two situations similarly incompatible?

(i)  For every pair u,v of worlds there is a world u&v such that for 
every proposition p, p is true in u&v if and only if it is true in both 
u and v.

(ii)  For every pair p,q of propositions there is a proposition pvq such 
that for all worlds w, w satisfies pvq if and only if it satisfies at 
least one of p or q.

The answer is that (i) and (ii) *are* compatible, but together they 
impose the draconian restriction that L and W are both linearly ordered 
by inclusion between the worlds satisfying them and the propositions 
they satisfy, respectively.  No strengthening of that restriction is 
possible because it entails (i) and (ii): u&v can always be taken to be 
the smaller of u or v while pvq likewise can be taken to be the larger 
of p or q.

More startling is that this very unstructured framework of an arbitrary 
binary relation of satisfiability between an arbitrary set of 
propositions and an arbitrary set of possible worlds necessarily admits 
an operation of deductive closure and another operation of class 
closure.   This is because every binary R \subseteq AxB induces a Galois 
connection between the power sets of A and B, whose two polarities 
constitute the two closure operations.  We know that this is true for 
equational logic, for which deductive closure of a set of equations is 
its congruence closure while class closure is HSP, Birkhoff's theorem. 
But there is nothing special about equational logic in that regard: 
*every* relation of satisfiability comes with such a pair of closure 
operations.

Yet another example is that if L is finitary then W is compact, both in 
a sense suitably general for this situation.  (Due to Gordon 
Plotkin--the generality part, that is.)

I don't know if this answers your question at all, but it does make the 
point that ostensibly simple interactions between word and object such 
as the requirement of a two-valued binary relation of satisfiability can 
have nontrivial consequences imposing possibly unexpected limits on 
one's freedom to organize word and object.


More information about the FOM mailing list