Virtual Labs

Equivalence Relation

Suppose

A

is a finite set with

n

elements. The number of elements and the rank of the largest equivalence relation on

A

are

{n,1}

Explanation

{n,n}

Explanation

{n^2,1}

Explanation

{1,n^2}

Explanation

Determine the number of equivalence classes that can be described by the set

{2, 4, 5}

125

Explanation

5

Explanation

16

Explanation

72

Explanation

For

a, b \in Z

defined

a \mid b

to mean that

a

divides

b

is a relation which does not satisfy ___________

a: irreflexive and symmetric relation Explanation

Explanation

b: reflexive relation and symmetric relation Explanation

Explanation

c: transitive relation Explanation

Explanation

d: symmetric relation Explanation

Explanation

Determine the partitions of the set

{3, 4, 5, 6, 7}

from the following subsets.

a: {3,5}, {3,6,7}, {4,5,6} Explanation

Explanation

b: {3}, {4,6}, {5}, {7} Explanation

Explanation

c: {3,4,6}, {7} Explanation

Explanation

d: {5,6}, {5,7} Explanation

Explanation

Consider the congruence

45 \equiv 3

(mod

7

). Find the set of equivalence class representatives.

a: {.., 0, 7, 14, 28, ..} Explanation

Explanation

b: {.., -3, 0, 6, 21, ..} Explanation

Explanation

c: {.., 0, 4, 8, 16, ..} Explanation

Explanation

d: {.., 3, 8, 15, 21, ..} Explanation

Explanation

Let

R

be an equivalence relation on a set

A

. If

[a]

and

[b]

are two equivalence classes of

R

, which statement must be true?

[a] \cap [b]

is always non-empty Explanation

Explanation

[a] \cup [b]

is always an equivalence class Explanation

Explanation

c: Either

[a] = [b]

[a] \cap [b] = \emptyset

Explanation

|[a]| = |[b]|

always holds Explanation

Explanation

R

is an equivalence relation on an infinite set

X

and

S

is an equivalence relation on an infinite set

Y

, what can be said about their Cartesian product

R \times S

X \times Y

a: It is always an equivalence relation Explanation

Explanation

b: It is never an equivalence relation Explanation

Explanation

c: It is an equivalence relation if and only if

X = Y

Explanation

d: It is an equivalence relation if and only if

R = S

Explanation

Let

R

be an equivalence relation on a set

A

with exactly

n

equivalence classes. What is the minimum possible size of

R

as a set of ordered pairs?

n

Explanation

2n

Explanation

n^2

Explanation

\lceil \frac{n(n+1)}{2} \rceil

Explanation

Let

R

be an equivalence relation on a set

A

where

|A| = 10

. If

R

has exactly 4 equivalence classes and one class contains 4 elements, what is the maximum possible size of the second largest equivalence class?

a: 4 Explanation

Explanation

b: 3 Explanation

Explanation

c: 2 Explanation

Explanation

d: 1 Explanation

Explanation

In a group of people, define relation

R

where

aRb

if and only if

a

and

b

share the same birth month and birth day (ignoring year). Which property about

R

must be true?

a: Each equivalence class must have the same size Explanation

Explanation

b: There must be exactly 12 equivalence classes Explanation

Explanation

c: There must be exactly 365 equivalence classes Explanation

Explanation

d: The number of equivalence classes must be less than or equal to 366 Explanation

Explanation

Let

R

be an equivalence relation on the set of all non-empty strings over alphabet

{a,b}

. For strings

x

and

y

, define

xRy

if and only if

x

can be obtained from

y

by a finite number of cyclic shifts. For string

'ababab'

, what is

|[ababab]_R|

a: 6 Explanation

Explanation

b: 3 Explanation

Explanation

c: 2 Explanation

Explanation

d: 1 Explanation

Explanation