[set theory] equivalence relation (concept of equivalence relation | examples of equivalence relation | equivalence relation and closure)

One 、 Equivalence relation

---

Concept of equivalence relation :

A

A

A Set is a non empty set ,

A

≠

∅

A \not= \varnothing

A​=∅ , also

R

R

R The relationship is

A

A

A Binary relations on sets ,

R

⊆

A

×

A

R \subseteq A\times A

R⊆A×A ;

If

R

R

R The relationship is introspect , symmetry , Pass on Of , So called

R

R

R The relationship is Equivalence relation ;

Two 、 Examples of equivalence relationships

---

1. Relationship

1

1

1 :

x

x

x And

y

y

y The same age ;

• introspect : $x$
• symmetry : $x$
• Pass on : $x$
• Equivalence relation : The relationship is introspect , symmetry , Pass on Of , So the relationship yes Equivalence relation ;

It can be seen from the above , Equivalence relations are used for classification , People born in the same year can be divided into an equivalent class ;

2. Relationship

2

2

2 :

x

x

x And

y

y

y Same last name ;

• introspect : $x$
• symmetry : $x$
• Pass on : $x$
• Equivalence relation : The relationship is introspect , symmetry , Pass on Of , So the relationship It's equivalence ;

3. Relationship

3

3

3 :

x

x

x Older than or equal to

y

y

y ;

• introspect : $x$
• symmetry : $x$
• Pass on : $x$
• Equivalence relation : The relationship is introspect , Pass on Of , It's not symmetrical , So the relationship It's not equivalent ;

4. Relationship

4

4

4 :

x

x

x And

y

y

y Take the same course ;

• introspect : $x$
• symmetry : $x$
• Pass on : $x$
• Equivalence relation : The relationship is introspect , symmetry Of , Not transitive , So the relationship It's not equivalent ;

5. Relationship

5

5

5 :

x

x

x Weight greater than

y

y

y ;

• introspect : $x$
• symmetry : $x$
• Pass on : $x$
• Equivalence relation : The relationship is Pass on Of , No introspect , symmetry Of , So the relationship It's not equivalent ;

3、 ... and 、 Examples of equivalence relations and closures

---

A

A

A Set is a non empty set ,

A

≠

∅

A \not= \varnothing

A​=∅ , also

R

R

R The relationship is

A

A

A Binary relations on sets ,

R

⊆

A

×

A

R \subseteq A\times A

R⊆A×A ;

Yes

R

R

R Three closures of relation , Yes

6

6

6 In a different order , Discuss the properties of these closure results ;

6

6

6 A property of finding closures :

• r

  t

  s

  (

  R

  )

  rts(R)

  rts(R) : First find the symmetric closure , Ask again Pass closures , Finally, find the reflexive closure ;

• t

  r

  s

  (

  R

  )

  trs(R)

  trs(R) : First find the symmetric closure , Then find the reflexive closure , Finally, ask for Pass closures ;

• t

  s

  r

  (

  R

  )

  tsr(R)

  tsr(R) : First find the reflexive closure , Then find the symmetric closure , Finally, ask for Pass closures ;

• r

  s

  t

  (

  R

  )

  rst(R)

  rst(R) : First seek Pass closures , Then find the symmetric closure , Finally, find the reflexive closure ;

• s

  r

  t

  (

  R

  )

  srt(R)

  srt(R) : First seek Pass closures , Then find the reflexive closure , Finally, find the symmetric closure ;

• s

  t

  r

  (

  R

  )

  str(R)

  str(R) : First find the reflexive closure , Ask again Pass closures , Finally, find the symmetric closure ;

Reference resources : 【 Set theory 】 Relational closure ( Relational closure method | Find closure of relation graph | Find closure of relation matrix | Closure operation and relation properties | Closure compound operation ) 5、 ... and 、 Closure compound operation

• $rs(R)=sr(R)$
• $rt(R)=tr(R)$
• $st(R)\subseteq ts(R)$

Therefore, there are two categories

• ① Transitive closure first , Then find the symmetric closure
• ② First find the symmetric closure , Then find the transitive closure

First find the symmetric closure , Then find the transitive closure :

• $rts(R)$
• $trs(R)$
• $tsr(R)$

Fix ts The order of operations , First t after s , r Operations can be placed anywhere ;

Reflexivity does not conflict with the other two closure operations , It can be anywhere ;

Symmetry and transmission , The transmission of subsequent requests , So the result is transitive ;

The result of the above three sequences is introspect , symmetry , Pass on Of , It satisfies the equivalence relation , The result is Equivalent closure ;

First ask for the transfer package , Then find the symmetric closure :

• $rst(R)$
• $srt(R)$
• $str(R)$

Fix st The order of operations , First s ( Symmetric closure ) after t ( Pass closures ) , r ( Symmetric closure ) Operations can be placed anywhere ;

Reflexivity does not conflict with the other two closure operations , It can be anywhere ;

Symmetry and transmission , The transmission of the first request , Then find symmetry , Symmetry destroys transmission , Therefore, the result is not transitive ;

The result of the above three sequences is introspect , symmetry , Don't deliver Of , It does not satisfy the equivalence relation ;

	$rts(R)=trs(R)==tsr(R)$	$rst(R)=srt(R)=str(R)$
introspect	establish	establish
symmetry	establish	establish
Pass on	establish	Don't set up
Equivalence relation	establish ( This closure is called an equivalent closure )	Don't set up