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 m≑n 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 y12βˆ’x1=y22βˆ’x2. Example equivalence classes for (0,0),(0,1),(1,βˆ’1).

(d)

Relation ≑ on A=P({a,b,c,d}), where X≑Y 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 v≑vβ€² means there exists a path in G from v to vβ€².

(f)

Given function f:Aβ†’B, the relation ≑ on the domain A, where a1≑a2 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,a2∈A, 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?