Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation / 6 / b

R

on a set

X

is an equivalence relation when it is a reflexive relation, a symmetric relation, and a transitive relation. In first-order logic, these three requirements are

\forall x \in X x R x, \forall x, y \in X (x R y \Rightarrow y R x), \forall x, y, z \in X ((x R y \land y R z) \Rightarrow x R z) .

(1)

ii

 0  0

Solution

 0  0

Suppose

R

is an equivalence relation, and

x R y

x R z

. Since it is a symmetric relation,

y R x

. Since it is a transitive relation,

y R x

together with

x R z

implies

y R z

. This proves

R an equivalence relation ⟹ R Euclidean .

(1)

iii

 0  0

Solution

 0  0

Suppose

R

is a reflexive relation and a Euclidean relation. To prove it is a symmetric relation, assume

x R y

. Reflexivity gives

x R x

, so applying the Euclidean implication to

x R y

and

x R x

gives

y R x

To prove it is a transitive relation, assume

x R y

and

y R z

. The symmetry just established gives

y R x

. Apply the Euclidean implication with common predecessor

y

y R x

and

y R z

; the conclusion is

x R z

. Thus all three requirements hold:

R reflexive and Euclidean ⟹ R an equivalence relation .

(1)

iv

 0  0

Solution

 0  0

On the nonempty set

X = {a}

take the empty binary relation

R = \emptyset

. There are no triples for which

x R y \land x R z

holds. The defining implication is therefore true for every triple by vacuous truth, making

R

a Euclidean relation.

But

a R a

is false, so

R

is not a reflexive relation and hence is not an equivalence relation:

(X, R) = ({a}, \emptyset) is a counterexample .

(1)

v

 0  0

Solution

 0  0

The answer is no, even when both original binary relations are equivalence relations. On

X = {a, b, c}

, let

R_{1}

have equivalence classes

{a, b}, {c}

and

R_{2}

have equivalence classes

{a}, {b, c}

. Each is a transitive relation and, by the earlier proof, a Euclidean relation.

Use exactly the paper's convention for composition of relations:

x R y

means

x R_{1} z

and

z R_{2} y

for some

z

. The possible successors are

R (a) = R (b) = {a, b, c}, R (c) = {b, c} .

(1)

Indeed, from

a

b

the first step can reach

a

b

, whose

R_{2}

successors together exhaust

X

; from

c

the first step must stay at

c

, whose

R_{2}

successors are only

b, c

. Consequently

c R b

and

b R a

, but not

c R a

. Therefore

R_{1} and R_{2} transitive and Euclidean does not force R transitive .

(2)

 Ancestors (11)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version

Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation / 6 / b

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion