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