# Who's afraid of impossible worlds?

12 17 April 2012 12:56PM

In order to clarify the semantics of paraconsistent and relevance logics, we need to make a detour into impossible worlds - a fruitful detour opening up fun new vistas. Note that this is an intuitive introduction to the subject, and logic is probably the area of mathematics where it is the most dangerous to rely on your intuition; this is no substitute for rigorously going through the formal definitions. With that proviso in mind, let's get cracking.

## Possible worlds: the meaning of necessity

Modal logics were developed around the concept of necessity and possibility. They do this with two extra operators: the necessity operator □, and possibility operator ◊. The sentence □A is taken to mean "it is necessary that A" and ◊A means "it is possible that A". The two operators are dual to each other – thus "it is necessary that A" is the same as "it not possible that not-A" (in symbols: □A ↔ ¬◊¬A). A few intuitive axioms then lead to an elegant theory.

There was just one problem: early modal logicians didn't have a clue what they were talking about. They had the syntax, the symbols, the formal rules, but they didn't have the semantics, the models, the meanings of their symbols.

To see the trouble they had, imagine someone tossing a coin and covering it with their hand. Call wH the world in which it comes out heads and wT the world in which it comes out, you guessed it, tails. Now, is the coin necessarily heads? Is it possibly heads?

Intuitively, the answers should be no and yes. But this causes a problem. We may be in the world wH. So if we agree that the coin is not necessarily heads, then it is not necessarily heads even though it is actually heads (forget your Bayescraft here and start thinking like a logician). Similarly, in wT, the coin is in actuality tails yet it is possibly heads.

Saul Kripke found the breakthrough: necessity and possibility are not about individual worlds, but about collections of possible worlds, and relationships between them. In this case, there is a indistinguishability relationship between wT and wH, because we can't (currently) tell them apart.

Because of this relationship, the statement A:"the coin is heads" is possible in both wT and wH. The rule is that a statement is possible in world w if it is true in at least one world that is related to w. For w=wH, ◊A is true because A is true in wH and wH is related to itself. Similarly, for w=wT, ◊A is true because A is true in wH and wH is related to wT.

Conversely B:"the coin is heads or the coin is tails" is necessary in both wT and wH: here the rule is that a statement is necessary in world w if it is true in all worlds related to w. wT and ware related only to each other through the indistinguishability relationship, and B is true in both of them, so □B is also true in both of them. However □A is not true in either wT or wH, because both those worlds are related to wT and A is false in wT.

This idea was formalised as a Kripke structure: a set W of worlds, a binary relationship R between some of the elements of W, and a rule that assigned the truth and falsity of statements in any particular world w. R is called the accessibility relationship (it need not be indistinguishability): wRv means that world v is 'accessible' from world w, and necessity and possibility are define, via R, as above.

As an extra treat for the less wrong crowd, it should be noted that Kripke structures are used in the semantics of common knowledge, key to the all-important Aumann agreement theorem.

## Impossible worlds: when necessary truth is not true, necessarily

It should be noted that all the worlds in W are possible worlds: the (classical) laws of logic apply. Hence every tautology is true in every world in W, and every contradiction is false. In standard ('normal') modal logic, there is a necessitation requirement: if A is a tautology, then □A ("it is necessary that A") is true in every world.

However, what if this were not the case? What if we added the requirement that □A not be true? Formally and symbolically, this seems a perfectly respectable thing to ask for. But can we come up with a model for this logic?

Not by using possible worlds, of course: since A is always true, we won't get very far. But we can enlarge our set W to also include impossible worlds: worlds where the laws of logic don't apply. Impossible worlds have truth values assigned to statements, but they don't need to be consistent or coherent ("Socrates is a man", "all men are mortal" and "Socrates is immortal" could all be true).

