📂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.