Ÿ

7

.

F

unk

je,

rela je

i

p

orz¡dki

Rela je

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

7

A

F

unk

je

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

7

C

Cz± io

w

e

p

orz¡dki

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

7

F

Linio

w

e

p

orz¡dki

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

7

H

Izomorzm

y

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

7

J

‚

wi zenia

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

7

O

Zadania

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

7

P

Rela je

☛

Zbiór,

którego

elemen

t

y

s¡

parami

up

orz¡dk

o

w

an

ymi,

nazyw

a¢

b

dziem

y

r

ela j¡

.

Rela jami

s¡

m.in.

zbiór

pust

y

oraz

k

a»dy

zbiór

p

osta i

u

× v

.

☛

W

ystpuj¡ e

dalej

rela je

b

dziem

y

ozna zali

literami

R

,

S

i

T

;

niektóre

sp

e jalne

rela je

b

d¡

ozna zane

ina zej,

przy

p

omo

y

sp

e jaln

y

h

sym

b

oli

taki

h

jak

<

,

≤

itd.

☛

Zbiory

D(R)

df

= {x :

∃

y

(x, y)

∈ R}

i

D

∗

(R)

df

= {y :

∃

x

(x, y)

∈ R}

to

o

dp

o

wiednio

dzie

dzina

i

prze

iwdzie-

dzina

rela ji

R

;

mo»na

wyk

aza¢,

»e

R

⊆ D(R) × D

∗

(R)

.

☛

T

o,

»e

dziedzina

i

prze iwdziedzina

s¡

p

opra

wnie

okre±lon

ymi

zbiorami,

wynik

a

z

aksjomatu

wy inania

i

z

tego,

»e

je±li

∃

y

(x, y)

∈ R

(

∃

x

(x, y)

∈ R

),

to

x

∈

S S

R

(

y

∈

S S

R

).

☛

Zamiast

pisa¢

(x, y)

∈ R

,

b

dziem

y

zasami

pisa¢

xRy

;

napis

xRy

zyta

si:

x

jest

w

rela ji

R

z

y

.

Przyjm

ujem

y

p

onadto,

»e:



∈

u

jest

rela j¡

dan¡

wzorem

x

∈

u

y ⇔ x

∈ u ∧ y ∈ u ∧ (x ∈ y ∨ x = y)

;



⊆

u

jest

rela j¡

dan¡

wzorem

x

⊆

u

y ⇔ x

∈ u ∧ y ∈ u ∧ x ⊆ y

;



=

u

jest

rela j¡

dan¡

wzorem

x =

u

y ⇔ x

∈ u ∧ x = y

.

Ÿ

7

.

F

unk

je,

rela je

i

p

orz¡dki

7

A

Rela je

(2)

☛

Rela j¡

o

dwr

otn¡

do

rela ji

R

nazyw

a¢

b

dziem

y

rela j

R

−1

df

= {(y, x) : (x, y)

∈ R}

;

zªo»eniem

rela ji

R

,

S

jest

rela ja

RS

dana

wzorem

xRSy ⇔

∃

z

(xRz ∧ zSy)

.

☛

Rela ja

R

jest:



zwr

otna

w

zbiorze

u

,

o

ile

∀

x∈u

(xRx)

;



prze

iwzwr

otna

w

zbiorze

u

,

o

ile

∀

x∈u

¬

(xRx)

;



symetry zna

w

zbiorze

u

,

o

ile

∀

x∈u

∀

y∈u

(xRy ⇒ yRx)

;



antysymetry zna

w

zbiorze

u

,

o

ile

∀

x∈u

∀

y∈u

((xRy ∧ yRx) ⇒ y = x)

;



prze

ho

dnia

w

zbiorze

u

,

o

ile

∀

x∈u

∀

y∈u

∀

z∈u

((xRy ∧ yRz) ⇒ xRz)

;



sp

ójna

w

zbiorze

u

,

o

ile

∀

x∈u

∀

y∈u

(xRy ∨ yRx)

.

☛

Rela ja,

która

jest

zwrotna,

symetry zna

i

prze

ho

dnia

