Wykład 1
Pojęcia wstępne
Będziemy używać, następujących oznaczeń:
N = {0, 1, 2, 3, . . .}-zbiór liczb naturalnych, N∗ = N \ {0},
Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . .}-zbiór liczb całkowitych,
Q-zbiór liczb wymiernych,
R-zbiór liczb rzeczywistych.
Wyżej wymienione zbiory spełniają następujące relacje:
N⊂Z⊂Q⊂R
Iloczynem kartezjańskim zbiorów X i Y nazywamy zbiór złożony ze
wszystkich par (x, y), takich że x ∈ X, y ∈ Y . Iloczyn kartezjański zbiorów
X i Y oznaczamy przez X × Y . Mamy więc:
X × Y = {(x, y) : x ∈ X, y ∈ Y }
Ogólniej jeśli X1 , X2 , . . . , Xn są dowolnymi zbiorami to iloczynem kartezjańskim X1 × X2 × · · · × Xn nazywamy zbiór:
X1 × X2 × · · · × Xn = {(x1 , x2 , . . . , xn ) : xi ∈ Xi , 1
i
n}
Jeśli X jest zbiorem to przyjmujemy oznaczenie: X n = X × X × · · · × X
n
Uwaga 1 Jeśli X i Y są zbiorami skończonymi i |X| = k, |Y | = l to mamy
|X × Y | = kl oraz |X n | = k n .
Odwzorowanie f zbioru A w zbiór B nazywamy funkcją jeśli każdemu
elementowi zbioru A przyporządkowany jest dokładnie jeden element zbioru
B i piszemy symbolicznie:
f :A→B
lub
f
A→B
Zbiór A nazywamy dziedziną funkcji, a zbiór B zbiorem wartości. Jeśli A i
B są dowolnymi zbiorami to przez B A oznaczamy zbiór wszystkich funkcji
przekształcających zbiór A w zbiór B:
f
B A = {f : A → B}
1
Przykład Niech X = {1, 2}. Wtedy X X jest zbiorem funkcji przekształcających X w X. Zbiór X X składa się z następujących funkcji:
f1 :
1→1
,
2→2
1→2
,
2→1
f2 :
f3 :
1→1
,
2→1
f4 :
1→2
.
2→2
W przypadku gdy X jest zbiorem skończonym, składającym się z elementów x1 , x2 , . . . , xn , to funkcję f ∈ X X możemy zapisać w postaci:
x1
x2
...
xn
f (x1 ) f (x2 ) . . . f (xn )
Dla X = {1, 2} mamy:
X X = f1 =
1 2
1 2
, f2 =
1 2
2 1
, f3 =
1 2
1 1
, f4 =
1 2
2 2
.
Jeśli X jest dowolnym zbiorem to przez 2X oznaczamy rodzinę wszystkich
podzbiorów zbioru X. Mamy więc A ∈ 2X ⇐⇒ A ⊆ X.
Przykład Niech X = {1, 2, 3}. Wtedy mamy
2X = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
Twierdzenie 1 Jeśli X jest zbiorem skończonym i |X| = n to |2X | = 2n .
Dowód Zbiór X jest skończony i ma n elementów, więc X = {x1 , x2 , . . . , xn }.
Każdy podzbiór wiąże się z wyborem pewnych jego elementów, a więc pewnych numerów. Możemy więc określić odwzorowanie:
ξ : 2X → {0, 1}n
podzbiorów zbioru X w zbiór wszystkich n-elementowych ciągów zero-jedynkowych. Jeśli A jest podzbiorem zbioru X to przyporządkowujemy mu ciąg
(a1 , a2 , . . . , an ) taki, że
ai =
1
0
jeśli
jeśli
xi ∈ A
xi ∈ A.
Na przykład:
∅
→ (0, 0, . . . , 0)
X
→ (1, 1, . . . , 1)
{x1 } → (1, 0, . . . , 0)
Nietrudno zauważyć, że każdemu podzbiorowi odpowiada dokładnie jeden
ciąg, różnym podzbiorom odpowiadają różne ciągi i każdy ciąg odpowiada
2
pewnemu podzbiorowi. Zatem elementów zbioru 2X jest dokładnie tyle samo
co elementów zbioru {0, 1}n , a tych ostatnich jest 2n .
Przykład Zilustrujmy działanie funkcji ξ, zdefiniowanej w dowodzie twierdzenia na przykładzie zbioru X = {1, 2, 3}:
∅
{1}
{2}
{3}
ξ:
{1, 2}
{1, 3}
... zobacz całą notatkę
Komentarze użytkowników (0)