8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

8

Li zb

y

p

orz¡dk

o

w

e

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

A

8

P

oró

wn

yw

anie

li zb

p

orz¡dk

o

wy

h

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

C

8

Li zb

y

naturalne

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

F

8

Induk

ja

p

ozask

o« zona

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

G

ε

8

-induk

ja

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

J

8

T

yp

y

p

orz¡dk

o

w

e

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

M

8

Do

da

w

anie

i

o

dejmo

w

anie

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

O

8

Mno»enie

i

dzielenie

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

P

8

‚

wi zenia

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

R

8

Zadania

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

S

Li zb

y

p

orz¡dk

o

w

e

☛

u

x ∈ u

x ⊆ u

Zbiór

jest

prze

ho

dni

wtedy

i

t

ylk

o

wtedy

,

gdy

dla

k

a»dego

mam

y

.

☛

u

S(u) S u T u

Zbiór

pust

y

jest

zbiorem

prze

ho

dnim;

je»eli

jest

zbiorem

prze

ho

dnim,

to

,

,

(o

ile

u 6= ∅

P(u)

)

i

s¡

zbiorami

prze

ho

dnimi.

☛

u

S u ⊆ u u ⊆ P(u)

u 6= ∅

Zbiór

jest

zbiorem

prze

ho

dnim

wtedy

i

t

ylk

o

wtedy

,

gdy

(

);

je»eli

jest

∅ ∈ u

zbiorem

prze

ho

dnim,

to

na

mo

y

aksjomatu

regularno± i.

☛

(u, x) df

= u ∩ x

∈u

u

(u, x) =

Przyjm

ujem

y

,

»e

pred

.

Je»eli

jest

rela j¡

z± io

w

ego

p

orz¡dku

w

,

to

pred

(u, x, ∈u)

u

x ∈ u

(u, x) = x

pred

;

je»eli

jest

zbiorem

prze

ho

dnim

i

,

to

pred

.

☛

u

∈u

u x ∈ u

x

Je»eli

jest

zbiorem

prze

ho

dnim,

jest

rela j¡

z± io

w

ego

p

orz¡dku

w

i

,

to

jest

zbiorem

y ∈ x

y ∈ u

y =

(u, y) ⊆

(u, x) = x

prze

ho

dnim,

b

o

je±li

,

to

oraz

pred

pred

.

☛

u

(u, ∈u)

Zbiór

prze

ho

dni

jest

li zb

¡

p

orz¡dkow¡

wtedy

i

t

ylk

o

wtedy

,

gdy

para

jest

zbiorem

dobrze

up

orz¡dk

o

w

an

ym.

8

8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

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

.

☛

α

S(α) T α

α 6= ∅

S α

Zbiór

pust

y

jest

li zb¡

p

orz¡dk

o

w

¡;

je»eli

jest

li zb¡

p

orz¡dk

o

w

¡,

to

,

(o

ile

)

i

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

¡

x ∈ α

x

i

,

to

jest

li zb¡

p

orz¡dk

o

w

¡.

☛

u

u

Je»eli

jest

zbiorem,

którego

elemen

t

y

s¡

li zbami

p

orz¡dk

o

wymi,

to

jest

li zb¡

p

orz¡dk

o

w

¡

wtedy

i

t

ylk

o

wtedy

,

gdy

jest

zbiorem

prze

ho

dnim.

☛

α

α 6= ∅

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

i

nie

istnieje

v

α = S(v)

takie

,

»e

.

☛

α

α

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

8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

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(β) α < β ⇔ S(α) ≤ β

i

.

☛

(fβ)β<α

f

α

Bdziem

y

pisa¢

,

ab

y

zazna zy¢,

»e

jest

i¡

giem

p

ozask

o« zon

ym

t

ypu

.

8

8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

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) (α, ∈α) ≃ (β, ∈β)

α = β

(3) α ⊆ β

β ⊆ α

tylko

wte

dy,

gdy

;

lub

;

(2) α = β α ∈ β

β ∈ α

