M6.pdf

Funkcje i elementy teorii mocy

Wstęp 2

1. Funkcje 3

2. Własności funkcji 6

3. Obrazy zbiorów wyznaczane przez funkcje i ich własności 11

4. Przeciwobrazy zbiorów wyznaczone przez funkcje i ich własności 14

5. Elementy teorii mocy. Zbiory przeliczalne i nieprzeliczalne oraz ich własności 16

Bibliograﬁa

Wstęp

Funkcje są podstawowymi narzędziami stosowanymi między innymi w informatyce

do opisu (modelowania, charakteryzowania, specyﬁkacji)własności szeroko pojętych

systemów informacyjnych, a przez to również systemów oprogramowania.

Pokażemy, że znane ze szkoły pojęcie funkcji — deﬁniowane tam jako pewnego

rodzaju przyporządkowanie — można precyzyjnie zdeﬁniować za pomocą

odpowiednich relacji. Zostaną przedstawione i omówione podstawowe własności

funkcji. Zdeﬁniujemy także i udowodnimy własności obrazów i przeciwobrazów

zbiorów wyznaczonych przez funkcje.

Istotną częścią tego modułu jest przedstawienie i omówienie podstawowych pojęć

związanych z teorią mocy. Udowodnimy między innymi, że liczb naturalnych jest

„tyle samo”, co liczb wymiernych. Zwieńczeniem modułu jest udowodnienie, że

liczb rzeczywistych nie jest „tyle samo”, co liczb naturalnych oraz faktu, że istnieje

nieskończenie wiele rodzajów nieskończoności.

1. Funkcje

Przypomnĳmy szkolną deﬁnicję funkcji. Funkcją odwzorowującą zbiór X w zbiór

Y nazywamy takie przyporządkowanie, które każdemu elementowi ze zbioru X

przyporządkowuje dokładnie jeden element ze zbioru Y .

Przykład 1

Bez trudu można zauważyć, że przyporządkowanie na rysunku 1a jest funkcją

(ponieważ spełnia podaną wyżej deﬁnicję), zaś przyporządkowanie dane na rysunku

1b nie jest funkcją. W zbiorze X istnieją bowiem takie elementy, którym nie są

przyporządkowane żadne elementy zbioru Y oraz są w zbiorze X takie elementy,

którym przyporządkowano więcej niż jeden element ze zbioru Y .

Rysunek 1

Jeżeli funkcja f odwzorowuje zbiór X w zbiór Y , to zbiór X nazywamy zwyczajowo

dziedziną funkcji f , zaś zbiór Y przeciwdziedziną . Zbiór tych elementów przeciwdziedziny,

które są wartościami funkcji dla pewnych argumentów, nazywamy zbiorem wartości

funkcji. Zbiór wartości funkcji f : X → Y oznaczać będziemy przez f ( X ). Zwyczajowo

również elementy dziedziny funkcji (zbioru X ) nazywamy argumentami funkcji , zaś

przyporządkowane tym argumentom elementy zbioru Y nazywamy wartościami

funkcji (jeżeli x jest argumentem, to zapis f ( x ) zwyczajowo oznacza wartość funkcji f

dla argumentu x ).

Zauważmy, że funkcję możemy charakteryzować za pomocą odpowiedniego zbioru

par uporządkowanych typu ( x , f ( x )), będących elementami iloczynu kartezjańskiego

X × Y . Funkcje zatem możemy deﬁniować jako podzbiory iloczynów kartezjańskich,

a przez to jako relacje.

Relację f ⊆ X × Y nazywamy funkcją odwzorowującą zbiór X w zbiór Y , jeżeli spełnia

ona dwa następujące warunki:

(a) ∀ x ∈ X ∀ y , z ∈ Y [( x , y ) ∈ f ∧ ( x , z ) ∈ f ⇒ y = z ] ,

(b) ∀ x ∈ X ∃ y ∈ Y ( x , y ) ∈ f .

Przy czym — jeżeli relacja f spełnia tylko warunek (a) — to nazywamy ją funkcją

częściową (warunek ten nazywany jest warunkiem prawostronnej jednoznaczności ).

Jeżeli spełnione są oba warunki, to funkcję f nazywamy czasem także funkcją totalną .

Oczywiście widać, że podana wyżej deﬁnicja funkcji jako relacji pewnego typu

odpowiada deﬁnicjiszkolnej.Warunek(b)stwierdzabowiem,że każdemu elementowi

ze zbioru X ma być przyporządkowany element ze zbioru Y . Warunek (a) determinuje,

że przyporządkowanie możliwe jest tylko na jeden sposób.

Zauważmy, że zgodnie z powyższą deﬁnicją zbiór wartości funkcji jest podzbiorem

przeciwdziedziny. Zauważmy również, że zbiór wartości nie musi być całą

przeciwdziedziną. Intuicję zbioru wartości funkcji przedstawia rysunek 2.

Rysunek 2

Przykład 2

Rozważmy relację f ⊆ R × R , daną zależnością ∀ x , y ∈ R [( x , y ) ∈ f ⇔ x 2 + y = 4].

Pokażemy, że relacja ta jest funkcją.

Weźmy dowolne liczby rzeczywiste x , y , z , spełniające warunek:

( x , y ) ∈ f ∧ ( x , z ) ∈ f.

Korzystając z deﬁnicji relacji f , mamy:

x 2 + y = 4 ∧ x 2 + z = 4,

czyli:

x 2 = 4 – y ∧ x 2 = 4 – z,

stąd:

y = z.

Spełniony jest zatem warunek prawostronnej jednoznaczności. Prawdziwy jest

również drugi z warunków funkcyjnych, mamy bowiem:

∀ x∈R ∃ y∈R ( x , y ) ∈ f ⇔ ∀ x∈R ∃ y∈R ( y = 4 – x 2 ).

Sprawdzenie tego warunku sprowadza się do próby wyznaczenia wartości y

z warunku deﬁniującego relację f i sprawdzenia, czy tak wyznaczona wartość y

należy do przeciwdziedziny.

Przykład 3

Rozważmy relację f ⊆ R × R , daną zależnością ∀ x,y∈R [( x , y ) ∈ f ⇔ x 2 + y 2 = 5 ].

Zauważmy, że relacja ta nie jest funkcją częściową. Mamy bowiem: (1, 2) ∈ f oraz

(1, –2) ∈ f . Istnieją zatem dwie różne liczby przyporządkowane liczbie 1.

Jeżeli relacja jest funkcją (spełnia oba warunki funkcyjne), to możemy zmienić formę

zapisu i stosować poniższą notację:

(a) zamiast f ⊆ X × Y , piszemy f : X → Y — czytamy: funkcja f odwzorowuje zbiór

X w zbiór Y,

(b) zamiast (x , y ) ∈ f piszemy f ( x ) = y — czytamy: element y jest wartością funkcji f

dla argumentu x.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: