24422

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:

/i:

1 — 2 —

2

2 '

W przypadku gdy X jest zbiorem skończonym, składającym się z elementów X\,X2, ...,x„, to funkcję / G X^A możemy zapisać w postaci:

/ xi x₂ ... i„ \

W(*i) /(**) ••• fMj

Dla X = {1.2} mamy:

Jeśli A' jest dowolnym zbiorem to przez 2^X oznaczamy rodzinę wszystkich podzbiorów zbioru X. Mamy więc A G 2^A <=► AC X.

Przykład Niech A' = {1.2.3}. Wtedy mamy

2^X = {0, {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 \2^X\ — 2ⁿ.

Dowód Zbiór X jest skończony i ma n elementów, więc X = {jtj . x₂...., x_n }. 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:

i \2^X — {0.1}ⁿ

podzbiorów zbioru X w zbiór wszystkich u-elementowych ciągów zero-jedyn-kowycli. Jeśli A jest podzbiorem zbioru X to przyporządkowujemy mu ciąg (ai, a₂,..., a_n) taki, że

/	1 jeśli	ii G A
a, = <	0 jeśli	Xi*A
0	— (0,0,	....0)
X	- (1.1.	...,1)
{*ił	- (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

Na przykład:

2