background image

S

(

µ

)

S

(

µ

)

=

µ

0

S

(

µ

)

µ

S

(

µ

)

µ

2

S

(

µ

)

. . .

= (

µ

0

µ

1

µ

2

. . .

)

(

µ

1

µ

2

µ

3

. . .

)

(

µ

2

µ

3

µ

4

. . .

)

=

µ

0

µ

1

µ

2

. . .

=

S

(

µ

)

.

7.3

Connectedness regarding binary relations

Before going to research connectedness for funcoids and reloids we will excurse
into the basic special case of connectedness regarding binary relations on a set

.

Definition 58

A set

A

is called

(strongly) connected

regarding a binary re-

lation

µ

when

X

P

(dom

µ

)

\ {∅}

, Y

P

(im

µ

)

\ {∅}

: (

X

Y

=

A

X

[

µ

]

Y

)

.

Let

be a set.

Definition 59

Path

between two elements

a, b

in a set

A

through

binary relation

µ

is the finite sequence

x

0

. . . x

n

where

x

0

=

a

,

x

n

=

b

for

n

N

and

x

i

(

µ

A

×

A

)

x

i

+1

for every

i

= 0

, . . . , n

1

.

n

is called path

length

.

Proposition 44

There exists path between every element

a

and that ele-

ment itself.

Proof

It is the path consisting of one vertex (of length 0).

Proposition 45

There is a path from element

a

to element

b

in a set

A

through

a binary relation

µ

iff

a

(

S

(

µ

A

×

A

))

b

(that is

(

a, b

)

S

(

µ

A

×

A

)

).

Proof

If a path from

a

to

b

exists, then

{

b

} ⊆ h

(

µ

A

×

A

)

n

i {

a

}

where

n

is the

path length. Consequently

{

b

} ⊆ h

S

(

µ

A

×

A

)

i {

a

}

;

a

(

S

(

µ

A

×

A

))

b

.

If

a

(

S

(

µ

A

×

A

))

b

then exists

n

N

such that

a

(

µ

A

×

A

)

n

b

. By defi-

nition of composition of binary relations this means that there exist finite
sequence

x

0

. . . x

n

where

x

0

=

a

,

x

n

=

b

for

n

N

and

x

i

(

µ

A

×

A

)

x

i

+1

for every

i

= 0

, . . . , n

1. That is there is path from

a

to

b

.

65