7

Ÿ

.

F

unk

je,

rela je

i

p

orz¡dki

7

Rela je

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

A

7

F

unk

je

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

C

7

Cz± io

w

e

p

orz¡dki

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

F

7

Linio

w

e

p

orz¡dki

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

H

7

Izomorzm

y

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

J

7

‚

wi zenia

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

O

7

Zadania

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

P

Rela je

☛ Zbiór, którego elementy s¡ parami uporz¡dkowanymi, nazywa¢ bdziemy rela j¡. Rela jami s¡ m.in.

u × v

zbiór

pust

y

oraz

k

a»dy

zbiór

p

osta i

.

☛

R S T

W

ystpuj¡ e

dalej

rela je

b

dziem

y

ozna zali

literami

,

i

;

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.

☛

D(R) df

= {x : ∃y(x, y) ∈ R} D∗(R) df

= {y : ∃x(x, y) ∈ R}

Zbiory

i

to

o

dp

o

wiednio

dzie

dzina

i

prze

iwdzie-

R

R ⊆ D(R) × D∗(R)

dzina

rela ji

;

mo»na

wyk

aza¢,

»e

.

☛ To, »e dziedzina i prze iwdziedzina s¡ poprawnie okre±lonymi zbiorami, wynika z aksjomatu wy inania

S S

S S

∃y(x, y) ∈ R ∃x(x, y) ∈ R

x ∈

R y ∈

R

i

z

tego,

»e

je±li

(

),

to

(

).

☛

(x, y) ∈ R

xRy

xRy

x

R

y

Zamiast

pisa¢

,

b

dziem

y

zasami

pisa¢

;

napis

zyta

si:

jest

w

rela ji

z

.

Przyjm

ujem

y

p

onadto,

»e:

∈u

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

jest

rela j¡

dan¡

wzorem

;

⊆u

x ⊆u y ⇔ x ∈ u ∧ y ∈ u ∧ x ⊆ y

jest

rela j¡

dan¡

wzorem

;

=u

x =u y ⇔ x ∈ u ∧ x = y

jest

rela j¡

dan¡

wzorem

.

7

7

Ÿ

.

F

unk

je,

rela je

i

p

orz¡dki

A

Rela je

(2)

☛

R

R−1 df

= {(y, x) : (x, y) ∈ R}

Rela j¡

o

dwr

otn¡

do

rela ji

nazyw

a¢

b

dziem

y

rela j

;

zªo»eniem

rela ji

R S

RS

xRSy ⇔ ∃z(xRz ∧ zSy)

,

jest

rela ja

dana

wzorem

.

☛

R

Rela ja

jest:

u

∀x∈u(xRx)

zwr

otna

w

zbiorze

,

o

ile

;

u

∀x∈u¬(xRx)

prze

iwzwr

otna

w

zbiorze

,

o

ile

;

u

∀x∈u∀y∈u(xRy ⇒ yRx)

symetry zna

w

zbiorze

,

o

ile

;

u

∀x∈u∀y∈u((xRy ∧ yRx) ⇒ y = x)

antysymetry zna

w

zbiorze

,

o

ile

;

u

∀x∈u∀y∈u∀z∈u((xRy ∧ yRz) ⇒ xRz)

prze

ho

dnia

w

zbiorze

,

o

ile

;

u

∀x∈u∀y∈u(xRy ∨ yRx)

sp

ójna

w

zbiorze

,

o

ile

.

☛ Rela ja, która jest zwrotna, symetry zna i prze hodnia w sumie swojej dziedziny i prze iwdziedziny,

=u

to

rela ja

r

ównowa»no± i

.

Przykªadem

rela ji

ró

wno

w

a»no± i

jest

.

☛ ⊆u

u ∈u

jest

rela j¡

zwrotn¡,

an

t

ysymetry zn¡

i

prze

ho

dni¡

w

;

jest

zwrotna

i

an

t

ysymetry zna.

7

7

Ÿ

.

F

unk

je,

rela je

i

p

orz¡dki

B

F

unk

je

☛

R

x

y

x

Rela ja

jest

funk j¡

wtedy

i

t

ylk

o

wtedy

,

gdy

dla

k

a»dego

istnieje

o

na

jwy»ej

jedno

takie

,

»e

R

y

jest