w

sumie

sw

o

jej

dziedzin

y

i

prze iwdziedzin

y

,

to

rela ja

r

ównowa»no± i

.

Przykªadem

rela ji

ró

wno

w

a»no± i

jest

=

u

.

☛

⊆

u

jest

rela j¡

zwrotn¡,

an

t

ysymetry zn¡

i

prze

ho

dni¡

w

u

;

∈

u

jest

zwrotna

i

an

t

ysymetry zna.

Ÿ

7

.

F

unk

je,

rela je

i

p

orz¡dki

7

B

F

unk

je

☛

Rela ja

R

jest

funk j¡

wtedy

i

t

ylk

o

wtedy

,

gdy

dla

k

a»dego

x

istnieje

o

na

jwy»ej

jedno

takie

y

,

»e

x

jest

w

rela ji

R

z

y

.



=

u

jest

funk

j¡



jest

to

tzw.

funk

ja

identy zno± iowa

;



u

× {v}

jest

funk

j¡



jest

to

tzw.

funk

ja

staªa

.

☛

W

ystpuj¡ e

dalej

funk

je

b

dziem

y

ozna zali

literami

e

,

f

,

g

i

h

;

je»eli

f

jest

funk

j¡,

to

jedyne

y

takie,

»e

xfy

b

dziem

y

ozna zali

sym

b

olem

f(x)

lub

f

x

.

☛

Bdziem

y

pisa¢

f : u → v

lub

u

∋ x 7→ f(x) ∈ v

,

ab

y

zazna zy¢,

»e

f

jest

funk

j¡,

której

dziedzin¡

jest

u

i

której

prze iwdziedzina

za

wiera

si

w

v

.

☛

Napis

f : u → v

zytam

y:

f

dziaªa

z

u

do

v

lub

f

przeksztaª

a

u

w

v

.

Zbiór

wszystki

h

funk

ji

dziaªa-

j¡ y

h

z

u

do

v

b

dziem

y

ozna za¢

sym

b

olem

v

u

;

v

u

jest

zbiorem,

gdy»

v

u

= {f

∈ P(u × v) : f : u → v}

.

Ÿ

7

.

F

unk

je,

rela je

i

p

orz¡dki

7

C

F

unk

je

(2)

☛

Ob

i

iem

funk

ji

f

do

zbioru

u

⊆ D(f)

nazyw

a¢

b

dziem

y

funk

j

f|

u

df

= {(x, y)

∈ f : x ∈ u}

;

zbiór

f[u]

df

= D

∗

(f|

u

)

to

obr

az

zbioru

u

wzgldem

funk

ji

f

.

Obraz

zbioru

ozna za

si

niekiedy

ina zej



zamiast

pisa¢

f[u]

pisze

si

{f

x

}

x∈u

lub

{f(x) : x

∈ u}

.

☛

Obraz

zbioru

wzgldem

funk

ji

ma

wiele

w

a»n

y

h

wªasno± i;

w

sz zególno± i,

pra

wdziw

e

s¡

nastpuj¡ e

implik

a je:



je»eli

x

⊆ D(f)

dla

k

a»dego

x

∈ u

,

to

f[

S

u] =

S

{f[x] : x

∈ u}

;



je»eli

x

⊆ D(f)

dla

k

a»dego

x

∈ u

i

u

6= ∅

,

to

f[

T

u]

⊆

T

{f[x] : x

∈ u}

;



je»eli

u

⊆ D(f)

i

v

⊆ D(f)

,

to

f[u] \ f[v]

⊆ f[u \ v]

;



je»eli

u

⊆ v ⊆ D(f)

,

to

f[u]

⊆ f[v]

.

☛

Przyjm

ujem

y

,

»e

je±li

f

jest

funk

j¡,

a

u

⊆ D(f)

zbiorem,

to

S

x∈u

f

x

df

=

S

f[u]

i

T

x∈u

f

x

df

=

T

f[u]

.

Ÿ

7

.

F

unk

je,

rela je

i

p

orz¡dki

7

D

F

unk

je

(3)

☛

F

unk

ja

f

jest

r

