Podstawy matematyki dla informatyków
Janusz J. Szuster
Zadania
z logiki i teorii mnogości
Lublin 2006
1. WST
P 2
1. Wstęp
W literaturze przedmiotu  Logika i teoria mnogości istnieje kilka zbiorów zadań wyda-
nych w języku polskim, które są powszechnie znane i cytowane w proponowanej czytelnikowi
literaturze. Jedne z nich zostały wydane już dość dawno, inne w ostatnich latach, ale jak to
zwykle bywa każdy z nich adresowany był do nieco innego odbiorcy. Wraz z upływem lat
zmieniły się programy nauczania, ale zmieniła się także pewnego rodzaju maniera w jakiej
redagowane były zadania. Sformułowanie nazwy przedmiotu jako  Logika i teoria mnogości
jest dość ogólne i nie uwzględnia specyfiki uczelni jak też poziomu wykształcenia. Ponieważ
w zasadzie każdy wykład jest inny, to jest koniecznością dobranie do tego konkretnego wy-
kładu zadań ilustrujących teorię i rozwijających jej rozumienie. W proponowanym zestawie
zadań zawarte zostały zadania, które w mojej intencji mają największy związek z zakresem
i poziomem wykładanego przedmiotu. W kolekcji znalazły się zadania, które wielokrotnie
zostały wykorzystane na ćwiczeniach audytoryjnych, ale także zadania zawarte w zestawach
kolokwialnych czy egzaminacyjnych. Każde z nich ma więc własną historię, swoje  ofiary i
zwycięzców. Ideą przewodnią tworzenia takiej kolekcji zadań, żeby nie powiedzeć zbyt mocno
zbioru zadań, była chęć ułatwienia studentom wyboru egzamplarzy treningowych, dostoso-
wanych do tematyki wykładu i poziomu odbiorców. Kolekcja ta jest ciągle otwarta i każda
nowa edycja wykładu, a wraz z nią nowa seria sprawdzianów, kolokwiów i egzaminów do-
starczać będzie kolejnych zadań. Pragnę podkreślić, że część z proponowanych zadań została
zaczerpnięta z cytowanych przez mnie zbiorów, częśc jest modyfikacją oryginałów, a pokaz
-
na część, to zadania mojego autorstwa. Jest dla mnie honorem móc podziękować Autorom
cytowanych zbiorów, z których czerpałem i których zadania stanowiły dla mnie standard
tak poziomu redakcyjnego jak i merytorycznego. Pozostaje mi mieć jedynie nadzieję, że
zestawienie ich z zadaniami mojego autorstwa nie będzie dla Nich powodem zakłopotania.
Na zakończenie chcę życzyć tym, którzy będą korzystać zaprezentowanych tu zadań, by
rozwiązując je przybliżyli się do wiedzy jaką zaplanowano na kursowy wykład. Będę także
zobowiązany za wskazanie usterek wszelkiej natury, co do istnienia których chwilowo nic nie
wiem, ale nie wierzę również w to, by nie istniały.
Janusz J. Szuster
2. WPROWADZENIE DO TEORII MNOGOÅšCI 3
2. Wprowadzenie do teorii mnogości
2.1. Narzędzia zapisu
Zadanie 1. KorzystajÄ…c z metody tablic Schrödera lub metody nie wprost sprawdzić czy
następujące formuły zdaniowe są twierdzeniami rachunku zdań:
(a) [p Ò! (q Ò! r)] Ô! [q Ò! (p Ò! r)]
(b) {(Ä… Ò! ²) '" [(<" Ä…) Ò! (<" ²)]} Ð!Ò!(Ä… Ô! ²)
(c) [(p Ò! q) (" (p Ò! r) (" (p Ò! s)] Ò! [p Ò! (q (" r (" s)] .
(d) (p '" q Ò! r) Ò! [p Ò! (q Ò! r)].
(e) [(p Ò! q) (" (r Ò! q)] Ò! [(p '" r) Ò! q].
(f) {[(p '" q) Ò! r] '" [p (" (q Ò!<" r)]}
Zadanie 2. Którego spoÅ›ród znaków Ô!, Ò!, Ð! należy użyć w miejscu kropek, aby nastÄ™-
pujący napis stał się tautologią rachunku zdań. Udowodnić słuszność wyboru.
(a) (p (" q) Ò! r . . . (p Ò! r) '" (q Ò! r)
(b) p Ò! (q '" r) . . . (p Ò! q) '" (p Ò! r)
(c) (p '" q) Ò! r . . . (p Ò! r) '" (q Ò! r)
(d) (p Ò! q) '" (q Ò! r) . . . (p Ò! r)
Zadanie 3. Posługując się symboliką logiczną zapisać następujące zdanie w postaci formuły
rachunku zdań, a następnie sprawdzić czy jest ono twierdzeniem tego rachunku:
(a)  Jeśli Chuck Norris nie jest szaleńcem to, jeśli Chuck Norris jest szaleńcem, to Chuck
urodził się w Ostrowie Lubelskim
(b)  Hans Kloss jest patriotą wtedy i tylko wtedy, gdy nie jest prawdą, że nie jest prawdą,
że Hans Kloss nie jest patriotą.
(c)  Jeśli James Bond nie jest agentem Jej Królewskiej Mości, to gdy James Bond jest
agentem Jej Królewskiej Mości, to jest studentem Informatyki.
Zadanie 4. Sprawdzić, czy następujące zdania są prawdziwe:
(a) (A *" C) \ B =(A \ B) *" (C \ B),
(b) (A \ C) *" B =(A )" C) \ (B *" C),
(c) A \ (B *" C) =(A \ B) )" (A \ C),
(d) A \ (B *" C) =(A \ B) \ C,
2. WPROWADZENIE DO TEORII MNOGOÅšCI 4
(e)  JeÅ›li A ‚" C i B ‚" C, to A *" B ‚" C.
(f)  JeÅ›li C ‚" A i C ‚" B, to C ‚" A )" B.
(g)  JeÅ›li A ‚" C i B ‚" D, to A *" B ‚" C *" D ,
(h)  JeÅ›li A ‚" C i B ‚" D, to A )" B ‚" C )" D ,
(i) (A ‚" B) '" (C ‚" D) =Ò! (A )" C ‚" B )" D),
(j) (j) (A ‚" B) '" (C ‚" D) =Ò! [(A \ D) ‚" (B \ C)],
(k) (k) A \ (B )" C) =(A *" C) )" (A \ B).
Zadanie 5. Wiedząc, że przez różnicę symetryczną zbiorów A i B rozumiemy zbiór A B
określony równością: A B =(A \ B) *" (B \ A) udowodnić, że dla dowolnych zbiorów A i B
zachodzi równość:
(i) (A *" B) \ (A )" B) =A B,
(ii) A *" (B C) =(A *" B) (A *" C),
(iii) (A *" B) (A )" B) =A B.
(iv) (A *" B) \ (A )" B) =A B
Zadanie 6. Wyznaczyć zbiory: A *" B, A \ B oraz A )" B, gdy:

"
5 1
5
(i) A = x " : log5 (x2 - 2) < log5 3|x| -1 , B = x " : log5 x - log"5 x>1 .
2 2 3
(ii) A = {x " : |x - 1| 3 (" x<1}, B = {x " : x2 - 7x +6< 0}.
Zadanie 7. Dla rodziny zbiorów X = {{Ä…, ²}, {x, y, z}} zbudować zbiory:
P(X ) oraz X × P(X ).
Zadanie 8. Dla zbiorów S = {a, b} oraz T = {Õ, È} utworzyć zbiór:
T × (P(S*"T ) \{S, T , "}.
Zadanie 9. Pamiętając, że istnieje możliwość zastąpienia implikacji alternatywą, podać
związek między zbiorami A i B (a tam gdzie to konieczne również C) odpowiadający nastę-
pujÄ…cej formule:
(a) (p (" q)'"<"p Ò! q,
(b) [(p Ò! q) '" p] Ò! q,
(c) (p Ò! q) Ò! [(r'"<"q) Ò! (r'"<"p)],
(d) {(p Ò! q) '" [(<" p) Ò! (<" q)]} Ô!(p Ô! q).
2. WPROWADZENIE DO TEORII MNOGOÅšCI 5
Zadanie 10. Podać przykład zbioru A gdy wiadomo, że B = {x " : x " (-2, 3)} oraz
A )" B = {x " : x " (-", -4) )" (-4, -2 > *" (4, ")}.
Zadanie 11. Podać przykład zbioru B gdy wiadomo, że A = {x " : x " (-4, -1) *"
0, 2)} oraz A )" B = {x " : x " (-", -3) )" (-3, -2 *"(-1, 0) *" (1, ")}.
Zadanie 12. Dla danego zbioru A zdefiniować pojęcie zbioru potęgowego P(A) (lub przy
innym oznaczeniu) 2A. Wyznaczyć zbiór P({a, b, c, d}).
Zadanie 13. Ile elementów ma zbiór P(n), gdzie n jest liczbą naturalną?
Zadanie 14. Wykazać, że jeśli dla dowolnych zbiorów A ą" B, to P(A) ą"P(B).
Zadanie 15. Czy dla dowolnych zbiorów A i B zachodzi równość: P(A)"B) =P(A))"P(B)?
Zadanie 16. Wykazać, że dla dowolnej rodziny zbiorów A zachodzi warunek:

AÄ…"P(A) Ð!Ò! AÄ…"A.
Zadanie 17. Dana jest rodzina zbiorów A. Która z implikacji wchodząca w skład następu-

jÄ…cej równoważnoÅ›ci jest prawdziwa: P(A) Ä…"AÐ!Ò!AÄ…" A ?

Zadanie 18. Wykazać, że dla każdego zbioru A prawdziwa jest równość P(A) =A.
2.2. Indukcja matematyczna
Zadanie 1. Wykazać, że jeśli Mą" jest zbiorem tych liczb naturalnych, że spełniają one
następujące zależności, to M jest zbiorem induktywnym.
n(n +1)
(a) 0+1+2+3+. . . + n = ;
2
n(n + 1)(2n +1)
(b) 02 +12 +22 +32 + . . . n2 = ;
6
n(n +1)(n +2)
(c) 0 · 1+1· 2+2· 3+. . . + n · (n - 1) = ;
3
12 22 (n +1)2 (n +1)(n +2)
(d) + + . . . + = ;
1 · 3 3 · 5 (2n + 1)(2n +3) 2(2n +3)
n

1 n
(e) = ;
(2i + 1)(2i +3) 2n +1
i=0
n

1 n
(f) = ;
(a + i)(a + i +1) a(a + n)
i=0

1
n
sin (n + )Ä…
1
2

(g) cos iÄ… = + ;
1
2
2sin Ä…
i=0
2
2. WPROWADZENIE DO TEORII MNOGOÅšCI 6
Zadanie 2. Wykazać, że jeśli Mą" jest zbiorem tych liczb naturalnych, że spełniają one
następujące zależności, to M jest zbiorem induktywnym.
(a) 133|(11n+2 +122n+1);
(b) 12|(10n+2 - 4);
(c) 3|(10n +4n - 2);
(d) 9|(4n+1 +15n + 14);

(e) 23 (52n+1 +2n+4 +2n+1);



(f) 37 (2n+5 · 34n +53n+1);
(g) cos x| sin 2nx;


(h) cos x cos (2n +1)x;


(i) 25 (2n+3 · 3n+1 +5n +1);

(j) (x - a)2 - an - nan-1(x - a)];
[xn

(k) (x - a)2
[nxn+1 - (n +1)axn + an+1;

(l) (x - a)3
[n2xn+2 - (2n2 +2n - 1)axn+1 +(n +1)2a2xn - an+1(x + a)];

(m) (x2 + x +1) +1)2n+1 + xn+2].
[(x

(n) 48 +20m), gdzie m jest liczbÄ… naturalnÄ… parzystÄ….
(m3
Zadanie 3. Wykazać, że jeśli Mą" jest zbiorem tych liczb naturalnych, że spełniają one
następujące zależności, to M jest zbiorem induktywnym.
(a) 2n >n;
(b) 3n+2 > (n +2)2 +4;
1 1 1
(c) + + . . . + 1;
n +1 n +2 3n +1
"
1 1 1
(d) 1 + + + . . . + < n +1;
2 3 n +1
"
1 1 1
" " "
(e) + + . . . + > n +1;
1 2 n +1
1 1 1
(f) 1 + + 2 - ;
22 (n +1)2 n +1
(g) (1 + a)n 1+na, (a >-1, n 0);
3. PRODUKT KARTEZJAC
SKI ZBIORÓW I RELACJE 7
n(n - 1)
(h) (1 + a)n 1+na + a2, (a 0, n 0);
2
n(n - 1) n(n - 1)(n - 2)
(i) (1 + a)n 1+na + a2 + a2, dla a >0, n 0.
2 6
3. Produkt kartezjański zbiorów i relacje
3.1. Podstawowe własności relacji
Zadanie 1. Zbadać prawdziwość równości:
(a) A × (B *" C) =(A × B) *" (A × C),
(b) A × (B )" C) =(A × B) )" (A × C),
(c) (A × B) *" (B × C) =A × C,
(d) A )" (B × C) =(A × B) )" (A × C),
(e) A × (B \ C) =(A × B) \ (A × C),
(f) (A \ B) × C =(A × C) \ (B × C).
2
Zadanie 2. Na płaszczyz
nie znalez
ć wykresy następujących relacji określonych w zbio-
rze :
(a) x y Ð!Ò! x2 + y2 < 1,
(b) x y Ð!Ò! x = y ("-x = y,
(c) x y Ð!Ò! x + y 1,
(d) x y Ð!Ò! |x| Która z tych relacji jest: a) zwrotna, b) spójna, c) symetryczna, d) przechodnia, e) an-
tysymetryczna?
Zadanie 3. Które z wymienionych w poprzednim zadaniu własności mają relacje określone
następująco:
(a) x y Ð!Ò! 7|x + y,
(b) x y Ð!Ò! x2 = y2,
(c) x y Ð!Ò! |x| < |y|,
(d) x y Ð!Ò! x + y2 =1.
3. PRODUKT KARTEZJAC
SKI ZBIORÓW I RELACJE 8
Zadanie 4. Dane sÄ… relacje ‚" × i · ‚" × okreÅ›lone nastÄ™pujÄ…co:
= {(1, 1), (1, 2), (3, 2), (3, 4), (3, 7), (2, 9), (5, 3)},
· = {(1, 2), (1, 7), (2, 5), (2, 4), (7, 9), (4, 10)}.
Znalez
ć dziedziny i przeciwdziedziny tych relacji (dziedziny lewostronne i dziedziny prawo-
stronne). Utworzyć relacje: ć% ·, · ć% , ·-1, -1, ·-1 ć% -1, (· ć% )-1, ·-1 ć% . Sprawdzić, że
·-1 ć% -1 =( ć% ·)-1.
Zadanie 5. Dana jest relacja · Ä…"{0, 1, 2, 3, . . . , 9}×{0, 1, 2, 3, . . . , 9} zdefiniowana warun-
kiem x·y Ô! x2 = y (" 2x - 3 =y. Wyznaczyć relacj e ·-1.
Zadanie 6. WiedzÄ…c, że = { a, b , b, b , c, d } zaÅ› · = { k, b , m, c }. Wyznaczyć ć%·-1.
Zadanie 7. WiedzÄ…c, że = { 1, 2 , 2, 2 , 3, 4 } zaÅ› · = { 4, , 2, © , 2, }. Wyzna-
czyć ć% ·.
Zadanie 8. Wyznaczyć ć% ·, · *" , · )" , gdy x, y "{1, 2, 3, 4, 5, 6}, a przy tym:
x, y " Ô! 2|x2 - y2 oraz x, y "· Ô! y = x2
Zadanie 9. Wyznaczyć ć% ·, · ć% , · )" , gdy:
= { 0, 1 , 0, 2 , 0, 3 , 1, 2 , 1, 4 , 2, 3 , 2, 4 , 3, 4 , }
· = { 0, 0 , 1, 1 , 2, 2 , 3, 3 , 4, 4 , 1, 0 , 1, 2 , 2, 4 , }
Zadanie 10. Relacja · Ä…" × jest okreÅ›lona warunkiem:
x, y "· Ð!Ò! x2 - 2x + y - 4 =0
2
Wyznaczyć zbiór Y Ä…" taki, że card { y, x " | y, x "·-1 '" y " Y } wynosi: (i) 2, (ii)
1, (iii) 0.
Zadanie 11. Relacja µ Ä…" × jest okreÅ›lona warunkiem:
x, y "µ Ð!Ò! x2 - 4x + y - 5 =0
2
Wyznaczyć zbiór Y Ä…" taki, że card { y, x " | y, x "µ-1 '" y " Y } wynosi: (i) 2, (ii)
1, (iii) 0.
3.2. Funkcje
Zadanie 1. Sformułować definicję funkcji: funkcji całkowitej i funkcji częściowej.
Zadanie 2. Podać przykłady funkcji całkowitej i funkcji częściowej określonych na tym
samym zbiorze.
Zadanie 3. Niech f : AA P(A) bÄ™dzie taka, że f(Õ) =Õ(A). Czy f jest różnowartoÅ›cio-
wa i czy jest na P(A)? Odpowiedz
przedyskutować w zależnośći od zbioru A.
3. PRODUKT KARTEZJAC
SKI ZBIORÓW I RELACJE 9
Zadanie 4. Niech A = " i niech f : A A. Udowodnić, że dla dowolnego a " A istnieje

najmniejszy zbiór X ą" A taki, że a " X oraz f-1(X) ą" X.
Zadanie 5. Niech f : P( ) ×P( ) P( ) bÄ™dzie okreÅ›lona wzorem f(A, B) = A )" B
dla dowolnych A, B " P( ). Zbadać czy f jest na P( ) różnowartościowa i czy jest na.
Wyznaczyć f-1({ }). Dla dowolnego zbioru C Ä…" wyznaczyć f(P(C) ×P(C)).
Zadanie 6. Niech f : P( ) ×P( ) P( ) bÄ™dzie okreÅ›lona wzorem f(A, B) = A )" B
dla dowolnych A, B " P( ). Zbadać czy f jest na P( ) różnowartościowa i czy jest na.
Wyznaczyć f-1({ }). Dla dowolnego zbioru C Ä…" wyznaczyć f(P(C) ×P(C)).
Zadanie 7. Niech f : P( ) bÄ™dzie taka, że f(Õ) =Õ-1({1}). Czy f jest różnowarto-
ściowa i czy jest na P( )? Znalez
ć obraz zbioru wszystkich funkcji stałych i przeciwobrazy
zbiorów: {{7}} oraz {7}.
Zadanie 8. Podać przykład takiej funkcji f oraz zbiorów A i B, że f-1 (f(A)) = A oraz

f (f-1(B)) = B.

Zadanie 9. Niech f, g : będą określone wzorami:

x
x +1, dla x<1,
(a) f(x) = oraz g(x) = .
x2 + x, dla x 1
x2 +1

x
x - 3, dla x<1,
(b) f(x) = oraz g(x) = .
x2 - 3x, dla x 1
x2 +2
Utworzyć możliwe superpozycje (złożenia) tych funkcji.
Zadanie 10. Dana jest funkcja f : określona wzorem:
ż#
ª# - 1, dla x<1,
2x
¨#
(a) f(x) = 3, dla x =1,
ª#
©#
x2 +4x +4, dla x>1.
ż#
ª# x +1, dla x<1,
¨#
(b) f(x) = 3, dla x =1,
ª#
©#
x2 +2x +1, dla x>1.
(i) Sprawdzić, czy f jest różnowartościowa;
(ii) wyznaczyć zbiór wartości funkcji f, tj. f( );
(iii) wyznaczyć funkcję odwrotną do f.
Zadanie 11. Niech f : A B. Wykazać, że f jest różnowartościowa wtedy i tylko wtedy,
gdy dla każdego zbioru C oraz dowolnych funkcji h : C A i g : C A, jeśli f ć% g = f ć% h,
to g = h.
3. PRODUKT KARTEZJAC
SKI ZBIORÓW I RELACJE 10
Zadanie 12. Niech f : A B. Wykazać, że f jest na B wtedy i tylko wtedy, gdy dla
każdego zbioru C i dowolnych g : B C oraz h : B C, jeśli g ć% f = h ć% f, to g = h.
Zadanie 13. Niech oraz oznaczają tym razem odpowiednio zbiór liczb rzeczywistych i
zbiór liczb wymiernych. Funkcja f : P( ) P(P( )) niech będzie taka, że f(A) =P(A) dla
każdego A ą" . Czy f jest różnowartościowa i czy jest na P(P( ))? Znalez
ć f-1(P(P( ))).
Zadanie 14. Funkcja f : P(A)B P(A × B) taka, że dla Õ "P(A)B jest f(Õ) ={ a, b "
A × B| a " Õ(b)}. Wykazać, że f jest bijekcjÄ….
Zadanie 15. Funkcja g : P(A × B) P(A)B dla C ‚" A × B oraz b " B jest okreÅ›lona
równością: g(C)(b) ={a " A| a, b "C}. Czy g jest bijekcją? Czy g jest funkcją odwrotną
do funkcji f z poprzedniego zadania?

Zadanie 16. Funkcja f : [0, 2Ą] ma wzór: f(x) = sin x + 1. Wyznaczyć f(A) oraz
3

f-1(B), gdy A =[0, Ä„] oraz B =[1, +").
2 2

Zadanie 17. Funkcja f : [0, 2Ą] ma wzór: f(x) = cos x + 1. Wyznaczyć f(A) oraz
3

f-1(B), gdy A =[0, Ä„] oraz B =[1, +").
2 2

Zadanie 18. Funkcja f : ma wzór f(x) = x2 - 3x + 2. Wyznaczyć: f({1, 2}),

f([0, 1]), f([-2, -1]), f-1({0}), f-1([0, 2]), f-1((-", -6)).

Zadanie 19. Funkcja f : ma wzór f(x) =2|x|. Wyznaczyć f( ), f({4}), f-1([0, 1]),

f-1((2, 3]).
-

Zadanie 20. Funkcja f : ma wzór f(x) =x2 - 4x + 5. Wyznaczyć zbiór f ([2, 5])
-
-1
(tj. obraz przedziału [2, 5] poprzez funkcję f), a także zbiór f ((2, 5]) (tzn. przeciwobraz
przedziału (2, 5] poprzez funkcję f.
-

Zadanie 21. Funkcja f : [2, 5] ma wzór f(x) =x2 -4x+ 3. Wyznaczyć zbiór f ([2, 5])
-
-1
(tj. obraz przedziału [2, 5] poprzez funkcję f), a także zbiór f ((1, 2]) (tzn. przeciwobraz
przedziału (1, 2] poprzez funkcję f.
"
x2 +4x
Zadanie 22. Funkcja f : (-", -4 *"(0, +") określona jest wzorem: f(x) = .
x
Dla x " (-", -4) wyznaczyć funkcję odwrotną do f, jeśli funkcja taka istnieje.
Zadanie 23. Dla funkcji f : określonej wzorem:

3 3

(i) f(x) =1 +sin x wyznaczyć :f({0, Ą}), f-1 {[0, Ą} , f-1 (1, ] ;
2 2

(ii) f(x) =x2 - 3x + 2 wyznaczyć f( ), f-1 ({6}), f-1 ((0, 2]);

(iii) f(x) =x2 - 3x + 2 wyznaczyć: f( ), f-1 ({6}), f-1 ((0, 2]).
3. PRODUKT KARTEZJAC
SKI ZBIORÓW I RELACJE 11
Zadanie 24. Wyznaczyć, o ile istnieje, funkcję odwrotną do funkcji f : określonej
równością:
(i) f(x) =(x +1) · |x +1|,
(ii) f(x) =(x - 2) · |x - 2|,
(iii) f(x) =x · |x|3,
1
Zadanie 25. Dana jest funkcja f : określona wzorem f(x) = . Dla
x2 +4x +5
x " (-", -2] wyznaczyć funkcję odwrotną do f, jeśli funkcja taka istnieje.
Zadanie 26. Funkcja f : ma wzór f(n) =(n - 1)2 + 1. Zbadać czy f jest różno-
wartościowa, czy jest  na , czy ma punkt stały. Określić, ze stosownym uzasadnieniem, jaka

jest moc zbioru f( ).
Zadanie 27. Funkcja f : ma wzór:
(i) f(x) =x2 +1,

x - 1, dla x " (-", 0)
(ii) f(x) =
2x +1, dla x " [0, ")

2x +3, dla x " (-", 0)
(iii) f(x) =
x2, dla x " [0, ")

1 - x, dla x " (-", 0)
(iv) f(x) =
x2 +1, dla x " [0, ")

Wyznaczyć f( ). Zbadać czy f jest injekcją, surjekcją.
2
Zadanie 28. Funkcja f : ma wzór: f(x) = x +1, 2x +1 . Zbadać czy f jest
injekcjÄ…, surjekcjÄ….
2 2
Zadanie 29. Funkcja f : ma wzór: f(x) = x + y, xy . Zbadać czy f jest injekcją,
surjekcjÄ….
2 2
Zadanie 30. Funkcja f : ma wzór: f(x) = x + y, x - y . Zbadać czy f jest
injekcją, surjekcją. Jeśli istnieje, to podać wzór funkcji odwrotnej f-1. Wyznaczyć obraz
prostej l o równaniu y = x + 1 poprzez funkcję f.
Zadanie 31. Wykazać, że f : X Y jest injekcjÄ… wtt, gdy dla dowolnego A ‚" X zachodzi

równość f-1(f(A)) = A.
Zadanie 32. Wykazać, że f : X Y jest injekcjÄ… wtt, gdy dla dowolnego B ‚" Y zachodzi

równość f(f-1(A)) = A.
3. PRODUKT KARTEZJAC
SKI ZBIORÓW I RELACJE 12
3.3. Relacje równoważności
def
Zadanie 1. Relacja Ä…"R2 ×R2 przy czym: x1, y1 x2, y2 Ð!Ò! |x1| + |y1| = |x2| + |y2|.
Na płaszczyz
nie z prostokątnym układem współrzędnych Oxy naszkicować zbiory:

(i) A = -1, 1 , B = a, 1 .
a"[-2,-1]
2 2
Zadanie 2. Dana jest relacja ‚" × okreÅ›lona warunkiem:
2 2
x1, y1 x2, y2 Ð!Ò!x2 + y1 = x2 + y2.
1 2
(a) Pokazać, że jest relacją równoważności.
(b) Na płaszczyz
nie z prostokątnym układem współrzędnych Oxy naszkicować zbiory:
"
A = 3, -1 oraz B = a, 1 .
"
a"[- 3,0]
2
(c) Znalez
ć interpretację geometryczną zbioru / .
Zadanie 3. Wzbiorze × definiujemy relacjÄ™ równoważnoÅ›ci w nastÄ™pujÄ…cy sposób
x1; y1 x2; y2 wtt, gdy x2 + |y1| = x2 + |y2|
1 2
"
(i) Wyznaczyć klasę abstrakcji relacji o reprezentancie 3, -1 .

(ii) Naszkicować zbiór a; 1 .
"
a"[1, 3]
2
Zadanie 4. Wzbiorze określamy relację w następujący sposób:
x1; y1 x2; y2 Ð!Ò!|x1| = |x2| '" log2 (1 + |y1|) =log2 (1 + |y2|)
2
(a) Zbadać czy jest relacją równoważności w .
(b) Wyznaczyć klasę abstrakcji o reprezentancie 1, 1
Zadanie 5. Dana jest relacja równoważnoÅ›ci ‚" ( × )2 okreÅ›lona warunkiem:
+
1 2
x1, y1 x2, y2 Ð!Ò!y12-x = y22-x .
2
(a) Na płaszczyz
nie zaznaczyć klasę abstrakcji relacji o reprezentancie 1, 0 .

2
(b) Na płaszczyz
nie naszkicować zbiór A = (1, a) .
a" -1,1
Zadanie 6. Wzbiorze × definiujemy relacjÄ™ równoważnoÅ›ci w nastÄ™pujÄ…cy sposób:
+
1 2
x1; y1 x2; y2 Ð!Ò!|log2 x1| = |log2 x2| '" 2|y | =2|y |
(a) Wyznaczyć klasę abstrakcji relacji o reprezentancie 1, 3 .
2

(b) Naszkicować zbiór a; b
1
a" ;2 ,b" 2;3
2
3. PRODUKT KARTEZJAC
SKI ZBIORÓW I RELACJE 13
Zadanie 7. Dany jest zbiór X = {x " : |x| 5} oraz relacja równoważnoÅ›ci ‚" X2 ×X2
określona warunkiem:
2 2
x1, y1 x2, y2 Ð!Ò! 4|(x1 - x2) '" 2|(y1 + y2).
Wyznaczyć zbiór || 2, -1 || *" || 0, 1 || .
2
Zadanie 8. Wzbiorze okreÅ›lamy relacjÄ™ µ w nastÄ™pujÄ…cy sposób:
2 2
x1; y1 µ x2; y2 Ð!Ò!|x3| + y1 = |x3| + y2
1 2
Zbadać czy µ jest relacjÄ… równoważnoÅ›ci. W przypadku odpowiedzi pozytywnej zaznaczyć
2
na płaszczyz
nie klasÄ™ abstrakcji pary 1, 2 .
Zadanie 9. WiedzÄ…c, że Ä…" (X × Y )2, gdzie X = {0, 1, 2, 3, 4, 5} i Y = {1, 2, 3, 4}, jest
relacją równoważności zdefiniowaną warunkiem
x1, y1 x2, y2 Ð!Ò![3|(x1 - x2) '" (y1 = y2)],
znalez
ć klasę abstrakcji relacji o reprezentancie 1, 1 .
2 2
Zadanie 10. Relacja Ä…" × przy czym:
x1 x2
def
x1, y1 x2, y2 Ð!Ò! = .
1+|y1| 1+|y2|
Na płaszczyz
nie z prostokątnym układem współrzędnych Oxy naszkicować zbiory: A =

1, 1 , B = p, 1 .
p"[1,2]
Ä„ Ä„
Zadanie 11. Relacja Ä…" (-Ä„ , ) × (-Ä„ , ) przy czym:
2 2 2 2
def
x1, y1 x2, y2 Ð!Ò! |x1| = |x2| '" | cos y1| = | cos y2|
Na płaszczyz
nie z prostokątnym układem współrzędnych Oxy naszkicować zbiory: A =

Ä„
Ä„ , , B = a, b .
4 3
Ä„ Ä„ Ä„
a"[0, ] b"{ , }
4 4 3
Zadanie 12. Wzbiorze [0; 2Ä„) × [0; 2Ä„) okreÅ›lamy relacjÄ™ w nastÄ™pujÄ…cy sposób:
x1; y1 x2; y2 Ð!Ò! sin x1 =sin x2 '" | cos y1| = | cos y2|.
(a) Wykazać, że jest relacją równoważności w [0; 2Ą).
Ä„
(b) Wyznaczyć klasę abstrakcji relacji o reprezentancie Ą ; .
6 3
(c) Zaznaczyć w układzie współrzędnych Oxy sumę mnogościową klas abstrakcji a; b
Ä„
reprezentowanych przez pary a; b takie, że a " [Ą ; ], zaś b " [Ą ; Ą].
6 2 3
Zadanie 13. Funkcja { } : określona jest wzorem: {x} = x - [x], gdzie [x] oznacza
część caÅ‚kowitÄ… z liczby rzeczywistej x. Wzbiorze [0; 2Ä„) × [0; 2Ä„) okreÅ›lamy relacjÄ™ w
następujący sposób:

y1 y2
x1; y1 x2; y2 Ð!Ò! sin x1 =sin x2 '" = .
Ä„ Ä„
3. PRODUKT KARTEZJAC
SKI ZBIORÓW I RELACJE 14
(a) Wykazać, że jest relacją równoważności w [0; 2Ą).
Ä„
(b) Wyznaczyć klasę abstrakcji relacji o reprezentancie Ą ; .
6 3
(c) Zaznaczyć w układzie współrzędnych Oxy sumę mnogościową klas abstrakcji x0; y0
Ä„
reprezentowanych przez pary x0; y0 takie, że x0 " [Ą ; ], zaś y0 " [Ą ; Ą].
6 2 3
Zadanie 14. Wzbiorze A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
okreÅ›lamy relacjÄ™ w taki sposób, że jeÅ›li x " A oraz y " A, to: x y Ð!Ò! 11|x2 - y2.
(a) Zbadać czy jest relacją równoważności.
(b) Jeśli odpowiedz
w punkcie (a) jest pozytywna, to wyznaczyć zbiór wszystkich klas abs-
trakcji tej relacji.
Zadanie 15. Wzbiorze B = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17} określamy
relacjÄ™ w taki sposób, że jeÅ›li s " B oraz t " A, to: s t Ð!Ò! 7|s2 - t2
(a) Zbadać czy jest relacją równoważności.
(b) Jeśli odpowiedz
w punkcie (a) jest pozytywna, to wyznaczyć zbiór wszystkich klas abs-
trakcji tej relacji.
Zadanie 16. Wzbiorze A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17} określamy
relację w taki sposób, że jeśli s " A oraz t " A, to:

s t Ð!Ò! 5|(s2 - t2) (" 5|(s2 + t2) .
(a) Zbadać czy jest relacją równoważności.
(b) Jeśli odpowiedz
w punkcie (a) jest pozytywna, to wyznaczyć zbiór wszystkich klas abs-
trakcji tej relacji.
Zadanie 17. Wzbiorze B = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17} określamy
relację w taki sposób, że jeśli s " B oraz t " B, to:
s t Ð!Ò! [3|(x2 - y2) (" 3|(x2 + y2)].
(a) Zbadać czy jest relacją równoważności.
(b) Jeśli odpowiedz
w punkcie (a) jest pozytywna, to wyznaczyć zbiór wszystkich klas abs-
trakcji tej relacji.
Zadanie 18. Niech TOx oznacza rodzinę wszystkich trójkątów zawartych w płaszczyz
nie
Oxy, których podstawy są równoległe do osi Ox (przyjmijmy, że jeśli ABC " TOx, to
AB pr.Ox). JeÅ›li T A B1C1 "TOx oraz T A B2C2 "TOx, to relacjÄ™ Ä…"TOx ×TOx okreÅ›lamy
1 2
warunkiem:
def
(T A B1C1) (T A B2C2) Ð!Ò! A1 = A2 '" B1 = B2 '" S A B1C1 = S A B2C2.
1 2 1 2
3. PRODUKT KARTEZJAC
SKI ZBIORÓW I RELACJE 15
(a) Naszkicować klasę abstrakcji T ABC , gdzie A =(2, 2), B =(5, 2) oraz C =(6, 5).

(b) Naszkicować zbiór T ABC , gdzie Ca =(6, a) oraz A =(2, 2) i B =(5, 2).
a
a"[5,7]
Zadanie 19. Wzbiorze F funkcji jednej zmiennej rzeczywistej, postaci p(x) = xm + ax,
1 2
gdzie m " oraz a " dla p1(x) =xm + ax oraz p2(x) =xm + ax relację określamy
+
1 2
następująco:

a1
p1(x) p2(x) Ð!Ò! |m1| = |m2| '" =1 (" a1a2 =1 .
a2
(a) Zbadać czy jest relacją równoważności.
(b) Jeśli odpowiedz
w punkcie (a) jest pozytywna, to wyznaczyć klasę abstrakcji tej relacji
o reprezentancie p(x) =x3 +7x.
Zadanie 20. Niech M2( ) oznacza zbiór wszystkich macierzy kwadratowych stopnia dru-
2
giego nad ciałem . Wzbiorze M2( ) definiujemy relacj e w następujący sposób:
2 2

A B wtt, gdy [a12 + a21 = b12 + b21].
A,B"M2( 2 )
(a) Zbadać czy jest relacją równoważności w M2( ).
2
(b) Jeśli odpowiedz
na pytanie w punkcie (a) jest pozytywna, to wyznaczyć klasę abstrakcji

0 1
macierzy .
0 0
Zadanie 21. Niech M( ) będzie zbiorem macierzy stopnia drugiego nad ciałem binarnym
2
=({0, 1}, •"2, 2). Definiujemy relacjÄ™ Ä…"M( ) ×M( ) takÄ…, że jeÅ›li A i B należą do
2 2 2
M(V ), to:
A B wtt, gdy det A =det B.
Pokazać, że jest relacją równoważności oraz wyznaczyć klasę abstrakcji tej relacji, do której

0 0
należy macierz .
0 1
Zadanie 22. Wykazać, że relacja określona w \{0+0i} warunkiem
4
z1
z1 z2 wtt, gdy =1
z2
jest relacją równoważności oraz znalez
ć klasy równoważności elementów -1, 2.
Zadanie 23. W zbiorze liczb zespolonych określona jest relacja równoważności taka, że
z1 z2 wtt, gdy rez1 =rez2 '" |imz1| = |imz2|.
(a) Wyznaczyć klasę abstrakcji relacji o reprezentancie z =1 - 2i.
3. PRODUKT KARTEZJAC
SKI ZBIORÓW I RELACJE 16

(b) Naszkicować zbiór (2, y) , tj. sumę klas abstrakcji relacji , gdy rez =2 i imz
y" 1;3
zmienia siÄ™ od 1 do 3.
2
Zadanie 24. Wzbiorze liczb zespolonych określamy relacje w następujący sposób:
Ä„
z1 z2 wtt, gdy |rez1| = |rez2| oraz |(|Argz1 - Argz2|).
2
(a) Wyznaczyć klasę abstrakcji relacji o reprezentancie 1 + i tj. 1+i .
(b) Na płaszczyz
nie C2 zaznaczyć zbiory:




Ä„ Ä„

(i) A = a cos + i sin (ii) B = a(cos Õ + i sin Õ) .

3 3
Ä„ Ä„
a"[1,2] a"[1,2] Õ"[ ; ]
6 3
Zadanie 25. Wzbiorze F2 funkcji postaci f(x) =ax2 + bx + c, gdzie a, b, c " oraz ai =0

definiujemy relacjÄ™ równoważnoÅ›ci · w nastÄ™pujÄ…cy sposób:
fi·fj wtt, gdy {x " : fi(x) =0} = {x " : fj(x) =0}
Naszkicować klasÄ™ abstrakcji relacji · o reprezentancie f(x) =x2 - 3x +2.
Zadanie 26. Niech F oznacza rodzinÄ™ funkcji f : postaci:
3 3
fi(x) =aix2 + bix + ci, dla i "{1, 2, . . . , 18}
przy czym ai, bi, ci " oraz ai =0. Wzbiorze F określamy relację w następujący sposób:

3
fi a" fj wtt, gdy {x " : fi(x) =0} = {x " : fj(x) =0},
3 3
gdzie i, j "{1, 2, . . . , 18}.
(a) Pokazać, że jest relacją równoważności.
(b) Wyznaczyć klasę abstrakcji relacji o reprezentancie f(x) =x2 +4x +3.
(c) Pamiętając, że Gr(f) = {(x; y) : x " Df '" y = f(x)} oznacza wykres funkcji f,
wyznaczyć zbiór będący sumą wykresów funkcji należących do klasy abstrakcji funkcji
f określonej w punkcie (b).
Zadanie 27. Niech będzie ciałem binarnym, W rodziną wielomianów określonych nad
2
, zaÅ› Ä…"W×W relacjÄ… zdefiniowanÄ… warunkiem:
2

(f, g) " wtt, gdy f2 - g2 = ax + b.
a" 2 b" 2
(a) Zbadać czy jest relacją równoważności w W.
(b) W przypadku pozytywnej odpowiedzi w punkcie (a) wyznaczyć klasę abstrakcji o repre-
zentancie f(x) =x +1.
4. MOC ZBIORU 17
2
Zadanie 28. Wzbiorze określamy relację równoważności w następujący sposób:
2 2
x1, y1 x2, y2 wtt, gdy log(1+x2 Ä„ =log(1+x2 Ä„ '" y1 - y1 = y2 - y2
) )
1 2
Wyznaczyć klasę abstrakcji tej relacji o reprezentancie -2, 1 .
2
Zadanie 29. Wzbiorze określamy relację równoważności w następujący sposób:

3 3 2 2
x1, y1 x2, y2 wtt, gdy 1+|x1| = 1+|x2| '" y1 +2y1 = y2 +2y2
Wyznaczyć klasę abstrakcji tej relacji o reprezentancie 3, -2 .
2
Zadanie 30. Wzbiorze liczb zespolonych określamy relacje w następujący sposób:


Ä„

z1 z2 wtt, gdy |rez1| = |rez2| oraz (|argz1 - argz2|).

2
(a) Wyznaczyć klasę abstrakcji relacji o reprezentancie 1 + i tj. 1+i .
2
(b) Na płaszczyz
nie zaznaczyć zbiory:




Ä„ Ä„

(i) A = a cos + i sin , (ii) B = a(cos Õ + i sin Õ) .

3 3
Ä„ Ä„
a"[1,2] a"[1,2] Õ"[ ; ]
6 3
Zadanie 31. Wykorzystując odpowiednią relację przedstawić konstrucję:
(i) zbioru liczb całkowitych ;
(ii) zbioru liczb wymiernych .
4. Moc zbioru
4.1. Równoliczność zbiorów
Zadanie 1. Udowodnić, że suma zbiorów przeliczalnych jest zbiorem przeliczalnym.
Zadanie 2. Udowodnić, że zbiór wszystkich skończonych ciągów o elementach z pewnego
zbioru przeliczalnego jest przeliczalny.
Zadanie 3. Udowodnić, że rodzina wszystkich skończonych podzbiorów zbioru przeliczal-
nego jest przeliczalna.
Zadanie 4. Udowodnić, że rodzina parami rozłącznych przedziałów otwartych na prostej
rzeczywistej (tj. osi Ox) jest co najwyżej przeliczalny.
Zadanie 5. Udowodnić, że zbiór punktów nieciągłości funkcji rzeczywistej określonej i mo-
notonicznej na jest przeliczalny.
4. MOC ZBIORU 18
Zadanie 6. Udowodnić, że jeÅ›li A ‚" jest dowolnym niepustym podzbiorem, natomiast
f : A dowolną funkcją, to zbiór punktów, w których funkcja ta ma ekstrema właściwe
jest przeliczalny.
Zadanie 7. Udowodnić, że zbiór wszystkich okręgów na płaszczyz
nie, dla których współ-
rzędne środka a także długość promienia są liczbami wymiernymi jest przeliczalny.
Zadanie 8. Zbadać, czy zbiór złożony z rozłącznych okręgów (niekoniecznie wszystkich)
leżących na płaszczyz
nie jest przeliczalny.
Zadanie 9. Zbadać, czy zbiór złożony z rozłącznych kół leżących na płaszczyz
nie jest prze-
liczalny.
Zadanie 10. Pokazać, że zbiór wszystkich macierzy nad oraz zbiór wszystkich parami
rozłącznych przedziałów prostej rzeczywistej są zbiorami tej samej mocy oraz ustalić moc
tych zbiorów.
Zadanie 11. Pokazać, że następujące zbiory są mocy 5!0:
(a) zbiór wszystkich trójkątów, których wierzchołki mają współrzędne całkowite,
(b) zbiór wszystkich macierzy stopnia drugiego o wyrazach całkowitych,
(c) zbiór wszystkich liczb zespolonych o całkowitych częściach rzeczywistej i urojonej,
(d) zbiór T wszystkich trójkątów zawartych z płaszczyz
nie z protokątnym układem współ-
rzędnych Oxy, których wierzchołki mają obie współrzędne wymierne,
(e) zbiór wszystkich układów dwóch równań liniowych z dwiema niewiadomy-mi o współ-
czynnikach ze zbioru Z,
(f) zbiór wszystkich wielomianów skończonych stopni o współczynnikach wymiernych,
(g) zbiór pierwiastków wymiernych wielomianów skończonych stopni o współczynnikach cał-
kowitych,
(h) zbiór wszystkich wielomianów jednej zmiennej o współczynnikach całkowitych (tzn. zbiór
[x]),
(i) zbiór wszystkich trójmianów kwadratowych o współczynnikach wymiernych nie mają-
cych pierwiastków,
ax+b
(j) zbiór wszystkich funkcji homograficznych postaci h(x) = o współczynnikach wy-
cx+d
miernych,
(k) zbiór wszystkich ciągów arytmetycznych o wyrazach wymiernych,
(l) zbiór wszystkich ciągów geometrycznych o wyrazach wymiernych.
4. MOC ZBIORU 19
Zadanie 12. Udowodnić, że zbiory punktów odcinka i kwadratu są równoliczne.
Zadanie 13. Udowodnić, że zbiory punktów dowolnych dwóch okręgów są równoliczne.
Zadanie 14. Udowodnić, że: (0, 1) <" (0, 1] <" [0, 1) <" [0, 1].
Zadanie 15. Udowodnić, że dla dowolnych liczb rzeczywistych a, b, c, d takich, że a c Zadanie 16. Pokazać, że: [0, 1] <" .
Zadanie 17. Określić funkcje ustalające równoliczność między:
(a) zbiorem liczb nieparzystych dodatnich i zbiorem liczb parzystych dodatnich;
(b) zbiorem liczb całkowitych podzielnych przez 3 oraz zbiorem liczb całkowitych podziel-
nych przez 4.
(c) zbiorem liczb całkowitych dodatnich i zbiorem wszystkich liczb całkowitych;
(d) zbiorami punktów dwóch różnych kół z brzegami,
(e) przedziałem [0, +") oraz przedziałem [0, a), gdzie a jest dowolnie ustaloną liczbą rze-
czywistÄ… dodatniÄ…,
(f) przedziałem (-", 1) oraz przedziałem (b, 1), gdzie b jest dowolnie ustaloną liczbą rze-
czywistÄ… ujemnÄ…,
2
(g) zbiorem { x, y " | xy =4} oraz przedziałem (5, +"),
+
"
x
2
(h) zbiorem { x, y " | =1} oraz przedziałem (7, +"),
+
y
(i) zbiorem oraz zbiorem M = { x, y |x " '" y =sin x},
(j) zbiorem oraz zbiorem M = { x, y |x " '" y =log2 x},
+
(k) zbiorem oraz zbiorem M = { x, y |x " '" y =3x},
+
(l) przedziałem [0, +") oraz brzegiem pięciokąta foremnego o boku a, gdzie a " jest
+
dowolnie ustalone,
(m) półprostą wraz z początkiem, brzegiem sześciociokąta foremnego o boku b, gdzie b "
+
jest dowolnie ustalone,
(n) pierścień kołowy (r1, r2) o promieniu wewnętrznym r1 oraz zewnętrznym r2, gdzie 0 <
r1 +
(o) zbiorami A oraz B, gdy pierwszy z nich składa się z punktów płaszczyzny będących
punktami przecięcia przekątnych trapezów, których współrzędne wierzchołków są licz-
bami wymiernymi, zaś drugi jest zbiorem punktów nieciągłości funkcji f : ,
4. MOC ZBIORU 20
(p) brzegu koła K o dodatnim promieniu oraz, dla każdej liczby n " \ {0, 1, 2}, brze-
gu pierścienia złożonego z wielokątów foremnych Wn oraz wn odpowiednio opisanego i
wpisanego w koło K ze zbiorem n |x| przy x " ,

"
2
(q) zbiory { x, y " : y = x2 +3x +3} oraz x " : tg x = 3 ,
(r) zbióru punktów dowolnego okręgu o dodatnim promieniu oraz zbiór rozwiązań nierów-
ności log2(x - 1) > 0 wzbiorze ,
(s) wnętrza dowolnego kwadratu z wykluczeniem jego środka symetrii, z zewnętrzem tego
kwadratu.
Zadanie 18. Stosując twierdzenie Cantora-Bernsteina wykazać, że następujące zbiory są
równej mocy:
(a) koło bez brzegu i koło z brzegiem;
(b) dwa dowolne wieloboki wypukłe;
(c) kula i sześcian;
(d) odcinek prostej i koło
(e) zbiór wszystkich punktów trójkąta oraz zbiór wszystkich punktów jego brzegu,
(f) wszystkich punktów kwadratu oraz zbiór wszystkich punktów jego brzegu,
(g) kula i dowolny wpisany w nią prostopadłościan,
(h) stożek oraz wpisany w niego sześcian,
(i) koło bez brzegu i koło z brzegiem,
(j) pierścień kołowy z brzegiem o promieniach długości r =3 oraz R = 5 i dowolny czworokąt
wypukły z brzegiem,
(k) trójkąt prostokątny (o dowolnej proporcji długości przyprostokątnych) oraz elipsa (o
dowolnej proporcji długosci osi),
(l) prostokąt (o dowolnej proporcji długości boków) oraz połówka dowolnego koła wraz z
brzegiem,
(m) dowolny stożek i dowolny wielościan prosty.
x
Zadanie 19. Dana jest funkcja h- : (-1, 0] określona wzorem h-(x) = . Zba-
1+x
-

dać czy funkcja ta realizuje równoliczność zbiorów (-1, 0] oraz h ((-1, 0]). Niech teraz
-
h+ : (0, 1) . Korzystając z informacji o funkcji h- zaproponować wzór funkcji h+ tak, by
funkcja k : (-1, 1) realizowała równoliczność zbiorów (-1, 1) oraz , gdy przyjmiemy,

h-(x), dla x " (-1, 0],
że k(x) =
h+(x), dla x " (0, 1).
5. RELACJE PORZ
DKUJ
CE 21
x
Zadanie 20. Dana jest funkcja f+ : (0, 1) określona wzorem f+(x) = . Zbadać
1 - x
-

czy funkcja ta realizuje równoliczność zbiorów (0, 1) oraz f ((0, 1)). Niech teraz
+
f- : (-1, 0] . Korzystając z informacji o funkcji f+ zaproponować wzór funkcji f-
tak, by funkcja g : (-1, 1) realizowała równoliczność zbiorów (-1, 1) oraz , gdy

f-(x), dla x " (-1, 0],
przyjmiemy, że g(x) =
f+(x), dla x " (0, 1).
Zadanie 21. Niech F = {f : : f(x) =ax + b '" a " \{0}'"b " }. Pokazać, że
jeśli Ffix{3} oznacza podzbiór F, którego elementy mają punkt stały 3, to card Ffix{3} = 5!0.
Zadanie 22. Niech F = {f : : f(x) =ax2 + bx + c '" a " \{0}'"b, c " }. Poka-
zać, że jeśli Ffix{1,2} oznacza podzbiór F, którego elementy mają punkty stałe 1 i 2, to
card Ffix{1,2} = 5!0.

b 1
Zadanie 23. Niech L = l : \{- } : l(x) = '" a " \{0}'"b " . Pokazać,
a ax+b
że jeśli Lfix{1} oznacza podzbiór L, którego elementy mają punkt stały 1, to card Lfix{1} = 5!0.
Zadanie 24. Wykazać, że jeżeli zbiory A i B są przeliczalne, to:
(a) zbiór A *" B jest przeliczalny,
(b) zbiór A )" B jest przeliczalny,
.
(c) zbiór A.B jest przeliczalny, gdzie A B =(A \ B) *" (B \ A).
Zadanie 25. Wykazać, że jeśli A jest zbiorem przeliczalnym, zaś B zbiorem skończonym,
to zbiór wszystkich funkcji z A w B jest przeliczalny.
5. Relacje porzÄ…dkujÄ…ce
5.1. Rodzaje porządków
Zadanie 1. Niech X = × oraz ‚" X2 × X2 bÄ™dzie zadana warunkiem:
a; b c; d wtt, gdy a c '" b|d.
Wyznaczyć, o ile istnieją, elementy minimalne i maksymalne oraz kresy zbioru

1
B = , 3k " X : k "{1, 2, 3, 4} .
3k
Zadanie 2. Wzbiorze P wszystkich prostopadÅ‚oÅ›cianów okreÅ›lamy relacjÄ™ µ nastÄ™pujÄ…cym
warunkiem:

P1µP2 wtt, gdy V(P1) V(P2),
P1,P2"P
gdzie V(P ) oznacza objętość prostopadłościanu P . Sprawdzić, które z wymienionych włas-
noÅ›ci speÅ‚nia relacja µ: zwrotność, antysymetria, symetria, spójność.
5. RELACJE PORZ
DKUJ
CE 22
Zadanie 3. Niech | Ä…" × oznacza relacjÄ™ podzielnoÅ›ci w zbiorze zdefiniowanÄ… nast e-
pujÄ…co:

m|n wtt, gdy km = n.
k"
Zbadać jakie własności w ma relacja |.
Niech A = {20, 30, 50}. Znalez
ć zbiór ograniczeń dolnych i zbiór ograniczeń górnych zbioru
A. Wskazać kresy dolny i górny tego zbioru.
3
Zadanie 4. Wzbiorze wszystkich trójwyrazowych ciągów liczb całkowitych definiujemy
relacjÄ™ µ w nastÄ™pujÄ…cy sposób:
a1, a2, a3 µ b1, b2, b3 wtt, gdy a1 b1 '" a2 b2 '" a3 b3.
Wyznaczyć, o ile istnieje, kresy górny i dolny zbioru
A = { 2, -2, 3 , 0, -5, 1 , 4, 1, -1 }
Zadanie 5. Dany jest zbiór A = {A1, A2, A3, A4, A5, A6}, którego elementy mają postać:
A1 = {x " : |x - 2| 1}, A4 = {x " : |x +1| 4},
A2 = {x " : |x| 2}, A5 = {x " : |x - 1| 5},
A3 = {x " : |x| 3}, A6 = {x " : |x| 6}.
(a) Zbadać czy i w jaki sposób A, ‚" jest uporzÄ…dkowany przez relacjÄ™,e inkluzji.
(b) Znalez
ć elementy wyróżnione (ograniczenia górne i dolne, kresy dolny i górny, elementy
minimalne, maksymalne, najmniejszy i najwiÄ™kszy) zbioru A, ‚" , o ile istniejÄ….
Zadanie 6. Wzbiorze T trójkątów na płaszczyz
nie definiujemy dwie relacje i ·:
(a) t1 t2 Ð!Ò! pole trójkÄ…ta T1 jest wiÄ™ksze od pola trójkÄ…ta T2.
(b) T1·T2 wtt, gdy trójkÄ…t T1 zawiera siÄ™ w trójkÄ…cie T2.
Czy relacje te są relacjami porządku częściowego, porządku liniowego, czy też nie spełniają
one definicji żadnego z tych porządków?
Zadanie 7. Niech dane będą zbiory:

1
X = x " : x = '" 1 n 100 '" n " oraz Y = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
n
Relacja ‚" (X × Y )2 okreÅ›lona jest równoÅ›ciÄ…:



1 1

x1, y1 x2, y2 wtt, gdy '" (y1 y2)
x1 x2

1 1
Ponadto niech będzie dany zbiór A = , 2 , , 3 .
5 7
5. RELACJE PORZ
DKUJ
CE 23

(a) Zbadać czy (X × Y )2 , jest zbiorem uporzÄ…dkowanym częściowo, liniowo.
(b) Znalez
ć kresy dolny i górny zbioru A.
(c) Zbadać czy zbiór A ma elementy najmniejszy i największy. Odpowiedz
szczegółowo uza-
sadnić.
2 2
Zadanie 8. Niech ‚" × bÄ™dzie okreÅ›lona warunkiem:
n1, k1 n2, k2 wtt, gdy n1 = n2 '" k1|k2.
2
(a) Zbadać czy , jest zbiorem uporządkowanym: częściowo, liniowo.
2
(b) Znalez
ć kresy dolny i górny zbioru A = { 1, 2 , 1, 3 } wzbiorze , .
(c) Czy zbiór A posiada element najmniejszy i element największy? Odpowiedz
uzasadnić.

1
Zadanie 9. NiechA = x " : x =1 + '" n " . Znalez
ć kresy dolny i górny zbioru A.
n
Zbadać, który z nich należy do A.
2
Zadanie 10. W wyróżniamy zbiór A = { x, y : x2 + y2 +4x - 6y 9} oraz określamy
2
relację porządku częściowego ą" :
x1, y1 x2, y2 wtt, gdy x1 x2 oraz y1 y2.
(a) Wyznaczyć zbiory ograniczeń dolnych oraz górnych zbioru A oraz kresy tego zbioru.
(b) Zawężając relację do zbioru A zbadać istnienie elementów minimalnego i maksymalnego
w tym zbiorze. W przypadku ich istnienia wskazać je oraz udowodnić, że to te elementy
zbioru A sÄ… odpowiednio elementem minimalnym i maksymalnym tego zbioru.
2
Zadanie 11. W wyróżniamy zbiór A = { x, y : |x +2| + |y - 4| 5} oraz określamy
2
relację porządku częściowego ą" :
x1, y1 x2, y2 wtt, gdy x1 x2 oraz y1 y2.
(a) Wyznaczyć zbiory ograniczeń dolnych i górnych zbioru A oraz kresy tego zbioru.
(b) Zawężając relację do zbioru A zbadać istnienie elementów minimalnego i maksymalnego
w tym zbiorze. W przypadku ich istnienia wskazać je oraz udowodnić, że to te elementy
zbioru A sÄ… odpowiednio elementem minimalnym i maksymalnym tego zbioru.
Zadanie 12. W zbiorze wszystkich liczb zespolonych z relacjÄ… porzÄ…dku częściowego µ
określoną warunkiem
z1µz2 wtt, gdy rez1 rez2 '" imz1 imz2.
"
7 4 1
Ä„i Ä„i Ä„i
4 3 3
wyróżniamy zbiór A = { 2e , 2e , 2e }
(a) Wyznaczyć zbiory ograniczeń dolnych i górnych zbioru A oraz kresy tego zbioru.
5. RELACJE PORZ
DKUJ
CE 24
(b) ZawężajÄ…c relacjÄ™ µ do zbioru A zbadać istnienie elementów minimalnego i maksymal-
nego w tym zbiorze. W przypadku ich istnienia wskazać je oraz udowodnić, że to te
elementy zbioru A sÄ… odpowiednio elementem minimalnym i maksymalnym tego zbioru.
3
Zadanie 13. Natomiast symbolem [x] oznaczamy zbiór wielomianów stopnia co najwyżej
trzeciego nad . W tym zbiorze dla wielomianów u(x) = u3x3 + u2x2 + u1x + u0 oraz
w(x) =w3x3 + w2x2 + w1x + w0 definiujemy relacjÄ™ · okreÅ›lonÄ… warunkiem:
u(x)·w(x) Ð!Ò! log (1 + ui) log (1 + wi) dla i "{0, 1, 2, 3}.
" 3
Zbadać czy zbiory M2×2 ( ) , oraz [x], · sÄ… uporzÄ…dkowane i w jaki sposób.
3
Zadanie 14. Niech [x] oznacza zbiór wszystkich wielomianów stopnia co najwyżej trze-
ciego nad , zaÅ› µ relacjÄ™ w tym zbiorze takÄ…, że gdy a(x) =a3x3 + a2x2 + a1x + a0 oraz
3
b(x) =b3x3 + b2x2 + b1x + b0 sÄ… elementami [x], to
a(x)µb(x) Ð!Ò! log (1 + ai) log (1 + bi) dla i "{0, 1, 2, 3}.
2
Symbolem oznaczamy zbiór wektorów w rozumianych jako uporządkowane pary
punktów o współrzędnych ze zbioru \{0}. Wzbiorze określamy relację :
1 2 3 4 1 3 2 4
A1(x1, y1), A2(x2, y1) A3(x3, y1), A4(x4, y1) Ð!Ò!x1|x3 '" y1|y1 '" x2|x4 '" y1|y1
1 1 1 1 1 1 1 1
3
Zbadać czy zbiory [x], µ oraz , sÄ… uporzÄ…dkowane i w jaki sposób.
2
Zadanie 15. W zbiorze par liczb zespolonych o naturalnej oraz dodatniej części rze-
"
czywistej i urojonej określamy relację:
x1 + iy1, x2 + iy2 x3 + iy3, x4 + iy4 Ð!Ò!x1|x3 '" y1|y3 '" x2|x4 '" y2|y4.
Natomiast w zbiorze funkcji homograficznych o współczynnikach naturalnych i dodatnich
a2x+b2
"
okreÅ›lamy relacjÄ™ H okreÅ›lamy relacjÄ™ µ takÄ…, że jesli h1(x) =a1x+b1 oraz h2(x) = ,
c1x+d1 c2x+d2
to
h1µh2 Ð!Ò! a1 a2 '" b1 b2 '" c1 c2 '" d1 d2.
2
"
Zbadać czy zbiory " , oraz H , µ sÄ… uporzÄ…dkowane i w jaki sposób.
5.2. Kraty
Zadanie 1. Niech tradycyjnie oznacza pierÅ›cieÅ„ {0, 1, . . . , p-1}, •"p, p , z dziaÅ‚aniami
p
modulo p. Rozpatrzmy zbiór M2×2( ) wszystkich macierzy stopnia drugiego o wyrazach z
5
, w którym definiujemy relacjÄ™ Ä…"M2×2( ) ×M2×2( ) w nastÄ™pujÄ…cy sposób.
5 5
5
a11 a12 b11 b12
Dla A = oraz B = mamy:
a21 a22 b21 b22
def
A B Ð!Ò! a11 b11 '" a12 b12 '" a21 b21 '" a22 b22
5. RELACJE PORZ
DKUJ
CE 25
(i) Czy M2×2( ), jest kratÄ…?
5
(ii) Czy M2×2( ), jest kratÄ… zupeÅ‚nÄ…?
5
(iii) Czy istnieją, a jeśli tak to jakie, elementy najmniejszy i największy?

3 2 1 3 4 1
(iv) Wyznaczyć kresy zbioru W = , , .
2 1 0 2 3 0
W każdym z podpunktów odpowiedz
uzasadnić (dowieść).
Zadanie 2. Wzbiorze P( ) × × okreÅ›lamy relacjÄ™ µ takÄ…, że:


1 1

A1, n1, k1 µ A2, n2, k2 wtt, gdy A1 Ä…" A2 oraz oraz k1 k2 .
2n1 - 1 2n2 - 1
(i) Zbadać czy para P( ) × × , µ jest kratÄ….
(ii) Zbadać czy para P( ) × × , µ jest kratÄ… zupeÅ‚nÄ….
(iii) Podać przykład zbioru B, B nie będącego kratą.
Niech tradycyjnie oznacza pierÅ›cieÅ„ {0, 1, . . . , p - 1}, •"p, p , z dziaÅ‚aniami modulo
p
p. Rozpatrzmy zbiór M2×2( ) wszystkich macierzy stopnia drugiego o wyrazach z , w
7 7
którym definiujemy relacjÄ™ µ Ä…"M2×2( ) ×M2×2( ) w nastÄ™pujÄ…cy sposób:
7 7

a11 a12 b11 b12
Dla A = oraz B = mamy:
a21 a22 b21 b22
def
AµB Ð!Ò! aij|bij dla i, j "{1, 2}.
(i) Czy M2×2( ), µ jest kratÄ…?
7
(ii) Czy M2×2( ), µ jest kratÄ… zupeÅ‚nÄ…?
7
(iii) Czy istnieją, a jeśli tak to jakie, elementy najmniejszy i największy?

2 3 1 4 3 5
(iv) Wyznaczyć kresy zbioru W = , , .
5 6 2 3 1 5
Zadanie 3. W pierścieniu [x] wielomianów zmiennej x nad ciałem nad określamy relację:
def
w1(x)µw2(x) Ð!Ò! deg w1(x)| deg w2(x) '" min{x " : w1(x) =0} min{x " : w2(x) =0}
(i) Zbadać czy para [x], µ jest kratÄ….
(ii) Zbadać czy para [x], µ jest kratÄ… zupeÅ‚nÄ….
(iii) Podać przykład zbioru A, A nie będącego kratą.
Zadanie 4. Wzbiorze okreÅ›lamy relacjÄ™ µ takÄ…, że:
z1µz2 wtt, gdy |z1| |z2| oraz argz1 argz2.
5. RELACJE PORZ
DKUJ
CE 26
(i) (3 pkt) Zbadać czy para , µ jest kratÄ…, kratÄ… zupeÅ‚nÄ….
" " " "
(ii) (3 pkt) Dla zbioru A = {1+ 3i, - 3+i, - 2 - 2i)} znalez
ć elementy wyróżnione
(ograniczenia górne i dolne, kresy dolny i górny, elementy minimalne, maksymalne,
najmniejszy i największy) zbioru A  o ile istnieją.
Zadanie 5. Wzbiorze × okreÅ›lamy relacjÄ™ µ takÄ…, że:
n1, z1 µ n2, z2 wtt, gdy n1|n2 oraz |z1| |z2| oraz argz1 argz2.
(i) Zbadać czy para × , µ jest kratÄ….
(ii) Zbadać czy para × , µ jest kratÄ… zupeÅ‚nÄ….
(iii) Podać przykład zbioru A, A nie będącego kratą.
Każdą z odpowiedzi udowodnić.
2
Zadanie 6. W zbiorze wielomianów [x] stopnia co najwyżej drugiego nad określamy
3
3
2
relacje oraz ¾ takÄ…, że dla wielomianów u(x) oraz w(x) z [x] mamy:
3
u(x) w(x) Ð!Ò! u(x)|w(x) oraz(u2x2+u1x+u0)¾(w2x2+w1x+w0) Ð!Ò! u2 w2'"u1|w1'"u0|w0
2
(i) Zbadać czy [x], ¾ jest kratÄ…, czy jest kratÄ… zupeÅ‚nÄ…?
3
2
(ii) Zbadać czy [x], ¾ ma elementy najmniejszy i najwiÄ™kszy, a w przypadku odpowiedzi
3
pozytywnej wskazać te elementy oraz uzasadnić odpowiedz
.
2 2
(iii) Zbiór A‚" [x] ma postać A = {2x +1, x2 +2, 2x2 +1}. W [x], wyznaczyć "A,
3 3


“A, A oraz A.
2
Zadanie 7. W zbiorze wielomianów [x] co najwyżej drugiego nad określamy relacje
3
3
2
oraz ¾ takie, że dla wielomianów a(x) oraz b(x) z [x] mamy:
3
a(x) b(x) Ð!Ò! a(x)|b(x) oraz (a2x2 +a1x+a0)¾(b2x2 +b1x+b0) Ð!Ò! a2|b2 '"a1|b1 '"a0 b0
2
(i) Zbadać czy [x], jest kratą i czy jest kratą zupełną?
3
2
(ii) Zbadać czy [x], ma elementy najmniejszy i największy, a w przypadku odpowiedzi
3
pozytywnej wskazać te elementy oraz uzasadnić odpowiedz
.
2 2
(iii) Zbiór B ‚" [x] ma postać B = {x +1, x+2, 2x2 +1}. W [x], ¾ wyznaczyć "B,
3 3


“B, B oraz B.
3
Zadanie 8. Wzbiorze ciÄ…gów trójwyrazowych nad okreÅ›lamy relacje oraz ¾ takie,
3
3
3
że dla ciągów u =(u0, u1, u2) oraz w =(w0, w1, w2) z [x] mamy:
3
u w Ð!Ò! u0|w0 '" u1|w1 '" u2|w2 oraz u¾w Ð!Ò! u2 w2 '" u1|w1 '" u0 w0
5. RELACJE PORZ
DKUJ
CE 27
3
(i) Zbadać czy , jest kratą, czy jest kratą zupełną?
3
3
(ii) Zbadać czy , ¾ ma elementy najmniejszy i najwiÄ™kszy, a w przypadku odpowiedzi
3
pozytywnej wskazać te elementy oraz uzasadnić odpowiedz
.
3 3
(iii) Zbiór A‚" ma postać A = { 0, 2, 1 , 1, 0, 2 , 2, 0, 1 }. W , wyznaczyć "A,
3 3


“A, A oraz A.
Zadanie 9. Sformułować definicję zbioru częściowo uporządkowanego oraz zbioru liniowo
uporzÄ…dkowanego.
(a) Zbadać jak uporządkowany jest zbiór ( \{0, 1}), , jeśli
n1 n2 Ð!Ò! {[Åš(n1) Åš(n2)] (" [Åš(n1) =Åš(n2) '" n1 n2]}
gdzie Ś(n) oznacza liczbę różnych dzielników pierwszych liczby naturalnej n.
(b) Zbadać jak uporzÄ…dkowany jest zbiór × ( \{0}), , jeÅ›li
n1, k1 n2, k2 Ð!Ò!n1 · k2 k1 · n2.
(c) Zbadać jak uporządkowany jest zbiór , , jeśli
n1, k1 n2, k2 Ð!Ò!n1 n2 '" k1|k2.
2 2
Zadanie 10. W określamy relację porządku częściowego ą" :
x1, y1 x2, y2 wtt, gdy x1 x2 oraz y1 y2.
Dla każdego z zbiorów Ai przy i " {1, 2, 3} gdzie: A1 = { x, y : x2 + y2 +4x - 6y 12}
A2 = { x, y : x2 + y2 - 2x +8y 19} oraz A3 = { x, y : |x +2| + |y - 4| 5}:
(a) Wyznaczyć zbiory ograniczeÅ„ dolnych "A oraz “A oraz kresy tego zbioru.
i i
(b) Zawężając relację do zbioru Ai zbadać istnienie elementów minimalnego i maksymal-
nego w tym zbiorze. W przypadku ich istnienia wskazać je oraz udowodnić, że to te
elementy zbioru A sÄ… odpowiednio elementem minimalnym i maksymalnym tego zbioru.
Zadanie 11. W zbiorze wszystkich liczb zespolonych z relacjÄ… porzÄ…dku częściowego µ
określoną warunkiem
z1µz2 wtt, gdy rez1 rez2 '" imz1 imz2.
"
7 4 1
Ä„i Ä„i Ä„i
4 3 3
wyróżniamy zbiór A = { 2e , 2e , 2e }
(i) Wyznaczyć zbiory ograniczeÅ„ dolnych "A oraz “A oraz kresy tego zbioru.
(ii) ZawężajÄ…c relacjÄ™ µ do zbioru A zbadać istnienie elementów minimalnego i maksymal-
nego w tym zbiorze. W przypadku ich istnienia wskazać je oraz udowodnić, że to te
elementy zbioru A sÄ… odpowiednio elementem minimalnym i maksymalnym tego zbioru.
5. RELACJE PORZ
DKUJ
CE 28
5.3. Izomorfizm zbiorów uporządkowanych. Dobre porządki
Zadanie 1. Dane są zbiory , oraz (0, 1), . Pokazać, że są one izomorficzne, a
-
1
izomorfizm ten realizuje funkcja f : (0, 1) postaci f(x) = .
-
1+x2
Zadanie 2. Dane są zbiory , oraz (-1, 1), . Pokazać, że są one izomorficzne, a
x
izomorfizm ten realizuje funkcja f : (-1, 1) postaci f(x) = .
1+|x|

1 1
Zadanie 3. Niech n " i niech An = x " | - x ; oraz A = {A1, A2, . . . , A10}.
n
n
2
Dla rodziny zbiorów A wyznaczyć A\ A oraz (A×A). Naszkicować zbiór B Ä…" taki,

że B =( A× A) \ ( A× A).

1 1
Zadanie 4. Niech n " oraz An = x " | 2 - x 2+ , a przy tym niech bÄ™-
n n

dzie A = {A1, A2, . . . , A10}. Dla rodziny zbiorów A wyznaczyć A\ A oraz (A×A).

2
Naszkicować zbiór H Ä…" taki, że H =( A× A) \ ( A× A).
Zadanie 5. Niech [z] oznacza zbiór wszystkich wielomianów zmiennej zespolonej o współczyn-
nikach caÅ‚kowitych. W tym zbiorze definiujemy relacjÄ™ µ w nastÄ™pujÄ…cy sposób:
def
w1(z)µw2(z) Ð!Ò! deg w1(z) deg w2(z) oraz w1(z)|w2(z)
(i) Zbadać czy [z], µ jest dobrym porzÄ…dkiem.
1
(ii) WiedzÄ…c, że O = {O(1 - ) : n " } zbadać, czy [z], µ jest izomorficzny ze
n+1
zbiorem O , ‚" .
Zadanie 6. Niech [z] oznacza zbiór wszystkich unormowanych wielomianów zmiennej
u
zespolonej (tj. o współczynniku 1 przy najwyższej potędze z) o współczynnikach całkowitych.
W tym zbiorze definiujemy relację w następujący sposób:
def
w1(z) w2(z) Ð!Ò! {z "C : w1(z) =0} ‚"{z "C : w2(z) =0}
(i) Zbadać czy [z], jest dobrym porządkiem.
u
(ii) Zbadać, czy [z], jest izomorficzny ze zbiorem {a}" uporządkowaną przez relację
u
prefiksowÄ….
Zadanie 7. Niech oznacza zbiór wszystkich liczb zespolonych całkowitych częściach rze-
czywistej i urojonej. W tym zbiorze definiujemy relacjÄ™ µ w nastÄ™pujÄ…cy sposób:
def
z1µz2 Ð!Ò! |z1| |z2|
(i) Zbadać czy , µ jest dobrym porzÄ…dkiem.
(ii) W przypadku pozytywnej odpowiedzi w punkcie (i), zbadać czy , µ jest izomor-
ficzny ze zbiorem wszystkich trójkątów prostokątnych o bokach, których długości są
liczbami naturalnymi, a porządek określa relacją niewiększości długości przeciwprosto-
kÄ…tnych.
5. RELACJE PORZ
DKUJ
CE 29
u
Zadanie 8. Niech [z] oznacza zbiór wszystkich wielomianów unormowanych (o współ-
czynniku 1 przy najwyższej potędze niewiadomej) nad . W tym zbiorze definiujemy relację
µ w nastÄ™pujÄ…cy sposób:
def
w1(z)µw2(z) Ð!Ò! |{z " : w1(z) =0}| |{z " : w2(z) =0}|
u
(i) Zbadać czy [x], µ jest dobrym porzÄ…dkiem.
u
(ii) W przypadku pozytywnej odpowiedzi w punkcie (i), zbadać czy [x], µ jest izomor-
ficzny ze zbiorem wszystkich ciągów skończonych nad . Symbol (cn) oznacza taki ciąg
k
def
dÅ‚ugoÅ›ci n. Wedy porzÄ…dek okreÅ›la relacja: (am) (bn) Ð!Ò! m n '" ai bi dla
k k
i "{1, 2, . . . m}.
" "
Zadanie 9. Niech \{0} = . Symbol M2×2 ( ) oznacza zbiór macierzy stopnia drugiego
" " "
o wyrazach z . RelacjÄ™ Ä…"M2×2 ( ) ×M2×2 ( ) okreÅ›lamy nastÄ™pujÄ…co:

a11 a12 b11 b12
Ð!Ò! a11|b11 '" a12|b12 '" a21|b21 '" a22|b22.
a21 a22 b21 b22
3
Natomiast symbolem [x] oznaczamy zbiór wielomianów stopnia co najwyżej trzeciego nad
. W tym zbiorze dla u(x) =u3x3 + u2x2 + u1x + u0 oraz w(x) =w3x3 + w2x2 + w1x + w0
definiujemy relacjÄ™ · okreÅ›lonÄ… warunkiem:
u(x)·w(x) Ð!Ò! log (1 + ui) log (1 + wi) dla i "{0, 1, 2, 3}.
" 3
(i) Zbadać czy zbiory M2×2 ( ) , oraz [x], · sÄ… uporzÄ…dkowane i w jaki sposób.
" 3
(ii) Zaproponować wzór funkcji f : M2×2 ( ) , [x], · realizujÄ…cej izomorfizm
między tymi zbiorami i dowieść, że w istocie jest ona izomorfizmem.

(iii) Dla wielomianu w(x) =2x2+x+3 oraz zaproponowanej funkcji f wyznaczyć f-1(w(x))).
3
Zadanie 10. Niech [x] oznacza zbiór wszystkich wielomianów stopnia co najwyżej trze-
ciego nad , zaÅ› µ relacjÄ™ w tym zbiorze takÄ…, że gdy a(x) =a3x3 + a2x2 + a1x + a0 oraz
3
b(x) =b3x3 + b2x2 + b1x + b0 sÄ… elementami [x], to
a(x)µb(x) Ð!Ò! log (1 + ai) log (1 + bi) dla i "{0, 1, 2, 3}.
2
Symbolem oznaczamy zbiór wektorów w rozumianych jako uporządkowane pary
punktów o współrzędnych ze zbioru \{0}. Wzbiorze określamy relację :
1 2 3 4 1 3 2 4
A1(x1, y1), A2(x2, y1) A3(x3, y1), A4(x4, y1) Ð!Ò!x1|x3 '" y1|y1 '" x2|x4 '" y1|y1
1 1 1 1 1 1 1 1
3
(i) Zbadać czy zbiory [x], µ oraz , sÄ… uporzÄ…dkowane i w jaki sposób.
3
(ii) Zaproponować wzór funkcji f : , [x], µ realizujÄ…cej izomorfizm miÄ™dzy tymi
zbiorami i dowieść, że w istocie jest ona izomorfizmem.
5. RELACJE PORZ
DKUJ
CE 30
(iii) Dla wielomianu b(x) =3x3 +5x2 +2x + 1 oraz zaproponowanej funkcji f wyznaczyć

f-1(b(x))).
2
Zadanie 11. W zbiorze par liczb zespolonych " o naturalnej oraz dodatniej części rze-
czywistej i urojonej określamy relację:
x1 + iy1, x2 + iy2 x3 + iy3, x4 + iy4 Ð!Ò!x1|x3 '" y1|y3 '" x2|x4 '" y2|y4.
Natomiast w zbiorze funkcji homograficznych o współczynnikach naturalnych i dodatnich
a2x+b2
"
okreÅ›lamy relacjÄ™ H okreÅ›lamy relacjÄ™ µ takÄ…, że jesli h1(x) =a1x+b1 oraz h2(x) = ,
c1x+d1 c2x+d2
to
h1µh2 Ð!Ò! a1 a2 '" b1 b2 '" c1 c2 '" d1 d2.
2
"
(i) Zbadać czy zbiory , oraz H , µ sÄ… uporzÄ…dkowane i w jaki sposób.
"
2
"
(ii) Zaproponować wzór funkcji f : " , H , µ realizujÄ…cej izomorfizm miÄ™dzy
tymi zbiorami i dowieść, że w istocie jest ona izomorfizmem.
3x+5

(iii) Dla wielomianu h(x) = oraz zaproponowanej funkcji f wyznaczyć f-1(h(x))).
2x+1
2
Zadanie 12. Na płaszczyz
nie dana jest rodzina T = {Tn : n " } trójkątów Tn =

n+1 1 2n+1
OnAnBn, gdzie On =(0, 0), An = , 0 , Bn = , . Natomiast S = {Sn : n " }
n+2 2 n+2
jest rodziną liczb wymiernych dodatnich wyrażających pola trójkątów.
1 1
(i) Wyznaczyć bijekcję f : T - S.
na
(ii) Zbadać czy zbiory T , ą" oraz S, są dobrze uporządkowane.
(iii) Zbadać czy zbiory T , ą" oraz S, są izomorficzne.
(iv) (3 pt) Czy prawdziwa jest równość T , ą" = S, ?
2
Zadanie 13. Na płaszczyz
nie dana jest rodzina T = {Tn : n " } trapezów Tn =

3n+3 3n+4 3n+2 3n+2
OnAnBnCn, gdzie On = (0, 0), An = , 0 , Bn = , , Cn = 0, .
n+2 2n+4 n+1 n+1
Natomiast S = {Sn : n " } jest rodziną liczb wymiernych dodatnich wyrażających pola
trapezów.
1 1
(i) Wyznaczyć bijekcję f : T - S.
na
(ii) Zbadać czy zbiory T , ą" oraz S, są dobrze uporządkowane.
(iii) Zbadać czy zbiory T , ą" oraz S, są izomorficzne.
(iv) Czy prawdziwa jest równość T , ą" = S, ?
2
Zadanie 14. Na płaszczyz
nie dana jest rodzina P = {Pn : n " } prostokątów Pn =

1 1 1
OnAnBnCn, gdzie On = (0, 0), An = 2 - , 0 , Bn = 2 - , 3 - oraz Cn =
n+1 n+1 n+1

1
0, 3 - . Natomiast L = {Ln : n " } jest rodziną liczb wymiernych dodatnich wyraża-
n+1
jących obwody prostokątów rodziny P.
5. RELACJE PORZ
DKUJ
CE 31
1 1
(i) Wyznaczyć bijekcję f : P - L.
na
(ii) Zbadać czy zbiory P, ą" oraz L, są dobrze uporządkowane.
(iii) Zbadać czy zbiory P, ą" oraz L, są izomorficzne.
(iv) Czy prawdziwa jest równość P, ą" = L, ?
1
Zadanie 15. Dany jest zbiór T , gdzie T = {T· : · = '" n "N } oraz
n
n3+1

T· = x, y "R2 : y2 ·nx oraz T· T· Ð!Ò! T· Ä…" T·
m n n m
Zbadać czy T , jest dobrze ufundowany, czy też jest dobrze uporządkowany?
"
Zadanie 16. Dany jest zbiór M, ą" gdzie M = {Mp : p = n2 +1'" n "N } oraz

Mp = x, y "R2 : y px2
Zbadać czy M, ą" jest dobrze ufundowany, czy też jest dobrze uporządkowany?
1
Zadanie 17. Dany jest zbiór B, Ä…" gdzie B = {B² : ² =1 - '" n " } oraz
n2+1

2
B² = x, y " : |x| + |y| ²
Zbadać czy B, ą" jest dobrze ufundowany, czy też jest dobrze uporządkowany?
Zadanie 18. Wykazać, że jeśli A ą"Rjest dowolnym nieprzeliczalnym podzbiorem zbioru
liczb rzeczywistych uporządkowanego przez relację niewiększości   , to A, nie jest
dobrze uporzÄ…dkowany.
Zadanie 19. Zbadać czy A, = B, , jeśli:

1 1
A = 3 - : n "N zaÅ› B = {1, 3}*" 3 - : n "N .
n +1 n +1
Zadanie 20. Pokazać, że:
(i) 1 + É = É;
(ii) 1 + É =2 +É =3 +É =4 +É = . . . = n + É = É;
(iii) É + É = É.

Zadanie 21.
Zadanie 22.
Zadanie 23.
Zadanie 24.
Zadanie 25.
5. RELACJE PORZ
DKUJ
CE 32
Zadanie 26.
Zadanie 27.
Zadanie 28.
Zadanie 29.
Zadanie 30.
Zadanie 31.
Zadanie 32.
Zadanie 33.
Zadanie 34.
Zadanie 35.
Zadanie 36.
Zadanie 37.
Zadanie 38.
Zadanie 39.
Zadanie 40.
Zadanie 41.
Zadanie 42.
Zadanie 43.
Zadanie 44.
Zadanie 45.