w

rela ji

z

.

=u

jest

funk

j¡

jest

to

tzw.

funk

ja

identy zno± iowa

;

u × {v}

jest

funk

j¡

jest

to

tzw.

funk

ja

staªa

.

☛

e f g

h

f

y

W

ystpuj¡ e

dalej

funk

je

b

dziem

y

ozna zali

literami

,

,

i

;

je»eli

jest

funk

j¡,

to

jedyne

xfy

f(x)

fx

takie,

»e

b

dziem

y

ozna zali

sym

b

olem

lub

.

☛

f : u → v

u ∋ x 7→ f(x) ∈ v

f

Bdziem

y

pisa¢

lub

,

ab

y

zazna zy¢,

»e

jest

funk

j¡,

której

dziedzin¡

jest

u

v

i

której

prze iwdziedzina

za

wiera

si

w

.

☛

f : u → v

f

u

v

f

u

v

Napis

zytam

y:

dziaªa

z

do

lub

przeksztaª

a

w

.

Zbiór

wszystki

h

funk

ji

dziaªa-

u

v

vu vu

vu = {f ∈ P(u × v) : f : u → v}

j¡ y

h

z

do

b

dziem

y

ozna za¢

sym

b

olem

;

jest

zbiorem,

gdy»

.

7

7

Ÿ

.

F

unk

je,

rela je

i

p

orz¡dki

C

F

unk

je

(2)

☛

f

u ⊆ D(f)

f|

df

u = {(x, y) ∈ f :

x ∈ u}

Ob

i

iem

funk

ji

do

zbioru

nazyw

a¢

b

dziem

y

funk

j

;

zbiór

f[u] df

= D∗(f|u)

u

f

to

obr

az

zbioru

wzgldem

funk

ji

.

Obraz

zbioru

ozna za

si

niekiedy

ina zej

zamiast

f[u]

{fx}x

{f(x) : x ∈ u}

∈u

pisa¢

pisze

si

lub

.

☛ Obraz zbioru wzgldem funk ji ma wiele wa»ny h wªasno± i; w sz zególno± i, prawdziwe s¡ nastpuj¡ e

implik

a je:

S

S

x ⊆ D(f)

x ∈ u

f[

u] =

{f[x] : x ∈ u}

je»eli

dla

k

a»dego

,

to

;

T

T

x ⊆ D(f)

x ∈ u u 6= ∅

f[

u] ⊆

{f[x] : x ∈ u}

je»eli

dla

k

a»dego

i

,

to

;

u ⊆ D(f) v ⊆ D(f)

f[u] \ f[v] ⊆ f[u \ v]

je»eli

i

,

to

;

u ⊆ v ⊆ D(f)

f[u] ⊆ f[v]

je»eli

,

to

.

S

S

T

T

☛

f

u ⊆ D(f)

f df

df

x =

f[u]

fx =

f[u]

Przyjm

ujem

y

,

»e

je±li

jest

funk

j¡,

a

zbiorem,

to

x∈u

i

x∈u

.

7

7

Ÿ

.

F

unk

je,

rela je

i

p

orz¡dki

D

F

unk

je

(3)

☛

f

f−1

F

unk

ja

jest

r

ó»nowarto± iowa

(jest

injek j¡

)

wtedy

i

t

ylk

o

wtedy

,

gdy

jest

funk

j¡;

funk

ja

f : u → v

D∗(f) = v

jest

na

(jest

suriek j¡

)

wtedy

i

t

ylk

o

wtedy

,

gdy

.

☛

f : u → v

x 6= y ⇒

Nietrudno

jest

wyk

aza¢,

»e

funk

ja

jest

injek

j¡

(suriek

j¡)

wtedy

i

t

ylk

o

wtedy

,

gdy

f(x) 6= f(y)

x, y ∈ u f[u] = v

dla

k

a»dy

h

(

).

☛

f

F

unk

ja,

która

jest

suriek

j¡

i

injek

j¡,

to

bijek ja

(funk

ja

wzajemnie

je

dnozna zna

).

Je»eli

jest

bijek

j¡,

to:

T

T

x ⊆ D(f)

x ∈ u u 6= ∅

f[

u] =

{f[x] : x ∈ u}

je»eli

dla

k

a»dego

i

,

to

;

