Accessibility Relation¶

A binary relation on the worlds or states of a Kripke frame that fixes which alternatives a modal operator quantifies over from each evaluation point.

Version: v2 · 2026-08-30 · History
Domain-specific #: 1225
Origin domain: mathematical logic
Subdomain: modal logic

Core Idea¶

An accessibility relation is the binary relation that gives Kripke-style modal semantics its local range of alternatives. A frame is a pair F = ⟨W,R⟩, where W is a nonempty set of worlds or states and R ⊆ W×W. Writing wRv says that v is an alternative admitted from evaluation point w for the modality being modeled. A model adds a valuation, M = ⟨W,R,V⟩, but the relation belongs to the frame and can be studied independently of how propositional letters are valued.^[1]^[2]

For ordinary normal propositional modal logic, it supplies the truth conditions.

M,w ⊨ □φ iff for every v ∈ W, if wRv then M,v ⊨ φ,

and.

M,w ⊨ ◇φ iff for some v ∈ W, wRv and M,v ⊨ φ.

The relation therefore does two jobs. Locally, it selects the worlds quantified over by a modal operator at a point. Globally, its structural properties constrain which modal formulas are valid on every model based on the frame. Reflexivity, seriality, symmetry, transitivity, and Euclideanness correspond to familiar modal axiom schemas under frame validity. This syntax–semantics bridge is the residual identity that makes Accessibility Relation an autonomous domain-specific abstraction rather than an unexpanded mention inside Modal Reasoning.^[2]^[3]

The word “accessible” is semantic terminology, not a promise of physical reachability, ease of use, or moral acceptability. Depending on the application, wRv may mean metaphysical possibility relative to w, compatibility with an agent's information, an ideal alternative under a normative standard, a successor state of a process, or another formally specified range condition. The common identity is the binary range-selection role in relational modal semantics.

Structural Signature¶

The abstraction has these mandatory roles:

world/state set W — a nonempty domain of evaluation points;
ordered world pairs — the Cartesian product W×W from which relation members are selected;
accessibility relation R — a binary subset of W×W, often represented by directed arrows;
origin world w — the point at which a modal formula is evaluated;
accessible successor set R(w) — {v ∈ W | wRv}, the alternatives relevant from that origin;
modal operator — normally □ or ◇, or an indexed epistemic, temporal, deontic, or dynamic operator;
valuation or satisfaction relation — what determines whether the embedded formula holds at each world;
local truth clause — universal quantification over R(w) for □ and existential quantification for ◇;
frame property — a relation-level constraint such as seriality, reflexivity, symmetry, transitivity, or Euclideanness;
frame-validity bridge — a modal formula is valid on F when it is true at every world under every valuation on that frame;
interpretive reading — the application-specific meaning assigned to the arrows, which must remain distinct from their formal relational properties.

Recognition requires more than any directed graph. The relation must occur in a relational semantics so that modal evaluation at w ranges over R(w), or in the frame-level study of that semantic role. Conversely, no special property is required merely to be an accessibility relation: the basic normal modal logic K admits arbitrary binary relations. Reflexivity or transitivity is a condition imposed for particular systems, not part of the genus.

The orientation is also load-bearing. wRv normally makes v accessible from w; reversing every pair can change modal truth. And R need not already be a reachability closure. In transition semantics, R may encode one step; nested modalities traverse successive steps, while R* would encode reflexive transitive reachability and generally validate different formulas.

What It Is Not¶

Accessibility Relation is not the Encyclopedia's domain_specific:accessibility, which concerns inclusive design for users with varied sensory, motor, cognitive, or infrastructural capabilities. The shared word is homonymy. One is a mathematical relation on worlds; the other is a normative design commitment.

It is not Modal Reasoning itself. Modal Reasoning is the inferential act of evaluating necessity, possibility, obligation, knowledge, or temporal claims over alternatives. The accessibility relation is one formal semantic parameter that makes such evaluation possible. A logician can compare frames, prove correspondence results, or transform relations without performing a particular piece of modal reasoning.

It is not a possible world, a valuation, a frame, or a full Kripke model. R is one constituent of a frame ⟨W,R⟩; a model adds V. Conflating them makes it impossible to distinguish a fact that holds because of one valuation from a formula valid on the frame under every valuation.

It is not physical access, database access control, web linkage, an “access relation” between agents and resources, or generic graph reachability. Nor does “accessible” necessarily mean logically possible in an unrestricted metaphysical sense. The relation is chosen to interpret a particular modality.

