> [!NOTE] Definition (Binary Relation in $L_{2}$) > In [[L2 (FOL)|L2]], a binary relation is a $2$ place predicate. > [!NOTE] **Definiton** (Set-theoretic binary relation) > A *relation* $R$ from [[Sets|sets]] $X$ to $Y$ is a set of [[Ordered pair|ordered pairs]]: $R\subseteq X \times Y$ > If $(x,y)\in R$, we write $xRy.$ **# Properties **Basic properties**: - [[Transitive Relation|Transitivity]]: $\forall x \forall y \forall z ((R(x,y) \land R(y,z))\to R(x,z))$ - [[Reflexive Relation|Reflexivity]]: $\forall x R(x,x)$ - [[Irreflexive relation|Irreflexive]]: $\forall x \lnot R(x,x).$ - [[Symmetric Relation|Symmetry]]: $\forall x \forall y (R(x,y) \to R(y,x))$ - [[Asymmetric Relation|Asymmetry]]: $\forall x \forall y (R(x,y) \to \lnot R(y,x))$ - [[Antisymmetric Relation|Antisymmetry]]: $\forall x \forall y ((R(x,y) \land R(y,x))\to x=y).$ An example is [[Partial Order|partial order relations]] since $x \leq y \land y \leq x \to x=y.$ - [[Total Relation|Total (or Strongly connected)]]: $\forall x \forall y (R(x,y) \lor R(y,x)).$ A [[Total Order|total order]] is a partial order that is also total. - [[Trichotomy]]: $\forall x \forall y (xRy \lor x=y \lor yRx).$ An example is [[Total Strict Order|total strict order]]. - [[Equivalence relations|Equivalence]]: relation on a set that is symmetric, transitive and reflexive. Examples are the identity and congruence modulo $n.$ **Inverse relations**: Given any set-theoretic binary relation $R$ on a set $D$, the inverse of that relation is the relation $R^{-1}$ defined by $R^{-1}=\{ (x,y) \mid (y,x) \in R \}.$ Thus, for example, the extension of smaller in some domain is always the inverse of the extension of larger. **Functions**: A binary relation between sets is a [[Function|function]] iff it satisfies it is (1) total in the sense that $\forall x \exists yR(x,y)$ and; (2) functional: $\forall x \exists^{\leq 1} y\; R(x,y).$