background image

16.2. FINITE UNIONS OF CARTESIAN PRODUCTS

259

Proof.

Let

a

X

. Then

[

a

] =

b

S

Q

X

0

Q

: (

a

X

0

b

X

0

)

b

S

Q

a

X

b

X

=

b

S

Q

b

X

=

X.

But [

a

]

R

(

Q

).

X

Y

6

=

follows from

Y

X

by the previous proposition.

Proposition

1380

.

If

X

Q

then

X

=

S

(

R

(

Q

)

P

X

).

Proof.

S

(

R

(

Q

)

P

X

)

X

is obvious.

Let

x

X

. Then there is

Y

R

(

Q

) such that

x

Y

. We have

Y

X

that

is

Y

P

X

by a proposition above. So

x

Y

where

Y

R

(

Q

)

P

X

and thus

x

S

(

R

(

Q

)

P

X

). We have

X

S

(

R

(

Q

)

P

X

).

16.2. Finite unions of Cartesian products

Let

A

,

B

be sets.

I will denote

X

=

A

\

X

.

Let denote Γ(

A, B

) the set of all finite unions

X

0

×

Y

0

. . .

X

n

1

×

Y

n

1

of

Cartesian products, where

n

N

and

X

i

P

A

,

Y

i

P

B

for every

i

= 0

, . . . , n

1.

Proposition

1381

.

The following sets are pairwise equal:

1

. Γ(

A, B

);

2

. the set of all sets of the form

S

X

S

(

X

×

Y

X

) where

S

are finite collections

on

A

and

Y

X

P

B

for every

X

S

;

3

. the set of all sets of the form

S

X

S

(

X

×

Y

X

) where

S

are finite partitions

of

A

and

Y

X

P

B

for every

X

S

;

4

. the set of all finite unions

S

(

X,Y

)

σ

(

X

×

Y

) where

σ

is a relation between

a partition of

A

and a partition of

B

(that is dom

σ

is a partition of

A

and im

σ

is a partition of

B

).

5

. the set of all finite intersections

T

i

=0

,...,n

1

X

i

×

Y

i

X

i

×

B

where

n

N

and

X

i

P

A

,

Y

i

P

B

for every

i

= 0

, . . . , n

1.

Proof.

1

2

,

2

3

Obvious.

1

2

Let

Q

Γ(

A, B

). Then

Q

=

X

0

×

Y

0

. . .

X

n

1

×

Y

n

1

. Denote

S

=

{

X

0

, . . . , X

n

1

}

. We have

Q

=

S

X

0

S

X

0

×

S

i

=0

,...,n

1

n

Y

i

X

i

=

X

0

o

2

.

2

3

Let

Q

=

S

X

S

(

X

×

Y

X

) where

S

is a finite collection on

A

and

Y

X

P

B

for every

X

S

. Let

P

=

[

X

0

R

(

S

)

 

X

0

×

[

X

S

Y

X

X

S

:

X

0

X

!

.

To finish the proof let’s show

P

=

Q

.

h

P

i

{

x

}

=

S

X

S

n

Y

X

X

S

:

X

0

X

o

where

x

X

0

.

Thus

h

P

i

{

x

}

=

S

Y

X

X

S

:

x

X

 

=

h

Q

i

{

x

}

. So

P

=

Q

.

4

3

.

S

(

X,Y

)

σ

(

X

×

Y

) =

S

X

dom

σ

X

×

S

n

Y

P

B

(

X,Y

)

σ

o

3

.