Saul Kripke's Logic of Possible Worlds

How can we rigorously reason about what is necessary, what is merely possible, or what constitutes a mathematical proof? How can language talk about its own truth without collapsing into paradox? These profound questions, which have challenged thinkers for centuries, found a revolutionary and elegant answer in the work of Saul Kripke. He introduced a simple yet powerful framework known as Kripke semantics, or the logic of "possible worlds," which provided a concrete, intuitive way to understand abstract logical systems that go beyond simple true-or-false statements. This article tackles the knowledge gap between the abstract rules of non-classical logics and their tangible meaning, demonstrating how Kripke's models provide a unifying foundation. The journey will begin by dissecting the core machinery of his theories, then expand to reveal their surprising and deep impact across a multitude of disciplines.

Imagine you're not just living in this world, but you have the ability to peek into other "possible worlds." These aren't necessarily parallel universes in the science fiction sense, but rather alternate scenarios. A world where you chose a different career. A world where a historical event turned out differently. A world where a different physical law holds. This simple, powerful idea is the starting point of Saul Kripke's most famous contribution: ​​Kripke semantics​​, or the logic of possible worlds.

To turn this intuitive picture into a rigorous tool, Kripke proposed we need only two things. First, a set of all the worlds we want to consider, which we'll call $W$. Second, and this is the crucial part, we need a map that tells us which worlds are "visible" or "accessible" from any given world. This map is the ​​accessibility relation​​, denoted by $R$. If you can get from world $w$ to world $v$, we write $R(w, v)$. A frame for our logic is just this pair: $(W, R)$.

The accessibility relation is the engine of the whole system. It defines the structure of possibility. Maybe from our current world, only futures where technology advances are possible. Maybe from a world in a dream, any bizarre world is accessible. The rules we put on this relation will, as we shall see, determine the very laws of logic that hold in our universe of worlds.

To complete the picture, we need to know what's true in each world. We introduce a ​​valuation​​ function, $V$, which for any basic proposition like "it is raining" (let's call it $p$), tells us the set of all worlds where $p$ is true. The full Kripke model is the triplet $(W, R, V)$. With these pieces, we can start to reason.

Now we can give precise meaning to our modal notions of "necessity" and "possibility." Let's invent two symbols for them: $\Box$ for necessity and $\Diamond$ for possibility. Their meaning is defined by standing in a world and looking out at the worlds you can access via the relation $R$.

• ​​Necessity ($\Box$)​​: A statement $\varphi$ is necessary in your current world $w$ (written $w \models \Box\varphi$) if $\varphi$ is true in every single world you can see from $w$. Think of it as a universal truth across all your immediate possibilities.

• ​​Possibility ($\Diamond$)​​: A statement $\varphi$ is possible in your world $w$ (written $w \models \Diamond\varphi$) if there is at least one world you can see from $w$ where $\varphi$ is true. You can glimpse a scenario where it holds.

Let's see this in action with a simple universe of three worlds: $W = \{w_0, w_1, w_2\}$. Suppose the accessibility is given by $R = \{(w_0, w_1), (w_0, w_2), (w_1, w_1)\}$. This means from $w_0$ you can "see" $w_1$ and $w_2$; from $w_1$ you can only see yourself; and from $w_2$ you can't see any worlds at all. Let's say the proposition $q$ ("the cat is on the mat") is only true in world $w_1$. Is $\Box q$ true at any of our worlds?

• At $w_0$: To check if $\Box q$ is true here, we look at all accessible worlds, $w_1$ and $w_2$. Is $q$ true in all of them? No. It's true in $w_1$ but not in $w_2$. So, $w_0 \not\models \Box q$.
• At $w_1$: The only world accessible from $w_1$ is $w_1$ itself. Is $q$ true in $w_1$? Yes. So, $w_1 \models \Box q$.
• At $w_2$: There are no worlds accessible from $w_2$. The condition "for all worlds $v$ such that $R(w_2, v)$, $q$ is true at $v$" is ​​vacuously true​​ because there are no such worlds to check! It's like promising to pay a dollar for every unicorn in the room—it's a promise you can't break. So, quite strangely, $w_2 \models \Box q$. At a "dead end" in the universe, everything is necessary!.

