Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

Li zb

y

p

orz¡dk

o

w

e

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

8

A

P

oró

wn

yw

anie

li zb

p

orz¡dk

o

wy

h

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

8

C

Li zb

y

naturalne

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

8

F

Induk

ja

p

ozask

o« zona

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

8

G

ε

-induk

ja

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

8

J

T

yp

y

p

orz¡dk

o

w

e

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

8

M

Do

da

w

anie

i

o

dejmo

w

anie

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

8

O

Mno»enie

i

dzielenie

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

8

P

‚

wi zenia

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

8

R

Zadania

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

8

S

Li zb

y

p

orz¡dk

o

w

e

☛

Zbiór

u

jest

prze

ho

dni

wtedy

i

t

ylk

o

wtedy

,

gdy

dla

k

a»dego

x

∈ u

mam

y

x

⊆ u

.

☛

Zbiór

pust

y

jest

zbiorem

prze

ho

dnim;

je»eli

u

jest

zbiorem

prze

ho

dnim,

to

S(u)

,

S u

,

T u

(o

ile

u

6= ∅

)

i

P(u)

s¡

zbiorami

prze

ho

dnimi.

☛

Zbiór

u

jest

zbiorem

prze

ho

dnim

wtedy

i

t

ylk

o

wtedy

,

gdy

S u ⊆ u

(

u

⊆ P(u)

);

je»eli

u

6= ∅

jest

zbiorem

prze

ho

dnim,

to

∅ ∈ u

na

mo

y

aksjomatu

regularno± i.

☛

Przyjm

ujem

y

,

»e

pred

(u, x)

df

= u

∩ x

.

Je»eli

∈

u

jest

rela j¡

z± io

w

ego

p

orz¡dku

w

u

,

to

pred

(u, x) =

pred

(u, x,

∈

u

)

;

je»eli

u

jest

zbiorem

prze

ho

dnim

i

x

∈ u

,

to

pred

(u, x) = x

.

☛

Je»eli

u

jest

zbiorem

prze

ho

dnim,

∈

u

jest

rela j¡

z± io

w

ego

p

orz¡dku

w

u

i

x

∈ u

,

to

x

jest

zbiorem

prze

ho

dnim,

b

o

je±li

y

∈ x

,

to

y

∈ u

oraz

y =

pred

(u, y)

⊆

pred

(u, x) = x

.

☛

Zbiór

prze

ho

dni

u

jest

li zb

¡

p

orz¡dkow¡

wtedy

i

t

ylk

o

wtedy

,

gdy

para

(u,

∈

u

)

jest

zbiorem

dobrze

up

orz¡dk

o

w

an

ym.

Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

8

A

Li zb

y

p

orz¡dk

o

w

e

(2)

☛

Istniej¡

zbiory

prze

ho

dnie

nie

b

d¡ e

li zbami

p

orz¡dk

o

wymi;

takim

zbiorem

jest

np.

{

∅, {∅}, {{∅}}}

.

Li zb

y

p

orz¡dk

o

w

e

b

d¡

dalej

ozna zane

sym

b

olami

α

,

β

,

γ

i

δ

.

☛

Zbiór

pust

y

jest

li zb¡

p

orz¡dk

o

w

¡;

je»eli

α

jest

li zb¡

p

orz¡dk

o

w

¡,

to

S(α)

,

T α

(o

ile

α

6= ∅

)

i

S α

s¡

li zbami

p

orz¡dk

o

wymi.

☛

Je»eli

α

,

β

i

γ

s¡

li zbami

p

orz¡dk

o

wymi,

α

∈ β

oraz

β

∈ γ

,

to

α

∈ γ

;

je»eli

α

jest

li zb¡

p

orz¡dk

o

w

¡

i

x

∈ α

,

to

x

jest

li zb¡

p

orz¡dk

o

w

¡.

☛

Je»eli

u

jest

zbiorem,

którego

elemen

t

y

s¡

li zbami

p

orz¡dk

o

wymi,

to

u

jest

li zb¡

p

orz¡dk

o

w

¡

wtedy

i

t

ylk

o

wtedy

,

gdy

jest

zbiorem

prze

ho

dnim.

☛

Li zba

p

orz¡dk

o

w

a

α

jest

gr

ani zn¡

li zb¡

p

orz¡dk

o

w

¡

wtedy

i

t

ylk

o

wtedy

,

gdy

α

6= ∅

i

nie

istnieje

takie

v

,

»e

α = S(v)

.

☛

Je»eli

α

jest

li zb¡

p

orz¡dk

o

w

¡,

to

k

a»d¡

funk

j,

której

dziedzin¡

jest

α

,

b

dziem

y

nazyw

a¢

i¡giem

p

ozasko« zonym

typu

α

.

Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

8

B

P

oró

wn

yw

anie

li zb

p

orz¡dk

o

wy

h

☛

P

o

wiem

y

,

»e

li zba

p

orz¡dk

o

w

a

α

jest

mniejsza

(

mniejsza

lub

r

ówna

)

o

d

li zb

y

p

orz¡dk

o

w

ej

β

