Supplement to Dynamic Epistemic Logic

Appendix C: Properties of binary relations

Below are the definitions of various adjectives that may be used to describe a binary relation R on a set W (of “worlds”): this is a set \(R\subseteq W\) for which we write \(wRv\) to mean that \((w,v)\in R\).

  • Reflexive: \(xRx\) for each \(x\in W\).
    “Each world has an R-arrow pointing from that world right back to that world.”
  • Transitive: \(xRy\) and \(yRz\) implies \(xRz\) for each \(x,y,z\in W\).
    “Every sequence of worlds connected by R-arrows gives rise to an R-arrow going directly from the first world to the last.”
  • Symmetric: \(xRy\) implies \(yRx\) for each \(x,y\in W\).
    “Every R-arrow going in one direction gives rise to another R-arrow going in the opposite direction.”
  • Equivalence relation: R is reflexive, transitive, and symmetric.
  • Euclidean: \(xRy\) and \(xRz\) implies \(yRz\) for each \(x,y,z\in W\).
    “Two R-arrows leaving from the same source world give rise to R-arrows going between their destinations in both directions.”
  • Serial: for every \(x\in W\), there is a \(y\in W\) such that \(xRy\).
    “Every world has a departing R-arrow.”
  • Connected: for each partition of W into two disjoint nonempty sets S and T, there is an \(x\in S\) and a \(y\in T\) such that \(xRy\) or \(yRx\).
    “All worlds are linked to the same R-arrow network.”
  • Complete (or Total): for any two different elements \(x\in W\) and \(y\in W\), we have \(xRy\) or \(yRx\).
    “Every pair of distinct worlds is ‘R-comparable’.” (Think of \(xRy\) as saying, “x is less than y.”)
  • Well-founded: every nonempty set \(S\subseteq W\) has an \(x\in S\) such that for no \(y\in S\) is it the case that \(yRx\).
    “Every nonempty set of worlds has an ‘R-minimal’ element.”
  • Converse well-founded: the converse relation \(R^-\) (defined by \(xR^-y\) iff \(yRx\)) is well-founded.
    “Every nonempty set of worlds has an ‘R-maximal’ element.”
  • Preorder: R is reflexive and transitive.

For information on the role of some of these properties in modal logic, we refer to the reader to our Appendix D or the Stanford Encyclopedia of Philosophy entry on Modal Logic.

← beginning of main article

Copyright © 2016 by
Alexandru Baltag <albaltag@yahoo.com>
Bryan Renne <bryan@renne.org>

Open access to the SEP is made possible by a world-wide funding initiative.
The Encyclopedia Now Needs Your Support
Please Read How You Can Help Keep the Encyclopedia Free