Relations

If we have a collection of sets \(A_{1}\) through \(A_{n}\), then we can take an \(n\)-ary relation on those sets. An \(n\)-ary relation on the sets \(A_{1}, ..., A_{n}\) is a set \(R\) such that \(R ⊆ A_{1} × ... × A_{n}\). In the special case of a binary relation on two sets \(A\) and \(B\), \(R\) is a set of pairs \(⟨a, b⟩\), such that \(a ∈ A\) and \(b ∈ B\). That is, \(R ⊆ A × B\). For \(n\)-ary relations \(R\), if the \(n\)-tuple \(⟨a₁, ..., aₙ⟩\) is a member of \(R\), we can indicate this by writing \[R(a₁, ..., aₙ)\]

An important operation on relations is relation composition. Given a relation \(R_{1} ⊂ A × B\) and a relation \(R_{2} ⊆ B × C\), their composition \(R_{2} ∘ R_{1} ⊆ A × C\) is defined as \[R_{2} ∘ R_{1} = \{⟨x, y⟩ ∣ \text{there is some $z$ such that } ⟨x, z⟩ ∈ R_{1} \text{ and } ⟨z, y⟩ ∈ R_{2}\}\] That is, \(R_{2} ∘ R_{1}\) is gotten by relating an element of \(A\) to an element of \(C\) just in case there is some element of \(B\) related to the first element by \(R_{1}\) and to the second element by \(R_{2}\).

---
title: "Relations"
bibliography: ../../semantics.bib
---

If we have a collection of sets $A_{1}$ through $A_{n}$, then we can take an $n$-ary *relation* on those sets. 
An $n$-ary *relation* on the sets $A_{1}, ..., A_{n}$ is a set $R$ such that $R ⊆ A_{1} × ... × A_{n}$.
In the special case of a binary relation on two sets $A$ and $B$, $R$ is a set of pairs $⟨a, b⟩$, such that $a ∈ A$ and $b ∈ B$.
That is, $R ⊆ A × B$.
For $n$-ary relations $R$, if the $n$-tuple $⟨a₁, ..., aₙ⟩$ is a member of $R$, we can indicate this by writing $$R(a₁, ..., aₙ)$$
    
<!-- Some properties of relations are useful to be able to describe. A relation -->
<!-- $R ⊆ A × A$ (that, is a relation $R$ on $A$) is said to be /reflexive/ if $⟨x, -->
<!-- x⟩ ∈ R$ for every $x ∈ A$. That is, $R$ relates everything in $A$ to -->
<!-- itself. A relation $R$ on $A$ is said to be /symmetric/ if $⟨y, x⟩ ∈ R$ -->
<!-- whenever $⟨x, y⟩ ∈ R$. It is said to be /antisymmetric/ if the only case in -->
<!-- which both $⟨x, y⟩ ∈ R$ and $⟨y, x⟩ ∈ R$ is when $x = y$. $R$ is said to be -->
<!-- /transitive/ if whenever $⟨x, y⟩, ⟨y, z⟩ ∈ R$, then $⟨x, z⟩ ∈ R$. A relation -->
<!-- $R$ on $A$ which is reflexive, transitive, and symmetric is said to be an -->
<!-- /equivalence relation/. -->
    
An important operation on relations is *relation composition*.
Given a relation $R_{1} ⊂ A × B$ and a relation $R_{2} ⊆ B × C$, their composition $R_{2} ∘ R_{1} ⊆ A × C$ is defined as $$R_{2} ∘ R_{1} = \{⟨x, y⟩ ∣ \text{there is some $z$ such that } ⟨x, z⟩ ∈ R_{1} \text{ and } ⟨z, y⟩ ∈ R_{2}\}$$
That is, $R_{2} ∘ R_{1}$ is gotten by relating an element of $A$ to an element of $C$ just in case there is some element of $B$ related to the first element by $R_{1}$ and to the second element by $R_{2}$.
    
<!-- If $R$ is a relation on $A$, then we will write $R^{n}$ to refer to the result -->
<!-- of composing $R$ with itself $n$ times. -->
<!-- By convention: -->
<!-- $$\begin{align*} -->
<!-- R^{0} &= \{⟨x, x⟩ ∣ x ∈ A\}\\ -->
<!-- R^{} &= R\\ -->
<!-- Rⁿ &= R^{n - 1} ∘ R -->
<!-- \end{align*}$$ -->
<!-- If $R ⊆ A × B$, we may define its /inverse/ as the relation $R^{-1} ⊆ B × A$ -->
<!-- such that $⟨y, x⟩ ∈ R^{-1}$ just in case $⟨x, y⟩ ∈ R$. That is, $R^{-1}$ is -->
<!-- just like $R$, but ``flipped around''. -->