background image

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

.

Denition 11.8.

A set

A

is called

(strongly) connected

regarding a binary relation

when

8

X

2

P

(

dom

)

n f;g

; Y

2

P

(

im

)

n f;g

: (

X

[

Y

=

A

)

X

[

]

Y

)

:

Let

f

be a set.

Denition 11.9.

Path

between two elements

a; b

2

f

in a set

A

f

through binary relation

is

the nite sequence

x

0

::: x

n

where

x

0

=

a

,

x

n

=

b

for

n

2

N

and

x

i

(

\

A

A

)

x

i

+1

for every

i

= 0

; :::;

n

¡

1

.

n

is called path

length

.

Proposition 11.10.

There exists path between every element

a

2

f

and that element itself.

Proof.

It is the path consisting of one vertex (of length

0

).

Proposition 11.11.

There is a path from element

a

to element

b

in a set

A

through a binary

relation

i

a

(

S

(

\

A

A

))

b

(that is

(

a; b

)

2

S

(

\

A

A

)

).

Proof.

)

.

If a path from

a

to

b

exists, then

f

b

g  h

(

\

A

A

)

n

if

a

g

where

n

is the path length.

Consequently

f

b

g  h

S

(

\

A

A

)

if

a

g

;

a

(

S

(

\

A

A

))

b

.

(

.

If

a

(

S

(

\

A

A

))

b

then there exists

n

2

N

such that

a

(

\

A

A

)

n

b

. By denition of

composition of binary relations this means that there exist nite sequence

x

0

::: x

n

where

x

0

=

a

,

x

n

=

b

for

n

2

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

The following statements are equivalent for a binary relation

and a set

A

:

1. For every

a; b

2

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

2

A

there is a path between

a

and

b

in

A

through

. Then

a

(

S

(

\

A

A

))

b

for every

a; b

2

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

there exists a path from

a

to

b

.

(3)

)

(4).

Suppose

:

(

X

[

\

(

A

A

)]

Y

)

for some

X ; Y

2

P

f

n f;g

such that

X

[

Y

=

A

. Then

by a lemma

:

(

X

[(

\

(

A

A

))

n

]

Y

)

for every

n

2

N

. Consequently

:

(

X

[

S

(

\

(

A

A

))]

Y

)

.

So

S

(

\

(

A

A

)) =

/

A

A

.

148

Connectedness regarding funcoids and reloids