What is an equivalence relation?

A binary relation on a set that is reflexive, symmetric, and transitive.

What is an equivalence class?

For an equivalence relation on $X$, $[a]=\{x\in X:x\sim a\}$, the set of elements equivalent to $a$.

What is the quotient set $X/\sim$?

The set of all equivalence classes of elements of $X$.

When does a function $f:X\to Y$ descend to a function on $X/\sim$?

When $x_1\sim x_2$ implies $f(x_1)=f(x_2)$; then $g([x])=f(x)$ is well-defined.

What is the equivalence relation generated by a relation $R$?

The smallest equivalence relation containing $R$, connecting elements by finite chains of forward or backward $R$-steps.

Discrete mathematicsLesson 4 of 4 in the course Set theory and relations

Equivalence Relations, Classes, Quotients, and Induced Maps

5 flashcards · 5 quiz questions · 5 match pairs · 4 fill-in sentences · English

Save course

Lesson progress

0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

This lesson introduces equivalence relations and the three properties that define them. These ideas let us describe when elements should be treated as equivalent, even if they are not literally identical.

A binary relation on a set $X$ specifies which ordered pairs of elements of $X$ are related. We may write $a\sim b$ to say that $a$ is related to $b$ . An equivalence relation is a relation with three required properties: reflexivity, symmetry, and transitivity.

All flashcards

What is an equivalence relation?: A binary relation on a set that is reflexive, symmetric, and transitive.
What is an equivalence class?: For an equivalence relation on $X$ , $[a]=\{x\in X:x\sim a\}$ , the set of elements equivalent to $a$ .
What is the quotient set $X/\sim$ ?: The set of all equivalence classes of elements of $X$ .
When does a function $f:X\to Y$ descend to a function on $X/\sim$ ?: When $x_1\sim x_2$ implies $f(x_1)=f(x_2)$ ; then $g([x])=f(x)$ is well-defined.
What is the equivalence relation generated by a relation $R$ ?: The smallest equivalence relation containing $R$ , connecting elements by finite chains of forward or backward $R$ -steps.

Quiz questions

For an equivalence relation on a set, what can be concluded if two equivalence classes have an element in common?Answer: The two classes are identical.
How does a partition of a set define an equivalence relation?Answer: Two elements are equivalent precisely when they lie in the same cell.
What condition ensures that $g([x])=f(x)$ defines a function on the quotient set?Answer: Equivalent representatives must have equal values under $f$ .
How can the equivalence relation generated by a relation $R$ be characterized?Answer: Elements are related when joined by a finite chain of forward or backward $R$ -steps.
If $\sim$ is finer than $\approx$ , how are their equivalence classes related?Answer: Each $\sim$ -class is contained in an $\approx$ -class.

Based on the Wikipedia article Equivalence relation, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.

All Discrete mathematics lessons

Discrete mathematicsBinary Relations: Operations, Properties, Functions, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsPigeonhole Principle: Counting, Collisions, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsDe Morgan's Laws in Logic, Set Theory, and Boolean Algebra5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsEulerian Routes: Criteria, Construction, and Extensions5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsNumber Theory: Integer Structure, Methods, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsBinomial Coefficients: Expansion, Counting, and Identities5 flashcards · 5 quiz questions · 4 gamesPlay free →

Summary

All flashcards

Quiz questions

More in Discrete mathematics