background image

12.3. CONNECTEDNESS REGARDING BINARY RELATIONS

226

Proof.

S

(

µ

)

S

(

µ

) =

µ

0

t

S

(

µ

)

t

µ

S

(

µ

)

t

µ

2

S

(

µ

)

t · · ·

=

(

µ

0

t

µ

1

t

µ

2

t

. . .

)

t

(

µ

1

t

µ

2

t

µ

3

t

. . .

)

t

(

µ

2

t

µ

3

t

µ

4

t

. . .

) =

µ

0

t

µ

1

t

µ

2

t · · ·

=

S

(

µ

)

.

12.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

f

.

This is commonly studied in “graph theory” courses.

Digraph

as commonly

defined is essentially the same as an endomorphism of the category

Rel

.

Definition

1191

.

A set

A

is called

(strongly) connected

regarding a binary

relation

µ

on

U

when

X, Y

P

U

\ {∅}

: (

X

Y

=

A

X

[

µ

]

Y

)

.

Definition

1192

.

A typed set

A

of type

U

is called

(strongly) connected

re-

garding a

Rel

-endomorphism

µ

on

U

when

X, Y

T

(Ob

µ

)

\ {⊥

T

(Ob

µ

)

}

: (

X

t

Y

=

A

X

[

µ

]

Y

)

.

Obvious

1193

.

A typed set

A

is connected regarding

Rel

-endomorphism

µ

on

its type iff GR

A

is connected regarding GR

µ

.

Let

f

be a set.

Definition

1194

.

Path

between two elements

a, b

f

in a set

A

f

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

1195

.

There exists path between every element

a

f

and that

element itself.

Proof.

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

Proposition

1196

.

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 there exists

n

N

such that

a

(

µ

A

×

A

)

n

b

.

By definition 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 a path

from

a

to

b

.

Proposition

1197

.

There is a path from element

a

to element

b

in a set

A

through a binary relation

µ

iff

a

(

S

1

(

µ

A

×

A

))

b

(that is (

a, b

)

S

1

(

µ

A

×

A

)).

Proof.

Similar to the previous proof.

Theorem

1198

.

The following statements are equivalent for a binary relation

µ

and a set

A

:

1

. For every

a, b

A

there is a nonzero-length path between

a

and

b

in

A

through

µ

.