1 Definition and basic concepts
A relation in algebra is a way of pairing elements from one set with elements of another set, or with elements of the same set. It is a broad concept used to describe association, comparison, and structure. Unlike a function, a relation does not require each input to match a single output, so it can model many kinds of mathematical connections.
Relations are typically written as sets of ordered pairs. This makes them precise enough for algebraic study while remaining flexible enough to describe equality, divisibility, preference, correspondence, and many other patterns. Because of this generality, relations form an important foundation for later ideas such as equivalence relations, partial orders, and functions.
1.1 Ordered pairs
An ordered pair is a pair of elements written in a fixed order, usually as \((a, b)\). The order matters: \((a, b)\) is generally different from \((b, a)\) unless \(a = b\). Ordered pairs are the basic building blocks of relations because they record which element is associated with which.
In a relation, each ordered pair shows a connection from a first element to a second element. For example, the pair \((2, 5)\) may indicate that 2 is related to 5 in a particular way, such as being less than, dividing, or being connected by a rule. The meaning depends on the relation being studied.
1.2 Sets and Cartesian products
A set is a collection of distinct objects, called elements. To define relations rigorously, one often begins with two sets, say \(A\) and \(B\). The Cartesian product \(A \times B\) is the set of all ordered pairs \((a, b)\) where \(a \in A\) and \(b \in B\).
A relation from \(A\) to \(B\) is any subset of \(A \times B\). This means a relation selects some of the possible pairs and excludes others. If \(A = B\), the relation is said to be on the set \(A\). Such relations are especially important because they can compare elements within a single system.
1.3 Binary relations
A binary relation is a relation involving two elements at a time. In set-theoretic language, it is a subset of a Cartesian product \(A \times B\), and when \(A = B\), it relates elements of one set to itself. Many familiar mathematical relations, such as \(=\), \(<\), and divides, are binary relations.
The term binary refers to the fact that the relation links two objects in each pair. Higher-arity relations, which involve more than two elements, also exist, but binary relations are the most common in elementary algebra and discrete mathematics.
1.4 Domain, codomain, and range
For a relation from \(A\) to \(B\), the domain is the set of all first elements that appear in some ordered pair of the relation. The codomain is the set \(B\), the target set in which second elements are chosen. The range, sometimes called the image, is the set of all second elements that actually occur in the relation.
These notions help describe how widely a relation is used on the source set and how much of the target set it reaches. A relation may have a domain smaller than its starting set if some elements are not related to anything, and its range may be smaller than its codomain if not every target element is used.
2 Representations of relations
Relations can be represented in several equivalent ways. The choice of representation depends on the context and the size of the sets involved. Some forms emphasize exact membership, while others make visual patterns or structural properties easier to see.
2.1 Set notation
In set notation, a relation is written as a set of ordered pairs. For instance, a relation \(R\) on a set \(A\) might be listed as \(R = \{(a, b), (c, d), (e, f)\}\). This notation is direct and unambiguous, making it useful for proofs and formal definitions.
Set notation is especially convenient when a relation has only a few pairs. It also allows one to verify properties such as symmetry or transitivity by examining the listed pairs. When the set is large, however, other representations may be easier to interpret.
2.2 Arrow diagrams
An arrow diagram shows elements of the domain and codomain as points, with arrows drawn from each first element to its related second element. This picture gives an immediate sense of how elements correspond. Multiple arrows may leave one element, and some elements may have none.
Arrow diagrams are useful for small finite relations. They visually display whether a relation is one-sided, reciprocal, or clustered around certain elements. They are especially helpful in introductory study because they connect symbolic definitions with an intuitive image.
2.3 Graphical representation
A relation on a set can also be shown as a directed graph, where the elements are vertices and each ordered pair is a directed edge. If \((a, b)\) belongs to the relation, then there is an arrow from \(a\) to \(b\). When the relation is on a single set, this graph is often called a directed graph or digraph.
Graphical representation highlights structural features such as loops, cycles, and mutual connections. It is commonly used to study order relations, equivalence relations, and networks. The visual form can reveal properties that are less obvious in a plain list of pairs.
2.4 Matrix representation
A relation on a finite set can be represented by a matrix whose entries indicate whether a pair is included in the relation. This method is compact and useful for computation. Typically, rows and columns correspond to elements of the set, and a chosen entry records the presence or absence of a connection.
Matrix representations are widely used because they translate relations into algebraic objects that can be manipulated systematically. They are especially convenient in computer applications and in proofs involving finite structures.
2.4.1 Adjacency matrices
An adjacency matrix is a square matrix used to represent a relation on a finite set. If the element in row \(i\) and column \(j\) is 1, then the pair \((i, j)\) belongs to the relation; if it is 0, the pair does not belong.
This form is closely tied to directed graphs. Each row indicates the outgoing connections from one element, while each column indicates incoming connections to another. Adjacency matrices are useful for checking properties and for performing calculations related to paths and composition.
2.4.2 Incidence matrices
An incidence matrix represents how elements are connected to relation pairs or edges. In a relation context, it may be used to record which elements participate in which ordered pairs. The exact form depends on the convention used, but the basic goal is to encode participation in a matrix format.
Incidence matrices are less direct than adjacency matrices for ordinary binary relations, yet they are valuable in broader combinatorial settings. They are often used when the structure being studied involves both elements and connections as separate objects.
3 Properties of relations
Relations are classified by formal properties that describe how elements are connected. These properties are central because they determine the behavior of the relation and its role in more advanced structures. A relation may have none, some, or all of these properties.
3.1 Reflexive relations
A relation on a set is reflexive if every element is related to itself. In symbols, \(aRa\) holds for every element \(a\) in the set. Reflexivity means that each object has a self-connection.
The equality relation is reflexive, as every element equals itself. Many order-like relations also have this property. Reflexivity is often used as a baseline condition when analyzing relations on a single set.
3.2 Symmetric relations
A relation is symmetric if whenever \(a\) is related to \(b\), then \(b\) is also related to \(a\). In other words, the relation goes both ways between any related pair. Symmetry describes mutual connection.
An example is the relation of having the same parity, since if one number has the same parity as another, the reverse is also true. Symmetric relations are common in equivalence-type settings, where direction does not matter.
3.3 Antisymmetric relations
A relation is antisymmetric if whenever \(a\) is related to \(b\) and \(b\) is related to \(a\), then \(a\) and \(b\) must be the same element. This property allows two-way links only in the trivial case of identical elements.
The usual less-than-or-equal-to relation is antisymmetric. If \(a \leq b\) and \(b \leq a\), then \(a = b\). Antisymmetry is important in partial orders because it prevents distinct elements from being indistinguishable under the relation.
3.4 Asymmetric relations
A relation is asymmetric if whenever \(a\) is related to \(b\), \(b\) is not related to \(a\). This is a stronger condition than antisymmetry. In an asymmetric relation, no pair of distinct elements can be related in both directions, and no element can be related to itself.
The less-than relation \(<\) is asymmetric. If \(a < b\), then it is impossible for \(b < a\). Asymmetric relations often describe strict orderings.
3.5 Transitive relations
A relation is transitive if whenever \(a\) is related to \(b\) and \(b\) is related to \(c\), then \(a\) is related to \(c\). This property allows a chain of two links to imply a direct link.
Transitivity appears in many familiar examples, including equality, divisibility, and ordering relations. It is one of the most important properties in algebra because it supports consistent chaining of comparisons and classifications.
3.6 Irreflexive relations
A relation is irreflexive if no element is related to itself. Thus, \(aRa\) fails for every element \(a\) in the set. Irreflexivity is the opposite of reflexivity in the strict sense.
The relation \(<\) on numbers is irreflexive because no number is less than itself. Irreflexive relations are often paired with transitivity, especially in strict order settings.
4 Types of relations
Certain relations have special names because they satisfy characteristic patterns. These types appear repeatedly in algebra and related fields. They often serve as building blocks for more elaborate mathematical structures.
4.1 Empty relation
The empty relation contains no ordered pairs at all. It is a relation on any set because the empty set is a subset of every Cartesian product. Since it has no pairs, it vacuously satisfies some properties, such as symmetry and transitivity, depending on the definitions involved.
The empty relation is useful as a minimal example. It shows that a relation need not connect any elements in order to be formally valid.
4.2 Universal relation
The universal relation on a set contains every possible ordered pair from the Cartesian product of the set with itself. In other words, every element is related to every other element, including itself.
This relation is maximally inclusive. It is reflexive, symmetric, and transitive, though it is generally not antisymmetric unless the set has only one element. It serves as an extreme opposite of the empty relation.
4.3 Identity relation
The identity relation on a set consists of all pairs \((a, a)\) for elements \(a\) in the set. It relates each element only to itself and to nothing else.
This relation is both reflexive and antisymmetric, and it is also symmetric and transitive. Because of its simplicity, the identity relation often serves as a neutral or baseline example in relation theory.
4.4 Equivalence relations
An equivalence relation is a relation that is reflexive, symmetric, and transitive. Such a relation groups elements into classes of mutually related objects. The essential idea is that elements within the same class are considered equivalent under the relation.
Equivalence relations are central in algebra because they allow one to treat different objects as effectively the same for a given purpose. Examples include congruence modulo a number and equality of certain algebraic properties.
4.4.1 Equivalence classes
An equivalence class is the set of all elements equivalent to a given element under an equivalence relation. Every element belongs to exactly one equivalence class. The class of an element captures its entire equivalence group.
Equivalence classes simplify a set by collecting related elements into blocks. Once the classes are formed, reasoning can often shift from individual elements to the structure of the collection.
4.4.2 Partition of a set
A partition of a set is a division of the set into nonempty, disjoint subsets whose union is the whole set. Every equivalence relation determines a partition into equivalence classes, and every partition gives rise to an equivalence relation.
This connection is fundamental. It shows that grouping by equivalence and splitting into parts are two sides of the same idea. Partitions therefore provide a concrete way to visualize equivalence relations.
4.5 Partial orders
A partial order is a relation that is reflexive, antisymmetric, and transitive. It describes a structure in which some elements can be compared, but not necessarily every pair. Thus, the order may be only partial rather than complete.
Partial orders appear in divisibility, subset inclusion, and many algebraic hierarchies. They organize elements into a system where some are comparable and others are not.
4.5.1 Total orders
A total order is a partial order in which every pair of elements is comparable. For any two elements \(a\) and \(b\), either \(a \leq b\) or \(b \leq a\) holds. This makes the ordering complete across the set.
The usual ordering of numbers is a total order. Total orders are easier to visualize than partial orders because no pair remains incomparable.
4.5.2 Well-orders
A well-order is a total order with the additional property that every nonempty subset has a least element. This property is stronger than totality and is especially useful in proofs and constructions involving induction.
The natural numbers with their usual order form a well-order. Well-orders are significant because they guarantee a starting point in every nonempty collection.
5 Operations on relations
Relations can be combined and transformed in several ways. These operations produce new relations from existing ones and help reveal structural patterns. They are important in both theory and computation.
5.1 Inverse relation
The inverse of a relation is formed by reversing each ordered pair. If \((a, b)\) is in the relation, then \((b, a)\) is in its inverse. This operation reverses the direction of association.
If a relation is symmetric, it equals its own inverse. In general, the inverse provides a way to study the same information from the opposite perspective.
5.2 Composition of relations
The composition of relations combines two relations in sequence. If one relation connects \(a\) to \(b\) and another connects \(b\) to \(c\), then their composition connects \(a\) to \(c\). This is analogous to following a path through intermediate elements.
Composition is a key operation because it captures indirect connection. It also mirrors function composition, though relations are more general and may produce multiple results.
5.3 Union and intersection of relations
The union of two relations contains every ordered pair that appears in either relation. The intersection contains only those pairs that appear in both. These operations follow the usual set-theoretic meanings.
Union combines connection patterns, while intersection isolates common structure. They are useful for comparing relations and building new ones from existing components.
5.4 Complement of a relation
The complement of a relation, relative to a chosen Cartesian product, contains all ordered pairs not in the relation. In effect, it reverses membership: what was included is excluded, and what was excluded is included.
Complements are meaningful only with respect to a fixed underlying set product. They are helpful when studying what a relation does not connect, as well as what it does.
5.5 Power of a relation
The power of a relation refers to repeated composition of the relation with itself. The second power is the relation composed with itself once, the third power is composed twice, and so on. These powers describe paths of increasing length.
Relation powers are useful in graph theory and in studying reachability. They show how indirect connections develop through repeated steps.
6 Relations and functions
Functions are special kinds of relations. Studying them within the broader framework of relations clarifies what makes a function distinct and what behavior is allowed more generally. This comparison is one of the most useful aspects of relation theory.
6.1 Relation as a generalization of function
A relation generalizes a function because it allows one input to be associated with none, one, or many outputs. A function imposes stricter rules: each input must correspond to exactly one output. Every function is a relation, but not every relation is a function.
This broader viewpoint helps explain why functions have additional properties and why relations are often introduced first. Relations provide the underlying language from which functions can be selected as a special case.
6.2 One-to-one relations
A one-to-one relation, in an informal sense, is a relation in which each first element is paired with at most one second element and each second element with at most one first element. This pattern resembles a bijective matching, though relations do not require the full conditions of a function.
Such relations are useful when connections are uniquely matched in both directions. They occur in pairings, correspondences, and matching problems.
6.3 Many-to-one and one-to-many relations
A many-to-one relation allows several first elements to be related to the same second element. A one-to-many relation allows one first element to be related to several second elements. These patterns are common in ordinary relations and distinguish them from functions in different ways.
Many-to-one and one-to-many behavior makes relations flexible. A single set of objects can be linked in multiple directions, which is useful in classification, comparison, and network descriptions.
6.4 Functional relations
A functional relation is a relation that satisfies the rule of a function: each input is related to exactly one output. In this sense, every function is a functional relation. The term emphasizes the relation-theoretic viewpoint while preserving the defining uniqueness condition.
Functional relations bridge relation theory and function theory. They make it clear that functions are not separate from relations but rather a special, highly structured kind of relation.
7 Applications and examples
Relations appear throughout algebra and related branches of mathematics. They provide a language for describing structure in finite systems, numerical patterns, algebraic operations, and computational models. Their versatility makes them a standard tool in both theory and application.
7.1 Relations on finite sets
On a finite set, a relation can be fully listed, drawn, or encoded in a matrix. This makes finite relations especially easy to study. Properties such as reflexivity and transitivity can be checked directly from the data.
Finite relations often serve as examples and counterexamples. Because all elements can be examined one by one, they are ideal for learning how abstract definitions work in practice.
7.2 Relations on numbers
Relations on numbers include equality, inequality, divisibility, and congruence. These relations illustrate many important properties of relation theory. For instance, equality is an equivalence relation, less-than is a strict order, and divisibility is a partial order on positive integers.
Number relations are among the most familiar examples because their meanings are concrete and easy to test. They are also central to algebraic reasoning and proof.
7.3 Relations in algebraic structures
In algebraic structures, relations help describe when elements behave similarly or when one element is subordinate to another under a given rule. They can encode equivalence between expressions, order among substructures, or compatibility with operations.
Relations are also used to build quotient structures by grouping elements into equivalence classes. This process is important in many areas of algebra because it reduces complex systems to simpler ones while preserving essential information.
7.4 Relations in computer science
In computer science, relations are used to model databases, networks, state transitions, and dependency structures. A table in a relational database can be viewed as a relation in the mathematical sense, with rows corresponding to ordered tuples of data.
Relations also appear in algorithm design and discrete structures. Directed graphs, reachability, scheduling, and matching problems all use relational ideas. Because relations are flexible and computationally tractable, they are a natural fit for formal systems and data organization.