wyk%C5%82ad%207, studia, 1 semestr, LOGIKA, wykłady z logiki
[ Pobierz całość w formacie PDF ]
Wstep do logiki i teorii mnogosci, wyklad 7
Marek Balcerzak
1
Funkcje postaci f : N ! Y nazywamy ciagiem. Jesli a
n
= f(n), n 2 N,
to ciag zapisujemy jako (a
n
)
n2N
.
Denicja rekurencyjna (indukcyjna lub denicja przez rekursje) ciagu
polega na:
okresleniu poczatkowego wyrazu ciagu lub kilku poczatkowych wyrazow
ciagu (a
n
)
n2N
zakladajac, ze znane sa wartosci a
1
;:::;a
n
okreslamy wartosc a
n+1
(dla dowolnego n 2N).
Przyklad 1 (denicji rekurencyjnych).
(1) funkcja silnia
0! = 1
(n + 1)! = n!(n + 1); n 2N[f0g
(2) a
1
=
p
2; a
n+1
=
p
2 + a
n
; n 2N
(3) dany jest ciag zbiorow (A
n
). Okreslamy ciag sum skonczonych (S
n
):
S
1
= A
1
; S
n+1
= S
n
[A
n+1
n 2N.
Wowczas S
n
=
S
n
i=1
A
i
(sprawdzic, cwiczenie).
(4) Ciag Fibonacciego
a
0
= 0, a
1
= 1, a
n+2
= a
n+1
+ a
n
, n 2N[f0g.
Twierdzenie 1. Ogolny wyraz ciagu Fibonacciego wyraza sie wzorem
"
1 +
p
5
2
!
n
1
p
5
2
!
n
#
p
5
a
n
=
; n 2N[f0g:
2
Przyklad 2 (Pewne szczegolne funkcje).
(1) Funkcja identycznosciowa na zbiorze X
id : X ! X, id(x) = x.
(2) Funkcja charakterystyczna zbioru A X
A
: X !f0; 1g
A
(x) =
1 jesli x 2 A
0 jesli x 2 A
(3) Funkcja dwoch zmiennych ma postac f : X Y ! Z;
w szczegolnosci funkcjami dwoch zmiennych sa:
{ funkcje rzutowania pr
X
: X Y ! X, pr
X
(x;y) = x
oraz pr
Y
: X Y ! Y , pr
Y
(x;y) = y
{ dzialania dodawania + : RR!R; +(x;y) = x + y
oraz mnozenia : RR!R; (x;y) = xy
(4) Funkcje postaci f : A ! BC;
wtedy dla kazdego a 2 A istnieja f
1
(a) 2 B oraz f
2
(a) 2 C takie ze
f(a) = (f
1
(a);f
2
(a)).
W ten sposob deniujemy funkcje f
1
: A ! B oraz f
2
: A ! C,
nazywaja sie one funkcjami skladowymi funkcji f;
zapisujemy f = (f
1
;f
2
).
3
Rodzaje funkcji
Denicja 1. Niech f : X ! Y .
(a) Funkcja f nazywa sie roznowartosciowa (jest iniekcja), gdy
(8x
1
;x
2
2 X)(x
1
6= x
2
) f(x
1
) 6= f(x
2
)):
(b) Funkcja f nazywa sie funkcja na (jest suriekcja), gdy rng(f) = Y , tzn.
gdy
(8y 2 Y )(9x 2 X)y = f(x):
(c) Funkcja f nazywa sie wzajemnie jednoznaczna (jest bijekcja), gdy jest
jednoczesnie iniekcja i suriekcja.
Uwaga 1. Warunek denicyjny iniekcji mozna zapisac w formie rownowaznej
(8x
1
;x
2
2 X)(f(x
1
) = f(x
2
) ) x
1
= x
2
):
Przyklad 3. Funkcja kwadratowa f : R!R dana wzorem f(x) = x
2
nie jest ani iniekcja ani suriekcja.
Funkcja wykladnicza f : R ! R dana wzorem f(x) = 2
x
jest iniekcja
(jest rosnaca) i nie jest suriekcja.
Przykladem bijekcji f : R!R jest funkcja f(x) = ax + b, gdy a 6= 0.
Bijekcja zbioru f1; 2;:::;ng na siebie nazywa sie permutacja, np. f(x) =
5 x jest permutaca zbioru f1; 2; 3; 4g.
Dodawanie + : ZZ!Z w zbiorze liczb calkowitych Z jest suriekcja
i nie jest iniekcja.
Denicja 2. Niech f : X ! Y .
(a) Niech Z X. Obcieciem funkcji f do zbioru Z nazywamy funkcje
(fjZ) : Z ! Y dana wzorem (fjZ)(x) = f(x), x 2 Z.
(b) Przedluzeniem (rozszerzeniem) funkcji f do zbioru W X nazywamy
dowolna funkcje g: W ! Y taka, ze gjX = f.
Denicja 3. Niech f i g beda funkcjami. Zlozeniem (superpozycja) tych
funkcji nazywamy funkcje gf, ktorej dziedzina jest zbior
dom(gf) = fx 2 dom(f) : f(x) 2 dom(g)g
i ktora dana jest wzorem
(gf)(x) = g(f(x)) dla x 2 dom(gf):
4
Uwaga 2. Jesli f : X ! Y , g: Y ! Z, to dom(g f) = X. Zatem g
f : X ! Z.
Uwaga 3. Operacja superpozycji nie jest przemienna.
Twierdzenie 2. Niech f : X ! Y oraz g: Y ! Z.
(a) Jesli f i g sa iniekcjami, to gf jest iniekcja.
(b) Jesli f i g sa suriekcjami, to gf jest suriekcja.
(c) Jesli f i g sa bijekcjami, to gf jest bijekcja.
Twierdzenie 3 (lacznosc superpozycji). Niech f : X ! Y , g: Y ! Z,
h: Z ! W. Wowczas
h (gf) = (hg) f:
Uwaga 4. Jesli f : X ! Y jest bijekcja, to
(8y 2 Y )(9!x 2 X)y = f(x):
Denicja 4. Niech f : X ! Y bedzie bijekcja. Funkcja odwrotna do f
nazywamy funkcje g: Y ! X taka, ze
(8x 2 X)(8y 2 Y )(g(y) = x , y = f(x)):
Oznaczamy g = f
1
.
5
[ Pobierz całość w formacie PDF ]