 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/discrete-mathematics-probability-and-continuous-mathematics/3/d/solution

R

A

A \times A

. Its properties are quantified over elements of

A

A reflexive relation satisfies $\forall a \in A, a R a$ .
A symmetric relation satisfies $\forall a, b \in A, a R b \Rightarrow b R a$ .
An antisymmetric relation satisfies $\forall a, b \in A, (a R b \land b R a) \Rightarrow a = b$ .
A transitive relation satisfies $\forall a, b, c \in A, (a R b \land b R c) \Rightarrow a R c$ .
An irreflexive relation satisfies $\forall a \in A, \neg (a R a)$ .
A serial relation satisfies $\forall a \in A \exists b \in A, a R b$ .

Thus an equivalence relation is a binary relation that is simultaneously reflexive, symmetric and transitive. The equivalence class of

a

is the set of all elements related to it:

R is an equivalence relation ⟺ R is reflexive, symmetric and transitive; [a]_{R} = {b \in A : a R b} .

 New to topics? Read the docs here!