1.2: Relations

Sets, Logic, Computation · LibreTexts

0%

Contents

    Text

    Size
    100%
    Theme
    Typeface
    Line length
    Spacing

    From LibreTexts, under CC BY, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

    • 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

    This page titled 1.2: Relations was last modified on Sun, 12 Sep 2021 15:28:43 GMT and is shared under a CC BY license and was authored, remixed, and/or curated by Richard Zach et al. (Open Logic Project) .