Here is where the real magic happens. By imposing simple, intuitive conditions on the accessibility relation $R$, we can derive entire systems of logic. The "shape" of the accessibility graph dictates the "laws" of truth.

For example, what if we require that every world can see itself? That is, for every world $w$, the relation $R(w, w)$ holds. This property is called ​​reflexivity​​. What does this imply logically? If we know that $\Box\varphi$ is true at $w$, we know $\varphi$ is true in all accessible worlds. Since $w$ is now accessible from itself, $\varphi$ must be true at $w$. In other words, in any universe with a reflexive accessibility relation, the principle "If $\varphi$ is necessary, then $\varphi$ is true" (formally, $\Box\varphi \to \varphi$) holds as a law of logic.

This is a profound connection. What if we require the relation to be transitive (if you can get from $w_1$ to $w_2$, and from $w_2$ to $w_3$, you can get from $w_1$ to $w_3$)? This gives us a different axiom: $\Box\varphi \to \Box\Box\varphi$. If something is necessary, it is necessarily necessary. The geometry of possibility becomes the foundation of logical reasoning.

This framework also reveals subtle distinctions. Consider the difference between assuming a fact is true at one world versus assuming it's true everywhere. If we assume a proposition $p$ is true just at our world $w$, we can't conclude that $\Box p$ is true, because an accessible world might exist where $p$ is false. However, if we make the much stronger assumption that $p$ is true in every single world of our model (a ​​global assumption​​), then it follows that $\Box p$ must also be true everywhere. This difference between ​​local consequence​​ and ​​global consequence​​ is critical in modal logic; it's the difference between a local fact and a universal law.

Now, let's take Kripke's brilliant idea and repurpose it. Instead of "possible worlds," what if the worlds represent "states of knowledge" at different points in time? Let's replace the accessibility relation $R$ with an ordering relation $\leq$. The statement $w \leq v$ no longer means $v$ is possible from $w$, but that $v$ is a future state of knowledge that builds upon $w$. You know everything at $v$ that you knew at $w$, and maybe more.

This reinterpretation forces a fundamental change. In our modal logic of possibility, a fact could be true in one world but false in an accessible one. But this makes no sense for knowledge. If you have proven a theorem, you don't "un-prove" it later when you learn more. Truth, once established, must persist. This is the cornerstone of Kripke's semantics for ​​intuitionistic logic​​: the principle of ​​monotonicity​​ (or heredity).

​​Monotonicity​​: If a statement $\varphi$ is true at a state of knowledge $w$, and $v$ is any future state ($w \leq v$), then $\varphi$ must also be true at $v$.

This isn't just an optional extra; it's baked into the very foundation of the model. We require that the valuation for any basic proposition $p$ is ​​upward-closed​​: if $p$ is true at $w$, it must be true at all future states $v \geq w$. If we violate this—say, by defining $p$ to be true at $w_1$ but not at a future state $w_3$—the model no longer properly represents the accumulation of knowledge. From this atomic requirement, the property of monotonicity propagates to all complex formulas, guaranteed by the very way we define the logical connectives.

This "knowledge-based" model forces us to rethink what "true" even means. In classical logic, a statement like "Either there is a greatest prime number, or there is not" is obviously true. But an intuitionist, a follower of this constructive philosophy, would object. To claim a disjunction "$A$ or $B$" is true, you must be able to prove $A$ or prove $B$. We don't just get to assert its truth by default.

This constructive viewpoint leads to fascinating new definitions for the logical connectives. Conjunction ($\land$) and disjunction ($\lor$) are straightforward: to know $A \land B$ at state $w$ is to know $A$ and to know $B$; to know $A \lor B$ is to know $A$ or to know $B$. But implication is where things get truly interesting. In Kripke's model, the meaning of implication becomes a guarantee about the future:

​​Implication ($\to$)​​: A statement $\varphi \to \psi$ is true at a state of knowledge $w$ if, for every future state of knowledge $v$ (including $w$ itself), should we ever come to know that $\varphi$ is true, we will also know that $\psi$ is true.

