Looking for Structure inside a Relation

A relation is a set of ordered pairs.

But two relations can contain very different patterns even when they are defined on the same set.

Suppose \(R\) is a relation on

\[ A=\{1,2,3\}. \]

One relation might contain

\[ (1,1),(2,2),(3,3), \]

while another might contain

\[ (1,2),(2,3),(1,3). \]

The first pattern suggests that every element is related to itself. The second suggests a chain of relationships that carries through from \(1\) to \(3\).

Mathematicians give names to these recurring patterns: reflexive, symmetric, antisymmetric, and transitive.

These properties are not labels for decoration. They tell us how a relation behaves and what kinds of mathematical structures it can produce.

Relations on a Set

A relation on a set \(A\) is a subset of

\[ A\times A. \]

That means both components of every ordered pair come from the same set.

For example, if

\[ A=\{1,2,3\}, \]

then

\[ R=\{(1,1),(1,2),(2,2),(3,3)\} \]

is a relation on \(A\).

Once a relation is defined on one set, we can ask structural questions such as:

Those questions define the main relation properties.

Reflexive Relations

A relation \(R\) on \(A\) is reflexive when every element of \(A\) is related to itself.

\[ \boxed{ \forall a\in A,\quad (a,a)\in R } \]

In relation notation,

\[ aRa \]

must be true for every \(a\in A\).

Example

Let

\[ A=\{1,2,3\} \]

and

\[ R=\{(1,1),(2,2),(3,3),(1,2)\}. \]

Because all three required self-pairs appear,

\[ (1,1),\quad(2,2),\quad(3,3), \]

the relation is reflexive.

Equality Is Reflexive

The equality relation is reflexive because every object equals itself:

\[ a=a. \]

So if \(R\) means “is equal to,” then

\[ aRa \]

always holds.

One Missing Pair Is Enough to Fail

If

\[ A=\{1,2,3\} \]

but

\[ (3,3)\notin R, \]

then \(R\) is not reflexive.

Reflexivity requires the property for every element.

Symmetric Relations

A relation \(R\) on \(A\) is symmetric when every related pair can be reversed.

\[ \boxed{ (a,b)\in R \implies (b,a)\in R } \]

Example

Let

\[ R=\{(1,2),(2,1),(2,3),(3,2)\}. \]

Every pair appears together with its reverse, so the relation is symmetric.

Friendship as an Idealized Example

If a relation means “is friends with,” and friendship is treated as mutual, then

\[ aRb \]

implies

\[ bRa. \]

That is symmetric behavior.

Less Than Is Not Symmetric

If

\[ 3<7, \]

then it is not true that

\[ 7<3. \]

So the relation “is less than” is not symmetric.

Antisymmetric Relations

A relation \(R\) on \(A\) is antisymmetric when two different elements cannot be related in both directions.

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

This definition is easy to misread.

Antisymmetric does not mean “not symmetric.”

It means that if a pair and its reverse are both present, then the two components must actually be the same element.

Example: Less Than or Equal To

The relation

\[ \leq \]

is antisymmetric.

If

\[ a\leq b \]

and

\[ b\leq a, \]

then necessarily

\[ a=b. \]

A Relation Can Be Both Symmetric and Antisymmetric

Equality is both symmetric and antisymmetric.

If \(a=b\), then certainly \(b=a\), so equality is symmetric.

And if \(a=b\) and \(b=a\), the two elements are equal, so the antisymmetric condition is also satisfied.

This is why “antisymmetric” should never be interpreted as the simple opposite of symmetric.

Transitive Relations

A relation \(R\) is transitive when a relationship can pass through an intermediate element.

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

Example: Less Than

If

\[ 2<5 \]

and

\[ 5<9, \]

then

\[ 2<9. \]

So “is less than” is transitive.

Example: Divisibility

Suppose \(a\mid b\) means “\(a\) divides \(b\).”

If

\[ a\mid b \]

and

\[ b\mid c, \]

then

\[ a\mid c. \]