Finally, it is not universal to all modal semantics. Neighborhood, algebraic, topological, selection-function, and other semantics can interpret modal or counterfactual operators without a single ordinary binary accessibility relation. The node describes relational/Kripke semantics, not the essence of modality in every formal framework.

Scope of Application¶

The home domain is normal modal logic and its relational semantics. Kripke's early completeness and semantical-analysis work made relations among worlds a basis for distinguishing systems of modal propositional logic.^[1] Blackburn, de Rijke, and Venema develop modal languages as tools for analyzing relational structures, separating models, frames, correspondence, definability, completeness, and computational questions.^[4]

The same formal role recurs in several modal families. In epistemic logic, a relation R_a can collect the worlds agent a cannot rule out; K_a φ is true when φ holds at all such worlds. A multi-agent model usually carries one indexed relation per agent. In doxastic logic, the relation can represent belief-compatible alternatives and may satisfy different constraints from knowledge. In deontic logic, successors can be worlds admissible or ideal relative to a normative standard. In temporal and dynamic logics, arrows can represent next moments, program transitions, or process steps. In model checking, related states often encode permitted transitions, though the exact formalism may impose totality, labels, paths, or temporal operators beyond the basic modal case.

These are literal in-domain transfers because the tuple ⟨W,R,V⟩, range-restricted satisfaction clauses, and relation-property reasoning remain. By contrast, calling a web page, building, or service “accessible” does not instantiate this abstraction unless a formal modal model is actually being specified.

Clarity¶

A practical diagnostic asks six questions.

What is the nonempty set W of worlds or states?
What exactly makes an ordered pair (w,v) a member of R?
Which direction does the arrow point, and is R a one-step relation or a closure?
Which modal operator is interpreted by quantifying over R(w)?
Which properties of R are assumed rather than proved?
Is the claim about one model and valuation, or validity over every valuation on a frame?

The last distinction prevents a common error. A formula can happen to be true everywhere in a particular nonreflexive model because its valuation is favorable, while failing to be valid on that frame. To infer reflexivity from the schema □p → p, one needs frame validity—truth for every valuation—not one hand-picked model.^[2]

Another diagnostic is the dead-end case. If R(w) is empty, □φ is vacuously true at w and ◇φ is false there under the standard clauses. If an application rejects that outcome, it needs seriality (∀w∃v wRv), a different semantic convention, or an explicit terminal-state treatment; informal intuition does not change the mathematics silently.

Manages Complexity¶

An intensional notion such as “possible relative to here,” “compatible with what this agent knows,” or “reachable after one system step” could require a new semantic rule for every context. Accessibility Relation compresses these cases into one binary parameter. The modal language then uses the same two quantifier clauses while the application changes W, R, and the interpretation of the arrows.

At the system level, relational properties summarize infinitely many local edge facts. Rather than inspect every modal formula separately, correspondence theory connects a compact first-order condition on R with an axiom schema. Open Logic's standard table gives seriality with D: □p → ◇p, reflexivity with T: □p → p, symmetry with B: p → □◇p, transitivity with 4: □p → □□p, and Euclideanness with 5: ◇p → □◇p.^[2] These facts allow designers of a logic to work in two directions: choose a relation class that models the intended alternatives, or choose modal principles and determine what frame conditions they require.

The compression also has a cost. A binary arrow can hide why a world is admitted, which evidence supports the link, how likely a transition is, or which action produces it. Multi-relational, labeled, probabilistic, or weighted models restore such distinctions when a bare R discards too much.

Abstract Reasoning¶

The relation licenses exact inferences.

Monotonic range effect: with valuation fixed at the compared worlds, adding R-successors can make a box formula harder to satisfy and a diamond formula easier to satisfy; deleting successors has the opposite tendency. Nested formulas require recomputation because their truth may itself depend on the relation.
Vacuity test: a dead-end world satisfies every □φ and no ◇φ under standard normal semantics.
Reflexivity: if every world accesses itself, frame validity of □p → p follows; conversely, validity of that schema on a frame forces reflexivity.
Transitivity: if wRv and vRu imply wRu, a necessity at w propagates into necessity at accessible v, validating □p → □□p on the frame.
Symmetry: if wRv implies vRw, actuality at w is possible from each accessible v, validating p → □◇p.
Seriality: if every world has a successor, necessity cannot coexist with impossibility of the same proposition, yielding □p → ◇p.
Euclideanness: if two worlds accessible from one origin are related in the required direction, a possibility at the origin remains possible at every accessible world, yielding ◇p → □◇p.
Indexed separation: two agents or modalities can share W and V but have different relations, so the same formula can be known by one agent and not another, or executable under one transition type and not another.
Bisimulation sensitivity: modal formulas observe relational structure through successor patterns rather than arbitrary set-theoretic detail; suitable bisimulations can preserve modal truth across different-looking models.^[4]