ó»nowarto± iowa

(jest

injek j¡

)

wtedy

i

t

ylk

o

wtedy

,

gdy

f

−1

jest

funk

j¡;

funk

ja

f : u → v

jest

na

(jest

suriek j¡

)

wtedy

i

t

ylk

o

wtedy

,

gdy

D

∗

(f) = v

.

☛

Nietrudno

jest

wyk

aza¢,

»e

funk

ja

f : u → v

jest

injek

j¡

(suriek

j¡)

wtedy

i

t

ylk

o

wtedy

,

gdy

x

6= y ⇒

f(x)

6= f(y)

dla

k

a»dy

h

x, y

∈ u

(

f[u] = v

).

☛

F

unk

ja,

która

jest

suriek

j¡

i

injek

j¡,

to

bijek ja

(funk

ja

wzajemnie

je

dnozna zna

).

Je»eli

f

jest

bijek

j¡,

to:



je»eli

x

⊆ D(f)

dla

k

a»dego

x

∈ u

i

u

6= ∅

,

to

f[

T

u] =

T

{f[x] : x

∈ u}

;



je»eli

u

⊆ D(f)

i

v

⊆ D(f)

,

to

f[u] \ f[v] = f[u \ v]

.

☛

Ka»da

funk

ja

staªa

jest

suriek

j¡;

k

a»da

funk

ja

iden

t

y zno± io

w

a

jest

bijek

j¡.

Przykªadem

injek

ji

mo»e

b

y¢

funk

ja

dana

wzorem

u

∋ x 7→ P(x) ∈ P(P(

S

u))

.

Ÿ

7

.

F

unk

je,

rela je

i

p

orz¡dki

7

E

Cz± io

w

e

p

orz¡dki

☛

Rela ja

6

R

jest

rela j¡

z± iowe

go

p

orz¡dku

w

zbiorze

u

wtedy

i

t

ylk

o

wtedy

,

gdy

jest

zwrotna,

an

t

ysymetry zna

i

prze

ho

dnia

w

zbiorze

u

.

☛

Przyjm

ujem

y

,

»e

je±li

6

R

jest

rela j¡

z± io

w

ego

p

orz¡dku,

to

<

R

jest

rela j¡

dan¡

wzorem

x <

R

y ⇔

x 6

R

y ∧ x

6= y

;

<

R

jest

rela j¡

prze iwzwrotn¡,

an

t

ysymetry zn¡

i

prze

ho

dni¡.

☛

Przyjm

ujem

y

,

»e

>

R

jest

rela j¡

dan¡

wzorem

x >

R

y ⇔ y 6

R

x

;

rela ja

>

R

jest,

o

ªat

w

o

spra

wdzi¢,

rela j¡

o

dwrotn¡

do

6

R

.

☛

Zbiór

v

⊆ u

jest

ªa« u hem

wtedy

i

t

ylk

o

wtedy

,

gdy

x 6

R

y

lub

y 6

R

x

dla

k

a»dy

h

x, y

∈ v

;

zbiór

v

⊆ u

jest

ªa« u

hem

wtedy

i

t

ylk

o

wtedy

,

gdy

6

R

jest

rela j¡

sp

ó

jn¡

w

v

.

☛

⊆

u

i

=

u

s¡

z± io

wymi

p

orz¡dk

ami

w

u

;

dla

niektóry

h

zbioró

w

u

tak»e

∈

u

jest

z± io

wym

p

orz¡dkiem

w

u

.

Ÿ

7

.

F

unk

je,

rela je

i

p

orz¡dki

7

F

Cz± io

w

e

p

orz¡dki

(2)

☛

Je»eli

6

R

jest

z± io

wym

p

orz¡dkiem

w

u

,

v

⊆ u

i

x

∈ u

,

to

elemen

t

x

jest



elemen

tem

minimalnym

w

zbiorze

v

,

o

ile

x

∈ v

i

¬

∃

y∈v

(y <

R

x)

;



elemen

tem

maksymalnym

w

zbiorze

v

,

o

ile

x

∈ v

i

¬

∃

y∈v

(x <

R

y)