Divisibility is therefore transitive.

A Nonexample

The relation “is one year older than” is not transitive.

If Alice is one year older than Ben and Ben is one year older than Cara, then Alice is two years older than Cara, not one year older.

Testing Relation Properties

When a relation is given as a finite set of ordered pairs, a systematic check is useful.

To Test Reflexivity

For every \(a\in A\), check that

\[ (a,a)\in R. \]

To Test Symmetry

For every pair

\[ (a,b)\in R, \]

check whether

\[ (b,a)\in R. \]

To Test Antisymmetry

Look for two distinct elements \(a\neq b\) such that both

\[ (a,b)\in R \]

and

\[ (b,a)\in R. \]

If such a pair exists, antisymmetry fails.

To Test Transitivity

Look for chains

\[ (a,b)\in R \]

and

\[ (b,c)\in R. \]

Whenever such a chain occurs, check that

\[ (a,c)\in R. \]

One failed chain is enough to show that the relation is not transitive.

Equivalence Relations

An equivalence relation is a relation that is

Symbolically, \(R\) is an equivalence relation when all three conditions hold:

\[ aRa, \] \[ aRb\implies bRa, \]

and

\[ aRb\text{ and }bRc\implies aRc. \]

Why These Three?

Together, these properties make the relation behave like a generalized form of “being the same in some specified way.”

The objects need not be literally equal. They only need to be equivalent according to the feature we care about.

Example: Same Parity

Define a relation on the integers by

\[ aRb \iff a\text{ and }b\text{ have the same parity}. \]

That means they are both even or both odd.

This relation is reflexive because every integer has the same parity as itself.

It is symmetric because if \(a\) has the same parity as \(b\), then \(b\) has the same parity as \(a\).

It is transitive because if \(a\) has the same parity as \(b\), and \(b\) has the same parity as \(c\), then \(a\) and \(c\) have the same parity.

Therefore, “has the same parity as” is an equivalence relation.

Equivalence Classes

Once we have an equivalence relation, each element belongs to an equivalence class.

The equivalence class of \(a\) is the set of all elements related to \(a\):

\[ \boxed{ [a] = \{x\in A\mid xRa\} } \]

Same-Parity Classes

For the same-parity relation on \(\mathbb{Z}\), the class of \(0\) is

\[ [0] = \{\ldots,-4,-2,0,2,4,\ldots\}, \]

the even integers.

The class of \(1\) is

\[ [1] = \{\ldots,-3,-1,1,3,5,\ldots\}, \]

the odd integers.

There are only two distinct equivalence classes.

Equivalent Elements Have the Same Class

If

\[ aRb, \]

then

\[ [a]=[b]. \]

For example,

\[ [2]=[8] \]

under same parity because both represent the class of all even integers.

Different Classes Do Not Overlap

For an equivalence relation, two equivalence classes are either identical or disjoint.

They cannot partially overlap.

That fact is what connects equivalence relations with partitions.

Equivalence Relations and Partitions

A partition of a set divides it into nonempty pieces so that

Equivalence classes automatically form a partition of the underlying set.

For same parity on the integers, the partition is

\[ \mathbb{Z} = E\cup O, \]

where

\[ E=\{\text{even integers}\} \]

and

\[ O=\{\text{odd integers}\}. \]

Also,

\[ E\cap O=\varnothing. \]

Every integer belongs to exactly one of these two classes.

The Reverse Direction

A partition can also define an equivalence relation.

If a set has been divided into nonoverlapping groups, define

\[ aRb \]

to mean that \(a\) and \(b\) belong to the same group.

That relation will be reflexive, symmetric, and transitive.

So equivalence relations and partitions describe the same structural idea from two different directions.

Congruence Modulo \(n\)

One of the most important equivalence relations in mathematics is congruence modulo \(n\).

For a positive integer \(n\), we write

\[ a\equiv b\pmod n \]

when \(a\) and \(b\) leave the same remainder upon division by \(n\).

Equivalently,

