📂Set Theory

Mathematical Binary Relations

Definition ¹

1. For two sets $X,Y$, $$ R := \left\{ (x,y): x \in X , y \in Y \right\} \subset X \times Y $$ is defined as a (binary) relation and is represented as follows: $$ (x,y) \in R \iff x R y $$
2. $x R y \iff y R^{-1} x$ satisfying $$ R^{-1} : \left\{ (y,x): (x,y) \in R \right\} $$ is called the inverse relation of $R$.
3. For all $x \in X$, $ R \subset X^{2}$ satisfying the following condition is called reflexive: $$ x R x $$
4. For all $x,y \in X$, $ R \subset X^{2}$ satisfying the following condition is called symmetric: $$ x R y \implies y R x $$
5. For all $x,y,z \in X$, $ R \subset X^{2}$ satisfying the following condition is called transitive: $$ x R y \land y R z \implies x R z $$
6. For all $x,y \in X$, $ R \subset X^{2}$ satisfying the following condition is called antisymmetric: $$ x R y \land y R x \implies x = y $$

Explanation

Binary relations are not ambiguously described as ‘something being related to something in some way’ but can be clearly defined using Cartesian product. A relation is precisely a subset of a Cartesian product, and by looking at $x R y$, one should not understand it as ‘$x$ is somehow related to $y$’. Attention should be paid not to overlook the concept by just getting the intuitive understanding; otherwise, reading about ‘relations’ will become difficult whenever they come up.

Especially, a binary relation that is reflexive, symmetric, and transitive is called an equivalence relation. These properties are profoundly important throughout mathematics.

Example

Binary Relation and Inverse Relation

The function $f : X \to Y$ is a binary relation where, for all $x$, there exists a $y \in Y$ satisfying $y = f(x)$ and, for all $x_{1} , x_{2} \in X$, $$ x_{1} = x_{2} \implies f(x_{1}) = f(x_{2}) $$ is satisfied. Of course, if its inverse function $f^{-1}$ exists, then $f^{-1}$ becomes the inverse relation of $f$.

Reflexive Relation

An example of a reflexive relation is equality $=$, where $x=x$ always holds.

Symmetric Relation

An example of a symmetric relation is independence $\perp$, where $$ X \perp Y \implies Y \perp X $$ always holds.

Transitive Relation

An example of a transitive relation is the inequality $<$, where $$ x < y \land y < z \implies x < z $$ always holds.

Antisymmetric Relation

An example of an antisymmetric relation is the inclusion relation $\subset$, where $$ A \subset B \land B \subset A \implies A = B $$ always holds.