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.