\[ n\mid(a-b). \]

Example Modulo \(3\)

Because

\[ 8-2=6 \]

and

\[ 3\mid6, \]

we have

\[ 8\equiv2\pmod3. \]

Modulo \(3\), every integer belongs to one of three equivalence classes:

\[ [0],\qquad[1],\qquad[2]. \]

These may be represented as

\[ [0]=\{\ldots,-6,-3,0,3,6,\ldots\}, \] \[ [1]=\{\ldots,-5,-2,1,4,7,\ldots\}, \]

and

\[ [2]=\{\ldots,-4,-1,2,5,8,\ldots\}. \]

Every integer belongs to exactly one residue class modulo \(3\).

Why Congruence Is an Equivalence Relation

It is reflexive because

\[ a-a=0 \]

is divisible by \(n\).

It is symmetric because if

\[ n\mid(a-b), \]

then

\[ n\mid(b-a). \]

It is transitive because if

\[ n\mid(a-b) \]

and

\[ n\mid(b-c), \]

then adding the differences gives

\[ n\mid(a-c). \]

So congruence modulo \(n\) fits the equivalence-relation structure exactly.

A Preview of Order Relations

Equivalence relations use the combination

\[ \text{reflexive}+\text{symmetric}+\text{transitive}. \]

Another important family uses

\[ \text{reflexive}+\text{antisymmetric}+\text{transitive}. \]

This leads to partial orders.

For example, the relation

\[ \leq \]

on the real numbers is reflexive, antisymmetric, and transitive.

Likewise, set inclusion

\[ \subseteq \]

is reflexive, antisymmetric, and transitive.

We will develop order relations separately, but the comparison is worth noticing now:

\[ \boxed{ \begin{aligned} \text{equivalence} &: \text{ reflexive + symmetric + transitive},\\ \text{order} &: \text{ reflexive + antisymmetric + transitive}. \end{aligned} } \]

Practical Applications

Grouping Records by a Shared Attribute

Suppose customer records are considered equivalent when they share the same account identifier.

That equivalence relation groups all matching records into one class.

Each equivalence class can then be treated as representing one underlying customer.

File Types

Files can be grouped according to a chosen equivalence criterion such as having the same extension.

Then all .html files form one class, all .css files another, and so on.

Geometry

Geometric figures can be grouped under relations such as congruence or similarity.

When the required properties are satisfied, equivalence classes let us talk about entire families of shapes that are “the same” in the relevant sense.

Modular Scheduling

Clock arithmetic is modular arithmetic.

On a 12-hour clock,

\[ 14\equiv2\pmod{12}. \]

The numbers \(14\) and \(2\) represent the same clock position modulo \(12\).

Computer Science

Equivalence relations appear in state reduction, compiler analysis, partitioning algorithms, graph processing, and classification systems.

The general strategy is valuable: identify objects that behave the same for the purpose at hand, then work with the resulting classes instead of every individual object separately.

Worked Examples

Example 1: Testing Reflexivity

Let

\[ A=\{1,2,3\} \]

and

\[ R=\{(1,1),(2,2),(3,3),(1,2)\}. \]

All self-pairs are present:

\[ (1,1),(2,2),(3,3). \]

Therefore \(R\) is reflexive.

Example 2: Testing Symmetry

Let

\[ R=\{(1,2),(2,1),(2,3)\}. \]

The pair

\[ (2,3) \]

appears, but

\[ (3,2) \]

does not.

Therefore \(R\) is not symmetric.

Example 3: Testing Antisymmetry

Let

\[ R=\{(1,1),(2,2),(1,2)\}. \]

There is no pair of distinct elements \(a\neq b\) for which both \((a,b)\) and \((b,a)\) appear.

Therefore \(R\) is antisymmetric.

Example 4: Testing Transitivity

Let

\[ R=\{(1,2),(2,3),(1,3)\}. \]

The chain

\[ (1,2),(2,3) \]

requires

\[ (1,3), \]

and that pair is present.