wtedy

i

t

ylk

o

wtedy

,

gdy

α ( β

(

α

⊆ β

).

☛

Bdziem

y

pisa¢

α < β

,

ab

y

zazna zy¢,

»e

li zba

p

orz¡dk

o

w

a

α

jest

mniejsza

o

d

li zb

y

p

orz¡dk

o

w

ej

β

;

mo»na

wyk

aza¢,

»e

α < β

wtedy

i

t

ylk

o

wtedy

,

gdy

α

∈ β

.

☛

Bdziem

y

pisa¢

α

≤ β

,

ab

y

zazna zy¢,

»e

li zba

p

orz¡dk

o

w

a

α

jest

mniejsza

lub

ró

wna

o

d

li zb

y

p

orz¡dk

o

w

ej

β

;

sym

b

ol

≤

ma

nastpuj¡ e

wªasno± i:



α

≤ α

dla

k

a»dej

li zb

y

p

orz¡dk

o

w

ej

α

;



je»eli

α

≤ β

i

β

≤ γ

,

to

α

≤ γ

;

je»eli

α

≤ β

i

β

≤ α

,

to

α = β

;



α

≤ β

lub

β

≤ α

dla

wszystki

h

li zb

p

orz¡dk

o

wy

h

α

,

β

;



α

≤ β ⇔ α < S(β)

i

α < β ⇔ S(α) ≤ β

.

☛

Bdziem

y

pisa¢

(f

β

)

β<α

,

ab

y

zazna zy¢,

»e

f

jest

i¡

giem

p

ozask

o« zon

ym

t

ypu

α

.

Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

8

C

P

oró

wn

yw

anie

li zb

p

orz¡dk

o

wy

h

(2)

Je»eli

α

or

az

β

s¡

li zb

ami

p

orz¡dkowymi,

to:

(1)

(α,

∈

α

)

≃ (β, ∈

β

)

tylko

wte

dy,

gdy

α = β

;

(2)

α = β

,

α

∈ β

lub

β

∈ α

;

(3)

α

⊆ β

lub

β

⊆ α

;

(4)

α ( β ⇔ α ∈ β

.

Do

w

ó

d.

(1)

Nie

h

f : α → β

b

dzie

izomorzmem.

Gdyb

y

α

6= β

,

to

zbiór

t

y

h

x

∈ α

,

»e

f(x)

6= x

b

yªb

y

niepust

y

i

p

osiadaªb

y

elemen

t

na

jmniejszy

z

.

P

oniew

a»

z

∈ α

i

f(z)

∈ β

,

wi

z =

pred

(α, z)

i

f(z) =

pred

(β, f(z))

,

sk

¡d

f[

pred

(α, z)] = f[z] = {f(x) : x

∈ z} = {x : x ∈ z} = z

.

Co

wi ej,

f

jest

izomorzmem,

wi

f[

pred

(α, z)] =

pred

(β, f(z)) = f(z)

,

sk

¡d

f(z) = z



sprze zno±¢.

(2)

Na

mo

y

jednego

z

udo

w

o

dnion

y

h

w

ze±niej

t

wierdze«

(patrz

wykªad

p

o±wi on

y

p

orz¡dk

om,

punkt

p

o±wi on

y

izomorzmom)

za

ho

dzi

jedna

z

nastpuj¡ y

h

sytua ji:



(α,

∈

α

)

≃ (β, ∈

β

)

.

Wó

w

zas

α = β

na

mo

y

(1)

.



Istnieje

takie

x

∈ α

,

»e

(

pred

(α, x),

∈

α

)

≃ (β, ∈

β

)

.

Wó

w

zas

β =

pred

(α, x)

na

mo

y

(1)

,

o

w

p

oª¡ zeniu

z

ró

wno± i¡

x =

pred

(α, x)

da

je

β = x

∈ α

.



Istnieje

takie

y

∈ β

,

»e

(α,

∈

α

)

≃ (

pred

(β, y),

∈

β

)

.

Wó

w

zas

α =

pred

(β, y)

na

mo

y

(1)

,

o

w

p

oª¡ zeniu

z

ró

wno± i¡

y =

pred

(β, y)

da

je

α = y

∈ β

.

(3)

,

(4)

W

ynik

a

j¡

nat

y

hmiast

z

(2)

oraz

z

tego,

»e

α

i

β

s¡

zbiorami

prze

ho

dnimi.

2

Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

8

D

P

oró

wn

yw

anie

li zb

p

orz¡dk

o

wy

h

(3)

Je»eli

u

jest

niepustym

zbior

em,

któr

e

go

elementy

s¡

li zb

ami

p

orz¡dkowymi,

to

(u,

∈

u

)

jest

zbior

em

dobrze

up

orz¡dkowanym.

Do

w

ó

d.

T

o,

»e

(u,

∈

u

)

jest

zbiorem

z± io

w

o

up

orz¡dk

o

w

an

ym

wynik

a

z

punktu

(4)

p

oprzedniego

t

wier-

dzenia

oraz

z

tego,

»e

(u,

⊆

u

)

jest

zbiorem

z± io

w

o

up

orz¡dk

o

w

an

ym.

T

o,

»e

u

jest

ªa« u

hem,

wynik

a

z

punktu

(2)

tego

samego

t

wierdzenia.

Ab

y

zak

o« zy¢

do

w

ó

d,

wystar zy

wyk

aza¢,

»e

k

a»dy

niepust

y

zbiór

v

⊆ u

p

osiada

elemen

t

minimaln

y

,

b

o

dla

rela ji

linio

w

ego

p

orz¡dku

elemen

t

y

minimalne

s¡

to»same

z

na

jmniejszymi.

W

t

ym

elu

zau

w

a»m

y

,

»e

na

mo

y

aksjomatu

regularno± i

istnieje

x

∈ v

takie,

»e

x

∩ v = ∅

.

Wó

w

zas

dla

k

a»dego

y

∈ v

mam

y

y /

∈ x

,

o

k

o« zy

do

w

ó

d,

b

o

to

ozna za,

»e

x

jest

elemen

tem

minimaln

ym

w

zbiorze

v

.

2

Nie

istnieje

zbiór

wszystki h

li zb

p

orz¡dkowy h.

Do

w

ó

d.

Przypu±¢m

y

,

»e

u

jest

zbiorem

wszystki

h

li zb

p

orz¡dk

o

wy

h.

Je»eli

x

∈ u

,

to

x

jest

li zb¡

p

orz¡dk

o

w

¡,

sk

¡d

x

⊆ u

,

b

o

elemen

t

y

li zb

y

p

orz¡dk

o

w

ej

s¡

li zbami

p

orz¡dk

o

wymi.

Zatem

u

jest

zbiorem

prze

ho

dnim,

a

wi

i

li zb¡

p

orz¡dk

o

w

¡



sprze zno±¢,

b

o

z

tego

wynik

a,

»e

u

∈ u

.

2

Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

8

E

Li zb

y

naturalne

☛

Li zba

p

orz¡dk

o

w

a

α

jest

li zb

¡

natur

aln¡

wtedy

i

t

ylk

o

wtedy

,

gdy

dla

k

a»dej

niepustej

li zb

y

p

orz¡d-

k

o

w

ej

β

≤ α

istnieje

takie

γ

,

»e

β = S(γ)

.

☛

Zbiór

pust

y

jest

li zb¡

naturaln¡;

wystpuj¡ e

dalej

li zb

y

naturalne

b

dziem

y

ozna zali

literami

m

,

n

,

k

i

l

.

Je»eli

n

jest

li zb¡

naturaln¡

i

m < n

,

to

m

jest

li zb¡

naturaln¡.

☛

Zbiór

n

jest

li zb¡

naturaln¡

wtedy

i

t

ylk

o

wtedy

,

gdy

jego

nastpnik

S(n)

jest

li zb¡

naturaln¡;

przyjm

ujem

y

,

»e

0

df

=

∅

,

1

df

= S(0)

,

2

df

= S(1)

itd.

☛

Li zb

y

naturalne

t

w

orz¡

zbiór;

zbiór

ten

ozna za¢

b

dziem

y

sym

b

olem

ω

.

ω

jest

grani zn¡

li zb¡

p

orz¡dk

o

w

¡

i

ω =

S ω

.

☛

Ci¡

gi

p

ozask

o« zone

t

ypu

ω

nazyw

ane

s¡

i¡gami

;

i¡

gi

p

ozask

o« zone

t

ypu

n

∈ ω

nazyw

ane

s¡

i¡gami

sko« zonymi

.

Je»eli

zbiór

u

sp

eªnia

aksjomat

niesko« zono± i,

to

do

u

nale»¡

wszystkie

li zby

natur

alne.

Do

w

ó

d.

Gdyb

y

p

ewna

li zba

naturalna

n

nie

nale»aªa

do

u

,

to

m =

min

{k

≤ n : k /

∈ u}

b

yªab

y

p

opra

wnie

okre±lon¡

li zb¡

naturaln¡

nie

nale»¡ ¡

do

u

.

P

oniew

a»

0

∈ u

,

wi

m > 0

i

m = S(k)

dla

p

ewnej

li zb

y

naturalnej

k

.

Zgo

dnie

z

deni j¡

m

m

usi

b

y¢

k

∈ u

i

S(k) = m /

∈ u



sprze zno±¢.

2

Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

8

F

Induk

ja

p

ozask

o« zona

☛

Z

p

o

j iem

induk

ji

p

ozask

o« zonej

zwi¡zane

s¡

dw

a

t

wierdzenia:

t

wierdzenie

o

induk

ji

p

ozask

o« zo-

nej

i

t

wierdzenie

o

denio

w

aniu

przez

induk

j

p

ozask

o« zon¡.

☛

T

wierdzenie

o

denio

w

aniu

przez

induk

j

p

ozask

o« zon¡

wyk

orzystuje

si

w

do

w

o

da

h

istnienia

p

ew-

n

y

h

i¡

gó

w

p

ozask

o« zon

y

h.

☛

Zasada

induk

ji

matemat

y znej:

je»eli

ϕ

jest

form

uª¡

teoriomnogo± io

w

¡

p

osiada

j¡ ¡

jedn¡

zmienn¡

w

oln¡

x

,

to

(

∀

n∈ω

((

∀

m<n

ϕ(x := m)) ⇒ ϕ(x := n))) ⇒ (∀

n∈ω

ϕ(x := n))

.

Nie

h

(u, 6

R

)

b



dzie

zbior

em

dobrze

up

orz¡dkowanym,

a

ϕ

formuª¡

te

oriomno

go± iow¡

p

osiadaj¡

¡

je

dn¡

zmienn¡

woln¡

x

.

Wów zas



∀

z∈u



∀

y<

R

z

ϕ(x := y)



⇒ ϕ(x := z)



⇒



∀

y∈u

ϕ(x := y)



Do

w

ó

d.

Przypu±¢m

y

,

»e

istnieje

takie

y

∈ u

,

»e

zdanie

ϕ(x := y)

nie

jest

pra

wdziw

e.

Nie

h

z

b

dzie

na

jmniejszym

elemen

tem

zbioru

{y

∈ u : ¬ϕ(x := y)}

.

Wó

w

zas

dla

k

a»dego

y

∈ u

takiego,

»e

y <

R

z

zdanie

ϕ(x := y)

jest

pra

wdziw

e,

sk

¡d

na

mo

y

zaªo»enia

zdanie

ϕ(x := z)

m

usi

b

y¢

pra

wdziw

e



sprze zno±¢.

2

Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

8

G

Induk

ja

p

ozask

o« zona

(2)

Dla

ka»de

go

zbioru

u

,

ka»dej

li zby

p

orz¡dkowej

α

i

ka»dej

funk ji

h :

S

β<α

u

β

→ u

istnieje

dokªadnie

je

den

taki

i¡g

p

ozasko« zony

(f

β

)

β<α

,

»e

d

la

ka»de

go

β < α

f(β) = h(f|

β

)

.

(

∗

)

Do

w

ó

d.

Zau

w

a»m

y

na

jpierw,

»e

je»eli

taki

i¡

g

istnieje,

to

jest

dokªadnie

jeden.

Rze zywi± ie,

gdyb

y

istniaª

inn

y

i¡

g

p

ozask

o« zon

y

(g

β

)

β<α

sp

eªnia

j¡ y

w

arunek

(

∗

),

to

zbiór

{β < α : f(β)

6= g(β)}

b

yªb

y

niepust

y

i

p

osiadaªb

y

elemen

t

na

jmniejszy

z

.

Wó

w

zas

f|

z

= g|

z

,

sk

¡d

f(z) = h(f|

z

) = h(g|

z

) = g(z)



sprze zno±¢.

Przypu±¢m

y

,

»e

istnieje

taki

zbiór

u

,

li zba

p

orz¡dk

o

w

a

α

i

funk

ja

h

,

»e

»aden

i¡

g

p

ozask

o« zon

y

nie

sp

eªnia

w

arunku

(

∗

).

Nie

h

β

b

dzie

na

jmniejsz¡

sp

o±ró

d

li zb

p

orz¡dk

o

wy

h

mniejszy

h

lub

ró

wn

y

h

α

,

dla

który

h

nie

istnieje

i¡

g

p

ozask

o« zon

y

sp

eªnia

j¡ y

w

arunek

(

∗

).

Wó

w

zas

dla

k

a»dego

γ < β

istnieje

dokªadnie

jeden

i¡

g

p

ozask

o« zon

y

(g(γ)

δ

)

δ<γ

taki,

»e

g(γ)(δ) = h(g(γ)|

δ

)

dla

k

a»dego

δ < γ

.

Zau

w

a»m

y

,

»e

je»eli

δ < γ < β

,

to

g(δ) = g(γ)|

δ

,

o

wynik

a

z

tego,

»e

obie

te

funk

je

sp

eªnia

j¡

w

arunek

deniuj¡ y

g(δ)

i

z

tego,

»e

istnieje

dokªadnie

jedna

tak

a

funk

ja.

Mo»liw

e

s¡

t

ylk

o

dwie

sytua je:

(1)

β

jest

grani zn¡

li zb¡

p

orz¡dk

o

w

¡.

Wó

w

zas

przyp

orz¡dk

o

w

anie

β

∋ γ 7→ g(γ) ∈

S

δ<β

u

δ

jest

funk

j¡,

o

wynik

a

z

aksjomatu

zastp

o

w

ania,

aksjomatu

wy inania

i

tego,

»e

istnieje

jednozna zna

Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

8

H

Induk

ja

p

ozask

o« zona

(3)

form

uªa

teoriomnogo± io

w

a

ró

wno

w

a»na

z

y = g(γ)

(t

form

uª

mo»na

uzysk

a¢

np.

jak

o

k

oniunk

j

trze

h

w

arunk

ó

w:

y

jest

funk

j¡,

dziedzin¡

y

jest

γ

i

dla

k

a»dego

δ < γ

oraz

k

a»dej

funk

ji

e : δ → u

mam

y

e

⊆ y ⇒ y(δ) = h(e)

).

Co

wi ej,

f =

S

γ<β

g(γ)

jest

p

opra

wnie

okre±lon

ym

i¡

giem

p

ozask

o« zon

ym

t

ypu

β

i

f(γ) = g(S(γ))(γ) = h(g(S(γ))|

γ

) = h(f|

γ

)

dla

k

a»dego

γ < β



sprze zno±¢,

b

o

zgo

dnie

z

zaªo»eniem

taki

i¡

g

nie

mo»e

istnie¢.

(2)

β = S(δ)

dla

p

ewnej

li zb

y

p

orz¡dk

o

w

ej

δ

.

Wó

w

zas

f = g(δ)

∪ {(δ, h(g(δ)))}

jest

i¡

giem

p

oza-

sk

o« zon

ym

t

ypu

β

,

f(γ) = g(δ)(γ) = h(g(δ)|

γ

) = h(f|

γ

)

dla

k

a»dego

γ < δ

i

f(δ) = h(g(δ)) = h(f|

δ

)



sprze zno±¢,

b

o

zgo

dnie

z

zaªo»eniem

taki

i¡

g

nie

mo»e

istnie¢.

2

Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

8

I

ε

-induk

ja

Nie

h

ϕ

b



dzie

formuª¡

te

oriomno

go± iow¡,

któr

a

p

osiada

je

dn¡

zmienn¡

woln¡

x

.

Je»eli

∀

x



∀

y∈x

ϕ(x := y)



⇒ ϕ



,

to

ϕ(x)

d

la

ka»de

go

x

.

Do

w

ó

d.

Przypu±¢m

y

,

»e

¬ϕ(z)

dla

p

ewnego

z

.

Nie

h

w

b

dzie

takim

zbiorem

prze

ho

dnim,

»e

z

∈ w

.

Nie

h

v = {x

∈ w : ¬ϕ(x)}

.

Wó

w

zas

z

∈ v

,

wi

v

6= ∅

.

Na

mo

y

aksjomatu

regularno± i

istnieje

takie

x

∈ v

,

»e

x

∩ v = ∅

.

P

oniew

a»

¬ϕ(x)

,

wi

m

usi

istnie¢

takie

y

∈ x

,

»e

¬ϕ(y)

.

Z

prze

ho

dnio± i

zbioru

w

wynik

a,

»e

y

∈ w

(b

o

y

∈ x

,

x

∈ v

,

a

v

⊆ w

),

sk

¡d

y

∈ v



sprze zno±¢.

2

Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

8

J

ε

-induk

ja

(2)

Dla

ka»dej

li zby

p

orz¡dkowej

α

istnieje

taki

i¡g

p

ozasko« zony

(f(α))

β<α

,

»e

f(α)(β) =











∅

gdy

β = 0

,

[

γ<β

P(f(α)(γ))

gdy

β > 0

.

Do

w

ó

d.

Przypu±¢m

y

,

»e

dla

p

ewnej

li zb

y

α

szuk

an

y

i¡

g

nie

istnieje.

Bez

strat

y

ogólno± i

mo»em

y

zaªo»y¢,

»e

α

jest

na

jmniejsz¡

li zb¡

p

orz¡dk

o

w

¡

o

tej

wªasno± i.

Wó

w

zas

dla

k

a»dego

β < α

istnieje

dokªadnie

jeden

taki

i¡

g

p

ozask

o« zon

y

(g(β)

γ

)

γ<β

,

»e

g(β)(γ) =











∅

gdy

γ = 0

,

[

δ<γ

P(g(β)(δ))

gdy

γ > 0

.

Mo»liw

e

s¡

t

ylk

o

dwie

sytua je:



α

jest

grani zn¡

li zb¡

p

orz¡dk

o

w

¡.

Wó

w

zas

przyp

orz¡dk

o

w

anie

α

∋ β 7→ g(β)

jest

funk

j¡,

o

wynik

a

z

aksjomatu

zastp

o

w

ania,

aksjomatu

wy inania

i

tego,

»e

istnieje

jednozna zna

form

uªa

teoriomno-

go± io

w

a

ró

wno

w

a»na

z

y = g(β)

(t

form

uª

mo»na

uzysk

a¢

np.

jak

o

k

oniunk

j

trze

h

w

arunk

ó

w:

y

Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

8

K

ε

-induk

ja

(3)

jest

funk

j¡,

dziedzin¡

y

jest

β

i

dla

k

a»dego

γ < β

oraz

k

a»dej

funk

ji

e

,

której

dziedzin¡

jest

δ

mam

y

e

⊆ y ⇒ y(δ) =

S

δ

′

<δ

P(e(δ

′

))

.

Co

wi ej,

f =

S

β<α

g(β)

jest

p

opra

wnie

okre±lon

ym

i¡

giem

p

oza-

sk

o« zon

ym

t

ypu

α

i

f(β) = g(S(β))(β) =

S

γ<β

P(g(S(β))(γ)) =

S

γ<β

P(f(γ))

dla

k

a»dego

β < α



sprze zno±¢,

b

o

zgo

dnie

z

zaªo»eniem

taki

i¡

g

nie

mo»e

istnie¢.



α = S(β)

dla

p

ewnej

li zb

y

β

.

Wó

w

zas

f = g(β)

∪ {(β,

S

γ<β

P(g(β)(γ))}

jest

i¡

giem

p

oza-

sk

o« zon

ym

t

ypu

α

,

f(γ) = g(β)(γ) =

S

δ<γ

P(g(β)(δ)) =

S

δ<γ

P(f(δ))

dla

k

a»dego

γ < δ

i

f(β) =

S

γ<β

P(g(β)(γ)) =

S

γ<β

P(f(γ))



sprze zno±¢,

b

o

zgo

dnie

z

zaªo»eniem

taki

i¡

g

nie

mo»e

istnie¢.

2

Dla

ka»de

go

zbioru

u

istnieje

taka

li zb

a

p

orz¡dkowa

α

,

»e

u

⊆ f(S(α))(α)

.

Do

w

ó

d.

Sk

orzystam

y

z

t

wierdzenia

o

ε

-induk

ji.

Zaªó»m

y

,

»e

dla

k

a»dego

x

∈ u

istnieje

tak

a

li zba

p

orz¡dk

o

w

a

β

,

»e

x

⊆ f(S(β))(β)

.

Wó

w

zas

przyp

orz¡dk

o

w

anie

u

∋ x 7→ g(x) =

min

{β : x

⊆ f(S(β))(β)}

jest

p

opra

wnie

okre±lon¡

funk

j¡.

P

oniew

a»

elemen

tami

D

∗

(g)

s¡

li zb

y

p

orz¡dk

o

w

e,

wi

α =

S D

∗

(g)

jest

li zb¡

p

orz¡dk

o

w

¡.

Zau

w

a»m

y

,

»e

je»eli

x

∈ u

,

to

x

∈ P(f(S(g(x)))(g(x))) ⊆

S

β∈D

∗

(g)

P(f(S(β))(β))

⊆

S

β∈α

P(f(S(β))(β)) = f(S(α))(α)

,

o

k

o« zy

do

w

ó

d.

2

Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

8

L

T

yp

y

p

orz¡dk

o

w

e

☛

Li zba

p

orz¡dk

o

w

a

α

jest

typ

em

p

orz¡dkowym

zbioru

dobrze

up

orz¡dk

o

w

anego

(u, 6

R

)

wtedy

i

t

ylk

o

wtedy

,

gdy

(u, 6

R

)

≃ (α, ∈

α

)

.

☛

T

yp

y

p

orz¡dk

o

w

e

izomor zn

y

h

zbioró

w

dobrze

up

orz¡dk

o

w

an

y

h

s¡

iden

t

y zne;

t

yp

p

orz¡dk

o

wy

zbioru

(u, 6

R

)

ozna za¢

b

dziem

y

sym

b

olem

hu, 6

R

i

.

☛

Je»eli

α

jest

li zb¡

p

orz¡dk

o

w

¡,

to

hα, ∈

α

i = α

.

Je»eli

(u, 6

u

)

jest

zbior

em

dobrze

up

orz¡dkowanym,

to

istnieje

dokªadnie

je

dna

taka

li zb

a

p

orz¡dkowa

α

,

»e

(u, 6

u

)

≃ (α, ∈

α

)

.

Do

w

ó

d.

W

ystar zy

wyk

aza¢,

»e

tak

a

li zba

p

orz¡dk

o

w

a

istnieje,

b

o

jej

jednozna zno±¢

wynik

a

z

prze-

ho

dnio± i

≃

i

z

jednego

z

p

oprzedni

h

t

wierdze«.

Nie

h

v

b

dzie

zbiorem

t

y

h

i

t

ylk

o

t

y

h

elemen

tó

w

x

∈ u

,

dla

który

h

istnieje

tak

a

li zba

p

orz¡dk

o

w

a

β

,

»e

(

pred

(u, x, 6

R

), 6

R

)

≃ (β, ∈

β

)

.

Przyjmijm

y

tak»e,

»e

f

jest

funk

j¡,

która

przyp

orz¡dk

o

wuje

elemen

to

wi

x

∈ v

t

jedyn¡

li zb



p

orz¡dk

o

w

¡

β

,

która

sp

eªnia

w

arunek

(

pred

(u, x, 6

R

), 6

R

)

≃ (β, ∈

β

)

(to,

»e

tak

a

funk

ja

istnieje,

wynik

a

z

aksjomatu

zastp

o

w

ania)

oraz

α = f[v]

.

Wó

w

zas:

(1)

f

jest

funk

j¡

ró»no

w

arto± io

w

¡.

Rze zywi± ie,

je»eli

f(x) = f(y) = β

,

to

(

pred

(u, x, 6

R

), 6

R

)

≃

(β,

∈

β

)

i

(

pred

(u, y, 6

R

), 6

R

)

≃ (β, ∈

β

)

,

sk

¡d

(

pred

(u, x, 6

R

), 6

R

)

≃ (

pred

(u, y, 6

R

), 6

R

)

i

x = y

.

Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

8

M

T

yp

y

p

orz¡dk

o

w

e

(2)

(2)

α

jest

li zb¡

p

orz¡dk

o

w

¡.

Elemen

t

y

α

s¡

li zbami

p

orz¡dk

o

wymi,

wi

wystar zy

wyk

aza¢,

»e

α

jest

zbiorem

prze

ho

dnim.

Nie

h

γ

∈ β

i

β

∈ α

.

Wó

w

zas

γ

jest

li zb¡

p

orz¡dk

o

w

¡

i

γ =

pred

(β, γ)

.

P

oniew

a»

β

∈ α

,

wi

(β,

∈

β

)

≃ (

pred

(u, x, 6

R

), 6

R

)

dla

p

ewnego

x

∈ v

,

sk

¡d

wynik

a

o

d

razu,

»e

k

a»dy

o

d inek

p

o

z¡tk

o

wy

za

w

art

y

w

β

jest

izomor zn

y

z

p

ewn

ym

o

d inkiem

p

o

z¡tk

o

wym

za

w

art

ym

w

pred

(u, x, 6

R

)

.

Zatem

(γ,

∈

γ

)

≃ (

pred

(u, y, 6

R

), 6

R

)

dla

p

ewnego

y

∈ u

,

sk

¡d

γ

∈ α

.

(3)

f : v → α

jest

izomorzmem.

f

jest

bijek

j¡

na

mo

y

(1)

,

wi

wystar zy

wyk

aza¢,

»e

x <

R

y ⇔

f(x)

∈ f(y)

dla

wszystki

h

x, y

∈ v

.

Zau

w

a»m

y

,

»e

x <

R

y

wtedy

i

t

ylk

o

wtedy

,

gdy

pred

(u, x, 6

R

) (

pred

(u, y, 6

R

)

.

P

oniew

a»

(

pred

(u, x, 6

R

), 6

R

)

≃ (f(x), ∈

f(x)

)

i

(

pred

(u, y, 6

R

), 6

R

)

≃ (f(y), ∈

f(y)

)

,

wi

pred

(u, x, 6

R

) (

pred

(u, y, 6

R

)

wtedy

i

t

ylk

o

wtedy

,

gdy

f(x)

jest

izomor zne

z

p

ewn

ym

o

d inkiem

p

o

z¡tk

o

wym

za

w

art

ym

w

f(y)

,

a

to

za

ho

dzi

wtedy

i

t

ylk

o

wtedy

,

gdy

f(x)

∈ f(y)

.

(4)

u = v

.

Gdyb

y

u

6= v

,

to

zbiór

u \ v

b

yªb

y

niepust

y

i

p

osiadaªb

y

elemen

t

na

jmniejszy

z

.

Zau

w

a»m

y

,

»e

v

m

usi

b

y¢

o

d inkiem

w

u

,

o

wynik

a

z

deni ji

v

i

tego,

»e

o

d inki

p

o

z¡tk

o

w

e

za

w

arte

w

li zba

h

p

orz¡dk

o

wy

h

s¡

li zbami

p

orz¡dk

o

wymi.

St¡d

v =

pred

(u, z, 6

R

)

,

o

w

p

oª¡ zeniu

z

(v, 6

R

)

≃ (α, ∈

α

)

da

je

z

∈ v



sprze zno±¢.

2

Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

8

N

Do

da

w

anie

i

o

dejmo

w

anie

☛

Sum¡

li zb

p

orz¡dk

o

wy

h

α

,

β

nazyw

a¢

b

dziem

y

t

yp

p

orz¡dk

o

wy

zbioru

((α

× {0}) ∪ (β × {1}), 6

αβ

)

,

gdzie

6

αβ

jest

rela j¡

dan¡

wzorem

(x, y) 6

αβ

(z, t) ⇔ (y = 0 ∧ t = 1) ∨ (y = t ∧ (x ∈ z ∨ x = z))

.

☛

Sum

li zb

p

orz¡dk

o

wy

h

α

,

β

ozna za¢

b

dziem

y

sym

b

olem

α + β

;

suma

jest

dobrze

zdenio

w

ana,

b

o

6

αβ

jest

rela j¡

dobrego

p

orz¡dku

w

(α

× {0}) ∪ (β × {1})

.

☛

Do

da

w

anie

li zb

p

orz¡dk

o

wy

h

jest

ª¡ zne,

tzn.

α + (β + γ) = (α + β) + γ

dla

wszystki

h

α

,

β

i

γ

,

ale

nie

jest

przemienne,

tzn.

istniej¡

takie

li zb

y

α

i

β

,

»e

α + β

6= β + α

.

☛

0

jest

elemen

tem

neutraln

ym

do

da

w

ania,

tzn.

α+0 = 0+α

dla

k

a»dej

li zb

y

p

orz¡dk

o

w

ej

α

;

do

da

w

anie

li zb

p

orz¡dk

o

wy

h

ma

p

onadto

nastpuj¡ e

wªasno± i:



α + 1 = S(α)

dla

k

a»dego

α

;



je»eli

α < β

,

to

γ + α < γ + β

i

α + γ

≤ β + γ

dla

k

a»dego

γ

;



je»eli

α

≤ β

,

to

α + γ

≤ β + γ

i

γ + α

≤ γ + β

dla

k

a»dego

γ

.

☛

Je»eli

α

≥ β

,

to

istnieje

dokªadnie

jedna

tak

a

li zba

p

orz¡dk

o

w

a

γ

,

»e

α = β + γ

;

t

li zb



nazyw

am

y

r

ó»ni

¡

li zb

α

,

β

i

ozna zam

y

sym

b

olem

α − β

.

☛

Do

da

w

anie

li zb

naturaln

y

h

jest

przemienne;

suma

i

ró»ni a

(o

ile

istnieje)

li zb

naturaln

y

h

to

li zb

y

naturalne.

Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

8

O

Mno»enie

i

dzielenie

☛

Ilo

zynem

li zb

p

orz¡dk

o

wy

h

α

,

β

nazyw

a¢

b

dziem

y

t

yp

p

orz¡dk

o

wy

zbioru

(β

× α, 6

∗
αβ

)

,

gdzie

6

∗
αβ

jest

rela j¡

dan¡

wzorem

(x, y) 6

∗
αβ

(z, t) ⇔ (x ∈ z) ∨ (x = z ∧ (y ∈ t ∨ y = t))

.

☛

Ilo

zyn

li zb

p

orz¡dk

o

wy

h

α

,

β

ozna za¢

b

dziem

y

sym

b

olem

α

· β

;

ilo

zyn

jest

dobrze

zdenio

w

an

y

,

b

o

6

∗
αβ

jest

rela j¡

dobrego

p

orz¡dku

w

β

× α

.

☛

Mno»enie

li zb

p

orz¡dk

o

wy

h

jest

ª¡ zne,

tzn.

α

· (β · γ) = (α · β) · γ

dla

wszystki

h

α

,

β

i

γ

,

ale

nie

jest

przemienne,

tzn.

istniej¡

takie

li zb

y

α

i

β

,

»e

α

· β 6= β · α

.

☛

1

jest

elemen

tem

neutraln

ym

mno»enia,

tzn.

α

· 1 = 1 · α

dla

k

a»dej

li zb

y

p

orz¡dk

o

w

ej

α

;

mno»enie

li zb

p

orz¡dk

o

wy

h

ma

p

onadto

nastpuj¡ e

wªasno± i:



α

· 0 = 0

dla

k

a»dego

α

;

je»eli

α

· β = 0

,

to

α = 0

lub

β = 0

;



je»eli

α < β

i

γ

6= 0

,

to

γ

· α < γ · β

i

α

· γ ≤ β · γ

dla

k

a»dego

γ

;



je»eli

α

≤ β

,

to

α

· γ ≤ β · γ

i

γ

· α ≤ γ · β

dla

k

a»dego

γ

;



α

· (β + γ) = α · β + α · γ

dla

wszystki

h

α

,

β

i

γ

.

Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

8

P

Mno»enie

i

dzielenie

(2)

☛

Dla

wszystki

h

li zb

p

orz¡dk

o

wy

h

α

6= 0

i

β

istniej¡

takie

li zb

y

p

orz¡dk

o

w

e

γ

i

δ < α

,

»e

β = α

·γ+δ

;

γ

nazyw

am

y

ilor

azem

,

a

δ

r

eszt¡

z

dzielenia

β

przez

α

.

☛

Iloraz

i

reszta

z

dzielenia

s¡

wyzna zone

jednozna znie;

b

dziem

y

pisa¢

α|β

(

α

dzieli

β

,

β

jest

p

o

dzielne

przez

α

),

je»eli

istnieje

takie

γ

,

»e

β = α

· γ

.

☛

Mno»enie

li zb

naturaln

y

h

jest

przemienne;

ilo

zyn,

iloraz

i

reszta

z

dzielenia

li zb

naturaln

y

h

to

li zb

y

naturalne.

☛

Przyjmijm

y

,

»e

ω

[n]

jest

li zb¡

p

orz¡dk

o

w

¡

dan¡

wzorem

rekuren yjn

ym

ω

[0]

= 1

i

ω

[n+1]

= ω

[n]

· ω

.

Je»eli

n

,

m

,

k

i

l

s¡

li zbami

naturaln

ymi,

to



je»eli

n < m

i

l > 0

,

to

ω

[n]

· k + ω

[m]

· l = ω

[m]

· l

;



je»eli

n = m

,

to

ω

[n]

· k + ω

[m]

· l = ω

[m]

· (k + l)

;



je»eli

n > 0

i

k > 0

,

to

k

· ω

[n]

= ω

[n]

;



je»eli

α < ω

[n]

,

m > 0

i

k > 0

,

to

(ω

[n]

· k + α) · ω

[m]

= ω

[n+m]

.

Ÿ

8

.

Li zb

y

p

orz¡dk

o

w

e

8

Q