1.2: Relations

• 1.2.1: Relations as Sets

  A relation $R$ on a set $A$ is a way of relating elements of $A$. We write $Rxy$ if the relation holds between $x$ and $y$. Formally, we can consider $R$ as the sets of pairs $\langle x,y \rangle \in A^2$ such that $Rxy$.

• 1.2.2: Philosophical Reflections

  We define relations as certain sets. What is such a definition doing?

• 1.2.3: Special Properties of Relations

  A relation $R$ is reflexive if everything is $R$-related to itself; symmetric, if with $Rxy$ also $Ryx$ holds for any $x$ and $y$; and transitive if $Rxy$ and $Ryz$ guarantees $Rxz$.

• 1.2.4: Equivalence Relations

  A relation that is reflexive, symmetric, and transitive is called an equivalence relation.

• 1.2.5: Orders

  A relation which is both reflexive and transitive is called a preorder. A preorder which is also anti-symmetric is called a partial order. A partial order which is also connected is called a linear order.

• 1.2.6: Graphs

  Every relation $R$ on a set $X$ can be seen as a directed graph $\langle X, R \rangle$.

• 1.2.7: Operations on Relations

  Since relations are sets (of pairs), they can be operated on as sets (e.g., we can form the union and intersection of relations). We can also chain them together (relative product $R \mid S$). If we form the relative product of $R$ with itself arbitrarily many times we get the transitive closure $R^+$ of $R$.

• 1.2.8: Summary