[set theory] equivalence classes (concept of equivalence classes | examples of equivalence classes | properties of equivalence classes | quotient sets | examples of quotient sets)*

One 、 Equivalence class

---

R

R

R Relationship yes

A

A

A aggregate The binary relationship on ,

A

A

A Set is not empty ,

A

≠

∅

A \not= \varnothing

A​=∅ ,

about

A

A

A In the collection arbitrarily

x

x

x Elements ,

∀

x

∈

A

\forall x \in A

∀x∈A ,

x

x

x About

R

R

R Equivalence class of relation yes

[

x

]

R

=

{

y

∣

y

∈

A

∧

x

R

y

}

[x]_R = \{ y | y \in A \land xRy \}

[x]R​={ y∣y∈A∧xRy} ;

x

x

x About

R

R

R Equivalence class of relation , Referred to as

x

x

x The equivalent class of , Write it down as

[

x

]

[x]

[x] ;

[

x

]

R

[x]_R

[x]R​ Express

x

x

x About

R

R

R Equivalence classes under relation ;

The equivalence class is composed of all And

x

x

x have

R

R

R Relational

y

y

y Set of components ;

If there is only one equivalence relation , Aforementioned

R

_R

R​ Subscripts can be omitted ,

[

x

]

R

[x]_R

[x]R​ It can be abbreviated as

[

x

]

[x]

[x]

Two 、 Examples of equivalence classes

---

aggregate

A

=

{

1

,

2

,

3

,

4

,

5

,

8

}

A = \{1,2,3,4,5,8\}

A={ 1,2,3,4,5,8}

R

R

R Relationship yes aggregate

A

A

A Upper model

3

3

3 Same as relation

Symbolized as :

R

=

<

x

,

y

>

∣

x

,

y

∈

A

∧

x

≡

y

(

m

o

d

3

)

R = {<x, y> | x, y \in A \land x \equiv y\pmod{3} }

R=<x,y>∣x,y∈A∧x≡y(mod3)

≡

\equiv

≡ The meaning of the symbol is Equal to

1

1

1 stay

R

R

R The equivalence class in relation is

{

1

,

4

}

\{ 1, 4 \}

{ 1,4}

2

2

2 stay

R

R

R The equivalence class in relation is

{

2

,

5

,

8

}

\{ 2, 5, 8 \}

{ 2,5,8}

3

3

3 stay

R

R

R The equivalence class in relation is

{

3

}

\{ 3 \}

{ 3}

Above

3

3

3 Equivalent classes , There is a global relationship inside the equivalence class , There is no relationship between equivalence classes ;

3、 ... and 、 Equivalence properties

---

R

R

R Relationship yes

A

A

A aggregate The equivalence relationship on ,

A

A

A Set is not empty ,

A

≠

∅

A \not= \varnothing

A​=∅ , For any

A

A

A The elements in the collection

x

,

y

x,y

x,y ,

∀

x

,

y

∈

A

\forall x,y \in A

∀x,y∈A , It has the following properties :

① The equivalent class of each element is not empty ;

[

x

]

R

≠

∅

[x]_R \not= \varnothing

[x]R​​=∅

② If there is a relationship between the two elements , Then their equivalent classes are equal ;

x

R

y

⇒

[

x

]

R

=

[

y

]

R

xRy \Rightarrow [x]_R = [y]_R

xRy⇒[x]R​=[y]R​

③ If there is no relationship between the two elements , Then their equivalence classes must not intersect ;

¬

x

R

y

⇒

[

x

]

R

∩

[

y

]

R

=

∅

\lnot xRy \Rightarrow [x]_R \cap [y]_R = \varnothing

¬xRy⇒[x]R​∩[y]R​=∅

④ Union of all equivalence classes , Is the original set

A

A

A ;

⋃

{

[

x

]

R

∣

x

∈

A

}

=

A

\bigcup \{ [x]_R | x \in A \} = A

⋃{ [x]R​∣x∈A}=A

