background image

Proof

(1)

(2)

Let for every

a, b

A

there is a path between

a

and

b

in

A

through

µ

.

Then

a

(

S

(

µ

C

(

A

×

A

)))

b

for every

a, b

A

. It is possible only when

S

(

µ

C

(

A

×

A

))

A

×

A

.

(3)

(1)

For every two vertices

a

and

b

we have

a

(

S

(

µ

(

A

×

C

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

×

C

A

)

Y

) for some

X, Y

P

U

\ {∅}

such

that

X

Y

=

A

and

X

Y

=

. Then by a lemma

¬

(

X

(

µ

(

A

×

C

A

))

n

Y

)

for every

n

N

. Consequently

¬

(

X

S

(

µ

(

A

×

C

A

))

Y

). So

S

(

µ

(

A

×

C

A

))

6

=

A

×

A

.

(4)

(3)

If

S

(

µ

C

(

A

×

A

))

{

v

}

=

A

for every vertex

v

then

S

(

µ

C

(

A

×

A

)) =

A

×

C

A

. Consider the remaining case when

V

def

=

S

(

µ

(

A

×

C

A

))

{

v

} ⊂

A

for some vertex

v

. Let

W

=

A

\

V

. If card

A

= 1 then

S

(

µ

C

(

A

×

A

))

(=)

|

A

=

A

×

C

A

; otherwise

W

6

=

. Then

V

W

=

A

and so

V

[

µ

]

W

what

is equivalent to

V

µ

C

(

A

×

A

)

W

that is

µ

C

(

A

×

A

)

V

W

6

=

.

This is impossible because

µ

(

A

×

C

A

)

V

=

µ

(

A

×

C

A

)

 

S

(

µ

(

A

×

C

A

))

V

S

(

µ

(

A

×

C

A

))

V

=

V

.

(2)

(3)

Because

S

(

µ

(

A

×

C

A

))

A

×

C

A

.

(5)

(4)

Obvious.

(4)

(5)

Let (4) holds and let

X

Y

=

A

. If

X

=

Y

=

A

then

X

[

µ

]

Y

because

A

6

=

. Otherwise

X

A

or

Y

A

. Let for example

X

A

. Then

Y

\

X

6

=

. So

X

[

µ

]

Y

\

X

by (4) and consequently

X

[

µ

]

Y

.

Corollary 2

A set

A

is connected regarding a digraph

µ

iff it is connected

regarding

µ

(

A

×

C

A

)

.

Theorem 4

The following statements are equivalent for each digraph

µ

=

(

U

;

f

)

and sets

X, Y

P

U

:

1.

X T

(

U

;

τ

)

Y

;

2.

X

×

C

Y

S

(

µ

((

X

Y

)

×

C

(

X

Y

)))

;

3.

X

×

C

Y

=

S

(

µ

((

X

Y

)

×

C

(

X

Y

)))

.

8