This is a far cry from the simple truth table you learned in introductory logic! An implication is a durable commitment, a strategy for converting a future proof of $\varphi$ into a proof of $\psi$.

With this definition, cherished laws of classical logic begin to crumble. Consider the ​​Law of the Excluded Middle​​: $\varphi \lor \neg\varphi$. Is this always true? Let's use our model. At our current state $w$, do we know $\varphi$ or do we know $\neg\varphi$? Maybe neither! We might be in a state of suspense, where we haven't yet found a proof of $\varphi$, but we also haven't been able to show that assuming $\varphi$ leads to a contradiction. In such a world, the disjunction fails.

Similarly, the law of ​​double negation elimination​​, $\neg\neg\varphi \to \varphi$, is not valid. In our model, $\neg\varphi$ means that in all future states, we will never find a proof of $\varphi$. So $\neg\neg\varphi$ means it's impossible that we will never find a proof of $\varphi$. But does this guarantee that we actually have a proof of $\varphi$ right now, at our current state? No! It only tells us that the search is not hopeless. To claim $\varphi$, we need the proof in hand, not just the promise that one might be findable. A famous counterexample involves a simple two-world chain, $w_0 \leq w_1$, where a proposition $p$ is unknown at $w_0$ but becomes known at $w_1$. At world $w_0$, it turns out that $\neg\neg p$ is true, but $p$ itself is not. The implication fails.

Kripke's intellectual journey culminates in a daring application of these ideas to one of philosophy's oldest and deepest wounds: the ​​Liar's Paradox​​. Consider the sentence:

​​L​​: This sentence is false.

If L is true, then what it says must be the case, so it's false. If L is false, then what it says is not the case, so it's true. Contradiction.

The great logician Alfred Tarski had famously shown that no sufficiently powerful formal language could contain its own truth predicate without generating such paradoxes. His solution was to create a strict hierarchy of languages, where a language at level $n$ could only talk about the truth of sentences at lower levels. It works, but it feels artificial and doesn't reflect how we actually use language.

Here, Kripke offers a breathtakingly elegant alternative, one that echoes the constructive spirit of his intuitionistic models. He says: let's not assume from the outset that every sentence is either true or false. Let's build up the set of true sentences, just like we built up knowledge over time.

We start with a language that contains its own truth predicate, $T$. Initially, we assume nothing is true and nothing is false. This is our ground state, Stage 0.

• ​​Stage 1​​: We look at all the sentences that don't involve the truth predicate $T$, like "Snow is white." We evaluate them. "Snow is white" is true. We add it to our set of truths. "Snow is blue" is false. We add it to our set of falsities.
• ​​Stage 2​​: Now we can evaluate sentences that involve $T$, but only when applied to sentences whose truth value we decided at Stage 1. For example, $T(\ulcorner \text{"Snow is white"} \urcorner)$ is now true.
• ​​Iteration​​: We keep repeating this process. At each stage, we add more sentences to the growing sets of truths and falsities. This process is monotonic—once a sentence is declared true, it stays true.

Because the process is monotonic, the famous Knaster-Tarski fixed-point theorem guarantees that this iteration must eventually reach a ​​fixed point​​—a stage where applying the procedure one more time gives us nothing new. At this fixed point, we have a stable notion of truth.

So what happens to the Liar sentence, L, which is equivalent to $\neg T(\ulcorner L \urcorner)$? It never gets a truth value. At Stage 0, it's not in the set of truths or falsities. At Stage 1, we can't evaluate it, because it depends on the truth of L, which we don't know yet. This situation persists forever. The Liar sentence, along with other paradoxical sentences like the Truth-Teller ("This sentence is true"), remains in a ​​truth-value gap​​. It is neither true nor false.

By abandoning classical two-valued logic and embracing the idea of partial, constructively defined truth, Kripke doesn't "solve" the paradox in a way that assigns L a value. Instead, he creates a coherent framework where the paradox simply fails to arise. The same core idea—an iterative construction over a structured set of "worlds" or "stages"—that gave us a new way to understand necessity and mathematical proof also gives us our most powerful model for understanding truth itself. It is a stunning display of the unity and beauty inherent in logical discovery.