u ⊆ D(f) v ⊆ D(f)

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

je»eli

i

,

to

.

☛ Ka»da funk ja staªa jest suriek j¡; ka»da funk ja identy zno± iowa jest bijek j¡. Przykªadem injek ji

S

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

u))

mo»e

b

y¢

funk

ja

dana

wzorem

.

7

7

Ÿ

.

F

unk

je,

rela je

i

p

orz¡dki

E

Cz± io

w

e

p

orz¡dki

☛

6R

u

Rela ja

jest

rela j¡

z± iowe

go

p

orz¡dku

w

zbiorze

wtedy

i

t

ylk

o

wtedy

,

gdy

jest

zwrotna,

u

an

t

ysymetry zna

i

prze

ho

dnia

w

zbiorze

.

☛

6R

<R

x <R y ⇔

Przyjm

ujem

y

,

»e

je±li

jest

rela j¡

z± io

w

ego

p

orz¡dku,

to

jest

rela j¡

dan¡

wzorem

x 6R y ∧ x 6= y <R

;

jest

rela j¡

prze iwzwrotn¡,

an

t

ysymetry zn¡

i

prze

ho

dni¡.

☛

>R

x >R y ⇔ y 6R x

>R

Przyjm

ujem

y

,

»e

jest

rela j¡

dan¡

wzorem

;

rela ja

jest,

o

ªat

w

o

spra

wdzi¢,

6R

rela j¡

o

dwrotn¡

do

.

☛

v ⊆ u

x 6R y

y 6R x

x, y ∈ v

Zbiór

jest

ªa« u hem

wtedy

i

t

ylk

o

wtedy

,

gdy

lub

dla

k

a»dy

h

;

zbiór

v ⊆ u

6R

v

jest

ªa« u

hem

wtedy

i

t

ylk

o

wtedy

,

gdy

jest

rela j¡

sp

ó

jn¡

w

.

☛ ⊆u =u

u

u

∈u

i

s¡

z± io

wymi

p

orz¡dk

ami

w

;

dla

niektóry

h

zbioró

w

tak»e

jest

z± io

wym

p

orz¡dkiem

u

w

.

7

7

Ÿ

.

F

unk

je,

rela je

i

p

orz¡dki

F

Cz± io

w

e

p

orz¡dki

(2)

☛

6R

u v ⊆ u x ∈ u

x

Je»eli

jest

z± io

wym

p

orz¡dkiem

w

,

i

,

to

elemen

t

jest

v

x ∈ v ¬∃y∈v(y <R x)

elemen

tem

minimalnym

w

zbiorze

,

o

ile

i

;

v

x ∈ v ¬∃y∈v(x <R y)

elemen

tem

maksymalnym

w

zbiorze

,

o

ile

i

;

v

x ∈ v ∀y∈v(x 6R y)

elemen

tem

najmniejszym

w

zbiorze

,

o

ile

i

;

v

x ∈ v ∀y∈v(y 6R x)

elemen

tem

najwikszym

w

zbiorze

,

o

ile

i

;

v

∀y∈v(x 6R y)

o

gr

ani zeniem

dolnym

zbioru

,

o

ile

;

v

∀y∈v(y 6R x)

o

gr

ani zeniem

górnym

zbioru

,

o

ile

.

☛

v

6

v

6

v

6R

Na

jmniejszy

(na

jwikszy)

elemen

t

zbioru

ozna zam

y

sym

b

olem

min

R

(max

R

);

sym

b

ol

b

-

dziem

y

opusz za¢,

je»eli

z

k

on

tekstu

b

dzie

jasno

wynik

aªo,

o

jak

¡

rela j

ho

dzi.

☛ Porz¡dki w zbiora h sko« zony h mo»na przedstawia¢ w posta i tzw. diagramów Hassego. Istnieje niesk

omplik

o

w

an

y

algorytm

ryso

w

ania

t

y

h»e

diagramó

w.

☛ Dysponuj¡ diagramem Hassego mo»na bez trudu od zyta¢, które elementy s¡ minimalne, które mak-symalne,

mo»na

wyzna zy¢

ograni zenia

k

a»dego

zbioru

itd.

7

7

Ÿ

.

F

unk

je,

rela je

i

p

orz¡dki

G

Linio

w

e