No other required chain fails, so the relation is transitive.

Example 5: Same Remainder Modulo \(4\)

Define

\[ aRb \iff a\equiv b\pmod4. \]

Then

\[ 6R10 \]

because

\[ 10-6=4 \]

is divisible by \(4\).

The equivalence class of \(2\) is

\[ [2] = \{\ldots,-6,-2,2,6,10,14,\ldots\}. \]

Example 6: Equality as an Equivalence Relation

Equality is reflexive:

\[ a=a. \]

It is symmetric:

\[ a=b\implies b=a. \]

It is transitive:

\[ a=b \text{ and } b=c \implies a=c. \]

Therefore equality is an equivalence relation.

Common Errors

1. Confusing Symmetric with Antisymmetric

Symmetric means

\[ (a,b)\in R\implies(b,a)\in R. \]

Antisymmetric means

\[ (a,b),(b,a)\in R\implies a=b. \]

These are different conditions.

2. Thinking Antisymmetric Means “Not Symmetric”

A relation may be both symmetric and antisymmetric.

Equality is the standard example.

3. Checking Reflexivity Only for Elements That Appear Elsewhere

Reflexivity depends on the entire underlying set \(A\), not just the elements that happen to appear in non-diagonal pairs.

4. Checking Only One Transitive Chain

Every possible chain

\[ (a,b),(b,c) \]

must produce

\[ (a,c). \]

One successful chain does not prove transitivity.

5. Assuming Equivalence Means Equality

Equivalent objects need not be identical.

They are considered the same only with respect to the chosen relation.

6. Forgetting That Equivalence Classes Are Sets

The notation

\[ [a] \]

represents a set of all elements equivalent to \(a\), not just the single element \(a\).

Practice

Property Testing

Let

\[ A=\{1,2,3\} \]

and

\[ R= \{(1,1),(2,2),(3,3),(1,2),(2,1)\}. \]

Determine whether \(R\) is:

  1. reflexive,
  2. symmetric,
  3. antisymmetric,
  4. transitive.
Check Answers
  1. Reflexive: yes. All three self-pairs are present.
  2. Symmetric: yes. The only non-diagonal pair \((1,2)\) has its reverse \((2,1)\).
  3. Antisymmetric: no. Both \[ (1,2) \] and \[ (2,1) \] appear even though \[ 1\neq2. \]
  4. Transitive: yes. The available chains produce pairs already in the relation.

Equivalence Relation Practice

On the integers, define

\[ aRb \iff a-b\text{ is even}. \]

Is \(R\) an equivalence relation?

Check Answer

Yes.

Reflexive:

\[ a-a=0 \]

is even.

Symmetric: if \(a-b\) is even, then

\[ b-a=-(a-b) \]

is also even.

Transitive: if \(a-b\) and \(b-c\) are even, then

\[ (a-b)+(b-c)=a-c \]

is even.

Therefore \(R\) is an equivalence relation.

Equivalence Classes

For congruence modulo \(5\), list the five equivalence classes by a standard representative.

Check Answer \[ [0],[1],[2],[3],[4]. \]

Every integer belongs to exactly one of these five classes.

The Deeper Idea

Relation properties let us move from isolated ordered pairs to reusable mathematical structures.

Reflexivity, symmetry, antisymmetry, and transitivity describe how a relation behaves across an entire set.

When reflexivity, symmetry, and transitivity occur together, the relation groups objects into equivalence classes.

Those classes form a partition:

\[ \boxed{ \text{equivalence relation} \longleftrightarrow \text{partition into equivalence classes} } \]

This is a powerful organizing idea. Instead of treating every object separately, mathematics can identify which objects are equivalent for the problem at hand and work with the classes themselves.

The same strategy appears later in modular arithmetic, abstract algebra, geometry, topology, computer science, and quotient structures.

Summary

Equivalence relations formalize the idea that different objects may be treated as the same for a particular purpose. Their equivalence classes turn that idea into a precise partition of the underlying set.

Sets, Relations, and Functions