Let X = {a, b, c} and let A = P(A) be the power set of X. Define the relation R on A as follows: For all sets U, V ∈ P(A), U R V ⇔ N(U) = N(V)I assume that N(U) means the number of elements...

Let X = {a, b, c} and let A = P(A) be the power set of X. Define the relation R on A as follows: For all sets U, V ∈ P(A), U R V ⇔ N(U) = N(V)

I assume that N(U) means the number of elements of the set U. 

* How could i generate a proof by using definitions that R is an equivalence rleation?

* Can anyone show my a sketch of the directed graph for this relation?

1 Answer | Add Yours

mfonda's profile pic

Matthew Fonda | eNotes Employee

Posted on

To show that R is an equivalence relation, we must show that it is symmetric, reflexive, and transitive.

Let A = P({a,b,c}) and let xRy iff |x| = |y| for all x, y in A.

Symmetric: Let x, y be let elements of A, and let xRy. Therefore |x| = |y|, or |y| = |x|. Therefore yRx. Since xRy => yRx, R is symmetric.

Reflexive: Let x be an element of x. |x| = |x|, and therefore xRx. Since xRx, R is reflexive.

Transitive: Let x, y, z be elements of A. Suppose xRy. It follows then that |x| = |y| = n, for some integer n. Suppose yRz. Since |y| = n and yRz, it follows that |z| = n. Therefore xRy and yRz implies xRz, and thus R is transitive.

 

A graph G of R on A has elements of A as nodes, and edges between nodes u,v iff uRv. We can sketch G as follows:

{}

{a}<---->{b}<---->{c}

 ^--------------------^

{a,b}<---->{a,c}<---->{b,c}

 ^----------------------------^

{a,b,c}

Sources:

We’ve answered 318,979 questions. We can answer yours, too.

Ask a question