Relations

Precise definition

A binary relation $R$ from $A$ to $B$ is a subset of $A\times B$; write $aRb$ when $(a,b)\in R$. A relation on $A$ is reflexive if $aRa$ for all $a$, symmetric if $aRb\Rightarrow bRa$, antisymmetric if $aRb$ and $bRa$ imply $a=b$, and transitive if $aRb$ and $bRc$ imply $aRc$.

Notation and mathematical language

An equivalence relation is reflexive, symmetric, and transitive; it partitions $A$ into equivalence classes $[a]=\{x:xRa\}$. A partial order is reflexive, antisymmetric, and transitive. Symmetric and antisymmetric are not opposites: equality satisfies both.

Conceptual picture

A relation is a selected set of arrows between elements. Matrices and directed graphs display finite relations; property tests become patterns involving loops, reversed arrows, and completed two-step paths. Equivalence classes group indistinguishable elements under the chosen criterion.

Conditions and key results

Every property is relative to the stated underlying set. To disprove a universal property, one counterexample pair or triple suffices; to prove it, use arbitrary elements. Transitivity concerns composable pairs, and antisymmetry allows $aRa$—it only restricts distinct elements linked both ways.

A reliable strategy

1. State the underlying set and give the relation by rule, ordered pairs, matrix, or digraph.
2. Translate each requested property into its quantified definition.
3. Prove a property with arbitrary elements or refute it with an explicit legal counterexample.
4. If the relation is an equivalence or order, compute classes or draw the Hasse-style structure as an independent check.

Fully worked example

Interpretation and application

Relations model prerequisites, database links, rankings, congruence, and state reachability. A partial order may leave elements incomparable; interpreting it as a complete ranking adds information the relation does not contain.

Common mistakes

Verification and reasonableness

• For finite relations, enumerate all loops, reversed pairs, and length-two paths from the ordered-pair list.
• Check equivalence classes are disjoint or identical and their union is the whole set.
• Use a concrete counterexample with all elements in the domain when a property fails.

Practice

1. Is $\le$ on integers symmetric?
2. Is equality an equivalence relation?
3. What are the equivalence classes modulo 2?

Further deduction

An equivalence relation creates a quotient set $A/R=\{[a]:a\in A\}$. Although many representatives name the same class, classes are either identical or disjoint. A partial order instead organizes comparison; its Hasse diagram omits reflexive loops and edges implied by transitivity. Those omissions are conventions for display, not missing relation pairs. Confusing an equivalence partition with an order hierarchy obscures the different roles of symmetry and antisymmetry. For example, divisibility on positive integers is a partial order: it is reflexive and transitive, and mutual divisibility forces equality. Numbers such as 2 and 3 are incomparable, demonstrating why a partial order need not be a total order.

The inverse relation $R^{-1}$ reverses every ordered pair, while composition $S\circ R$ links $a$ to $c$ when some intermediate $b$ satisfies $aRb$ and $bSc$. These operations resemble inverse functions and composition but remain valid for many-to-many relations.

Related topics

• Set Operations
• Functions in Discrete Mathematics
• Graphs and Networks