Question

In: Computer Science

select the relation that is an equivalence relation. THe domain set is (1,2,3,4). a. (1,4)(4,1),(2,2)(3,3) b....

select the relation that is an equivalence relation. THe domain set is (1,2,3,4).

a. (1,4)(4,1),(2,2)(3,3)

b. (1,4) (4,1)(1,3)(3,1)(2,2)

c. (1,4)(4,1)(1,1)(2,2)(3,3)(4,4)

d. (1,4)(4,1)(1,3)(3,1)(1,1)(2,2)(3,3)(4.4)

Expert Solution

Before directly going to the answer let us check what is an equivalence relation.

Equivalence relation set is nothing but a relation which is

Symmetry, transitive and reflexive.

Symmetry =aRb->bRa for all a, b belongs to A(domain set).
Transitive =aRb and bRc - > aRc for a, b, c belongs to A(domain set).
Reflexive = aRa for all a belongs A(domain set) .

Now let us take each of the given relations in the question.

a) for reflexive test every element of the domain set should have a (a, a) relation where a belongs to domain set. But here (2,2)&(3,3) belongs to relation.. But the relations does not cover every element, ie. (1,1)&(4,4)

So the relations is not reflexive.

Since this is not reflexive there is no chance for the relation to be a equivalence relation. So we don't want to check other criteria..

a is not a equivalence relation.

b) a mentioned above let us check for reflexive.

And this is clear thatvthe relation don't have a (a, a) relation. So b is not reflexive and there by not equivalence relation.

c) here (1,1),(2,2),(3,3)& (4,4) belongs to the relations. So the relation is reflexive.

Then let us check for Symmetry relation. As mentioned above for Symmetry aRb->bRa for a, b belongs to A(domain set).

Here (1,4)&(4,1)belongs to relation set R and satisfy the conditions. So this is an symmetric relation.

Finally let us check for transitive . As mentioned above to be a transitive relation aRb and bRc - > aRc for all a, b, c belongs to A(domain set).

Here (1,4),(4,1) & (1,1) belongs to the relation. And hence this is also a transitive relation.

Hence c is symmetric, reflexive and transitive this is an equivalence relation.

d) this is clear that it is an reflexive relation. ((1,1),(2,2),(3,3),(4,4)).

This is clear that it is also a Symmetrical relation((1,4),(4,1) also (1,3),(3,1)).

Finally for transitive it is clear that the relation also a transitive reaction. ((1,4),(4,1),(1,1)).

So Hence d is symmetric, reflexive and transitive this is an equivalence relation.

venereology answered 2 weeks ago

Prove that the equivalence classes of an equivalence relation form a partition of the domain of...

Prove that the equivalence classes of an equivalence relation form a partition of the domain of the relation. Namely, suppose ? be an equivalence relation on a set ? and define the equivalence class of an element ?∈? to be [?]?:={?∈?|???}. That is [?]?=?(?). Divide your proof into the following three peices: Prove that every partition block is nonempty and every element ? is in some block. Prove that if [?]?∩[?]?≠∅, then ???. Conclude that the sets [?]? for ?∈?...

Determine whether the given relation is an equivalence relation on the set. Describe the partition arising...

Determine whether the given relation is an equivalence relation on the set. Describe the partition arising from each equivalence relation. (c) (x1,y1)R(x2,y2) in R×R if x1∗y2 = x2∗y1.

For each part below, find a binary relation on the set S = {1,2,3,4} that satisfies...

For each part below, find a binary relation on the set S = {1,2,3,4} that satisfies the given combination of properties a) reflexive, symmetric, and transitive b) not reflexive, but symmetric and transitive c) not symmetric, but reflexive and transitive d) not transitive, but reflexive and symmetric e) neither reflexive nor symmetric, but transitive f) neither reflexive nor transitive, but symmetric g) neither symmetric not transitive, but reflexive h) not reflexive, not symmetric, and not transitive

Prove that \strongly connected" is an equivalence relation on the vertex set of a directed graph

Show that the relation 'a R b if and only if a−b is an even integer defined on the Z of integers is an equivalence relation.

7. Prove that congruence modulo 10 is an equivalence relation on the set of integers. What...

7. Prove that congruence modulo 10 is an equivalence relation on the set of integers. What do the equivalence classes look like?

An equivalence relation partitions the plane R2 into the set of lines with slope 2. Describe...

An equivalence relation partitions the plane R2 into the set of lines with slope 2. Describe the relation on R .

Let X be a non-empty set and R⊆X × X be an equivalence relation. Prove that...

Let X be a non-empty set and R⊆X × X be an equivalence relation. Prove that X / R is a partition of X.

Let X be a finite set. Describe the equivalence relation having the greatest number of distinct...

Let X be a finite set. Describe the equivalence relation having the greatest number of distinct equivalence classes, and the one with the smallest number of equivalence classes.

Let X be the set of equivalence classes. So X = {[(a,b)] : a ∈ Z,b...

Let X be the set of equivalence classes. So X = {[(a,b)] : a ∈ Z,b ∈ N} (recall that [(a,b)] = {(c,d) ∈Z×N : (a,b) ∼ (c,d)}). We deﬁne an addition and a multiplication on X as follows: [(a,b)] + [(c,d)] = [(ad + bc,bd)] and [(a,b)]·[(c,d)] = [(ac,bd)] Prove that this addition and multiplication is well-deﬁned on X.