[set theory] relation properties (transitivity | transitivity examples | transitivity related theorems)

One 、 Transitivity

---

Transitivity :

R

⊆

A

×

A

R \subseteq A \times A

R⊆A×A

R

R

R It's delivered

⇔

\Leftrightarrow

⇔

∀

x

∀

y

∀

z

(

x

∈

A

∧

y

∈

A

∧

z

∈

A

∧

x

R

y

∧

y

R

z

→

x

R

z

)

\forall x \forall y \forall z ( x \in A \land y \in A \land z \in A \land xRy \land yRz \to xRz )

∀x∀y∀z(x∈A∧y∈A∧z∈A∧xRy∧yRz→xRz)

⇔

\Leftrightarrow

⇔

(

∀

x

∈

A

)

(

∀

y

∈

A

)

(

∀

z

∈

A

)

[

x

R

y

∧

y

R

z

→

x

R

z

]

(\forall x \in A)(\forall y \in A)(\forall z \in A)[xRy \land yRz \to xRz]

(∀x∈A)(∀y∈A)(∀z∈A)[xRy∧yRz→xRz]

R

R

R Non transitive

⇔

\Leftrightarrow

⇔

∃

x

∃

y

∃

z

(

x

∈

A

∧

y

∈

A

∧

z

∈

A

∧

x

R

y

∧

y

R

z

→

¬

x

R

z

)

\exist x \exist y \exist z ( x \in A \land y \in A \land z \in A \land xRy \land yRz \to \lnot xRz )

∃x∃y∃z(x∈A∧y∈A∧z∈A∧xRy∧yRz→¬xRz)

Transitivity description : Any three elements

x

,

y

,

z

x,y,z

x,y,z ,

x

x

x And

y

y

y It matters

x

R

y

xRy

xRy ,

y

y

y and

z

z

z It matters

y

R

z

yRz

yRz ,

x

x

x and

z

z

z It matters

x

R

z

xRz

xRz ;

Greater than , Greater than or equal to , Less than , Less than or equal to , be equal to , Such as relationship , It's delivered ;

Two 、 Transitive examples

---

In the above diagram , accord with When

x

R

y

xRy

xRy ,

y

R

z

yRz

yRz when , There is

x

R

z

xRz

xRz , Then the above relationship is transitive ;

In the above diagram , accord with When

x

R

y

xRy

xRy ,

y

R

z

yRz

yRz when , non-existent

x

R

z

xRz

xRz , Then the above relationship is not transitive ;

In the above diagram , Do not conform to the

x

R

y

xRy

xRy ,

y

R

z

yRz

yRz The premise of , Therefore, there is no need to verify whether it exists

x

R

z

xRz

xRz , Transitivity exists by default , When there is a

x

R

y

xRy

xRy ,

y

R

z

yRz

yRz when , There must also be

x

R

z

xRz

xRz , If the premise does not hold , Relationships are transitive by default ;

Empathy , The above diagram does not meet the premise , The default is passed ;

The preconditions of the above diagram meet , Yes

x

R

y

xRy

xRy ,

y

R

z

yRz

yRz when , non-existent

x

R

z

xRz

xRz , At this time, the transmission is not established , Therefore, the above relationship is non transitive ;

3、 ... and 、 Transitivity theorem

---

Transitivity theorem :

R

R

R It's delivered

⇔

\Leftrightarrow

⇔

R

∘

R

⊆

R

R \circ R \subseteq R

R∘R⊆R

⇔

\Leftrightarrow

⇔

R

−

1

R^{-1}

R−1 It's delivered

⇔

\Leftrightarrow

⇔

∀

i

∀

j

,

M

(

R

∘

R

)

(

i

,

j

)

≤

M

(

R

)

(

i

,

j

)

\forall i \forall j , M(R \circ R)(i,j) \leq M(R)(i,j)

∀i∀j,M(R∘R)(i,j)≤M(R)(i,j)

⇔

\Leftrightarrow

⇔

G

(

R

)

G(R)

G(R) In the diagram ,

∀

a

i

∀

a

j

∀

a

k

\forall a_i \forall a_j \forall a_{k}

∀ai​∀aj​∀ak​ , If there is a directed edge

<

a

i

,

a

j

>

<a_i, a_j>

<ai​,aj​> and

<

a

j

,

a

k

>

<a_j , a_k>

<aj​,ak​> , Then there must be a directed edge

<

a

j

,

a

k

>

<a_j , a_k>

<aj​,ak​> ;