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