p

orz¡dki

☛

u

u

Rela ja

z± io

w

ego

p

orz¡dku

w

zbiorze

jest

rela j¡

liniowe

go

p

orz¡dku

w

zbiorze

wtedy

i

t

ylk

o

u

wtedy

,

gdy

jest

sp

ó

jna

w

.

☛

u

u

Rela ja

linio

w

ego

p

orz¡dku

w

zbiorze

jest

rela j¡

dobr

e

go

p

orz¡dku

w

zbiorze

wtedy

i

t

ylk

o

wtedy

,

u

gdy

k

a»dy

niepust

y

p

o

dzbiór

p

osiada

elemen

t

na

jmniejszy

.

☛

6R

u

Rela ja

jest

rela j¡

gste

go

p

orz¡dku

w

zbiorze

wtedy

i

t

ylk

o

wtedy

,

gdy

jest

rela j¡

linio

w

ego

u

x, y ∈ u

x <R y

z ∈ u

x <R z z <R y

p

orz¡dku

w

i

dla

wszystki

h

je»eli

,

to

istnieje

takie

,

»e

i

.

☛

(v, w)

u

6R

v∪w = u v∩w = ∅

P

ara

jest

przekr

ojem

zbioru

wzgldem

rela ji

wtedy

i

t

ylk

o

wtedy

,

gdy

,

x ∈ v y ∈ w

x <R y

i

dla

wszystki

h

,

mam

y

.

☛

6R

u

Rela ja

jest

rela j¡

i¡gªe

go

p

orz¡dku

w

zbiorze

wtedy

i

t

ylk

o

wtedy

,

gdy

jest

rela j¡

gstego

u

(v, w)

v

w

p

orz¡dku

w

i

dla

k

a»dego

przekro

ju

alb

o

p

osiada

elemen

t

na

jwikszy

,

alb

o

p

osiada

elemen

t

na

jmniejszy

.

☛

(u, 6R)

6R

u

P

ar

,

gdzie

jest

rela j¡

z± io

w

ego

(linio

w

ego,

dobrego

itd.)

p

orz¡dku

w

,

nazyw

a¢

b

-

dziem

y

zbiorem

z± iowo

(liniowo

,

dobrze

itd.)

up

orz¡dkowanym

.

☛

6

Rela ja

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

7

Ÿ

.

F

unk

je,

rela je

i

p

orz¡dki

H

Linio

w

e

p

orz¡dki

(2)

☛

(u, 6R) (v, 6S)

Je»eli

i

s¡

zbiorami

z± io

w

o

(linio

w

o,

dobrze)

up

orz¡dk

o

w

an

ymi,

to

para:

(u × v, 6RS)

6RS

,

gdzie

jest

rela j¡

dan¡

wzorem

(x, y) 6RS (z, t) ⇔ (x <R z) ∨ (x = z ∧ y 6S t), 6RS

jest

zbiorem

z± io

w

o

(linio

w

o,

dobrze)

up

orz¡dk

o

w

an

ym.

Rela ja

nazyw

ana

jest

p

orz¡dkiem

leksyko

gr

a znym

;

(u × v, 6∗ )

6∗

SR , gdzie

SR jest rela j¡ dan¡ wzorem

(x, y) 6∗ (z, t) ⇔ (y <

SR

S t) ∨ (y = t ∧ x 6R z),

6∗

jest

zbiorem

z± io

w

o

(linio

w

o,

dobrze)

up

orz¡dk

o

w

an

ym.

Rela ja

SR nazywana jest porz¡dkiem antyleksyko

gr

a znym

.

7

7

Ÿ

.

F

unk

je,

rela je

i

p

orz¡dki

I

Izomorzm

y

☛

(u, 6R) (v, 6S)

Izomorzmem

zbioró

w

z± io

w

o

up

orz¡dk

o

w

an

y

h

,

nazyw

a¢

b

dziem

y

k

a»d¡

tak

¡

bi-

f : u → v

x 6R y ⇔ f(x) 6S f(y)

x, y ∈ u

jek

j

,

»e

dla

wszystki

h

.

☛

(u, 6R) (v, 6S)

Zbiory

z± io

w

o

up

orz¡dk

o

w

ane

,

s¡

izomor zne

wtedy

i

t

ylk

