background image

CHAPTER 5

Boolean funcoids

1. One-element boolean lattice

Let

A

be a boolean lattice and

B

=

P

0. It’s sole element is

.

f

pFCD

(

A

;

B

)

⇔ ∀

X

A

: (

h

f

i

X

6 ⊥ ⇔ h

f

1

i⊥ 6

X

)

⇔ ∀

X

A

: (0

f

1

⊥ 6

X

)

⇔ ∀

X

A

:

f

1

⊥ 

X

⇔ ∀

X

A

:

f

1

=

A

f

1

=

A

f

1

=

{

(

;

A

)

}

.

Thus card

pFCD

(

A

;

P

0) = 1.

2. Two-element boolean lattice

Consider the two-element boolean lattice

B

=

P

1.

Let

f

be a pointfree protofuncoid from

A

to

B

(that is (

A

;

B

;

α

;

β

) where

α

B

A

,

β

A

B

).

f

pFCD

(

A

;

B

)

⇔ ∀

X

A

, Y

B

: (

h

f

i

X

6

Y

f

1

Y

6

X

)

⇔ ∀

X

A

, Y

B

: ((0

∈ h

f

i

X

0

Y

)

(1

∈ h

f

i

X

1

Y

)

⇔ h

f

1

i

Y

6

X

).

T

=

n

X

A

0

∈h

f

i

X

o

is an ideal. Really: That it’s an upper set is obvious. Let

P

Q

n

X

A

0

∈h

f

i

X

o

. Then 0

∈ h

f

i

(

P

Q

) =

h

f

i

P

∪ h

f

i

Q

; 0

∈ h

f

i

P

0

∈ h

f

i

Q

.

Similarly

S

=

n

X

A

1

∈h

f

i

X

o

is an ideal.

Let now

T, S

P

A

be ideals. Can we restore

h

f

i

? Yes, because we know

0

∈ h

f

i

X

and 1

∈ h

f

i

X

for every

X

A

.

So it is equivalent to

X

A

, Y

B

: ((

X

T

0

Y

)

(

X

S

1

Y

)

h

f

1

i

Y

6

X

).

f

pFCD

(

A

;

B

) is equivalent to conjunction of all rows of this table:

Y

equality

f

1

=

{0}

X

T

f

1

{

0

} 6

X

{1}

X

S

f

1

{

1

} 6

X

{0,1}

X

T

X

S

f

1

{

0

,

1

} 6

X

Simplified:

Y

equality

f

1

=

{0}

T

=

f

1

{

0

}

{1}

S

=

f

1

{

1

}

{0,1}

T

S

=

f

1

{

0

,

1

}

From the last table it follows that

T

and

S

are principal ideals.

So we can take arbitrary either

f

1

{

0

}

,

h

f

1

i{

1

}

or principal ideals

T

and

S

.

In other words, we take

f

1

{

0

}

,

h

f

1

i{

1

}

arbitrary and independently. So

we have

pFCD

(

A

;

B

) equivalent to product of two instances of

A

. So it a boolean

lattice.

FiXme

: I messed product with disjoint union below.)

35