Skip to main content
Logo image

Activities 18.6 Activities

Activity 18.1.

For each of the relations provided, carry out the following steps.
  1. Verify that the relation is an equivalence relation on the set A.
  2. Consider a few example equivalence classes, for the specific example representative elements provided (if applicable). What other elements are in that class?
  3. Devise a general way to describe every equivalence class, using your experience from the example classes already considered (if applicable). Make your class descriptions more meaningful than just “all elements equivalent to a specific representative element.”
  4. List/describe all elements in the quotient A/.

(a)

Relation on A=Z, where mn means m2=n2. Example equivalence classes for 1,10,2,0.

(b)

Relation on A=R×R, where (x1,y1)(x2,y2) means x12+y12=x22+y22. Example equivalence classes for (1,1),(3,4),(2/2,2/2),(0,0).

(c)

Relation on A=R×R, where (x1,y1)(x2,y2) means y12x1=y22x2. Example equivalence classes for (0,0),(0,1),(1,1).

(d)

Relation on A=P({a,b,c,d}), where XY means |Xc|=|Yc|. Example equivalence classes for ,{a},{a,b},{a,b,c},{a,b,c,d}.

(e)

Relation on the vertex set A=V of a graph G, where vv means there exists a path in G from v to v.

(f)

Given function f:AB, the relation on the domain A, where a1a2 means f(a1)=f(a2).

Activity 18.2.

A sequence from a set A could also be called an ordered list. For example, given distinct a1,a2A, the finite sequences a1,a1,a2 and a1,a2,a1 are different sequences, because order matters in a sequence. However, as an unordered list, a1,a1,a2 is the same as a1,a2,a1.
Write SA for the set of all finite sequences from A. Devise an equivalence relation on SA such that the quotient set SA/ represents the set of all finite unordered lists from A.
Hint.
When should two different finite sequences be considered equivalent as unordered lists?

Activity 18.3.

Suppose and are equivalence relations on a set A. Determine which of the following are also equivalence relations.

(a)

c

(b)

(c)