binaryrelational

Binary relation is a basic concept in set theory and logic that describes a relationship between elements of sets. Formally, if A and B are sets, a binary relation R from A to B is a subset of the Cartesian product A × B. An element a ∈ A is related to b ∈ B by R if and only if (a, b) ∈ R, often written as aRb. When the two sets coincide (A = B), R is a relation on A.

Common properties of binary relations help classify them. A relation is reflexive if every element relates to itself, symmetric if aRb implies bRa, and transitive if aRb and bRc imply aRc. A relation that is antisymmetric satisfies that aRb and bRa imply a = b. Irreflexive means no element relates to itself. Equivalence relations are reflexive, symmetric, and transitive, and they partition the underlying set into equivalence classes. Partial orders are reflexive, antisymmetric, and transitive, providing a notion of comparison.

Relations can be specialized. A function is a relation in which every input is related to exactly one output; a partial or total function relaxes or extends this requirement. The inverse relation R−1 consists of all pairs (b, a) with aRb, and the composition of relations connects chains of relations across sets.

Graphically, a binary relation can be represented by a directed graph, where vertices are elements of the domain and edges a → b indicate aRb. In matrix form, R is represented by a boolean adjacency matrix. Binary relations underpin many areas, including order theory, algebra, database theory, and logic, where they model connections, equivalence, and precedence.