These inferences depend on precise quantifier scope. The fact that a schema is true in one model is weaker than its validity on the underlying frame, and a one-way soundness statement about a property is weaker than a full correspondence theorem.

Knowledge Transfer¶

The abstraction transfers literally within relational modal semantics. Alethic, epistemic, doxastic, deontic, temporal, dynamic, and computational interpretations can reuse the same frame structure while changing what an arrow means and which relation properties are justified. A practitioner who understands dead ends, frame validity, indexed relations, and correspondence in one modal family can carry those diagnostics into another.

For example, an epistemic model may read wR_av as “at w, agent a cannot exclude v.” The same universal clause then interprets knowledge. Fagin, Halpern, Moses, and Vardi use possible-world models to make this apparatus practical in distributed systems, artificial intelligence, and game theory.^[5] A process model may read wRv as a permitted next state; then ◇φ asserts a successor satisfying φ, while repeated modalities inspect paths of greater depth.

What transfers beyond formal semantics is the broader prime Relation: typed relata, ordered pairs, membership rule, direction, and algebraic properties. An informal claim that some option is “accessible” does not inherit modal truth clauses or correspondence results. The domain node should therefore not be promoted to a prime.

Examples¶

Three-world modal model. Let W={u,v,w}, let R={(w,v)}, and let P be true only at v. Then M,w ⊨ ◇P, because v is an accessible witness. If Q is true only at u, M,w ⊭ ◇Q, because truth at an unrelated world does not enter the existential range. At v, which has no successors, every box formula is vacuously true and every diamond formula false.

Reflexive frame. Add (x,x) for every x∈W. Now any □φ at x requires φ at x itself, so □p→p is valid under every valuation. A single model in which this implication happens to hold would not be enough; reflexivity is recovered at the frame-validity level.

Transitive process reading. Suppose aRb, bRc, and aRc. If p holds at all successors of a, then it holds at b and c; because every successor of b is also a successor of a, □p holds at b. Thus □p→□□p holds. If aRc is omitted, the one-step relation is nontransitive and the inference can fail.

Epistemic indexing. On one set of scenarios, R_A relates worlds Alice cannot distinguish and R_B relates worlds Bob cannot distinguish. If all R_A-successors of w satisfy p but one R_B-successor falsifies it, then K_A p is true at w and K_B p false. The indexed relations, not different truth rules, explain the difference.^[5]

Serial deontic frame. If R selects normatively admissible successors, requiring every world to have at least one such successor blocks the degenerate case where every obligation is vacuously true at a world with no admissible alternatives. Seriality is a formal modeling choice; it does not itself decide which worlds ought to count as ideal.

Non-example—web accessibility. A page that meets keyboard, contrast, and screen-reader requirements may be accessible in the design sense without containing a set W, binary R, modal operator, or Kripke truth clause. It does not instantiate Accessibility Relation.

Non-example—transitive closure. If R represents one program step, replacing it by R* changes the alternatives available to a single ◇. That may be useful for reachability but is not a harmless restatement of the original relation.

Structural Tensions¶

semantic generality vs. interpretive adequacy — one binary relation unifies many modal families, but each family must justify what its arrows mean;
local model truth vs. frame validity — valuations can make a schema accidentally true, while correspondence requires truth under every valuation;
one-step transition vs. reachability closure — a small relation preserves step structure, while a closure answers broader reachability questions but changes modal depth;
arbitrary frames vs. intended axioms — unrestricted R supports basic K, while knowledge, obligation, time, or process interpretations often demand additional properties;
vacuous necessity vs. live alternatives — dead ends make every box true, which is formally clean but sometimes semantically unacceptable;
single relation vs. indexed modalities — one R is economical, while multiple agents, actions, or times require distinct relations to avoid collapsing meanings;
structural compression vs. lost edge content — binary membership enables correspondence theory but omits probability, reason, action label, cost, and evidential provenance;
canonical Kripke semantics vs. semantic pluralism — relational semantics is powerful and recurrent, but not every modal phenomenon is best represented by ordinary accessibility arrows.

