## 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