✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-MAT-AALG-004

Relations and Equivalence Relations

A relation describes how elements of one set are connected to elements of another set or to elements of the same set. An equivalence relation is a special relation that is reflexive, symmetric and transitive, allowing elements to be grouped according to a shared mathematical property.

a ~ b ⇔ (a, b) ∈ R

Explanation

Definition of a relation: A binary relation R from a set A to a set B is a subset of the Cartesian product A × B. When A = B, it is called a relation on A.

Ordered pairs: If (a, b) belongs to R, we say that a is related to b and may write a R b.

Reflexivity: A relation R on A is reflexive if every element is related to itself. Formally, a R a for all a ∈ A.

Symmetry: A relation is symmetric if a R b implies b R a for all a, b ∈ A.

Transitivity: A relation is transitive if a R b and b R c together imply a R c.

Equivalence relation: A relation is an equivalence relation precisely when it satisfies reflexivity, symmetry and transitivity.

Equivalence classes: For an element a, its equivalence class contains all elements related to a. Equivalence classes are central to constructing quotient sets and quotient algebraic structures.

Not every relation is an equivalence relation. For example, the usual less-than relation is transitive but is not reflexive or symmetric.

Example or application

A worked example has not yet been added.

Axioms

NameCondition

Reflexivity

a ~ a for every a ∈ A.

Symmetry

If a ~ b, then b ~ a.

Transitivity

If a ~ b and b ~ c, then a ~ c.

Examples

NameRelationClassificationExplanation

Equality

a ~ b if and only if a = b

Equivalence relation

Every element equals itself, equality is symmetric and equality is transitive.

Congruence modulo n

a ~ b if n divides (a - b)

Equivalence relation

Congruence modulo a positive integer n satisfies all three equivalence properties.

Less-than relation

a < b

Not an equivalence relation

It is not reflexive or symmetric, although it is transitive.

Applications

  • Constructing modular arithmetic systems.

  • Defining equivalence classes and quotient sets.

  • Building quotient groups and quotient rings.

  • Classifying mathematical objects according to shared properties.

Common Mistakes

  • Checking only one or two of the three equivalence properties.

  • Confusing symmetry with antisymmetry.

  • Assuming every transitive relation is an equivalence relation.

  • Forgetting that an equivalence relation must be defined on the same underlying set.

Related Concepts

  • Cartesian Product

  • Equivalence Classes

  • Partitions

  • Congruence Relations

  • Quotient Structures

Learning Outcomes

  • Define a binary relation.

  • Test reflexivity, symmetry and transitivity.

  • Determine whether a relation is an equivalence relation.

  • Recognize the role of equivalence relations in quotient constructions.

Learning Guide

Core Idea

A relation describes how elements of one set are connected to elements of another set or to elements of the same set. An equivalence relation is a special relation that is reflexive, symmetric and transitive, allowing elements to be grouped according to a shared mathematical property.

Worked Example

Name: Equality
Relation: a ~ b if and only if a = b
Classification: Equivalence relation
Explanation: Every element equals itself, equality is symmetric and equality is transitive.

Name: Congruence modulo n
Relation: a ~ b if n divides (a - b)
Classification: Equivalence relation
Explanation: Congruence modulo a positive integer n satisfies all three equivalence properties.

How To Study

  • Write the formal definition and identify every object, operation, and hypothesis.

  • Work through the supplied example one step at a time; explain why each step is valid.

  • Check the listed properties and compare the example with at least one common mistake.

  • Try the self-check questions without looking at the answers, then explain the reasoning aloud or in writing.

Self Check

QuestionAnswer

In your own words, what is relations and equivalence relations?

A relation describes how elements of one set are connected to elements of another set or to elements of the same set. An equivalence relation is a special relation that is reflexive, symmetric and transitive, allowing elements to be grouped according to a shared mathematical property.

What definition, condition, or property should you check first when solving a problem about relations and equivalence relations?

Start from the formal definition and identify its hypotheses. In particular, check: Definition of a relation: A binary relation R from a set A to a set B is a subset of the Cartesian product A × B.

How is relations and equivalence relations connected to the wider study of abstract algebra?

It belongs to Foundations and mathematical language. It connects naturally with Cartesian Product, Equivalence Classes, Partitions, Congruence Relations.

Mastery Checklist

  • I can state the definition of relations and equivalence relations accurately.

  • I can identify the assumptions and notation used in a problem.

  • I can explain at least one example and justify each important step.

  • I can recognize a common mistake and explain why it is incorrect.

Key Properties

  • The concept is governed by its formal definition: A relation describes how elements of one set are connected to elements of another set or to elements of the same set. An equivalence relation is a special relation that is reflexive, symmetric and transitive, allowing elements to be grouped according to a shared mathematical property.

  • The assumptions in a theorem or definition must be checked before using the result.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Standard introductory discrete mathematics and abstract-algebra definitions; no specific external reference has been independently verified.

Suggest a correction or source · More in Abstract Algebra