Relations

Overview

An ordered pair of $x$ and $y$, denoted $⟨x,y⟩$, is defined as: $⟨x,y⟩=\{\{x\},\{x,y\}\}$. We define the first coordinate of $⟨x,y⟩$ to be $x$ and the second coordinate to be $y$.

A relation $R$ is a set of ordered pairs. The domain of $R$ ($\mathrm{dom}R$), the range of $R$ ($\mathrm{ran}R$), and the field of $R$ ($\mathrm{fld}R$) is defined as:

• $x\in \mathrm{dom}R\iff \exists y,⟨x,y⟩\in R$
• $x\in \mathrm{ran}R\iff \exists t,⟨t,x⟩\in R$
• $\mathrm{fld}R=\mathrm{dom}R\cup \mathrm{ran}R$

A set $A$ is single-valued iff for each $x$ in $\mathrm{dom}A$, there is only one $y$ such that $xAy$. A set $A$ is single-rooted iff for each $y\in \mathrm{ran}A$, there is only one $x$ such that $xAy$.

n-ary Relations

We define ordered triples as $⟨x,y,z⟩=⟨⟨x,y⟩,z⟩$. We define ordered quadruples as $⟨x_1,x_2,x_3,x_4⟩=⟨⟨⟨x_1,x_2⟩,x_3⟩,x_4⟩$. This idea generalizes to $n$-tuples. As a special case, we define the $1$-tuple $⟨x⟩=x$.

An $n$-ary relation on $A$ is a set of ordered $n$-tuples with all components in $A$. Keep in mind though, a unary ($1$-ary) relation on $A$ is just a subset of $A$ and may not be a relation at all.

Reflexivity

A relation $R$ is reflexive on $A$ iff $xRx$ for all $x\in A$. In relational algebra, we define $R$ to be reflexive on $A$ iff $I_A\subseteq R$.

Irreflexivity

A relation $R$ is irreflexive on $A$ iff $\neg xRx$ for all $x\in A$. That is, it is never the case that $xRx$.

Symmetry

A relation $R$ is symmetric iff whenever $xRy$, then $yRx$. In relational algebra, we define $R$ to be symmetric iff $R^{-1}\subseteq R$.

Antisymmetry

A relation $R$ is antisymmetric iff whenever $x\ne y$ and $xRy$, then $\neg yRx$.

Asymmetry

A relation $R$ is asymmetric iff whenever $xRy$, then $\neg yRx$.

Transitivity

A relation $R$ is transitive iff whenever $xRy$ and $yRz$, then $xRz$. In relational algebra, we define $R$ to be transitive iff $R\circ R\subseteq R$.

Connected

A binary relation $R$ on set $A$ is said to be connected if for any distinct $x,y\in A$, either $xRy$ or $yRx$. The relation is strongly connected if for all $x,y\in A$, either $xRy$ or $yRx$.

Trichotomy

A binary relation $R$ on $A$ is trichotomous if for all $x,y\in A$, exactly one of the following holds: $xRy,x=y,yRx$

Bibliography

• “Antisymmetric Relation,” in Wikipedia, January 24, 2024, https://en.wikipedia.org/w/index.php?title=Antisymmetric_relation.
• “Asymmetric Relation,” in Wikipedia, February 21, 2024, https://en.wikipedia.org/w/index.php?title=Asymmetric_relation.
• “Cartesian Product,” in Wikipedia, April 17, 2024, https://en.wikipedia.org/w/index.php?title=Cartesian_product.
• “Connected Relation,” in Wikipedia, July 14, 2024, https://en.wikipedia.org/w/index.php?title=Connected_relation.
• Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).