;



elemen

tem

najmniejszym

w

zbiorze

v

,

o

ile

x

∈ v

i

∀

y∈v

(x 6

R

y)

;



elemen

tem

najwikszym

w

zbiorze

v

,

o

ile

x

∈ v

i

∀

y∈v

(y 6

R

x)

;



o

gr

ani zeniem

dolnym

zbioru

v

,

o

ile

∀

y∈v

(x 6

R

y)

;



o

gr

ani zeniem

górnym

zbioru

v

,

o

ile

∀

y∈v

(y 6

R

x)

.

☛

Na

jmniejszy

(na

jwikszy)

elemen

t

zbioru

v

ozna zam

y

sym

b

olem

min

6

R

v

(

max

6

R

v

);

sym

b

ol

6

R

b

-

dziem

y

opusz za¢,

je»eli

z

k

on

tekstu

b

dzie

jasno

wynik

aªo,

o

jak

¡

rela j

ho

dzi.

☛

P

orz¡dki

w

zbiora

h

sk

o« zon

y

h

mo»na

przedsta

wia¢

w

p

osta i

tzw.

diagramó

w

Hassego.

Istnieje

niesk

omplik

o

w

an

y

algorytm

ryso

w

ania

t

y

h»e

diagramó

w.

☛

Dysp

on

uj¡

diagramem

Hassego

mo»na

b

ez

trudu

o

d zyta¢,

które

elemen

t

y

s¡

minimalne,

które

mak-

symalne,

mo»na

wyzna zy¢

ograni zenia

k

a»dego

zbioru

itd.

Ÿ

7

.

F

unk

je,

rela je

i

p

orz¡dki

7

G

Linio

w

e

p

orz¡dki

☛

Rela ja

z± io

w

ego

p

orz¡dku

w

zbiorze

u

jest

rela j¡

liniowe

go

p

orz¡dku

w

zbiorze

u

wtedy

i

t

ylk

o

wtedy

,

gdy

jest

sp

ó

jna

w

u

.

☛

Rela ja

linio

w

ego

p

orz¡dku

w

zbiorze

u

jest

rela j¡

dobr

e

go

p

orz¡dku

w

zbiorze

u

wtedy

i

t

ylk

o

wtedy

,

gdy

k

a»dy

niepust

y

p

o

dzbiór

u

p

osiada

elemen

t

na

jmniejszy

.

☛

Rela ja

6

R

jest

rela j¡

gste

go

p

orz¡dku

w

zbiorze

u

wtedy

i

t

ylk

o

wtedy

,

gdy

jest

rela j¡

linio

w

ego

p

orz¡dku

w

u

i

dla

wszystki

h

x, y

∈ u

je»eli

x <

R

y

,

to

istnieje

takie

z

∈ u

,

»e

x <

R

z

i

z <

R

y

.

☛

P

ara

(v, w)

jest

przekr

ojem

zbioru

u

wzgldem

rela ji

6

R

wtedy

i

t

ylk

o

wtedy

,

gdy

v

∪w = u

,

v

∩w = ∅

i

dla

wszystki

h

x

∈ v

,

y

∈ w

mam

y

x <

R

y

.

☛

Rela ja

6

R

jest

rela j¡

i¡gªe

go

p

orz¡dku

w

zbiorze

u

wtedy

i

t

ylk

o

wtedy

,

gdy

jest

rela j¡

gstego

p

orz¡dku

w

u

i

dla

k

a»dego

przekro

ju

(v, w)

alb

o

v

p

osiada

elemen

t

na

jwikszy

,

alb

o

w

p

osiada

elemen

t

na

jmniejszy

.

☛

P

ar

(u, 6

R

)

,

gdzie

6

R

jest

rela j¡

z± io

w

ego

(linio

w

ego,

dobrego

itd.)

p

orz¡dku

w

u

,

nazyw

a¢

b

-

dziem

y

zbiorem

z± iowo

(

liniowo

,

dobrze

itd.)

up

orz¡dkowanym

.

☛

Rela ja

6

jest

rela j¡

linio

w

ego