Four 、 Quotient set

---

R

R

R Relationship yes

A

A

A aggregate The equivalence relationship on ,

A

A

A Set is not empty

A

A

A aggregate About

R

R

R Relationship The quotient set of yes

A

/

R

=

{

[

x

]

R

∣

x

∈

A

}

A/R = \{ [x]_R | x \in A \}

A/R={ [x]R​∣x∈A}

abbreviation :

A

A

A The quotient set of

The essence of quotient set : Quotient set The essence is a aggregate , The elements in the set are Equivalence class , This equivalence class is based on

R

R

R Relational ;

5、 ... and 、 Quotient set example 1

---

aggregate

A

=

{

1

,

2

,

3

,

4

,

5

,

8

}

A = \{1,2,3,4,5,8\}

A={ 1,2,3,4,5,8}

R

R

R Relationship yes aggregate

A

A

A Upper model

3

3

3 Same as relation

Symbolized as :

R

=

<

x

,

y

>

∣

x

,

y

∈

A

∧

x

≡

y

(

m

o

d

3

)

R = {<x, y> | x, y \in A \land x \equiv y\pmod{3} }

R=<x,y>∣x,y∈A∧x≡y(mod3)

≡

\equiv

≡ The meaning of the symbol is Equal to

1

1

1 stay

R

R

R The equivalence class in relation is

{

1

,

4

}

\{ 1, 4 \}

{ 1,4}

2

2

2 stay

R

R

R The equivalence class in relation is

{

2

,

5

,

8

}

\{ 2, 5, 8 \}

{ 2,5,8}

3

3

3 stay

R

R

R The equivalence class in relation is

{

3

}

\{ 3 \}

{ 3}

Quotient set definition :

A

/

R

=

{

[

x

]

R

∣

x

∈

A

}

A/R = \{ [x]_R | x \in A \}

A/R={ [x]R​∣x∈A}

A

A

A Set about

R

R

R The quotient set of relation is :

A

/

R

=

{

{

1

,

4

}

,

{

2

,

5

,

8

}

,

{

3

}

}

A/R = \{ \{ 1, 4 \} , \{ 2, 5, 8 \} , \{ 3 \} \}

A/R={ { 1,4},{ 2,5,8},{ 3}}

6、 ... and 、 Quotient set example 2

---

aggregate

A

=

{

a

1

,

a

2

,

⋯
 

,

a

n

}

A = \{ a_1 , a_2 , \cdots , a_n \}

A={ a1​,a2​,⋯,an​} The equivalence relation on has :

I

A

I_A

IA​ Identity ,

E

A

E_A

EA​ Global relations ;

1. Identity

I

A

I_A

IA​ : Each element in the set is an equivalent class ; classification The smallest particle size ;

A

A

A Set about Identity

I

A

I_A

IA​ The quotient set of :

A

/

I

A

=

{

{

a

1

}

,

{

a

2

}

,

⋯
 

,

{

a

n

}

}

A/I_A = \{ \{ a_1 \} , \{ a_2 \} , \cdots , \{ a_n \} \}

A/IA​={ { a1​},{ a2​},⋯,{ an​}}

2. Global relations

E

A

E_A

EA​ : In the collection All elements are equivalent classes ; Put all the elements together , Every element has a relationship with each other ; This classification The coarsest particle size ;

A

A

A Set about Global relations

E

A

E_A

EA​ The quotient set of :

A

/

E

A

=

{

{

a

1

,

a

2

,

⋯
 

,

a

n

}

}

A/E_A = \{ \{ a_1 ,a_2 , \cdots , a_n \} \}

A/EA​={ { a1​,a2​,⋯,an​}}

3.

R

i

j

R_{ij}

Rij​ Relationship : Identity And

<

a

i

,

a

j

>

,

<

a

j

,

a

i

>

<a_i , a_j> , <a_j , a_i>

<ai​,aj​>,<aj​,ai​> Union ; The relationship is introspect , symmetry , Delivered , It's equivalence ;