Now assume there is a world w', where A is not labelled true (since A is a tautology, w' must be an impossible world). Also assume that w' is accessible from possible world w (hence wRw'). Then w is a perfectly respectable possible world, with A true in it; however, □A is not true in w, because it has an accessible world (w') where A isn't true. Voila!

This seems like a cheap trick – a hack to build a model for a quirky odd logic that doesn't feel particularly intuitive anyway. But there are more things to be done with impossible worlds...

## Some possibilities are more possible than others

Lewis built on the possible world idea to construct a theory of counterfactuals. Assume that the world is as we know it, and consider the two statements:

• A: If the Titanic didn't hit an iceberg, then it didn't sink on its maiden voyage.
• B: If the Titanic didn't hit an iceberg, then it was elected Pope in the controversial Martian election of 58 BC.

Both of these statements are true in our world: we can show that the antecedent is contradicted (because the Titanic actually did hit an iceberg), and then imply anything. Nevertheless, there is a strong intuitive sense in which A is 'more true' than B. The consequent of A is 'less extraordinary' than that of B, and seems to derive more directly from the antecedent. A seems at least counterfactually truer than B.

We can't use the Kripke accessibility relationship to encode this: R is a simple yes or no binary, with no gradation. Lewis suggested that we instead use a measure that encodes relative distance between possible worlds, some way of saying that world v is closer to w than u is. Some way of saying that a world where the English invented chocolate is less distant from us than a world in which all the English are made of chocolate.

With this distance, we can rigorously state whether A and B are true as counterfactual statements. Define C:"the Titanic didn't hit an iceberg", D:"the Titanic didn't sink on its maiden voyage" and E:"the Titanic was elected Pope in the controversial Martian election of 58 BC."

So, how shall we encode "C counterfactually implies D (in our world)"? Well, this could be true if C were false in every possible world; but no such luck. Otherwise, we could look for worlds where C is true and D is also true; yes, but there are also possible worlds where C is true but D is false (such as the world where the Titanic swerved to avoid the iceberg only to get sunk by the Nautilus). This is where the distance between worlds comes in: we say that "C counterfactually implies D (in our world)" if D is true in w, where w is the closest world to our own where C is true. For any intuitive distance measure, it does seem quite likely that C does counterfactually imply D (in our world): most ships cross the Atlantic safely, so if the Titanic hadn't hit an iceberg, it should have done so as well.

Basically a counterfactual is true if the consequent is true in the least weird world where the antecedent is true. A similar approach shows that "C counterfactually implies E (in our world)" is false. Unless we have made some very peculiar choices for our distance measure, the closest world to us in which the Titanic didn't hit an iceberg, is not one in which a large metal contraption was elected Pope on an uninhabited planet thousands of years before it was even built.

So far, this seems pretty intuitive; but what about this "distance measure" between possible worlds, which seems to be doing all the work? Where does that come from? Well, that, of course, is left as an exercise to the interested reader. By which I mean the problem is unsolved. But there is progress: we started with an unsolved informal problem (what is a counterfactual) and replaced it with an unsolved formal problem (how to specify the relative distance between possible worlds). Things are looking up!

## Some impossibilities are less impossible than others

It should be noted that in the previous section, the fact that the worlds were logically consistent was never used. This immediately suggests we can extend the setup to include impossible worlds as well. This was Edwin Mares's idea, and it allowed him to construct models for the logic of paradox.

All that we need is our magical "relative distance between worlds" measure, as before, except we now measure relative distance to impossible worlds as well. With that, we can start talking about the truths of counterpossible statements - conditional statements where the antecedent is contradictory. Assume for instance that both Euclidean geometry and Peano arithmetic are true, and consider:

• A: the existence of an equilateral triangle with a right angle counterpossibly implies the existence of a triangle whose angles sum up to 270 degrees.
• B: the existence of an equilateral triangle with a right angle counterpossibly implies the existence of many even primes.

For many intuitive distance-between-worlds measures, A is true in our world and B is false. This is, for instance, the case for some distance measures that penalise doubly impossible worlds (worlds where Euclidean geometry and Peano arithmetic both have contradictions) more than singly impossible worlds (where only one of the theories have contradictions). Again, the informal mystery about counterpossibles is reduced to the formal problem of specifying this distance measure between worlds.

Sort By: Best
Comment author: 17 April 2012 10:31:54PM 5 points [-]

But there is progress: we started with an unsolved informal problem (what is a counterfactual) and replaced it with an unsolved formal problem (how to specify the relative distance between possible worlds).

I wouldn't call the latter a formal problem, since there is no formal criteria in the problem statement for judging what constitutes a correct solution. Intuition and philosophy are still all we have to go on.

There is still progress, but I think a better way of putting it is that we have found one possible way in which the original problem might be solved.

Comment author: 18 April 2012 03:55:27AM 2 points [-]

We say that "C counterfactually implies D (in our world)" if D is true in w, where w is the closest world to our own where C is true.

This has a somewhat subtle error in it: C []-> D is true in w iff there is no world in which C is true and D is false that is closer to w than every world in which C is true and D is true. In other words, C []-> D is true in w iff for every world in which C is true and D is false, there is a closer world in which both C and D are true. (At least, I think those two statements are equivalent.)

Your definition requires that there be a closest world to w in which C is true. But there is no guarantee that there is such a world. There might be a continuum of worlds approaching w but no closest one.

Comment author: 18 April 2012 08:07:24AM 0 points [-]

My post is an "intuitive introduction to the subject", which is "no substitute for rigorously going through the formal definitions" :-) But yeah, it can get complicated, especially as the "distance measure" need not be a metric at all.

