Relations

GALACTIC core kernel

Kernel

A relation [Pin14] is a way to describe how elements from one or more sets are connected or associated with each other. It’s a fundamental idea in mathematics and other fields that helps us understand and organize information based on these connections.

Cartesian product

Definition

Let \(A\) and \(B\) be two sets. The Cartesian product of \(A\) and \(B\), denoted \(A \times B\), is the set of all ordered pairs \((a, b)\) where \(a\) is an element of \(A\) and \(b\) is an element of \(B\). Formally,

\[A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}\]

Properties

Non-commutative

In general, \(A \times B \neq B \times A\). The pairs \((a, b)\) and \((b, a)\) are distinct unless \(a = b\).

Cardinality

If \(A\) and \(B\) are finite sets, then the cardinality of \(A \times B\) is the product of the cardinalities of \(A\) and \(B\). If \(|A| = m\) and \(|B| = n\), then \(|A \times B| = m \times n\).

Associativity

The Cartesian product is associative in the sense that \((A \times B) \times C\) is isomorphic to \(A \times (B \times C)\).

Binary relations

Definition

Let \(A\) and \(B\) be two sets. A binary relation \(R\) from \(A\) to \(B\) is a subset of the Cartesian product \(A \times B\). In other words, \(R\) is a set of ordered pairs \((a, b)\) where \(a \in A\) and \(b \in B\). Formally,

\[R \subseteq A \times B\]

\(n\)-ary relations

Definition

Let \(A_1, A_2, \ldots, A_n\) be \(n\) sets. An n-ary relation \(R\) over these sets is a subset of the Cartesian product \(A_1 \times A_2 \times \cdots \times A_n\). In other words, \(R\) is a set of ordered n-tuples \((a_1, a_2, \ldots, a_n)\) where \(a_i \in A_i\) for \(i = 1, 2, \ldots, n\). Formally,

\[R \subseteq A_1 \times A_2 \times \cdots \times A_n\]

Endo relations

Definition

An endo-relation is a binary relation on a single set \(A\). It is a subset of the Cartesian product \(A \times A\), meaning it relates elements within the same set. Formally, an endo-relation \(R\) on \(A\) is defined as:

\[R \subseteq A \times A\]

This means \(R\) consists of ordered pairs \((a, b)\) where both \(a\) and \(b\) are elements of \(A\).

Properties

Reflexivity

A relation \(R\) is reflexive if every element is related to itself. Formally:

\[\forall a \in A, (a, a) \in R\]

Irreflexivity

A relation \(R\) is irreflexive if no element is related to itself. Formally:

\[\forall a \in A, (a, a) \notin R\]

Symmetry

A relation \(R\) is symmetric if whenever \(a\) is related to \(b\), then \(b\) is related to \(a\). Formally:

\[\forall a, b \in A, (a, b) \in R \implies (b, a) \in R\]

Antisymmetry

A relation \(R\) is antisymmetric if whenever \(a\) is related to \(b\) and \(b\) is related to \(a\), then \(a\) must be equal to \(b\). Formally:

\[\forall a, b \in A, (a, b) \in R \text{ and } (b, a) \in R \implies a = b\]

Asymmetry

A relation \(R\) is asymmetric if whenever \(a\) is related to \(b\), then \(b\) cannot be related to \(a\). Formally:

\[\forall a, b \in A, (a, b) \in R \implies (b, a) \notin R\]

Transitivity

A relation \(R\) is transitive if whenever \(a\) is related to \(b\) and \(b\) is related to \(c\), then \(a\) is related to \(c\). Formally:

\[\forall a, b, c \in A, (a, b) \in R \text{ and } (b, c) \in R \implies (a, c) \in R\]

Connected (or Total)

A relation \(R\) is connected if for every pair of distinct elements \(a\) and \(b\), either \(a\) is related to \(b\) or \(b\) is related to \(a\). Formally:

\[\forall a, b \in A, a \neq b \implies (a, b) \in R \text{ or } (b, a) \in R\]