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 w_H the world in which it comes out heads and w_T 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 w_H. 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 w_T, 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 w_T and w_H, because we can't (currently) tell them apart.

Because of this relationship, the statement A:"the coin is heads" is possible in both w_T and w_H. 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=w_H, ◊A is true because A is true in w_H and w_H is related to itself. Similarly, for w=w_T, ◊A is true because A is true in w_H and w_H is related to w_T.

Conversely B:"the coin is heads or the coin is tails" is necessary in both w_T and w_H: here the rule is that a statement is necessary in world w if it is true in all worlds related to w. w_T and w_H are 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 w_T or w_H, because both those worlds are related to w_T and A is false in w_T.

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.