(4) α ( β ⇔ α ∈ β

,

lub

;

.

(1)

f : α → β

α 6= β

x ∈ α

f(x) 6= x

Do

w

ó

d.

Nie

h

b

dzie

izomorzmem.

Gdyb

y

,

to

zbiór

t

y

h

,

»e

z

z ∈ α

f(z) ∈ β

z =

(α, z)

b

yªb

y

niepust

y

i

p

osiadaªb

y

elemen

t

na

jmniejszy

.

P

oniew

a»

i

,

wi

pred

f(z) =

(β, f(z))

f[

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

i

pred

,

sk

¡d

pred

.

Co

wi ej,

jest

f[

(α, z)] =

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

f(z) = z

izomorzmem,

wi

pred

pred

,

sk

¡d

sprze zno±¢.

(2) Na mo y jednego z udowodniony h w ze±niej twierdze« (patrz wykªad po±wi ony porz¡dkom,

punkt

p

o±wi on

y

izomorzmom)

za

ho

dzi

jedna

z

nastpuj¡ y

h

sytua ji:

(α, ∈α) ≃ (β, ∈β)

α = β

(1)

.

Wó

w

zas

na

mo

y

.

x ∈ α

(

(α, x), ∈α) ≃ (β, ∈β)

β =

(α, x)

(1)

Istnieje

takie

,

»e

pred

.

Wó

w

zas

pred

na

mo

y

,

o

w

x =

(α, x)

β = x ∈ α

p

oª¡ zeniu

z

ró

wno± i¡

pred

da

je

.

y ∈ β

(α, ∈α) ≃ (

(β, y), ∈β)

α =

(β, y)

(1)

Istnieje

takie

,

»e

pred

.

Wó

w

zas

pred

na

mo

y

,

o

w

y =

(β, y)

α = y ∈ β

p

oª¡ zeniu

z

ró

wno± i¡

pred

da

je

.

(3) (4)

(2)

α β

2

,

W

ynik

a

j¡

nat

y

hmiast

z

oraz

z

tego,

»e

i

s¡

zbiorami

prze

ho

dnimi.

8

8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

D

P

oró

wn

yw

anie

li zb

p

orz¡dk

o

wy

h

(3)

u

(u, ∈u)

Je»eli

jest

niepustym

zbior

em,

któr

e

go

elementy

s¡

li zb

ami

p

orz¡dkowymi,

to

jest

zbior

em

dobrze

up

orz¡dkowanym.

(u, ∈u)

(4)

Do

w

ó

d.

T

o,

»e

jest

zbiorem

z± io

w

o

up

orz¡dk

o

w

an

ym

wynik

a

z

punktu

p

oprzedniego

t

wier-

(u, ⊆u)

u

dzenia

oraz

z

tego,

»e

jest

zbiorem

z± io

w

o

up

orz¡dk

o

w

an

ym.

T

o,

»e

jest

ªa« u

hem,

wynik

a

(2)

z

punktu

tego

samego

t

wierdzenia.

Ab

y

zak

o« zy¢

do

w

ó

d,

wystar zy

wyk

aza¢,

»e

k

a»dy

niepust

y

v ⊆ u

zbiór

p

osiada

elemen

t

minimaln

y

,

b

o

dla

rela ji

linio

w

ego

p

orz¡dku

elemen

t

y

minimalne

s¡

to»same

x ∈ v

z

na

jmniejszymi.

W

t

ym

elu

zau

w

a»m

y

,

»e

na

mo

y

aksjomatu

regularno± i

istnieje

takie,

»e

x ∩ v = ∅

y ∈ v

y /

∈ x

x

.

Wó

w

zas

dla

k

a»dego

mam

y

,

o

k

o« zy

do

w

ó

d,

b

o

to

ozna za,

»e

jest

elemen

tem

v

2

minimaln

ym

w

zbiorze

.

Nie

istnieje

zbiór

wszystki h

li zb

p

orz¡dkowy h.

u

x ∈ u

x

Do

w

ó

d.

Przypu±¢m

y

,

»e

jest

zbiorem

wszystki

h

li zb

p

orz¡dk

o

wy

h.

Je»eli

,

to

jest

li zb¡

x ⊆ u

u

p

orz¡dk

o

w

¡,

sk

¡d

,

b

o

elemen

t

y

li zb

y

p

orz¡dk

o

w

ej

s¡

li zbami

p

orz¡dk

o

wymi.

Zatem

jest

zbiorem

u ∈ u

2

prze

ho

dnim,

a

wi

i

li zb¡

p

orz¡dk

o

w

¡

sprze zno±¢,

b

o

z

tego

wynik

a,

»e

.

8

8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

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-

β ≤ α

γ

β = S(γ)

k

o

w

ej

istnieje

takie

,

»e

.

☛

m

Zbiór

pust

y

jest

li zb¡

naturaln¡;

wystpuj¡ e

dalej

li zb

y

naturalne

b

dziem

y

ozna zali

literami

,

n k l

n

m < n

m

,

i

.

Je»eli

jest

li zb¡

naturaln¡

i

,

to

jest

li zb¡

naturaln¡.

☛

n

S(n)

Zbiór

jest

li zb¡

naturaln¡

wtedy

i

t

ylk

o

wtedy

,

gdy

jego

nastpnik

jest

li zb¡

naturaln¡;

0 df

= ∅ 1 df

= S(0) 2 df

= S(1)

przyjm

ujem

y

,

»e

,

,

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¡

ω = S ω

p

orz¡dk

o

w

¡

i

.

☛

ω

n ∈ ω

Ci¡

gi

p

ozask

o« zone

t

ypu

nazyw

ane

s¡

i¡gami

;

i¡

gi

p

ozask

o« zone

t

ypu

nazyw

ane

s¡

i¡gami

sko« zonymi

.

u

u

Je»eli

zbiór

sp

eªnia

aksjomat

niesko« zono± i,

to

do

nale»¡

wszystkie

li zby

natur

alne.

n

u

m =

{k ≤ n : k /

∈ u}

Do

w

ó

d.

Gdyb

y

p

ewna

li zba

naturalna

nie

nale»aªa

do

,

to

min

b

yªab

y

p

opra

wnie

u

0 ∈ u

m > 0

m = S(k)

okre±lon¡

li zb¡

naturaln¡

nie

nale»¡ ¡

do

.

P

oniew

a»

,

wi

i

dla

p

ewnej

li zb

y

k

m

k ∈ u S(k) = m /

∈ u

2

naturalnej

.

Zgo

dnie

z

deni j¡

m

usi

b

y¢

i

sprze zno±¢.

8

8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

F

Induk

ja

p

ozask

o« zona

☛ Z poj iem induk ji pozasko« zonej zwi¡zane s¡ dwa twierdzenia: twierdzenie o induk ji pozasko« zo-

nej

i

t

wierdzenie

o

denio

w

aniu

przez

induk

j

p

ozask

o« zon¡.

☛ Twierdzenie o deniowaniu przez induk j pozasko« zon¡ wykorzystuje si w dowoda h istnienia pew-

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¡

x

(∀n∈ω((∀m<nϕ(x := m)) ⇒ ϕ(x := n))) ⇒ (∀n∈ωϕ(x := n)) w

oln¡

,

to

.

(u, 6R)

ϕ

Nie

h

b

dzie

zbior

em

dobrze

up

orz¡dkowanym,

a

formuª¡

te

oriomno

go± iow¡

p

osiadaj¡

¡

x

je

dn¡

zmienn¡

woln¡

.

Wów zas

∀

∀ ϕ(x := y) ⇒ ϕ(x := z)

⇒

∀ ϕ(x := y)

z∈u

y<Rz

y∈u

y ∈ u

ϕ(x := y)

z

Do

w

ó

d.

Przypu±¢m

y

,

»e

istnieje

takie

,

»e

zdanie

nie

jest

pra

wdziw

e.

Nie

h

b

dzie

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

y ∈ u

y <R z

na

jmniejszym

elemen

tem

zbioru

.

Wó

w

zas

dla

k

a»dego

takiego,

»e

ϕ(x := y)

ϕ(x := z)

zdanie

jest

pra

wdziw

e,

sk

¡d

na

mo

y

zaªo»enia

zdanie

m

usi

b

y¢

pra

wdziw

e

2

sprze zno±¢.

8

8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

G

Induk

ja

p

ozask

o« zona

(2)

u

α

h : S

uβ → u

Dla

ka»de

go

zbioru

,

ka»dej

li zby

p

orz¡dkowej

i

ka»dej

funk ji

β<α

istnieje

dokªadnie

(fβ)β<α

β < α

je

den

taki

i¡g

p

ozasko« zony

,

»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

(gβ)β<α

∗

{β < α : f(β) 6= g(β)}

istniaª

inn

y

i¡

g

p

ozask

o« zon

y

sp

eªnia

j¡ y

w

arunek

(

),

to

zbiór

b

yªb

y

z

f|z = g|z

f(z) = h(f|z) = h(g|z) = g(z)

niepust

y

i

p

osiadaªb

y

elemen

t

na

jmniejszy

.

Wó

w

zas

,

sk

¡d

sprze zno±¢.

u

α

h

Przypu±¢m

y

,

»e

istnieje

taki

zbiór

,

li zba

p

orz¡dk

o

w

a

i

funk

ja

,

»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

(g(γ)δ)δ<γ

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

δ < γ

istnieje

dokªadnie

jeden

i¡

g

p

ozask

o« zon

y

taki,

»e

dla

k

a»dego

.

δ < γ < β

g(δ) = g(γ)|δ

Zau

w

a»m

y

,

»e

je»eli

,

to

,

o

wynik

a

z

tego,

»e

obie

te

funk

je

sp

eªnia

j¡

w

arunek

g(δ)

deniuj¡ y

i

z

tego,

»e

istnieje

dokªadnie

jedna

tak

a

funk

ja.

Mo»liw

e

s¡

t

ylk

o

dwie

sytua je:

(1) β

β ∋ γ 7→ g(γ) ∈ S

uδ

jest

grani zn¡

li zb¡

p

orz¡dk

o

w

¡.

Wó

w

zas

przyp

orz¡dk

o

w

anie

δ<β

jest

funk

j¡,

o

wynik

a

z

aksjomatu

zastp

o

w

ania,

aksjomatu

wy inania

i

tego,

»e

istnieje

jednozna zna

8

8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

H

Induk

ja

p

ozask

o« zona

(3)

y = g(γ)

form

uªa

teoriomnogo± io

w

a

ró

wno

w

a»na

z

(t

form

uª

mo»na

uzysk

a¢

np.

jak

o

k

oniunk

j

trze

h

y

y

γ

δ < γ

e : δ → u

w

arunk

ó

w:

jest

funk

j¡,

dziedzin¡

jest

i

dla

k

a»dego

oraz

k

a»dej

funk

ji

mam

y

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

f = S

g(γ)

).

Co

wi ej,

γ<β

jest

p

opra

wnie

okre±lon

ym

i¡

giem

p

ozask

o« zon

ym

β

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

t

ypu

i

dla

k

a»dego

sprze zno±¢,

b

o

zgo

dnie

z

zaªo»eniem

taki

i¡

g

nie

mo»e

istnie¢.

(2) β = S(δ)

δ

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

dla

p

ewnej

li zb

y

p

orz¡dk

o

w

ej

.

Wó

w

zas

jest

i¡

giem

p

oza-

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

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

sk

o« zon

ym

t

ypu

,

dla

k

a»dego

i

2

sprze zno±¢,

b

o

zgo

dnie

z

zaªo»eniem

taki

i¡

g

nie

mo»e

istnie¢.

8

8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

I

ε-induk ja

ϕ

x

Nie

h

b

dzie

formuª¡

te

oriomno

go± iow¡,

któr

a

p

osiada

je

dn¡

zmienn¡

woln¡

.

Je»eli

∀

∀ ϕ(x := y) ⇒ ϕ ,

x

y∈x

ϕ(x)

x

to

d

la

ka»de

go

.

¬ϕ(z)

z

w

z ∈ w

Do

w

ó

d.

Przypu±¢m

y

,

»e

dla

p

ewnego

.

Nie

h

b

dzie

takim

zbiorem

prze

ho

dnim,

»e

.

v = {x ∈ w : ¬ϕ(x)}

z ∈ v

v 6= ∅

Nie

h

.

Wó

w

zas

,

wi

.

Na

mo

y

aksjomatu

regularno± i

istnieje

takie

x ∈ v

x ∩ v = ∅

¬ϕ(x)

y ∈ x

¬ϕ(y)

w

,

»e

.

P

oniew

a»

,

wi

m

usi

istnie¢

takie

,

»e

.

Z

prze

ho

dnio± i

zbioru

y ∈ w

y ∈ x x ∈ v

v ⊆ w

y ∈ v

2

wynik

a,

»e

(b

o

,

,

a

),

sk

¡d

sprze zno±¢.

8

8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

J

ε-induk ja (2)

α

(f(α))β<α

Dla

ka»dej

li zby

p

orz¡dkowej

istnieje

taki

i¡g

p

ozasko« zony

,

»e





∅

β = 0

gdy

,

f(α)(β) =

[



P(f(α)(γ))

β > 0



gdy

.

γ<β

α

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

(g(β)γ)γ<β

dokªadnie

jeden

taki

i¡

g

p

ozask

o« zon

y

,

»e





∅

γ = 0

gdy

,

g(β)(γ) =

[



P(g(β)(δ))

γ > 0



gdy

.

δ<γ

Mo»liw

e

s¡

t

ylk

o

dwie

sytua je:

α

α ∋ β 7→ g(β)

jest

grani zn¡

li zb¡

p

orz¡dk

o

w

¡.

Wó

w

zas

przyp

orz¡dk

o

w

anie

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-

y = g(β)

y

go± io

w

a

ró

wno

w

a»na

z

(t

form

uª

mo»na

uzysk

a¢

np.

jak

o

k

oniunk

j

trze

h

w

arunk

ó

w:

8

8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

K

ε-induk ja (3)

y

β

γ < β

e

δ

jest

funk

j¡,

dziedzin¡

jest

i

dla

k

a»dego

oraz

k

a»dej

funk

ji

,

której

dziedzin¡

jest

mam

y

e ⊆ y ⇒ y(δ) = S

P(e(δ′))

f = S

g(β)

δ′<δ

.

Co

wi ej,

β<α

jest

p

opra

wnie

okre±lon

ym

i¡

giem

p

oza-

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

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

P(f(γ))

β < α

sk

o« zon

ym

t

ypu

i

γ<β

γ<β

dla

k

a»dego

sprze zno±¢,

b

o

zgo

dnie

z

zaªo»eniem

taki

i¡

g

nie

mo»e

istnie¢.

α = S(β)

β

f = g(β) ∪ {(β, S

P(g(β)(γ))}

dla

p

ewnej

li zb

y

.

Wó

w

zas

γ<β

jest

i¡

giem

p

oza-

α f(γ) = g(β)(γ) = S

P(g(β)(δ)) = S

P(f(δ))

γ < δ

sk

o« zon

ym

t

ypu

,

δ<γ

δ<γ

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

u

α

u ⊆ f(S(α))(α)

Dla

ka»de

go

zbioru

istnieje

taka

li zb

a

p

orz¡dkowa

,

»e

.

ε

x ∈ u

Do

w

ó

d.

Sk

orzystam

y

z

t

wierdzenia

o

-induk

ji.

Zaªó»m

y

,

»e

dla

k

a»dego

istnieje

tak

a

li zba

β

x ⊆ f(S(β))(β)

u ∋ x 7→ g(x) =

{β : x ⊆ f(S(β))(β)}

p

orz¡dk

o

w

a

,

»e

.

Wó

w

zas

przyp

orz¡dk

o

w

anie

min

D∗(g)

α = S D∗(g)

jest

p

opra

wnie

okre±lon¡

funk

j¡.

P

oniew

a»

elemen

tami

s¡

li zb

y

p

orz¡dk

o

w

e,

wi

x ∈ u

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

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

jest

li zb¡

p

orz¡dk

o

w

¡.

Zau

w

a»m

y

,

»e

je»eli

,

to

β∈D∗(g)

S

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

β

2

∈α

,

o

k

o« zy

do

w

ó

d.

8

8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

L

T

yp

y

p

orz¡dk

o

w

e

☛

α

(u, 6R)

Li zba

p

orz¡dk

o

w

a

jest

typ

em

p

orz¡dkowym

zbioru

dobrze

up

orz¡dk

o

w

anego

wtedy

i

t

ylk

o

(u, 6R) ≃ (α, ∈α)

wtedy

,

gdy

.

☛ Typy porz¡dkowe izomor zny h zbiorów dobrze uporz¡dkowany h s¡ identy zne; typ porz¡dkowy

(u, 6R)

hu, 6Ri

zbioru

ozna za¢

b

dziem

y

sym

b

olem

.

☛

α

hα, ∈αi = α

Je»eli

jest

li zb¡

p

orz¡dk

o

w

¡,

to

.

(u, 6u)

Je»eli

jest

zbior

em

dobrze

up

orz¡dkowanym,

to

istnieje

dokªadnie

je

dna

taka

li zb

a

p

orz¡dkowa

α

(u, 6u) ≃ (α, ∈α)

,

»e

.

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-

≃

v

ho

dnio± i

i

z

jednego

z

p

oprzedni

h

t

wierdze«.

Nie

h

b

dzie

zbiorem

t

y

h

i

t

ylk

o

t

y

h

elemen

tó

w

x ∈ u

β

(

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

,

dla

który

h

istnieje

tak

a

li zba

p

orz¡dk

o

w

a

,

»e

pred

.

Przyjmijm

y

tak»e,

f

x ∈ v

β

»e

jest

funk

j¡,

która

przyp

orz¡dk

o

wuje

elemen

to

wi

t

jedyn¡

li zb

p

orz¡dk

o

w

¡

,

która

sp

eªnia

(

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

w

arunek

pred

(to,

»e

tak

a

funk

ja

istnieje,

wynik

a

z

aksjomatu

zastp

o

w

ania)

α = f[v]

oraz

.

Wó

w

zas:

(1) f

f(x) = f(y) = β

(

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

jest

funk

j¡

ró»no

w

arto± io

w

¡.

Rze zywi± ie,

je»eli

,

to

pred

(β, ∈β) (

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

(

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

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

i

pred

,

sk

¡d

pred

pred

i

.

8

8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

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»

β ∈ α

(β, ∈β) ≃ (

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

x ∈ v

,

wi

pred

dla

p

ewnego

,

sk

¡d

wynik

a

o

d

razu,

»e

k

a»dy

o

d inek

β

(u, x, 6R)

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, y, 6R), 6R)

y ∈ u

γ ∈ α

Zatem

pred

dla

p

ewnego

,

sk

¡d

.

(3) f : v → α

f

(1)

x <R y ⇔

jest

izomorzmem.

jest

bijek

j¡

na

mo

y

,

wi

wystar zy

wyk

aza¢,

»e

f(x) ∈ f(y)

x, y ∈ v

x <R y

(u, x, 6R) (

dla

wszystki

h

.

Zau

w

a»m

y

,

»e

wtedy

i

t

ylk

o

wtedy

,

gdy

pred

(u, y, 6R)

(

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

(

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

pred

.

P

oniew

a»

pred

f(x)) i

pred

f(y)), wi

(u, x, 6R) (

(u, y, 6R)

f(x)

pred

pred

wtedy

i

t

ylk

o

wtedy

,

gdy

jest

izomor zne

z

p

ewn

ym

o

d inkiem

f(y)

f(x) ∈ f(y)

p

o

z¡tk

o

wym

za

w

art

ym

w

,

a

to

za

ho

dzi

wtedy

i

t

ylk

o

wtedy

,

gdy

.

(4) u = v

u 6= v

u \ v

z

.

Gdyb

y

,

to

zbiór

b

yªb

y

niepust

y

i

p

osiadaªb

y

elemen

t

na

jmniejszy

.

Zau

w

a»m

y

,

v

u

v

»e

m

usi

b

y¢

o

d inkiem

w

,

o

wynik

a

z

deni ji

i

tego,

»e

o

d inki

p

o

z¡tk

o

w

e

za

w

arte

w

li zba

h

v =

(u, z, 6R)

(v, 6R) ≃ (α, ∈α)

p

orz¡dk

o

wy

h

s¡

li zbami

p

orz¡dk

o

wymi.

St¡d

pred

,

o

w

p

oª¡ zeniu

z

z ∈ v

2

da

je

sprze zno±¢.

8

8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

N

Do

da

w

anie

i

o

dejmo

w

anie

☛

α β

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

Sum¡

li zb

p

orz¡dk

o

wy

h

,

nazyw

a¢

b

dziem

y

t

yp

p

orz¡dk

o

wy

zbioru

,

6αβ

gdzie

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,

6αβ

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

b

o

jest

rela j¡

dobrego

p

orz¡dku

w

.

☛

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

α β γ

Do

da

w

anie

li zb

p

orz¡dk

o

wy

h

jest

ª¡ zne,

tzn.

dla

wszystki

h

,

i

,

ale

α β

α + β 6= β + α

nie

jest

przemienne,

tzn.

istniej¡

takie

li zb

y

i

,

»e

.

☛ 0

α+0 = 0+α

α

jest

elemen

tem

neutraln

ym

do

da

w

ania,

tzn.

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

.

☛ Dodawanie li zb naturalny h jest przemienne; suma i ró»ni a (o ile istnieje) li zb naturalny h to li zby

naturalne.

8

8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

O

Mno»enie

i

dzielenie

☛

α β

(β × α, 6∗ )

6∗

Ilo

zynem

li zb

p

orz¡dk

o

wy

h

,

nazyw

a¢

b

dziem

y

t

yp

p

orz¡dk

o

wy

zbioru

αβ , gdzie

αβ

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

,

6∗

β × α

b

o

αβ jest rela j¡ dobrego porz¡dku w

.

☛

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

α β

γ

Mno»enie

li zb

p

orz¡dk

o

wy

h

jest

ª¡ zne,

tzn.

dla

wszystki

h

,

i

,

ale

nie

α β

α · β 6= β · α

jest

przemienne,

tzn.

istniej¡

takie

li zb

y

i

,

»e

.

☛ 1

α · 1 = 1 · α

α

jest

elemen

tem

neutraln

ym

mno»enia,

tzn.

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

α

α · β = 0

α = 0

β = 0

dla

k

a»dego

;

je»eli

,

to

lub

;

α < β γ 6= 0

γ · α < γ · β α · γ ≤ β · γ

γ

je»eli

i

,

to

i

dla

k

a»dego

;

α ≤ β

α · γ ≤ β · γ γ · α ≤ γ · β

γ

je»eli

,

to

i

dla

k

a»dego

;

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

α β γ

dla

wszystki

h

,

i

.

8

8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

P

Mno»enie

i

dzielenie

(2)

☛

α 6= 0 β

γ δ < α

β = α·γ+δ

Dla

wszystki

h

li zb

p

orz¡dk

o

wy

h

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 naturalny h jest przemienne; ilo zyn, iloraz i reszta z dzielenia li zb naturalny h to

li zb

y

naturalne.

☛

ω[n]

ω[0] = 1

ω[n+1] = ω[n] · ω

Przyjmijm

y

,

»e

jest

li zb¡

p

orz¡dk

o

w

¡

dan¡

wzorem

rekuren yjn

ym

i

.

n m k l

Je»eli

,

,

i

s¡

li zbami

naturaln

ymi,

to

n < m l > 0

ω[n] · k + ω[m] · l = ω[m] · l

je»eli

i

,

to

;

n = m

ω[n] · k + ω[m] · l = ω[m] · (k + l)

je»eli

,

to

;

n > 0 k > 0

k · ω[n] = ω[n]

je»eli

i

,

to

;

α < ω[n] m > 0 k > 0

(ω[n] · k + α) · ω[m] = ω[n+m]

je»eli

,

i

,

to

.

8

8

Ÿ

.

Li zb

y

p

orz¡dk

o

w

e

Q