Question

8. Let R be the relation on the set of all sets of real numbers such that SRT if and only if S and T have the same cardinality. Show that R is an equivalence relation. What are the equivalence classes of the sets {0, 1, 2) and Z?

Answer 1

Answer:

We must prove that the relation is reflexive, symmetric and transitive. Recall that to sets have the same cardinality if there exist a bijective mapping between them.

Reflexive: Take the identity map $I:S\rightarrow S$, which is bijective. Then SRS.

Symmetric: If SRT then, there exist a bijective map $f:S\rightarrow R$. In order to prove that TRS just take the inverse map of $f$: $f^{-1}$ which is also bijective. Therefore, TRS.

Transitivity: Suppose that SRT and TRU. Also, assume that $f$ is the bijective map between S and T, and $g$ the bijective map between T and U. It is not difficult to check that the map $h=g(f)$ is bijective and $h:S\rightarrow U$. Therefore, SRU.

Hence, the relation R is an equivalence relation.

The equivalence class of the set {0,1,2} is the class of all the sets with three elements, and we can associate it with the number 3. There is a construction of natural numbers based on this idea.

The equivalence class of Z is the same equivalence class of N. Therefore, is the class of all denumerable or countable sets.

Step-by-step explanation:

When we want to prove that a given relation R is equivalence, we need to check that R satisfies all the three conditions: reflexive, symmetric and transitivity. Usually the first two are very simple to prove and comes directly from the definition. The transitivity is more tricky. In this case we need to recall the definition of cardinality.