Equivalence Relation

Abstract

Let $A$ be a Set and $R$ be a Relation on $A$
$R$ is equivalence relation iff $R$ is Reflexive, Symmetric and Transitive

Equivalence Class

Subset of Equivalence Relation
Basically same as the component of a Set Partition
Can be represented with $[a]_{re l a t i o n}$ , it means the Equivalence Class contains element $a$
$[a]_{re l a t i o n}$ and $[b]_{re l a t i o n}$ are the same iff $b$ is in the same equivalence class as $a$

Lemma Rel.1

Equivalence Relation
Let ~ be an Equivalence Class on Set $A$ and $x, y \in A$
1. $x$ is equivalent related to $y$
2. The equivalent class $x$ is in is same as the equivalent class $y$ is in
3. $[x] \cap [y] \neq = \emptyset$
here is a nice proof

Congruence Modulo 3

\forall x, y \in Z (x R y \leftrightarrow 3∣ (x - y))

Two integers $a$ and $y$ are congruent modulo iff they have the same remainder when divided by $m$
A Relation that is Equivalence Relation, here is a nice proof

Important

$- 2 \equiv 3$ is $1$ , because $3 m o d - 2$ is $- 2$ but the remainder needs to be a non-negative integer. So we add $3$ to the result, and we get $1$ .

Important

The Equivalence Class of congruent modulo $m$ are called congruent classes modulo $m$ .

The congruence class of an integer $x$ modulo $m$ is denoted by $[x]_{m}$ . The formula is following $[x]_{m} = {\dots, x - 2 m, x - m, x, x + m, x + 2 m, \dots}$

CS Notes

Recent Updates

Common Programming Operations

API Notes

CPP Notes

Explorer

Equivalence Relation

Abstract

Equivalence Class

Lemma Rel.1

Congruence Modulo 3

References

Table of Contents

Backlinks

Graph View