o

wtedy

,

gdy

istnieje

f : u → v

(u, 6R)

(v, 6S)

(u, 6R

izomorzm

;

to,

»e

jest

izomor zne

z

b

dziem

y

sym

b

oli znie

zapisyw

a¢

) ≃ (v, 6S).

☛ Funk ja odwrotna do izomorzmu jest izomorzmem; zªo»enie izomorzmów jest izomorzmem, wi

(u, 6R) ≃ (v, 6S) (v, 6S) ≃ (w, 6T) (u, 6R) ≃ (w, 6T)

z

,

wynik

a

.

☛

(u, x, 6R) df

= {y ∈ u : y <R x}

x ∈ u

Zbiór

pred

to

o

d inek

p

o

z¡tkowy

wyzna zon

y

przez

elemen

t

;

zbiór

v ⊆ u

u = v

x ∈ u

v =

(u, x, 6R)

jest

o

d inkiem

wtedy

i

t

ylk

o

wtedy

,

gdy

lub

istnieje

takie

,

»e

pred

.

☛

x, y ∈ u x <R y

(u, x, 6R) =

(

(u, y, 6R), x, 6R)

x 6R y

(u, x, 6R

Je»eli

i

,

to

pred

pred

pred

;

je»eli

,

to

pred

) ⊆

(u, y, 6R)

pred

.

7

7

Ÿ

.

F

unk

je,

rela je

i

p

orz¡dki

J

Izomorzm

y

(2)

(u, 6R)

Nie

h

b

dzie

zbior

em

dobrze

up

orz¡dkowanym.

Wów zas:

(1)

x ∈ u

(u, 6R) ≃ (

(u, x, 6R), 6R)

nie

istnieje

taki

element

,

»e

pred

;

(2)

x, y ∈ u

(

(u, x, 6R), 6R) ≃ (

(u, y, 6R), 6R) ⇔ x = y

je»eli

,

to

pred

pred

.

(1)

x ∈ u

(u, 6R) ≃ (

(u, x, 6R), 6R)

f : u →

Do

w

ó

d.

Przypu±¢m

y

,

»e

istnieje

takie

,

»e

pred

.

Nie

h

(u, x, 6R)

v = {f(y) : f(y) 6= y ∧ y ∈ u}

pred

b

dzie

izomorzmem.

Zbiór

jest

niepust

y

,

b

o

nale»y

do

niego

f(x) x /

∈

(u, x, 6R)

f(x) 6= x

f(z)

np.

(

pred

implikuje

),

wi

p

osiada

elemen

t

na

jmniejszy

.

Mo»liw

e

s¡

t

ylk

o

dwie

sytua je:

z <R f(z)

f(z) 6= z

z 6= f−1(z)

z ∈ v

f(z) =

v

f(z) 6R z

.

P

oniew

a»

,

wi

.

St¡d

,

a

p

oniew

a»

min

,

wi

sprze zno±¢.

f(z) <R z

f(f(z)) <R f(z)

f(f(z)) 6= f(z)

f(f(z)) ∈ v

f(z) =

v

.

Wtedy

,

sk

¡d

.

St¡d

,

a

p

oniew

a»

min

,

wi

f(z) 6R f(f(z)) sprze zno±¢.

(2)

(

(u, x, 6R), 6R) ≃ (

(u, y, 6R), 6R)

x 6= y

x <R y

(u, x, 6R) =

Gdyb

y

pred

pred

i

,

to

b

yªob

y

i

pred

(

(u, y, 6R), x, 6R)

y <R x

(u, y, 6R) =

(

(u, x, 6R), y, 6R)

pred

pred

lub

i

pred

pred

pred

sprze zno±¢,

b

o

(1)

2

obie

te

sytua je

s¡

na

mo

y

niemo»liw

e.

7

7

Ÿ

.

F

unk

je,

rela je

i

p

orz¡dki

K

Izomorzm

y

(3)

(u, 6R)

(v, 6S)

(u, 6R) ≃ (v, 6S)

Nie

h

or

az

b

d¡

zbior

ami

dobrze

up

orz¡dkowanymi.

Je±li

,

to

istnieje

f : u → v

dokªadnie

je

den

izomorzm

.

f, g : u → v

f 6= g

x ∈ u

Do

w

ó