Now that we have explored the machinery of Kripke semantics—the "how" of its operation—we can turn to the more exciting question: "Why does it matter?" What is the use of these "possible worlds," which might seem like a philosopher's abstract fancy? The answer, it turns out, is that Kripke's framework is far from a mere logical curiosity. It is a master key, unlocking deep insights and practical solutions across an astonishing range of disciplines. It provides a common language for logicians, mathematicians, computer scientists, and philosophers to tackle some of their most fundamental problems. Let us embark on a journey to see how this single, elegant idea radiates outward, revealing the inherent beauty and unity of disparate fields of thought.

The most immediate and foundational application of Kripke semantics lies within logic itself. Before Kripke, non-classical logics, like intuitionistic logic, were often seen as esoteric systems defined by formal rules that rejected certain "obvious" classical truths. It was Kripke who provided an intuitive, concrete world for these logics to inhabit.

In intuitionistic logic, truth is identified with constructive proof. A statement is true only if we have a proof for it. This is a higher bar than in classical logic, where a statement is either true or false, even if we can never know which. Kripke semantics beautifully captures this idea of knowledge accumulating over time. A Kripke model represents a research program: the "worlds" are states of knowledge, and the accessibility relation points from current states to possible future states where more has been proven.

Consider the classical Law of the Excluded Middle, $p \lor \neg p$. Classically, this is an unassailable truth. But is it intuitionistically valid? Let's use a Kripke model to find out. Imagine a simple model with two worlds: a starting world $w_0$ and a future world $w_1$, accessible from $w_0$. Suppose that in our current state of knowledge, $w_0$, we have no proof of the proposition $p$. Thus, at $w_0$, we cannot assert that $p$ is true. However, we can imagine a future where we do find a proof; this is our world $w_1$, where $p$ is true.

Now, standing at $w_0$, can we assert $p \lor \neg p$? We can't assert $p$, as we don't have a proof for it yet. Can we assert $\neg p$? In Kripke's semantics, to assert $\neg p$ at $w_0$ means that $p$ can never become true in any accessible future world. But this contradicts the existence of our world $w_1$, where $p$ is true. Therefore, at $w_0$, we can assert neither $p$ nor $\neg p$. The Law of the Excluded Middle fails. This simple story, formalized in a two-world Kripke model, provides a powerful counterexample and a clear intuition for why intuitionists reject this classical law.

This same method provides a toolkit for investigating the entire landscape of logic. We can construct similar, slightly more elaborate models to show why other cherished classical principles, such as Double Negation Elimination ($\neg \neg A \to A$) and Peirce's Law ($((A \to B) \to A) \to A$), are also not intuitionistically valid. Kripke semantics transforms logic from a game of symbol manipulation into a science of exploring the structure of possible information states.

It is a deep and recurring theme in mathematics that a single structure can be viewed from different perspectives, for example, geometrically and algebraically. The same is true here. A Kripke model, with its worlds and arrows, has a certain "spatial" or "geometric" feel. It turns out this geometry has a perfect algebraic counterpart: the Heyting algebra.

A Heyting algebra is an abstract algebraic structure with operations for "meet" ($\land$), "join" ($\lor$), and a special "implication" ($\to$) that captures the constructive nature of intuitionistic logic. The connection is this: for any Kripke model, the set of all "upward-closed" sets of worlds—subsets of worlds that, once entered, cannot be escaped by moving to an accessible world—forms a perfect Heyting algebra. The logical operations on formulas correspond precisely to algebraic operations on these sets of worlds.

For instance, the truth of $p \lor q$ in a world corresponds to that world being in the union of the sets of worlds for $p$ and $q$. The truth of $p \to q$ is more subtle, corresponding to a more complex algebraic operation, but the correspondence is exact. This duality is not just an aesthetic curiosity; it is a profound link that allows logicians and mathematicians to translate problems back and forth between the two domains. A complex semantic argument in Kripke models can be transformed into a crisp algebraic calculation in a Heyting algebra, and vice-versa. The simple three-element Heyting algebra $\{0, \frac{1}{2}, 1\}$ where the Law of Excluded Middle fails corresponds directly to the two-world Kripke model we discussed earlier, providing a beautiful, unified picture of a non-classical logical structure.