Structural–Framed Character¶

Accessibility Relation is structural, with an aggregate of 0.08. It is a binary subset of W×W with formally checkable properties and value-neutral truth clauses. The relation can model normative, epistemic, temporal, or computational content, but those readings are supplied by applications rather than built into the abstract mathematical object.

Structural Core vs. Domain Accent¶

The structural core is typed alternatives + directed membership relation + origin-relative successor set + universal or existential range test + property-level inference. Relation already carries most of this skeleton and explains why reflexivity, symmetry, and transitivity matter across domains.

The domain accent is nevertheless indispensable: possible worlds or modal states, Kripke frames and models, satisfaction at a world, box/diamond operators, frame validity under all valuations, and modal correspondence. Removing those roles leaves a binary Relation or transition graph, not an accessibility relation in modal semantics. The abstraction is therefore a strict domain-specific subtype of Relation rather than a new prime.

Relation — every accessibility relation is a binary relation on one set of worlds; this is the minimal prospective parent by strict subsumption.
Modal Reasoning — modal inference quantifies propositions over the successors selected by the relation, but the relation remains a semantic component rather than the reasoning act itself.
State and State Transition — in computational and dynamic readings, the arrows can encode possible next states; this is an application-specific relation, not a universal parent.
Dependency — modal truth at an origin depends on truth at selected successor worlds, but dependency does not specify the Kripke clauses.
Quantifier — box and diamond behave like universal and existential quantification over R(w).

The prospective DAG uses only a strict subsumption edge to Relation. Modal Reasoning stays in prose because neither node is literally a subtype of the other: Accessibility Relation is an object used by the reasoning pattern.

Relationships to Other Abstractions¶

Current abstraction Accessibility Relation Domain-specific

Parents (1) — more general patterns this builds on

Accessibility Relation is a kind of Relation Prime

every accessibility relation is a binary relation on one set of worlds; this is the minimal prospective parent by strict subsumption.

Hierarchy path (1) — routes to 1 parentless root

Accessibility Relation → Relation

Neighborhood in Abstraction Space¶

Accessibility Relation sits in a sparse region of the domain-specific corpus (76^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Accessibility in inclusive design, WCAG, disability access, or the built environment;
physical reachability or geographic access;
access-control relations between subjects and resources;
a generic link, edge, dependency, or graph adjacency relation;
a possible world or state;
the successor set R(w) rather than the full relation R;
a Kripke frame ⟨W,R⟩;
a Kripke model ⟨W,R,V⟩;
Modal Reasoning as an inferential practice;
logical possibility without an explicitly relativized semantics;
the reflexive transitive closure of a one-step transition relation;
similarity orderings or selection functions used for counterfactual conditionals;
neighborhood or algebraic modal semantics that do not use an ordinary binary R;
a claim that every accessibility relation must be reflexive, serial, transitive, symmetric, Euclidean, or an equivalence relation.

References¶

[1] Saul A. Kripke, “Semantical Analysis of Modal Logic I: Normal Modal Propositional Calculi,” Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 9(5–6) (1963): 67–96, https://doi.org/10.1002/malq.19630090502. registry ↩a ↩b

[2] Open Logic Project, Normal Modal Logic, chapters “Syntax and Semantics” and “Frame Definability,” release 08c0fa2, 2025-11-26, https://builds.openlogicproject.org/content/normal-modal-logic/normal-modal-logic.pdf. registry ↩a ↩b ↩c ↩d

[3] James Garson, “Modal Logic,” Stanford Encyclopedia of Philosophy, substantive revision 2023, https://plato.stanford.edu/entries/logic-modal/. registry ↩

[4] Patrick Blackburn, Maarten de Rijke, and Yde Venema, Modal Logic, Cambridge Tracts in Theoretical Computer Science 53, Cambridge University Press, 2001, https://doi.org/10.1017/CBO9781107050884. registry ↩a ↩b

[5] Ronald Fagin, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi, Reasoning About Knowledge, MIT Press, 1995; paperback 2004, https://mitpress.mit.edu/9780262562003/reasoning-about-knowledge/. registry ↩a ↩b

[6] “Accessibility relation,” Wikipedia, frozen revision 1320635173, 2025-11-05, https://en.wikipedia.org/wiki/Accessibility_relation. registry