background image

Theorem 73

The following statements are equivalent for a relation

µ

and a

set

A

:

1. For every

a, b

A

there is a path between

a

and

b

in

A

through

µ

.

2.

S

(

µ

(

A

×

A

))

A

×

A

.

3.

S

(

µ

(

A

×

A

)) =

A

×

A

.

4.

A

is connected regarding

µ

.

Proof

(1)

(2)

Let for every

a, b

A

there is a path between

a

and

b

in

A

through

µ

. Then

a

(

S

(

µ

A

×

A

))

b

for every

a, b

A

. It is possible only when

S

(

µ

(

A

×

A

))

A

×

A

.

(3)

(1)

For every two vertices

a

and

b

we have

a

(

S

(

µ

A

×

A

))

b

. So (by

the previous theorem) for every two vertices

a

and

b

exist path from

a

to

b

.

(3)

(4)

Suppose that

¬

(

X

[

µ

(

A

×

A

)]

Y

) for some

X, Y

P

\ {∅}

such

that

X

Y

=

A

. Then by a lemma

¬

(

X

[(

µ

A

×

A

)

n

]

Y

) for every

n

N

. Consequently

¬

(

X

[

S

(

µ

A

×

A

)]

Y

). So

S

(

µ

A

×

A

)

6

=

A

×

A

.

(4)

(3)

If

h

S

(

µ

(

A

×

A

))

i {

v

}

=

A

for every vertex

v

then

S

(

µ

A

×

A

) =

A

×

A

. Consider the remaining case when

V

def

=

h

S

(

µ

A

×

A

)

i {

v

} ⊂

A

for some vertex

v

. Let

W

=

A

\

V

. If card

A

= 1 then

S

(

µ

A

×

A

)

(=) =

A

×

A

; otherwise

W

6

=

. Then

V

W

=

A

and so

V

[

µ

]

W

what

is equivalent to

V

[

µ

A

×

A

]

W

that is

h

µ

A

×

A

i

V

W

6

=

. This

is impossible because

h

µ

A

×

A

i

V

=

h

µ

A

×

A

i h

S

(

µ

A

×

A

)

i

V

=

h

S

1

(

µ

A

×

A

)

i

V

⊆ h

S

(

µ

A

×

A

)

i

V

=

V

.

(2)

(3)

Because

S

(

µ

A

×

A

)

A

×

A

.

Corollary 20

A set

A

is connected regarding a binary relation

µ

iff it is con-

nected regarding

µ

(

A

×

A

)

.

Definition 60

A

connected component

of a set

A

regarding a binary relation

F

is a maximal connected subset of

A

.

Theorem 74

The set

A

is partitioned into connected components (regarding

every binary relation

F

).

66