(dobrego,

gstego,

i¡

gªego)

p

orz¡dku

w

zbiorze

li zb

aªk

o

wit

y

h

(naturaln

y

h,

wymiern

y

h,

rze zywist

y

h).

Ÿ

7

.

F

unk

je,

rela je

i

p

orz¡dki

7

H

Linio

w

e

p

orz¡dki

(2)

☛

Je»eli

(u, 6

R

)

i

(v, 6

S

)

s¡

zbiorami

z± io

w

o

(linio

w

o,

dobrze)

up

orz¡dk

o

w

an

ymi,

to

para:



(u

× v, 6

RS

)

,

gdzie

6

RS

jest

rela j¡

dan¡

wzorem

(x, y) 6

RS

(z, t) ⇔ (x <

R

z) ∨ (x = z ∧ y 6

S

t)

,

jest

zbiorem

z± io

w

o

(linio

w

o,

dobrze)

up

orz¡dk

o

w

an

ym.

Rela ja

6

RS

nazyw

ana

jest

p

orz¡dkiem

leksyko

gr

a znym

;



(u

× v, 6

∗
SR

)

,

gdzie

6

∗
SR

jest

rela j¡

dan¡

wzorem

(x, y) 6

∗
SR

(z, t) ⇔ (y <

S

t) ∨ (y = t ∧ x 6

R

z)

,

jest

zbiorem

z± io

w

o

(linio

w

o,

dobrze)

up

orz¡dk

o

w

an

ym.

Rela ja

6

∗
SR

nazyw

ana

jest

p

orz¡dkiem

antyleksyko

gr

a znym

.

Ÿ

7

.

F

unk

je,

rela je

i

p

orz¡dki

7

I

Izomorzm

y

☛

Izomorzmem

zbioró

w

z± io

w

o

up

orz¡dk

o

w

an

y

h

(u, 6

R

)

,

(v, 6

S

)

nazyw

a¢

b

dziem

y

k

a»d¡

tak

¡

bi-

jek

j

f : u → v

,

»e

x 6

R

y ⇔ f(x) 6

S

f(y)

dla

wszystki

h

x, y

∈ u

.

☛

Zbiory

z± io

w

o

up

orz¡dk

o

w

ane

(u, 6

R

)

,

(v, 6

S

)

s¡

izomor zne

wtedy

i

t

ylk

o

wtedy

,

gdy

istnieje

izomorzm

f : u → v

;

to,

»e

(u, 6

R

)

jest

izomor zne

z

(v, 6

S

)

b

dziem

y

sym

b

oli znie

zapisyw

a¢

(u, 6

R

)

≃ (v, 6

S

)

.

☛

F

unk

ja

o

dwrotna

do

izomorzm

u

jest

izomorzmem;

zªo»enie

izomorzmó

w

jest

izomorzmem,

wi

z

(u, 6

R

)

≃ (v, 6

S

)

,

(v, 6

S

)

≃ (w, 6

T

)

wynik

a

(u, 6

R

)

≃ (w, 6

T

)

.

☛

Zbiór

pred

(u, x, 6

R

)

df

= {y

∈ u : y <

R

x}

to

o

d inek

p

o

z¡tkowy

wyzna zon

y

przez

elemen

t

x

∈ u

;

zbiór

v

⊆ u

jest

o

d inkiem

wtedy

i

t

ylk

o

wtedy

,

gdy

u = v

lub

istnieje

takie

x

∈ u

,

»e

v =

pred

(u, x, 6

R

)

.

☛

Je»eli

x, y

∈ u

i

x <

R

y

,

to

pred

(u, x, 6

R

) =

pred

(

pred

(u, y, 6

R

), x, 6

R

)

;

je»eli

x 6

R

y

,

to

pred

(u, x, 6

R

)

⊆

pred

(u, y, 6

R

)

.

Ÿ

7

.

F

unk

je,

rela je

i

p

orz¡dki

7

J

Izomorzm

y

(2)

Nie

h

(u, 6

R

)

b



dzie

zbior

em

dobrze

up

orz¡dkowanym.

Wów zas:

(1)

nie

istnieje