d.

Nie

h

b

d¡

izomorzmami.

Gdyb

y

,

to

zbiór

t

y

h

,

dla

który

h

f(x) 6= g(x)

z

f(x) = g(x)

x <R z

b

yªb

y

niepust

y

i

p

osiadaªb

y

elemen

t

na

jmniejszy

.

Wó

w

zas

dla

k

a»dego

,

f(z) =

{y ∈ v : ∀x<

{y ∈ v : ∀x<

2

sk

¡d

min

R zf(x) <S y} = min

R zg(x) <S y} = g(z) sprze zno±¢.

☛

(u, 6u)

f : u → u

Je»eli

jest

dobrym

p

orz¡dkiem,

to

jedyn

ym

izomorzmem

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

7

Ÿ

.

F

unk

je,

rela je

i

p

orz¡dki

L

Izomorzm

y

(4)

(u, 6R)

(v, 6S)

Nie

h

i

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, 6R) ≃ (v, 6S);

(2)

x ∈ u

(

(u, x, 6R), 6R) ≃ (v, 6S)

istnieje

takie

,

»e

pred

;

(3)

y ∈ v

(u, 6R) ≃ (

(v, y, 6S), 6S)

istnieje

takie

,

»e

pred

.

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-

f

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

b

dzie

rela j¡

dan¡

wzorem

f = {(x, y) ∈ u × v : (

(u, x, 6R), 6R) ≃ (

(v, y, 6S), 6S)}.

pred

pred

f

(x, y) ∈ f (x, z) ∈ f

y 6= z

f

≃

Zau

w

a»m

y

,

»e

jest

funk

j¡,

b

o

je±li

,

i

,

to

z

deni ji

i

prze

ho

dnio± i

(

(v, y, 6S), 6S) ≃ (

(v, z, 6S), 6S)

f : D(f) → D∗(f)

otrzym

ujem

y

pred

pred

,

o

jest

niemo»liw

e.

Co

wi ej,

jest

izomorzmem,

b

o

jest

bijek

j¡

(to,

»e

jest

suriek

j¡,

jest

o

zywiste,

a

to,

»e

jest

injek

j¡

wynik

a

z

x 6R y ⇔

(u, x, 6R) ⊆

(u, y, 6R) ⇔

(v, f(x), 6S) =

t

wierdzenia

z

p

oprzedniej

stron

y)

oraz

pred

pred

pred

f[

(u, x, 6R)] ⊆ f[

(u, y, 6R)] =

(v, f(y), 6S) ⇔ f(x) 6S f(y) D(f)

pred

pred

pred

.

Zau

w

a»m

y

tak»e,

»e

m

usi

u

x ∈ D(f) y ∈ u y <R x

(

(u, y, 6R), 6R) ≃ (

(v, g(y), 6S), 6S)

b

y¢

o

d inkiem

w

,

b

o

je»eli

,

i

,

to

pred

pred

,

7

7

Ÿ

.

F

unk

je,

rela je

i

p

orz¡dki

M

Izomorzm

y

(5)

g :

(u, x, 6R) →

(v, f(x), 6S)

f

y ∈

gdzie

pred

pred

jest

izomorzmem

istniej¡ ym

na

mo

y

deni ji

,

sk

¡d

D(f)

D∗(f)

v

.

Analogi znie

mo»na

wyk

aza¢,

»e

jest

o

d inkiem

w

,

wi

ab

y

zak

o« zy¢

do

w

ó

d,

wystar zy

D(f) = u

D∗(f) = v

D(f) 6= u D∗(f) 6= v

g : D(f) ∪ {x} → D∗(f) ∪ {y}

wyk

aza¢,

»e

lub

.

Gdyb

y

i

,

to

funk

ja

g = f ∪ {(x, y)}

x =

(u \ D(f)) y =

(v \ D∗(f))

dana

wzorem

,

gdzie

min

i

min

,

b

yªab

y

izomorzmem,

sk

¡d

(u, x, 6R) =

(D(f) ∪ {x}, x, 6R) ≃

(D∗(f) ∪ {y}, y, 6S) =

(v, y, 6S)

2

pred

pred

pred

pred

sprze zno±¢.

7

7

Ÿ

.

F

unk

je,

rela je

i

p

orz¡dki

N