[set theory] relational closure (relational closure related theorem)

One 、 Relational closure theorem ( Closure operation fixed point )

---

R

R

R The relationship is

A

A

A Binary relations on sets ,

R

⊆

A

R \subseteq A

R⊆A , And

A

A

A Set is not empty ,

A

≠

∅

A \not= \varnothing

A​=∅

R

R

R Relationships are reflexive , If and only if

R

R

R Reflexive closure of relation

r

(

R

)

r ( R )

r(R) It's also

R

R

R Relationship itself ;

R

since

back

⇔

r

(

R

)

=

R

R introspect \Leftrightarrow r(R) = R

R since back ⇔r(R)=R

R

R

R The relationship is symmetrical , If and only if

R

R

R Symmetric closure of relation

s

(

R

)

s ( R )

s(R) It's also

R

R

R Relationship itself ;

R

Yes

call

⇔

s

(

R

)

=

R

R symmetry \Leftrightarrow s(R) = R

R Yes call ⇔s(R)=R

R

R

R Relationships are transitive , If and only if

R

R

R Transitive closure of relation

t

(

R

)

t ( R )

t(R) It's also

R

R

R Relationship itself ;

R

Pass on

Deliver

⇔

t

(

R

)

=

R

R Pass on \Leftrightarrow t(R) = R

R Pass on Deliver ⇔t(R)=R

Two 、 Relational closure theorem ( Monotonicity of closure operation )

---

R

1

,

R

2

R_1 , R_2

R1​,R2​ The relationship is

A

A

A Binary relations on sets ,

R

2

R_2

R2​ Relationships include

R

1

R_1

R1​ Relationship ,

R

1

⊆

R

2

⊆

A

×

A

R_1 \subseteq R_2 \subseteq A \times A

R1​⊆R2​⊆A×A , And

A

A

A Set is not empty ,

A

≠

∅

A \not= \varnothing

A​=∅

R

1

R_1

R1​ Reflexive closure of relation Included in

R

2

R_2

R2​ Reflexive closure of relation

r

(

R

1

)

⊆

r

(

R

2

)

r(R_1) \subseteq r(R_2)

r(R1​)⊆r(R2​)

R

1

R_1

R1​ Symmetric closure of relation Included in

R

2

R_2

R2​ Symmetric closure of relation

s

(

R

1

)

⊆

s

(

R

2

)

s(R_1) \subseteq s(R_2)

s(R1​)⊆s(R2​)

R

1

R_1

R1​ Transitive closure of relation Included in

R

2

R_2

R2​ Transitive closure of relation

t

(

R

1

)

⊆

t

(

R

2

)

t(R_1) \subseteq t(R_2)

t(R1​)⊆t(R2​)

3、 ... and 、 Relational closure theorem ( The relationship between closure operation and union operation )

---

R

1

,

R

2

R_1 , R_2

R1​,R2​ The relationship is

A

A

A Binary relations on sets ,

R

2

R_2

R2​ Relationships include

R

1

R_1

R1​ Relationship ,

R

1

⊆

R

2

⊆

A

×

A

R_1 \subseteq R_2 \subseteq A \times A

R1​⊆R2​⊆A×A , And

A

A

A Set is not empty ,

A

≠

∅

A \not= \varnothing

A​=∅

Reflexive closure union :

R

1

R_1

R1​ Relationship And

R

2

R_2

R2​ Relationship Combine Of Reflexive closure , be equal to

R

1

R_1

R1​ Reflexive closure of relation And

R

2

R_2

R2​ Reflexive closure of relation Union ;

r

(

R

1

∪

R

2

)

=

r

(

R

1

)

∪

r

(

R

2

)

r(R_1 \cup R_2) = r(R_1) \cup r(R_2)

r(R1​∪R2​)=r(R1​)∪r(R2​)

Symmetric closure union :

R

1

R_1

R1​ Relationship And

R

2

R_2

R2​ Relationship Combine Of Symmetric closure , be equal to

R

1

R_1

R1​ Symmetric closure of relation And

R

2

R_2

R2​ Symmetric closure of relation Union ;

s

(

R

1

∪

R

2

)

=

s

(

R

1

)

∪

s

(

R

2

)

s(R_1 \cup R_2) = s(R_1) \cup s(R_2)

s(R1​∪R2​)=s(R1​)∪s(R2​)

Transitive closure union :

R

1

R_1

R1​ Relationship And

R

2

R_2

R2​ Relationship Combine Of Pass closures , contain

R

1

R_1

R1​ Transitive closure of relation And

R

2

R_2

R2​ Transitive closure of relation Union ;

t

(

R

1

∪

R

2

)

⊇

t

(

R

1

)

∪

t

(

R

2

)

t(R_1 \cup R_2) \supseteq t(R_1) \cup t(R_2)

t(R1​∪R2​)⊇t(R1​)∪t(R2​)

Four 、 Transitive closure union counterexample

---

Pass closures Counter examples of :

aggregate

A

=

{

a

,

b

}

A = \{a, b\}

A={ a,b}

Relationship

R

1

=

{

<

a

,

b

>

}

R_1 = \{ <a,b> \}

R1​={ <a,b>} , Relationship

R

2

=

{

<

b

,

a

>

}

R_2 = \{ <b,a> \}

R2​={ <b,a>}

R

1

R_1

R1​ Transitive closure of relation :

t

(

R

1

)

=

{

<

a

,

b

>

}

t(R_1) = \{ <a,b> \}

t(R1​)={ <a,b>}

R

2

R_2

R2​ Transitive closure of relation :

t

(

R

2

)

=

{

<

b

,

a

>

}

t(R_2) = \{ <b,a> \}

t(R2​)={ <b,a>}

Closure of union :

t

(

R

1

∪

R

2

)

=

{

<

a

,

b

>

,

<

a

,

a

>

,

<

b

,

a

>

,

<

b

,

b

>

}

t(R_1 \cup R_2) = \{ <a,b> , <a,a> , <b,a> , <b,b> \}

t(R1​∪R2​)={ <a,b>,<a,a>,<b,a>,<b,b>}

Union of closures :

t

(

R

1

)

∪

t

(

R

2

)

=

{

<

a

,

b

>

,

<

b

,

a

>

}

t(R_1) \cup t(R_2) = \{ <a,b> , <b, a> \}

t(R1​)∪t(R2​)={ <a,b>,<b,a>} , The relationship is non transitive ;