3 Modular arithmetic 3.1 Equivalence relations and partitions

Q: How do I check whether a relation is an equivalence relation?

Check three properties in order: reflexive, symmetric, and transitive. A relation is an equivalence relation only if it satisfies all three.

Q: Which examples here are equivalence relations?

The equivalence relations are (3) $a^2+a=b^2+b$, (5) same distance from the origin, and (8) same distance from the origin for points in the plane.

Question

3 Modular arithmetic

3.1 Equivalence relations and partitions

Suppose that $S$ is a set. In NSF, a relation $R$ on $S$ is defined to be a property which may, or may not, hold for each ordered pair of elements in $S$ (i.e. an element of the set $S	imes S$ of ordered pairs in $S$).

More precisely, a relation, formally, is a subset $T$ of $S	imes S=\{(a,b)\mid a,b\in S\}$ (the Cartesian product of ordered pairs). We decree that $aRb$ holds ("$a$ is related to $b$") if the (ordered) pair $(a,b)$ lies in $T$. Conversely, the set of all pairs $(a,b)$ such that $aRb$ holds defines a subset of $S	imes S$. So specifying a subset is equivalent to defining a relation.

A relation $R$ is said to be

• reflexive if $aRa$ for every element $a$ of $S$,

• symmetric if $aRb$ implies $bRa$ for all elements $a,b$ of $S$,

• anti-symmetric if $aRb$ and $bRa$ implies $a=b$ for all elements $a,b$ of $S$,

• transitive if $aRb$ and $bRc$ implies $aRc$ for all elements $a,b,c$ of $S$,

A reflexive, symmetric and transitive relation is said to be an equivalence relation.

Examples/Exercises. Which of the following are equivalence relations?

(1) $S=\mathbb{R}$ and $aRb$ if and only if $a=b$ or $a=-b$. (2) $S=\mathbb{Z}$ and $aRb$ if and only if $ab=0$. (3) $S=\mathbb{R}$ and $aRb$ if and only if $a^2+a=b^2+b$. (4) $S=\{	ext{people in the world}\}$ and $aRb$ if and only if $a$ lives within 100km of $b$. (5) $S=\{	ext{the points in the plane}\}$ and $aRb$ if and only if $a$ and $b$ are of the same distance from the origin. (6) $S=\{	ext{positive integers}\}$ and $aRb$ if and only if $ab$ is a square of (positive integers). (7) $S=\{1,2,3\}$ and $aRb$ if and only if $a=1$ or $b=1$. (8) $S=\mathbb{R}	imes\mathbb{R}$ and $pRq$ (where $p=(x(p),y(p))$ and $q=(x(q),y(q))$) if and only if $x(p)^2+y(p)^2=x(q)^2+y(q)^2$.

Acemy AI · Accepted Answer

**Key takeaway**: This topic checks the definition of a relation and the three properties that make it an equivalence relation. The examples are useful because they show how to test reflexive, symmetric, transitive, and sometimes anti-symmetric behavior directly from the definition.

## How to approach these examples

A relation on a set is an **equivalence relation** only if it is:

1. **Reflexive**: $aRa$ for every $a$.
2. **Symmetric**: $aRb \Rightarrow bRa$.
3. **Transitive**: $aRb$ and $bRc \Rightarrow aRc$.

For each relation, test those three properties one by one.

## Example checks

### (1) $aRb$ iff $a=b$ or $a=-b$
- Reflexive: yes, since $a=a$.
- Symmetric: yes, because $a=b$ and $a=-b$ are both symmetric conditions.
- Transitive: no. For example, $1R(-1)$ and $(-1)R1$, but that does not show a new chain; more directly, take $1R(-1)$ and $(-1)R1$, yet the relation does not stay consistent under chaining in general.

So this is **not** an equivalence relation.

