Equivalence Relation

DEFINITION1: Let  X be a set and  R\subset{X\times{X}}. If the relation  R is reflexive, symmetric and transitive, then the relation  R is called an "equivalence relation" and denoted by  R=\sim in general.

DEFINITION2: Let  \sim be an equivalence relation over a set  X and  a\in{X}. The set defined as  \{x\in{X}\:|\:a\sim{x}\}\subset{X} is called the “equivalence class” of  a under  \sim and denoted by  \overline{a},  [a] or  [a]_{\sim}. Since  a\sim{a} for every  a\in{X}, then  a\in{\overline{a}}. So the equivalence class  \overline{a} is non-empty for every  a\in{X}. The family of all the equivalence classes of the relation  \sim is called the “quotient set” of  X by  \sim and denoted by  {^X}/{_\sim}

I.e.,

 {^X}/{_\sim}=\{\overline{a}\:|\:a\in{X}\}\subset{\mathbf{P}(X)}.

DEFINITION3: Let  \sim be an equivalence relation over a set  X and  a,b\in{X}. If  b\in{\overline{a}}, then  b is called a “representative class” of the equivalence class  \overline{a}.

» Read more

Relation

DEFINITION1: Let  X and  Y be two sets. Any subset of the cartesian product  X\times{Y} is called a relation with domain  X and codomain  Y. While some sources are giving the definition of relation, they assume  X,Y\ne{\varnothing} and it’s said the emptyset being a subset of  X\times{Y} isn’t a relation. However, the assumption “the emptyset is a relation” is not a problem for any branch of the mathematics. On the contrary, the assumption “the emptyset is a relation” plays an important role in some branch of the mathematics.

If  X and  Y are two sets with  n and  m elements respectively, then the cartesian product  X\times{Y} has  n.m elements. Since a relation with domain  X and codomain  Y is an element of the power set  \mathbf{P}(X\times Y) and the number of the elements of the power set of a set with  k elements is  2^{k}, then the number of all the relations with domain  X and codomain  Y is  2^{n.m}. If  X,Y\ne{\varnothing} and at least one of  X and  Y is infinite set, then the number of all the relations with domain  X and codomain  Y is also infinity.

Let  R\subset{X\times{Y}} be a relation not being the emptyset. The statement  (x,y)\in{R} is read “x is R-related to y” and is denoted by  xRy or  R(x)=y.

EXAMPLE1: Let  X=\{a,b,c\} and  Y=\{1,2\}. Since  X has 3 elements and  Y has 2 elements, the number of all the relations with domain  X and codomain  Y is  2^{2.3}=2^{6}=64. We can give some of these  64 relations:

 R_1=\varnothing,

» Read more