While these applications in pure logic and algebra are profound, Kripke's ideas find some of their most impactful applications in the very practical world of computer science. What is a computing system—a microprocessor, a network protocol, a piece of software—if not a universe of possible states with well-defined transitions between them? A Kripke structure is the perfect mathematical abstraction for such a system. The "worlds" are the system's possible configurations, and the "accessibility relation" models the execution steps that transition it from one state to the next.

This perspective opens the door to ​​model checking​​, a powerful automated technique for verifying that a system design is correct. We can specify desired properties, such as "the system will never enter a deadlock state" or "every request for a resource will eventually be granted," using formal languages called temporal logics. A formula in Computation Tree Logic (CTL), for instance, can state that ​​A​​long all ​​G​​lobal execution paths, if a request is made, then ​​A​​long that path, grant will hold at some ​​F​​uture point: $\text{AG}(\text{req} \to \text{AF grant})$. Verifying this property then becomes a matter of systematically exploring the Kripke model of the system to see if the formula holds at the initial state.

The computational difficulty of this task reveals a deep connection to complexity theory. The problem is not merely the potentially vast number of states. The very structure of nested temporal operators, such as the AG (a greatest fixed-point computation) containing an AF (a least fixed-point computation), creates a sequential dependency that mirrors the layered evaluation of a Boolean circuit. This connection is so fundamental that CTL model checking is known to be ​​P-complete​​—it captures the essence of all problems that can be solved efficiently by a sequential computer, making it a cornerstone problem in computational complexity.

Furthermore, Kripke semantics provides a precise answer to a critical question in system design: When are two systems, despite having different internal structures, behaviorally equivalent? The concept of ​​bisimulation​​ gives the answer. Two states are bisimilar if they satisfy the same basic properties, and for any move one can make, the other can make a corresponding move to a state that is, in turn, bisimilar. This allows engineers to take an enormous, complex Kripke model representing a real-world design and mathematically "minimize" it to its smallest equivalent form, making the task of verification tractable.

Finally, we arrive at the most profound philosophical territory, where Kripke's work has reshaped our understanding of language and truth itself.

One subtle but important question in logic and the philosophy of mathematics concerns quantification. When we say "for all $x$...", what is the domain of individuals that $x$ ranges over? Kripke models with ​​varying domains​​ can model situations where this universe of discourse is not fixed but can expand as we move to future states of knowledge. This is crucial for reasoning about entities that may not exist yet but could in the future. In such models, certain classically "obvious" formulas, like the schema for constant domains, fail to hold, revealing that our logical principles are deeply tied to our metaphysical assumptions about the world.

Perhaps Kripke's most celebrated contribution is his theory of truth, which offers a solution to the ancient Liar Paradox: "This sentence is false." In the 1930s, Alfred Tarski proved that no language obeying classical logic could define its own truth predicate without leading to contradiction. This seemed to place a fundamental limit on the expressive power of formal languages.

Kripke's breathtaking move was to change the rules of the game. He abandoned the strict dichotomy of bivalence (every sentence is either true or false) and instead used a three-valued logic (true, false, or undefined). He then envisioned constructing a truth predicate iteratively. Starting with an empty truth predicate, he repeatedly applied a rule: a sentence is declared "true" at a given stage if the current truth predicate makes it so. This process, iterated through the transfinite ordinals, eventually reaches a "fixed point" where the truth predicate no longer changes.

In this final, stable state, sentences like "Snow is white" are true, and "Snow is green" are false. The Liar Sentence, however, remains stubbornly outside both categories—it is permanently assigned the value "undefined," falling into a truth-value gap. This brilliantly sidesteps Tarski's impossibility result. Kripke's theory doesn't provide a truth predicate that is definable within arithmetic (the construction is too complex) nor one that is total (it leaves gaps). It shows that by relaxing the demand for bivalence, we can have a consistent and powerful theory of self-referential truth.

From the foundations of proof to the verification of microchips to the nature of truth itself, Kripke's semantics of possible worlds stands as a testament to the power of a simple, beautiful idea to illuminate the deepest questions and build bridges between worlds of thought.