Question

Let S be a set of n elements. The number of ordered pairs in the largest and the
smallest equivalence relations on S are:
(A) n and n (B) n^2 and n (C) n^2 and 0 (D) n and 1

Answer 1

Answer on Question #38168 - Math - Set Theory

Question: Let $S$ be a set of $n$ elements. The number of ordered pairs in the largest and the smallest equivalence relations on $S$ are:

a) $n$ and $n$

b) $n^2$ and $n$

c) $n^2$ and 0

d) $n$ and 1

Solution. The largest equivalence relation on $S$ is a relation that contains all pairs $(x, y)$, where $x$ and $y$ are elements of $S$. The number of such (ordered) pairs is $n * n = n^2$.

The smallest equivalence relation on $S$ is such a relation that every element $x$ of $S$ is only equivalent to itself. Thus, this relation will have $n$ ordered pairs.

Note that any equivalence relation must be reflexive (i.e. each element must be equivalent to itself), so we cannot have 0 or 1 pair in this case.

Answer. b) The number of ordered pairs in the largest and the smallest equivalence relations on $S$ are $n^2$ and $n$.

www.AssignmentExpert.com