S2, C6: Equivalence Relations

Question 1

What is a relation?

Answer 1

A relation R on the set A is a non-empty subset of the Cartesian product AxA.

Question 2

A relation called congruence modulo n

Answer 2

aRb iff a-b is divisible by n.

Question 3

Reflexive

Answer 3

A relation R on a set A is said to be reflexive if

aRa for all a∈A

Question 4

Symmetric

Answer 4

A relation R on a set A is said to be symmetric if:

whenever a, b ϵ A with aRb, then bRa.

Question 5

Transitive

Answer 5

A relation R on a set A is said to be transitive if:

whenever a, b, c ∈ A with aRb and bRc, then aRc.

Question 6

Equivalence relation

Answer 6

A relation that is reflexive, symmetric and transitive.

Question 7

Equivalence Class

Answer 7

If R is an equivalence relation on a set A then, for each a ∈ A, the equivalence class of a is the set
a(bar) = {b ∈ A : bRa}

Question 8

Partition

Answer 8

A partition of a non-empty set A is given by a collection of non-empty subsets Ai of A such that
Ui Ai = A, and Ai ∩ Aj = ∅ whenever Ai is not equal to Aj.
I.e. every element of A belong to exactly one Ai.