[FOM] S5 models & RE sets
rgheck at brown.edu
Mon Jun 7 17:40:53 EDT 2010
On 06/04/2010 12:26 AM, Michael Carroll wrote:
> I've formulated a question I'm having trouble answering. I was hoping an
> FOMer might help.
> Take the modal propositional system S5 and Kripke models for it. Say a model
> M verifies a formula A if A is true at all possible worlds in M. Say M
> falsifies A if A is false at all. Note that in general A may be neither
> verified nor falsified by M. Let T be the set of formulas verified by M, and
> F the set falsified. Then T and F are disjoint, and for some models M there
> are formulas which are in neither T nor F.
> Introduce an appropriate coding from the formulas to the integers. Let T*
> and F* be the sets of integers corresponding to the sets T and F for a given
> Are T* and F* recursively separable, or effectively inseparable, or what?
Just a few thoughts, as the question, as stated, doesn't seem clear
enough to be answered.
First, I presume we are talking about some fixed model M. For some
models M, the problem will be easier than in other cases, e.g., if M is
a model with one world. Of course, even in saying that, I am assuming
that the model itself is "given" in some fairly simple way, in
particular, that set of formulae true at the sole world of the model is,
say, recursive. But even then, I don't know what the answer is: What is
the complexity of the set of formulae true at the sole world of this
model, assuming the set of sentence-letters true at that world is
recursive? p.r.? finite?
The next case to consider would be finite models. Then we could look at
infinite models, but here, the question how the model is "given" will
become more complicated and, I'd suppose, important.
This does not really address the question asked, but that has me a bit
puzzled, too. I could be wrong about this, but it looks to me as if F*
is a primitive recursive function of T*, since F* simply contains the
negations of the things in T* (and the results of eliminating double
negations). I don't know if that means anything as to the question, though.
Richard G Heck Jr
Romeo Elton Professor of Natural Theology
More information about the FOM