Comment author: 17 April 2012 09:31:41PM *  3 points [-]

What does it do?

What goal is all this intended to accomplish?

If I try to build an AI that lacks all this stuff, what sort of real-world task can it not solve?

Comment author: 18 April 2012 04:40:11AM 4 points [-]

When you ask, "What does it do?" what is "it" referring to? Modal logic? Counterfactuals? Stuart's specific application of modal logic and counterfactuals?

I'll guess that you mean to ask about the whole apparatus of modal logic. Aside from Stuart's stated goals -- having to do with relevance and reactions to explosion and certain paradoxes, like the liar -- modal logics have been used to study provability, knowledge and belief, moral obligation, tense, and action, just to name a few. You might also take a look at Section 3 of Benthem's book Modal Logic for Open Minds for some applications of modal logic.

Counterfactuals have found special application in causal inference. Lewis' approach to counterfactuals provides a semantics for the Neyman-Rubin approach to causal inference. (See, for more detail, Glymour's discussion piece following Holland's well-known 1986 paper on causal inference.) Pearl takes it a step further by proving that the do() calculus is equivalent to Rubin's and to Lewis' approaches.

Your last question is a whole lot harder to answer. Maybe all of these things can be implemented in some way that does not require any modal logic or anything formally equivalent to modal logic. One might try a non-counterfactual approach to causal inference, like that suggested by Dawid, for example. (However, Dawid's approach is not equivalent to the Neyman-Rubin-Lewis-Pearl approach: they don't always endorse the same inferences.) I don't know enough about AI approaches to the other problems to say whether or not modal logics have serious competitors. Maybe you could point me to some further reading(s)?

Comment author: 17 April 2012 10:15:04PM 7 points [-]

Stuart explained his motivations in Paraconsistency and relevance: avoid logical explosions:

For Less Wrong, the best use of relevance logic would be to articulate counterfactuals without falling into the Löbian/self-confirming trap and blowing up.

Comment author: 18 April 2012 08:16:01AM 3 points [-]

Wot Wei_Dai said.

I personally think that taking a probabilistic approach to logical truths (and using P(A|B) rather than B→A) is going to be the best way of fixing the Loebian and logical uncertainty problems of UDT. But before doing this, I thought I should at least glance at the work that logicians have been doing, and put it out on Less Wrong, in case someone gets inspired brainwaves from it.

If I try to build an AI that lacks all this stuff, what sort of real-world task can it not solve?

Paraconsistent logics are weaker than classical logics, so an AI with this has less stuff than a classical AI, so it can solve less. The hope is that it would still be able to solve a lot, and wouldn't be able to solve the problematic Loebian spurious proofs.

Comment author: 18 April 2012 11:59:35AM 1 point [-]

