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.

Definition

10

.

The

identity relation

on a set

A

is id

A

=

n

(

a

;

a

)

a

A

o

.

Definition

11

.

A

preorder

on a set

A

is a binary relation

v

which is:

reflexive on

A

((

v

)

id

A

);

transitive ((

v

)

(

v

)

(

v

)).

Definition

12

.

A

partial order

on a set

A

is a preorder on

A

which is anti-

symmetric ((

v

)

(

v

)

(=)).

The reverse relation is denoted

w

.

Definition

13

.

a

is a subelement of

b

(or what is the same

a

is

contained

in

b

or

b

contains

a

) iff

a

v

b

.

Obvious

14

.

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

Definition

15

.

A poset is a set

A

together with a partial order on it is called

a

partially ordered set

(

poset

for short).

Definition

16

.

Strict partial order

@

corresponding to the partial order

v

on

a set

A

is defined by the formula (

@

) = (

v

)

\

id

A

.

Definition

17

.

A partial order on a set

A

restricted

to a set

B

A

is (

v

)

(

B

×

B

).

Obvious

18

.

A partial order on a set

A

restricted to a set

B

A

is a partial

order on

B

.

The

least

element

of a poset

A

is defined by the formula

a

A

:

⊥ v

a

.

The

greatest

element

>

of a poset

A

is defined by the formula

a

A

:

> w

a

.

Proposition

19

.

There exist no more than one least element and no more

than one greatest element (for a given poset).

Proof.

By antisymmetry.

Definition

20

.

The

dual

order for

v

is

w

.

Obvious

21

.

Dual of a partial order is a partial order.

Definition

22

.

The

dual

poset for a poset (

A

;

v

) is the poset (

A

;

w

).

Below we will sometimes use

duality

that is replacement of the partial order and

all related operations and relations with their duals. In other words, it is enough

to prove a theorem for an order

v

and the similar theorem for

w

follows by duality.

12