R

i

j

R_{ij}

Rij​ Relationship description :

R

i

j

=

I

A

∪

{

<

a

i

,

a

j

>

,

<

a

j

,

a

i

>

}

R_{ij} = I_A \cup \{ <a_i , a_j> , <a_j , a_i> \}

Rij​=IA​∪{ <ai​,aj​>,<aj​,ai​>}

A

A

A Set about Global relations

R

i

j

R_{ij}

Rij​ The quotient set of :

• take $a_i,a_j$

  { ai​,aj​}, Corresponding

• Put in the collection except $I_A$

  ai​,aj​ Other elements besides are divided into a separate category , Corresponding

A

/

R

i

j

=

{

{

a

i

,

a

j

}

,

{

a

1

}

,

⋯
 

,

{

a

i

−

1

}

,

{

a

i

+

1

}

,

⋯
 

,

{

a

j

−

1

}

,

{

a

j

+

1

}

,

⋯
 

,

a

n

}

,

}

A/R_{ij} = \{ \{ a_i , a_j \} , \{a_1\} , \cdots , \{a_{i - 1}\}, \{a_{i + 1}\}, \cdots , \{a_{j - 1}\} , \{a_{j + 1}\}, \cdots , a_n \} , \}

A/Rij​={ { ai​,aj​},{ a1​},⋯,{ ai−1​},{ ai+1​},⋯,{ aj−1​},{ aj+1​},⋯,an​},}

4. Empty relation

∅

\varnothing

∅ It's not a collection

A

A

A The equivalence relationship on , Empty relationships are not reflexive ;

7、 ... and 、 Quotient set example 3

---

aggregate

A

=

{

a

,

b

,

c

}

A = \{ a , b , c \}

A={ a,b,c} All equivalence relations on : share Five equivalence relations , Only Three elements , On the basis of identity , Consider two elements Between 2 In one direction Ordered pair composition The relationship between ;

①

R

1

=

I

A

R_1 = I_A

R1​=IA​ Identity : The corresponding quotient set is :

A

/

I

A

=

{

{

a

}

,

{

b

}

,

{

c

}

}

A/I_A = \{ \{ a \} , \{ b \} , \{ c \} \}

A/IA​={ { a},{ b},{ c}}

②

R

2

=

E

A

R_2 = E_A

R2​=EA​ Global relations : The corresponding quotient set is :

A

/

E

A

=

{

{

a

,

b

,

c

}

}

A/E_A = \{ \{ a , b , c \} \}

A/EA​={ { a,b,c}}

③

R

3

=

I

A

∪

{

<

b

,

c

>

,

<

c

,

b

>

}

R_3 = I_A \cup \{ <b,c>, <c,b> \}

R3​=IA​∪{ <b,c>,<c,b>} Relationship : The corresponding quotient set is :

A

/

R

3

=

{

{

a

}

,

{

b

,

c

}

}

A/R_3 = \{ \{ a \} , \{ b , c \} \}

A/R3​={ { a},{ b,c}}

④

R

4

=

I

A

∪

{

<

a

,

c

>

,

<

c

,

a

>

}

R_4 = I_A \cup \{ <a,c>, <c,a> \}

R4​=IA​∪{ <a,c>,<c,a>} Relationship : The corresponding quotient set is :

A

/

R

4

=

{

{

b

}

,

{

a

,

c

}

}

A/R_4= \{ \{ b \} , \{ a , c \} \}

A/R4​={ { b},{ a,c}}

⑤

R

5

=

I

A

∪

{

<

a

,

b

>

,

<

b

,

a

>

}

R_5 = I_A \cup \{ <a,b>, <b,a> \}

R5​=IA​∪{ <a,b>,<b,a>} Relationship : The corresponding quotient set is :

A

/

R

5

=

{

{

c

}

,

{

a

,

b

}

}

A/R_5 = \{ \{ c \} , \{ a , b \} \}

A/R5​={ { c},{ a,b}}