... is going to be the best way of fixing the Loebian and logical uncertainty problems of UDT

To repeat my complaint here, the problems with UDT are conundrums, not obstacles. Finding workarounds doesn't obviously explain what was wrong and why workarounds are supposed to work. This would only be useful to the extent a workaround gets understood better than an original prototype.

Comment author: 20 April 2012 08:54:50AM *  0 points [-]

explain what was wrong

What was wrong is that we had yet another version of Russell's/liar/self-reference paradox. Things reasoning about themselves (even implicitly) causes problems. So looking at systems designed to avoid those paradoxes is probably worth doing.

Comment author: 20 April 2012 10:50:34AM *  1 point [-]

So looking at systems designed to avoid those paradoxes is probably worth doing.

The distinction I'm making is between techniques designed to avoid problems (refuse to consider the situations that contain them, or reduce the damage they cause, symptomatic treatment) and those allowing to resolve/understand them. For example, Goedel numbering is the kind of technique that significantly clarified what was going on with self-reference paradoxes, at which point you deal with complicated structure rather than confusing paradoxes.

Comment author: 17 April 2012 04:43:16PM *  1 point [-]

There is a provability semantics for the modal logic, which forms a model for the logic within mathematics, without using constructs like impossible possible worlds. In the provability semantics, "□A" means "A is a theorem [of some sufficiently rich formal system such as PA]".

It just occurred to me that the diagonalized implementations of ADT/UDT implicitly use this semantics: when a UDT agent looks for moral arguments
□(A()=a => U()=u)
the diagonal rule guarantees that
□(~A()=a) => A()=a
which (assuming the proof system is consistent) implies ~□(~A()=a), or ◊(A()=a), thus keeping the counterfactual worlds "possible".

Comment author: 19 April 2012 11:36:21AM 0 points [-]

Comment author: 19 April 2012 04:58:10PM 1 point [-]

Thanks! It looks interesting. Will need to study some of the references to understand it better.

I wonder why EY is so hostile to modal logic.

Comment author: 19 April 2012 05:05:54PM 1 point [-]

I wonder why EY is so hostile to modal logic.

He explains here.

Comment author: 19 April 2012 05:43:30PM 0 points [-]

Philosophy is a mind killer. Modal logic is pure math.

Comment author: 20 April 2012 08:49:59AM *  1 point [-]

Yep, but classifying the holonomy of normal conformal Cartan connections is also maths, and I don't post it to Less Wrong. There has to be some connection with AI or rationality or decision making.

I should have clarified that I wasn't writing in defense of modal logic, but purely using it as an illustration to introduce Kripke structures and impossible worlds, which are needed for the semantics of relevance logics (and might be useful tools in their own right).

Comment author: 20 April 2012 09:44:05AM 0 points [-]

classifying the holonomy of normal conformal Cartan connections

The paper is rather intimidating, I don't understand anything in it. Do your results have implications at a more accessible level?

Comment author: 20 April 2012 10:11:16AM 0 points [-]

No, they don't - that was my point.

Comment author: 20 April 2012 10:13:44AM 0 points [-]

Unlike modal logic, which does - that was mine.

Comment author: 20 April 2012 10:15:28AM 0 points [-]

But it's relevant implications here are philosophical or practical, not mathematical.

Comment author: 17 April 2012 05:20:58PM *  0 points [-]

the diagonal rule guarantees that
□(~A()=a) => A()=a

Something like that, but not quite, as you can't get an implication from provability if agent is a program, it's not decidable (unless you use a provability oracle). So you only impose some finite difficulty on (un)provability of a statement, not outright impossibility. See this comment.

Comment author: 17 April 2012 05:58:53PM 1 point [-]

You're saying, the use of "□" is not justified, because for the agent it means "provable with a proof length of up to N" and not simply "provable"?

This is technically correct, but is this case significantly different from the cases where we assume variables in programming languages are integers, when in fact they are members of Zn for some large n? The resource limits only mean we have to additionally prove that (1) the modal logic axioms hold for all statements with sufficiently short proofs, or something like that, and (2) that the N is sufficiently large for our purposes.