background image

Chapter 2
Common knowledge, part 1

In this chapter we will consider some well known mathematical theories. If you already know them
you may skip reading this chapter (or its parts).

2.1 Order theory

2.1.1 Posets

Denition 2.1.

The

identity relation

on a set

A

is id

A

=

f

(

a

;

a

)

j

a

2

A

g

.

Denition 2.2.

A

preorder

on a set

A

is a binary relation

v

which is:

reexive on

A

(

(

v

)

id

A

);

transitive (

(

v

)

(

v

)

(

v

)

).

Denition 2.3.

A

partial order

on a set

A

is a preorder on

A

which is antisymmetric (

(

v

)

\

(

v

)

¡

1

(=)

).

The reverse relation is denoted

w

.

Denition 2.4.

a

is a

subelement

of

b

(or what is the same

a

is

contained

in

b

or

b

contains

a

)

i

a

v

b

.

Obvious 2.5.

The reverse of a partial order is also a partial order.

Denition 2.6.

A poset is a set

A

together with a partial order on it is called a

partially ordered

set

(

poset

for short).

Denition 2.7.

Strict partial order

@

corresponding to the partial order

v

on a set

A

is dened

by the formula

(

@

) = (

v

)

n

id

A

.

Denition 2.8.

A partial order on a set

A

restricted

to a set

B

A

is

(

v

)

\

(

B

B

)

.

Obvious 2.9.

A partial order on a set

A

restricted to a set

B

A

is a partial order on

B

.

Denition 2.10.

The

least

element

0

of a poset

A

is dened by the formula

8

a

2

A

: 0

v

a

.

The

greatest

element

1

of a poset

A

is dened by the formula

8

a

2

A

: 1

w

a

.

Proposition 2.11.

There exist no more than one least element and no more than one greatest

element (for a given poset).

Proof.

By antisymmetry.

Denition 2.12.

The

dual

order for

v

is

w

.

17