Binary relation
In mathematics, a binary relation (or simply relation) is a fundamental concept that establishes a correspondence between elements of two sets, capturing the idea of one element being connected to another in a specified way. Formally, given two sets A and B, a binary relation R from A to B is defined as a subset of the Cartesian product A × B, consisting of ordered pairs (a, b) such that a ∈ A, b ∈ B, and the pair satisfies the relation's condition.[1][2] When A = B, the relation is said to be a binary relation on the set A.[3] Binary relations can exhibit various structural properties that determine their behavior and utility in mathematical reasoning. Key properties include reflexivity (every element a ∈ A satisfies a R a), symmetry (if a R b then b R a), transitivity (if a R b and b R c then a R c), and antisymmetry (if a R b and b R a then a = b).[4][5] Combinations of these properties classify relations into important types: for example, an equivalence relation is reflexive, symmetric, and transitive, partitioning a set into equivalence classes; a partial order is reflexive, antisymmetric, and transitive, modeling hierarchical structures like precedence.[6][7] Binary relations form the basis for many core mathematical constructs and applications across disciplines. Functions, for instance, are special binary relations that are right-unique, meaning each element in the domain relates to exactly one element in the codomain.[8][6] Classic examples include the "less than" relation (<) on the real numbers, which is irreflexive, asymmetric, and transitive (a strict partial order), and the equality relation (=), which is an equivalence relation.[7] In set theory and logic, binary relations provide a common framework for describing structures like orders and equivalences, while in computer science, they underpin algorithms for graph traversal, database queries, and equivalence partitioning in programming.[9][10]Fundamentals
Definition
In set theory, the Cartesian product of two sets A and B, denoted A \times B, is the set of all ordered pairs (a, b) where a \in A and b \in B.[11] A binary relation R from a set A to a set B is a subset of the Cartesian product A \times B.[12] This formulation captures the idea that the relation specifies which elements of A are connected to which elements of B through selected ordered pairs.[1] Equivalently, R can be described as the collection of all ordered pairs (a, b) with a \in A and b \in B such that a is related to b by R.[1] The standard notation R \subseteq A \times B emphasizes this set-theoretic foundation, while R: A \to B is often used to indicate the relation's direction from A to B.[12][13]Domain, Codomain, and Field
In the context of a binary relation R \subseteq A \times B, the codomain of R is the set B, which serves as the target set for the elements related by R.[14] The domain of R, denoted \dom(R), is the subset of A consisting of all elements a \in A such that there exists at least one b \in B with (a, b) \in R; formally, \dom(R) = \{ a \in A \mid \exists b \in B \text{ such that } (a, b) \in R \}. This captures the elements from the source set that participate in the relation. The range or image of R, denoted \im(R), is the subset of the codomain B consisting of all elements b \in B that are related to at least one a \in A; formally, \im(R) = \{ b \in B \mid \exists a \in A \text{ such that } (a, b) \in R \}. Unlike the codomain, which is fixed by the ambient Cartesian product, the range identifies the actual elements in B that are "reached" by R, and it is always a subset of B. The field of R, denoted \field(R), is the union of the domain and the range: \field(R) = \dom(R) \cup \im(R). This set encompasses all elements from either A or B that appear in at least one pair of R. For the empty relation \emptyset \subseteq A \times B, both the domain and range are empty sets, so \dom(\emptyset) = \emptyset and \im(\emptyset) = \emptyset, with the field also empty.[15] In contrast, the full relation R = A \times B has domain equal to the entire source set A and range equal to the entire codomain B, so \dom(R) = A and \im(R) = B, making the field A \cup B.[16] The domain and range can be computed using existential projections from the pairs in R. The domain is the first-coordinate projection \pi_1(R) = \{ x \mid \exists y \ (x, y) \in R \}, while the range is the second-coordinate projection \pi_2(R) = \{ y \mid \exists x \ (x, y) \in R \}. These projections provide a set-theoretic mechanism to extract the active elements without enumerating all pairs.[16]Visual Representations
Binary relations are often visualized using graphical and diagrammatic methods to provide intuitive insights into their structure and facilitate analysis. These representations emphasize the connections between elements without delving into computational operations. A primary visual tool is the arrow diagram, which depicts a binary relation R \subseteq A \times B by arranging elements of the domain A on the left and the codomain B on the right, with directed arrows from a \in A to b \in B if (a, b) \in R.[17] This bipartite directed graph layout highlights the mapping from domain to codomain, making it straightforward to identify the range of related elements.[18] For homogeneous binary relations where A = B, the arrow diagram simplifies to a directed graph, or digraph, with vertices representing the elements of A and directed edges indicating related pairs.[13] In this representation, each vertex corresponds to an element, and an edge from x to y signifies x R y, allowing for a compact view of intra-set connections.[19] Another key representation is the incidence matrix, a rectangular binary matrix where rows index elements of A, columns index elements of B, and the entry m_{ij} = 1 if the corresponding pair is in R, otherwise 0.[20] For instance, consider the "less than" relation R = \{ (1,2), (1,3), (2,3) \} on the set \{1, 2, 3\}; its incidence matrix is:| 1 | 2 | 3 | |
|---|---|---|---|
| 1 | 0 | 1 | 1 |
| 2 | 0 | 0 | 1 |
| 3 | 0 | 0 | 0 |