Prove a set X is union of disjoint equivalence classes

Click For Summary
SUMMARY

The discussion centers on proving that a set X is the union of disjoint equivalence classes defined by an equivalence relation R. The participants confirm that if E1, · · · , Ek are disjoint equivalence classes, then X equals the union of these classes, and R can be expressed as the union of the Cartesian products of these classes (R = union of (Ej x Ej)). Key properties of equivalence relations, such as reflexivity, symmetry, and transitivity, are essential in establishing these conclusions.

PREREQUISITES
  • Understanding of equivalence relations and their properties (reflexivity, symmetry, transitivity).
  • Familiarity with set theory concepts, particularly unions and Cartesian products.
  • Knowledge of mathematical notation and proof techniques.
  • Basic experience with logical reasoning in mathematics.
NEXT STEPS
  • Study the properties of equivalence relations in depth.
  • Learn about set partitions and their implications in set theory.
  • Explore the concept of Cartesian products and their applications in relations.
  • Practice constructing formal proofs involving equivalence relations and set unions.
USEFUL FOR

Students of mathematics, particularly those studying abstract algebra or discrete mathematics, as well as educators seeking to clarify concepts related to equivalence relations and set theory.

Ceci020
Messages
10
Reaction score
0

Homework Statement


Prove: If E1, · · · , Ek are the disjoint equivalence classes
determined by an equivalence relation R over a set X, then
(a) X = union of disjoint equivalence classes Ej
(b) R = union of disjoint (Ej x Ej)

Homework Equations


R is a subset of X x X

The Attempt at a Solution


For (a), my thoughts are :
1/ By reflexive property of equiv. relation, there exists an element a in X such that <a,a> belongs to R
2/ I know "E1, · · · , Ek are the disjoint equivalence classes
determined by an equivalence relation R", so if a belongs to R, then a must also belongs to some of the equivalence classes.
3/ Then I use the fact that a is in X, and a belongs to some of equivalence classes, then X must be the union of those equiv. classes

But then I'm not sure if my thoughts are correct, probably what I'm confused is with my 3rd idea.

For (b), my thoughts are:
Since R is a subset of X x X
and by (a), X is an union of disjoint equiv. classes
then X x X = union of (Ej x Ej)

And again, I feel shaky about my reasoning

Would someone please give me some hints or ideas?
I really appreciate your time and your help.
 
Physics news on Phys.org
Hi:
You know an equivalence relation partitions your set into disjoint equivalence classes,right? If aRb and aRc, then bRa (symmetry) and aRc , so bRc (so b and c are in the same class) , so no element belongs to more than one equivalent class, and all elements belong to some class.

For (b), don't you mean R=EixEj , for Ei,Ej disjoint?
 

Similar threads

  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 7 ·
Replies
7
Views
1K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 9 ·
Replies
9
Views
3K
  • · Replies 8 ·
Replies
8
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
Replies
2
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
Replies
3
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K