 11.3. CONNECTEDNESS REGARDING BINARY RELATIONS

166

I call

S

1

and

S

endomorphism series

.

We will consider the collection of all binary relations (on a set

f

), as well as the

collection of all funcoids and the collection of all reloids on a fixed set, as categories

with single object

f

and the identity morphisms id

f

, id

FCD

(

f

)

, id

RLD

(

f

)

.

Proposition

880

.

The relation

S

(

µ

) is transitive for the category of binary

relations.

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

(

µ

)

.

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

.

FiXme

: Say that this is commonly studied in “graph theory” courses.

Graph

as

commonly defined is essentially the same as an endomorphism of the category

Rel

.

Definition

881

.

A set

A

is called

(strongly) connected

regarding a binary

relation

µ

when

X

P

(dom

µ

)

\ {∅}

, Y

P

(im

µ

)

\ {∅}

: (

X

Y

=

A

X

[

µ

]

Y

)

.

Let

f

be a set.

Definition

882

.

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

883

.

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

884

.

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

.

Theorem

885

.

The following statements are equivalent for a binary 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

µ

.