I.Aksjomatyka Zermelo- Fraenkela
A.1. (ekstramalności - istnienia) [kiedy zbiory są takie same]
[(x
X
x
Y)
X=Y]Zbiory są równe, gdy są takie same.
A.2. (zbioru pustego) Istnieje zbiór, który nie ma żadnych elementów.
(x
X) Na mocy A.1. istnieje tylko jeden taki zbiór (Ø)
A.3. (aksj. pary) Dla dowolnych zbiorów X,Y istnieje zbiór, którego są one elementami.
(x
Z
x=X
x=Y) czyli istnieje zbiór dwuelementowy. Jeśli zbiory takie same to zapisujemy Z={X,X}={X} singlenton.
A.4. (sumy) Dla dowolnego zbioru X istnieje zb.S złozony z tych i tylko tych elementów, które są elementami któregoś ze zbiorów należących do X.
(y
S
(z
X
y
Z)), gdzie S-suma zbiorów należących do X co zapisujemy
.
Def.1.(doA.5.) A
B
( x
A
x
B), A jest podzbiorem B.
A.5. (zbioru potęgowego) Dla dowolnego zbioru X istnieje zbiór Y złożony z tych i tylko tych elementów, które są podzbiorami zbioru X.
(z
Y
Z
X); zb. Y jest zbiorem potęgowym zbioru X i ozn. P(X) lub
;
(X)=P(X)\ {Ø}.
A.6. (wyróżniania) Dla kazdej formuły teorio-mnogościowej
i dla każdego zbioru X istnieje zb.Y złozony z tych i tylko tych elementów zb-u X, które spełniają
.
( X
Y
(x
X
); {x
X
}-zb.spełniający A.6.
A.7.(a.nieskończoności)Istnieje zb.A tż.: 1) Ø
A; 2)
(x
A
X
{x}
A) [zb.własności 1)i2) nazywamy nazywamy zbiorem induktywnym.
(Ř
A
(x
A
X
{x}
A);
nazywamy następnikiem zb-u X.<Niech F(X)=
, x
A, F: A
A; F(X)=F(Y);
=
X=Y, Ø
,
.
A.8.(a.zastępowania)Dla każdego zbioru X i dla każdej formuły t-mej jednoznacznej Ø istnieje zbiór będący obrazem zbioru X wyznaczonym przez formułę Ø(x,y);
[Ø(x,y)
Ø(x,z)
y=z]
[y
Y
Ø(x,y)].
A.9.(a.regularności)
X
Ø
X
Y= Ø w każdym zbiorze niepustym istnieje element c-minimalny
z
Y; wniosek: 1) nie istnieje x:x
X, 2) dla każdego n
N nie istnieje ciąg
tż
, 3) nie istnieje nieskończony ciąg
:
,
.
A.10.(a.wyboru)Dla każdej rodziny zbioru A niepustej i rozłącznej parami ze sobą istnieje zbiór B który ma dokładnie po jednym elemencie z każdego z tych zbiorów;
{x
Ø
(X
Y=>X
Y= Ø)=>
y
B
X=>y=x}. Aksjomat ten jest równoważny z tw.Curatowskiego-Zorna i ze stwierdzeniem Zermelo (każdy zb.da się uporządkować). Równoważny jest również nastepującemu tw., które również podawane jest zamiast niego: dla każdej rodziny zbiorów niepustych istnieje fcja wyboru, która każdemu zbiorowi przyporządkowuje jego element. (X,
)uporządkowany=>
x,y
X (x
y
y
x=>x=y),
x
X(x
x),
x,y,z
X(x
y
y
z=>x
z);
x,y
X (x
y
y
x-liniowy porządek; (X,
)
(X,
) są izomorficznie podobne
f:X
Y ; x
y=>f(x)
f(y).
Def.2. (para uporządkowana) (x,y)={{x},{x,y}}; x-poprzednik, y-nastepnik. Pary są równe, gdy następnik i poprzednik są takie same. (x,y)=(z,w)x=z
y=w
Def.3. (n-tki uporządkowane) Dla dowolnych elem-ów
{n
2}; (
)=((
),
) gdzie
-ita współrzędna.
Def.4. (iloczyn kartezj.) Iloczynem kartezjańskim zbiorów A i B jest zbiór wszystkich par (x,y) uporządkowanych dla których x
A i y
B. (x,y)={{x},{x,y}}; A
B={(x,y):x
A
y
B}.
Def.5. Iloczynem kartezjańskim n-zbiorów
nazywamy zbiór złożony z tych i tylko tych n-tek uporządkowanych (
), że
.
={(
):
dla i=1,…,n}.
Podzbiory il.kartezjańskich nazywamy relacjami. Relację nazywamy n-elementową jeżeli jest podzbiorem iloczynu kartezjańskiego n-zbiorów.
n=1 to unarna czyli jednoargum., n=2 to binarna czyli dwuargum., ozn. (x,y)
R, xRy.
Def.6. (dziedzina i przeciwdziedzina rel.2argum.) Jeżeli R jest relacją 2argum.,wtedy dziedziną R jest zb.: Dom(R)={x:
(x,y)
R}; Przeciwdziedziną nazywamy zb.:Ran(R)=
={y:
(x,y)
R}. Ran i Dom są zbiorami bo zawarte są w
.
Def.7.(funkcja) 2argum.relację nazywamy funkcją jeżeli
{xRz
xRy
z=y}-jednoznaczność. Funkcje ozn.f,g,h… dziedzina to zb. argumentów, przeciwdziedzina to zb. wartości.
Def.8.(odwzorowanie”w”)Niech f-funkcja. Jeżeli Dom(f)=X a Ran(f)
Y to f nazywamy przekształceniem zbioru X w Y. Zb.wszystkich takich odwzorowań oznaczamy przez:
, jest on zbiorem potęgowym
więc tez jest zbiorem.
Def.9.(odwz.”na”)Jeżeli Ran(f)=Y to mówimy, że f jest odwz. XnaY. f(x)=f(y)
x=y, x,y
X, f(x)-jedyny element taki, że xff(x), f:X
Y.
Def.10.(ocięcie)Obcieciem fcji f do zbioru Z
X jest fcja g tż:
f(x)=g(x) i Dom(g)=Z, g=f
z=(x,y)
f : x
Z}, zapisujemy g
f.
Def.11.(złożenie fcji) Jeżeli f i g są fcjami tż Ran(g)
Dom(f) wtedy złożeniem fcji f i g jest fcja z dziedziną Dom(f
g) tż (f
g)(x)=f(g(x)), x
Dom(g); f
g={(x,y) :
y=f(z)}
Def.12.(obraz zb.A dla f)Niech f:X
Y, A
X, obrazem zbioru A względem fcji f (dla f) nazywamy zb. wartości f dla argumentów
A, ozn. f(A),
={f(x) : x
A}={y :
y=f(x)}.
Def.13.(przeciwobraz zb.B dla f) B
Y to przeciwobr.zbioru B wzgl. f nazywamy zb.argumentów dla których wartości
do B.
={x
X: f(x)
B}.
Def.14.Jeżeli f jest wzajemnie jednoznaczna wtedy
f(y)=x; f
={(x,y)
Y
X(y,x)
f}.
Def.15. X
Y={x
X: x
Y}; X\Y={x
X: x
Y};
={t
:
(t
Y)}
Def.16.Zbiorem skończonym nazywamy taki zb.ktory ma n elementów, gdzie n jest pewną liczbą N i zb.A jest skopńczony jeżeli dla pewnej liczby naturalnej n element zbioru A można ponumerować liczbami od 0 do n. A={
},
.
Def.17.Zbior nazywamy nieskończonym jeżeli nie jest skończony w sposób równoważny. Można zdefiniować jako zbiór równoliczny ze pewnym swoim podzbiorem.
Def.18.Zbiory X,Y nazywamy rownolicznymi (X~Y)jeśli istnieje fcja f wzajemnie jednoznaczna odwzorowująca XnaY. O takich zbiorach mówimy, że mają równe moce
lub |X|=|Y|. Uwaga1. |X|
|Y| wtedy X~Z, Z
Y dla pewnego z; X|<|Y| wtedy X|
|Y| dla X
Y.
Def.19.Niech Ø(x,y) będzie funkcją t-m. Niech X będzie zbiorem Y={y:
(x
A
Ø(x,y))}nazywamy obrazem zbioru X wyznaczonym przez fcję Ø(x,y). Zb,X formuła Ø gwarantują istnienie zb. Ø(x,y).
Formułę t-mę nazywamy jednoznaczną wtw:
[Ø(x,y)
Ø(x,z)
y=z].
Def.20.Zbiór uporządkowany (X,
) nazywamy dobrze uporządkowanym jeśli każdy jego element niepusty ma element najmniejszy. Wnioski: Zbiór dobrze uporządkowany jest uporządkowany liniowo. Uwaga: Podobieństwo zachowuje: 1)dobre uporządkowanie, 2)elementy wyróżnione, 3)odcinek końcowy przechodzi na odcinek początkowy. [Y-nazywamy odcinkiem początkowym zbioru (X,
) wtw,gdy Y
X
(y
x=>y
Y). Uwaga: Dla dowolnego zbioru liniowo-uporządkowanego zbiór pusty i zb.X są odcinkami początkowymi X. Jeśli X jest dobrze uporz.to każdy odcinek początkowy właściwy(różny od X) jest postaci Y=O(x)={y
X: y<x}; y<xy
x
x
y [taki odcinek nazywamy odcinkiem początkowym wyznaczonym przez X].
Def.21.Mówimy, że w zbiorze l-u prawdziwa jest zasada indukcji pozaskończonej jeśli istnieje element najmniejszy
oraz dowolny podzbiór A
X spełniający warunki
A,
a
A z tego,że wszystkie elementy x
X tż x<a należą do A wynika, że a
A jest równy całemu zb.X. Twierdzenie mówi, że dla każdego zb.dobrze uporządkowanego X prawdziwa jest zasada indukcji.
Def.22.Jeżeli A-dobrze uporz., B
A i zb.B spełnia dla każdego x
A warunek (3) (O(x)
B=>x
B) to B=A. Mówimy, że f:A
A, gdzie (A,
)jest dobrze uporz., jest rosnąca to x
f(x) [wartość nie jest wcześniejsza niż argument].
Tw.1.Jeżeli zbiory A,B-dobrze uporz.to są albo podobne albo też jeden z nich jest podobny do odcinka początkowego drugiego. Wniosek: Dwa dobre porządki są ze sobą porównywalne.
Żaden zb.dobrze uporz.nie jest izomorficzny ze swoim właściwym odcinkiem początkowym.
Żadne 2 odcinki początkowe nie są ze sobą izomorficzne.
Tw.2.Jeżeli <A,e> i <B,s> są izomorficznymi dobrymi porządkami to izomorfizm między nimi jest jednoznaczny. Jedynym automorfizmem zbiorów dobrze uporz.jest identyczność.
Tw.3.Dla dowolnych pozłącznych dobrych porządków (A,
), (B,
) (A
B= Ø) nastepujące zbiory są dobrymi porządkami: 1) (A,
)
(B,
)=(A
B
) Na zbiorach A i B porządki są takie jak w zbiorach wyjściowych a każdy element zbioru A jest wcześniejszy jak każdy element zbioru B. 2) (A,
)
(B,
)=(A
B,
),
(
) [porządek antyleksykonograficzny).
Liczby porządkowe
Def.23.Zb.X nazywamy tranzytowym lub przechodnim jeśli prawdziwe jest zdanie: 1)
[x
X(
(y
x
X=>y
X)) ,Każdy element tego zbioru jest jego podzbiorem tran (X)-X jest tranzytywny. UWAGA: 1) Ø jest tranzytywny
Ø (x
Ø); 2) X jest tranzytywny to s(x)=X
{x} jest tranzytywny.
Tw.5.
(Ord(
)
x,y
(x
yx
y
x=y)). Wniosek:Relacje
i
pokrywają się na liczbach porządkowych. Tak jak < i
.
Tw.6.Jeżeli x będzie odcinkiem początkowym liczby porządkowej
wtedy x=
lub x=
, gdzie
jest najmniejszym elementem zbioru
-x.
Tw.7.Dowolne 2 liczby porządkowe są porównywalne. Tzn.że dla dowolnego
i
-porządkowych to
=
):
(Ord(
)
Ord(
)=>
=
). Wniosek:1)Jeżeli
jest liczba porządkową to
={
:
}={
:
<
; 2)Dowolny zbiór przechodni, którego elementami są liczby porządkowe jest liczbą porządkową; 3)
dla dowolnych liczb porządkowych
,
; 4)
jest odcinkiem początkowym w
[
to
=
, gdzie O-alfa(
)={
:
<
}=
.
Tw.8.Jeżeli
jest liczbą porządkową to S(
) jest najmniejszą liczbą porządkową większą od niej.
Def.25.Nastepnikiem l.porządkowej
nazywamy liczbę S(
). Oznaczamy ją również przez
+1. Liczbę porządkową
nazywamy następnikiem porządkowym lub następnikiem jeżeli jest nastepnikiem pewnej liczby
. Wniosek:Następnikami są wszystkie liczby N\{0}. Liczba omega
nie jest nastepnikiem żadnej liczby bo: n<
n+1<
[
składa się z Ø, nastepnik zbioru Ø, następnik nastepnika Ø] n<
<
,
. Niech Ø, S(Ø) S(S(Ø)) -ciąg następników zbioru pustego. Jest to przykład liczby granicznej.
Def.26.Liczbę
nazywamy l.graniczną jeżeli nie jest liczbą 0 i nie jest następnikiem żadnej liczby porządkowej.
Tw.9.Jeżeli 2 liczby są ze sobą izomorficzne to są równe. 1)Jeżeli x,y są l.porządkowymi i x
y(izomorf.)to x=y. 2)Jeżeli x,y,z są l.porzadkowymi i x
y
y
z
x
z. 3)Jeżeli C jest niepustym zbiorem liczb porządkowych to:
( x
y
x=y), a nawias to to samo co x
y, istnieje elem.najmniejszy. Tw.to sugeruje, że zb.wszystkich liczb porządkowych gdyby istniał to byłby liczbą porządkową.
Tw.10.(Anynomia Burali-Forti) Nie istnieje zbiór wszystkich liczb porządkowych tzn.:
(Ord(x)x
z).
Tw.11.Jesli X jest zbiorem liczb porządkowych to: 1)
=sup(X)=
jest najmniejszą liczbą porządkową, która jest wieksza lub równa od każdego elementu tego zbiory. Ponadto S(
) jest większa od kazdego elem. z X. 2)Jeżeli X
Ø, to
=min(X)=
jest najmniejszą l.porządkową z X. wniosek: ad1)jeżeli weźmiemy porządkowy to istnieje liczba początkowa większa od każdego elementu tego zbioru.
Tw.12.Jeżeli (A,R) będzie dobrym porządkiem wyedy istnieje dokładnie jedna liczba porządkowa
tże (A,R)
,(
,
).
Tw.13.Niech X
. Wtedy istnieje dokładnie jedna liczba porządkowa
tże (X,
)
(
,
). Wniosek:Jeżeli dwa zbiory A,B są dobrze uporządkowane w tym
i
odpowiednio A jest podobny do podzbioru
zbioru
, to
.
Tw.14.(o indukcji pozaskończonej)Niech
(x) będzie dowolną f-cją, wtedy:
(
[
(
)
(
)
[
]]).
Tw.15.(o rekursji pozaskończonej)Załóżmy, że
jest formułą taką że
(x,y). Wtedy:
(f jest f-cją i Dom(f)=
(
(f
,f(
)))). Wniosek:Rekursja pozaskończona pozwala na tworzenie fcji dowolnych długości porządkowych jeżeli znamy przepis na f(
) ma podstawie wartości f(
)
<
.
Def.27.Ciągiem pozaskończonym typu
nazywamy funkcję
, której zbiorem argumentów jest
. Wartości funkcji nazywamy wyrazami ciągu. Jeżeli wyrazy te są wyrazami porządkowymi i
.Niech
-ciąg pozaskończony typu
, gdzie
-liczba porządkowa graniczna, to istnieje taka liczba
=sup{
(
):
<
}=supA.
Tw.16.(I prawo monotoniczności dla dodawania liczb porządkowych)1)
<
, 2)0<
Suma dwóch licz porządkowych różnych od zera jest zawsze większa od pierwszego składania.
Tw.17.(II prawomonotoniczności dla dodawania liczb porządkowych) 3)
, 4)
, Suma dwóch liczb porządkowych jest zawsze większa lub równa od drugiego składnika.