当前位置：网站首页>[set theory] relational power operation (relational power operation | examples of relational power operation | properties of relational power operation)

[set theory] relational power operation (relational power operation | examples of relational power operation | properties of relational power operation)

2022-07-03 05:03:00 【Programmer community】

List of articles

One 、 Relational power operation
Two 、 Examples of relational power operations
3、 ... and 、 Properties of relational power operation

One 、 Relational power operation

Relationship

$R$ Of

$n$ Power definition :

⊆

∈

R \subseteq A \times A , n \in N

$R \subseteq A \times A, n \in N$

{

∘

(

≥

)

\begin{cases} R^0 = I_A & \\ R^{n +1} = R^n \circ R & ( n \geq 0 ) \end{cases}

${R^{0} = I_{A} R^{n + 1} = R^{n} \circ R (n \geq 0)$

Relationship

$R$ yes aggregate

$A$ Upper Binary relationship ,

$R$ Of

$0$ The next power

R^0

$R^{0}$ It's an identity relationship

I_A

$I_{A}$ , Relationship

$R$ Of

n + 1

$n + 1$ The power is equal to

∘

R^{n + 1} = R^n \circ R

$R^{n + 1} = R^{n} \circ R$ among

≥

n \geq 0

$n \geq 0$ ;

∘

R^1 = R^0 \circ R = R

$R^{1} = R^{0} \circ R = R$ , Identity relation and Relationship

$R$ Reverse order synthesis , The result is still related

$R$ , This relationship

$R$ It can be any relationship ;

The identity relationship is aggregate

$A$ Each element in has its own relationship with itself ;

Relationship

$R$ Power operation result

R^n

$R^{n}$ Relationship It's also a collection

$A$ The binary relationship on , So there is

⊆

R^n \subseteq A \times A

$R^{n} \subseteq A \times A$

Relationship

$R$ Of

$n$ The next power , Namely

$n$ individual

$R$ Relationship reverse order synthesis :

∘

⋯

∘

⏟

individual

The inverse

order

become

R^n = \begin{matrix} \underbrace{ R \circ R \circ \cdots \circ R } \\ n individual R Reverse order synthesis \end{matrix}

$R^{n} = R \circ R \circ \dots \circ R n individual R The inverse order close become$

Two 、 Examples of relational power operations

aggregate

{

}

A = \{ a, b, c \}

$A = {a, b, c}$ Relationship

$R$ yes aggregate

$A$ The binary relationship on ,

⊆

R \subseteq A \times A

$R \subseteq A \times A$ ,

{

}

R = \{ <a,b> , <b,a> , <a, c> \}

$R = {< a, b >, < b, a >, < a, c >}$

Relationship

$R$ Of Number of power sets :

$A$ It's a finite set ,

$A$ The number of ordered pairs on is

3 \times 3 = 9

$3 \times 3 = 9$ individual ,

$A$ The number of binary relations on , That is, the number of power sets of ordered pairs , yes

512

2^{3\times 3} =512

$2^{3 \times 3} = 512$ individual ;

Relationship

$R$ Of

$0$ The next power :

R^0 = I_A

$R^{0} = I_{A}$ ,

$R$ Relational

$0$ Power is an identity relationship , Graph is that every vertex has a ring , There is no relationship between vertices ;

Insert picture description here

Relationship

$R$ Of

$1$ The next power :

∘

R^1 = R^0 \circ R = R

$R^{1} = R^{0} \circ R = R$ , Identity

I_A

$I_{A}$ With any relationship in reverse order , The result is still that relationship ;

Insert picture description here

Relationship

$R$ Of

$2$ The next power :

∘

{

}

∘

{

}

{

}

\begin{array}{lcl}R^2 & = & R^0 \circ R \\\\ &=& R \circ R \\\\ &=& \{ <a,b> , <b,a> , <a, c> \} \circ \{ <a,b> , <b,a> , <a, c> \} \\\\ &=& \{ <a,a>, <b, b> , <b,c> \}\end{array}

$R^{2} = = = = R^{0} \circ R R \circ R {< a, b >, < b, a >, < a, c >} \circ {< a, b >, < b, a >, < a, c >} {< a, a >, < b, b >, < b, c >}$

Note that the above

∘

\circ

$\circ$ Reverse order synthesis during operation , Synthesize the previous relationship from the latter relationship ;

Insert picture description here

Relationship

$R$ Of

$3$ The next power : And

R_1

$R_{1}$ identical

∘

{

}

∘

{

}

{

}

\begin{array}{lcl}R^3 & = & R^1 \circ R \\\\ &=& \{ <a,a>, <b, b> , <b,c> \} \circ \{ <a,b> , <b,a> , <a, c> \} \\\\ &=& \{ <a,b>, <a, c> , <b,a> \} \\\\ &=& R^1 \end{array}

$R^{3} = = = = R^{1} \circ R {< a, a >, < b, b >, < b, c >} \circ {< a, b >, < b, a >, < a, c >} {< a, b >, < a, c >, < b, a >} R^{1}$