taki

element

x

∈ u

,

»e

(u, 6

R

)

≃ (

pred

(u, x, 6

R

), 6

R

)

;

(2)

je»eli

x, y

∈ u

,

to

(

pred

(u, x, 6

R

), 6

R

)

≃ (

pred

(u, y, 6

R

), 6

R

) ⇔ x = y

.

Do

w

ó

d.

(1)

Przypu±¢m

y

,

»e

istnieje

takie

x

∈ u

,

»e

(u, 6

R

)

≃ (

pred

(u, x, 6

R

), 6

R

)

.

Nie

h

f : u →

pred

(u, x, 6

R

)

b

dzie

izomorzmem.

Zbiór

v = {f(y) : f(y)

6= y ∧ y ∈ u}

jest

niepust

y

,

b

o

nale»y

do

niego

np.

f(x)

(

x /

∈

pred

(u, x, 6

R

)

implikuje

f(x)

6= x

),

wi

p

osiada

elemen

t

na

jmniejszy

f(z)

.

Mo»liw

e

s¡

t

ylk

o

dwie

sytua je:



z <

R

f(z)

.

P

oniew

a»

f(z)

6= z

,

wi

z

6= f

−1

(z)

.

St¡d

z

∈ v

,

a

p

oniew

a»

f(z) =

min

v

,

wi

f(z) 6

R

z



sprze zno±¢.



f(z) <

R

z

.

Wtedy

f(f(z)) <

R

f(z)

,

sk

¡d

f(f(z))

6= f(z)

.

St¡d

f(f(z))

∈ v

,

a

p

oniew

a»

f(z) =

min

v

,

wi

f(z) 6

R

f(f(z))



sprze zno±¢.

(2)

Gdyb

y

(

pred

(u, x, 6

R

), 6

R

)

≃ (

pred

(u, y, 6

R

), 6

R

)

i

x

6= y

,

to

b

yªob

y

x <

R

y

i

pred

(u, x, 6

R

) =

pred

(

pred

(u, y, 6

R

), x, 6

R

)

lub

y <

R

x

i

pred

(u, y, 6

R

) =

pred

(

pred

(u, x, 6

R

), y, 6

R

)



sprze zno±¢,

b

o

obie

te

sytua je

s¡

na

mo

y

(1)

niemo»liw

e.

2

Ÿ

7

.

F

unk

je,

rela je

i

p

orz¡dki

7

K

Izomorzm

y

(3)

Nie

h

(u, 6

R

)

or

az

(v, 6

S

)

b



d¡

zbior

ami

dobrze

up

orz¡dkowanymi.

Je±li

(u, 6

R

)

≃ (v, 6

S

)

,

to

istnieje

dokªadnie

je

den

izomorzm

f : u → v

.

Do

w

ó

d.

Nie

h

f, g : u → v

b

d¡

izomorzmami.

Gdyb

y

f

6= g

,

to

zbiór

t

y

h

x

∈ u

,

dla

który

h

f(x)

6= g(x)

b

yªb

y

niepust

y

i

p

osiadaªb

y

elemen

t

na

jmniejszy

z

.

Wó

w

zas

f(x) = g(x)

dla

k

a»dego

x <

R

z

,

sk

¡d

f(z) =

min

{y

∈ v : ∀

x<

R

z

f(x) <

S

y} =

min

{y

∈ v : ∀

x<

R

z

g(x) <

S

y} = g(z)



sprze zno±¢.

2

☛

Je»eli

(u, 6

u

)

jest

dobrym

p

orz¡dkiem,

to

jedyn

ym

izomorzmem

f : u → u

jest

funk

ja

iden

t

y zno±-

io

w

a.

Linio

w

e

p

orz¡dki

nie

ma

j¡

ju»

tej

wªasno± i.

Ÿ

7

.

F

unk

je,

rela je

i

p

orz¡dki

7

L

Izomorzm

y

(4)

Nie

h

(u, 6

R

)

i

(v, 6

S

)

b



d¡

zbior

ami

dobrze

up

orz¡dkowanymi.

Wów zas

pr

awdziwy

jest

