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

14

.

The

identity relation

on a set

A

is id

A

=

n

(

a,a

)

a

A

o

.

Definition

15

.

A

preorder

on a set

A

is a binary relation

v

on

A

which is:

reflexive

on

A

that is (

v

)

id

A

or what is the same

x

A

:

x

v

x

;

transitive

that is (

v

)

(

v

)

(

v

) or what is the same

x, y, z

: (

x

v

y

y

v

z

x

v

z

)

.

Definition

16

.

A

partial order

on a set

A

is a preorder on

A

which is

anti-

symmetric

that is (

v

)

(

v

)

id

A

or what is the same

x, y

A

: (

x

v

y

y

v

x

x

=

y

)

.

The reverse relation is denoted

w

.

Definition

17

.

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

18

.

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

Definition

19

.

A set

A

together with a partial order on it is called a

partially

ordered set

(

poset

for short).

An example of a poset is the set

R

of real numbers with

v

=

.

Another example is the set

P

A

of all subsets of an arbitrary fixed set

A

with

v

=

. Note that this poset is (in general) not linear (see definition of

linear

poset

below.)

Definition

20

.

Strict partial order

@

corresponding to the partial order

v

on

a set

A

is defined by the formula (

@

) = (

v

)

\

id

A

. In other words,

a

@

b

a

v

b

a

6

=

b.

An example of strict partial order is

<

on the set

R

of real numbers.

Definition

21

.

A partial order on a set

A

restricted

to a set

B

A

is (

v

)

(

B

×

B

).

Obvious

22

.

A partial order on a set

A

restricted to a set

B

A

is a partial

order on

B

.

Definition

23

.

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

.

15