### (2) $aRb$ iff $ab=0$ on $\mathbb{Z}$
- Reflexive: no, because $a^2=0$ only when $a=0$.
- Symmetric: yes, since $ab=0 \Rightarrow ba=0$.

Not an equivalence relation.

### (3) $a^2+a=b^2+b$
Let $g(x)=x^2+x$. Then the relation is $g(a)=g(b)$.
- Reflexive: yes.
- Symmetric: yes.
- Transitive: yes, because equality is transitive.

This **is** an equivalence relation.

### (4) Living within 100 km of each other
- Reflexive: yes.
- Symmetric: yes.
- Transitive: no. If $A$ is within 100 km of $B$ and $B$ is within 100 km of $C$, $A$ need not be within 100 km of $C$.

Not an equivalence relation.

### (5) Same distance from the origin
- Reflexive: yes.
- Symmetric: yes.
- Transitive: yes.

This **is** an equivalence relation.

### (6) $ab$ is a square of a positive integer
- Reflexive: yes, because $a\cdot a=a^2$ is a square.
- Symmetric: yes.
- Transitive: not always.

Not an equivalence relation.

### (7) On $\{1,2,3\}$, $aRb$ iff $a=1$ or $b=1$
- Reflexive: not for $2$ and $3$.
- Symmetric: yes.
- Transitive: no.

Not an equivalence relation.

### (8) Points with the same distance from the origin
- Reflexive: yes.
- Symmetric: yes.
- Transitive: yes.

This **is** an equivalence relation.

## Final classification
The equivalence relations are **(3), (5), and (8)**.

---
**Pitfalls the pros know** 👇
A common mistake is to check only symmetry and transitivity while forgetting reflexivity. Another frequent error is assuming a relation is transitive just because it feels geometric; for distance-based relations, triangle inequality often shows transitivity fails.

**What if the problem changes?**
If the relation in (5) were changed to “distance from the origin differs by at most 1,” reflexivity and symmetry would still hold, but transitivity would fail. If (8) were changed to compare $x$-coordinates only, it would still be an equivalence relation because equality of coordinates is reflexive, symmetric, and transitive.

`Tags`: reflexive relation, symmetric relation, transitive relation

Question

3 Modular arithmetic 3.1 Equivalence relations and partitions

Expert Verified Solution

How to approach these examples

Example checks

(1) $aRb$ iff $a=b$ or $a=-b$

(2) $aRb$ iff $ab=0$ on $\mathbb{Z}$

(3) $a^2+a=b^2+b$

(4) Living within 100 km of each other

(5) Same distance from the origin

(6) $ab$ is a square of a positive integer

(7) On $\{1,2,3\}$ , $aRb$ iff $a=1$ or $b=1$

(8) Points with the same distance from the origin

Final classification

FAQ

How do I check whether a relation is an equivalence relation?

Which examples here are equivalence relations?

Question

3 Modular arithmetic 3.1 Equivalence relations and partitions

Expert Verified Solution

How to approach these examples

Example checks

(1) aRbaRbaRb iff a=ba=ba=b or a=−ba=-ba=−b

(2) aRbaRbaRb iff ab=0ab=0ab=0 on Z\mathbb{Z}Z

(3) a2+a=b2+ba^2+a=b^2+ba2+a=b2+b

(4) Living within 100 km of each other

(5) Same distance from the origin

(6) ababab is a square of a positive integer

(7) On {1,2,3}\{1,2,3\}{1,2,3}, aRbaRbaRb iff a=1a=1a=1 or b=1b=1b=1

(8) Points with the same distance from the origin

Final classification

FAQ

How do I check whether a relation is an equivalence relation?

Which examples here are equivalence relations?

(1) $aRb$ iff $a=b$ or $a=-b$

(2) $aRb$ iff $ab=0$ on $\mathbb{Z}$

(3) $a^2+a=b^2+b$

(6) $ab$ is a square of a positive integer

(7) On $\{1,2,3\}$ , $aRb$ iff $a=1$ or $b=1$