dokªadnie

je

den

z

p

oni»szy h

warunków:

(1)

(u, 6

R

)

≃ (v, 6

S

)

;

(2)

istnieje

takie

x

∈ u

,

»e

(

pred

(u, x, 6

R

), 6

R

)

≃ (v, 6

S

)

;

(3)

istnieje

takie

y

∈ v

,

»e

(u, 6

R

)

≃ (

pred

(v, y, 6

S

), 6

S

)

.

Do

w

ó

d.

W

ystar zy

wyk

aza¢,

»e

w

k

a»dym

przypadku

za

ho

dzi

o

na

jmniej

jedna

z

p

o

wy»szy

h

mo»li-

w

o± i,

b

o

to,

»e

nie

mo»e

za

ho

dzi¢

wi ej

ni»

jedna

wynik

a

z

t

wierdzenia

z

p

oprzedniej

stron

y

.

Nie

h

f

b

dzie

rela j¡

dan¡

wzorem

f = {(x, y)

∈ u × v : (

pred

(u, x, 6

R

), 6

R

)

≃ (

pred

(v, y, 6

S

), 6

S

)}

.

Zau

w

a»m

y

,

»e

f

jest

funk

j¡,

b

o

je±li

(x, y)

∈ f

,

(x, z)

∈ f

i

y

6= z

,

to

z

deni ji

f

i

prze

ho

dnio± i

≃

otrzym

ujem

y

(

pred

(v, y, 6

S

), 6

S

)

≃ (

pred

(v, z, 6

S

), 6

S

)

,

o

jest

niemo»liw

e.

Co

wi ej,

f : D(f) → D

∗

(f)

jest

izomorzmem,

b

o

jest

bijek

j¡

(to,

»e

jest

suriek

j¡,

jest

o

zywiste,

a

to,

»e

jest

injek

j¡

wynik

a

z

t

wierdzenia

z

p

oprzedniej

stron

y)

oraz

x 6

R

y ⇔

pred

(u, x, 6

R

)

⊆

pred

(u, y, 6

R

) ⇔

pred

(v, f(x), 6

S

) =

f[

pred

(u, x, 6

R

)]

⊆ f[

pred

(u, y, 6

R

)] =

pred

(v, f(y), 6

S

) ⇔ f(x) 6

S

f(y)

.

Zau

w

a»m

y

tak»e,

»e

D(f)

m

usi

b

y¢

o

d inkiem

w

u

,

b

o

je»eli

x

∈ D(f)

,

y

∈ u

i

y <

R

x

,

to

(

pred

(u, y, 6

R

), 6

R

)

≃ (

pred

(v, g(y), 6

S

), 6

S

)

,

Ÿ

7

.

F

unk

je,

rela je

i

p

orz¡dki

7

M

Izomorzm

y

(5)

gdzie

g :

pred

(u, x, 6

R

) →

pred

(v, f(x), 6

S

)

jest

izomorzmem

istniej¡ ym

na

mo

y

deni ji

f

,

sk

¡d

y

∈

D(f)

.

Analogi znie

mo»na

wyk

aza¢,

»e

D

∗

(f)

jest

o

d inkiem

w

v

,

wi

ab

y

zak

o« zy¢

do

w

ó

d,

wystar zy

wyk

aza¢,

»e

D(f) = u

lub

D

∗

(f) = v

.

Gdyb

y

D(f)

6= u

i

D

∗

(f)

6= v

,

to

funk

ja

g : D(f)

∪ {x} → D

∗

(f)

∪ {y}

dana

wzorem

g = f

∪ {(x, y)}

,

gdzie

x =

min

(u \ D(f))

i

y =

min

(v \ D

∗

(f))

,

b

yªab

y

izomorzmem,

sk

¡d

pred

(u, x, 6

R

) =

pred

(D(f)

∪ {x}, x, 6

R

)

≃

pred

(D

∗

(f)

∪ {y}, y, 6

S

) =

pred

(v, y, 6

S

)



sprze zno±¢.

2

Ÿ

7

.

F

unk

je,

rela je

i

p

orz¡dki

7

N