SỐ NGUYÊN VÀ SỐ HỮU TỈ
B. Phép qui nạp toán học
Khi ta quan sát không phải một hiện tượng, một tính chất mà cảmột dãy hiện tượng hoặc một dãy tính chất Pnvớin là các sốnguyên dương, ta có thể dùng phép qui nạp toán học để chứng minh Pn đúng với mọin N chỉcần hai bước nhưsau :
Chứng minh Pn đúng vớin =N,
Cho k là một số nguyên dươngkN. Giảsử Pk đúng, chứng minh Pk+1cũngđúng.
Nếu làm được haiđiều trên, ta kết luận Pnđúng với mọin N.
150
Bài toán 5. Cho n Õ.Đặt Xn= 1+ 23 + ... +n3. Chứng minh 2( 1)2
n 4
X n n
Đặt P(n) là“ 2( 1)2 “. Ta thấyP(1) đúng
n 4
X n n GiảsửP(k) đúng với mộtk 1
2 2
3 3 ( 1)
1 2 4
k
X k k k
3 3 3 3 3
1 1 2 ( 1) 1 2 ( 1)
Xk k k k
3
1 ( 1)
k k
X X k
151
2 2
3 3
1
2 2
2 2
( 1) ( 1) ( 1)
4
1( 1) [ 4 4] ( 1) ( 2)
4 4
k k
X X k k k k
k k
k k k
Vậy theo qui nạp toán họcP(n) đúng với mọin 1.
2 2
3 3 ( 1)
1 2 4
k
X k k k
3
1 ( 1)
k k
X X k
152
KỸTHUẬT GIẢI TOÁN 1
Để chứng minh Pnđúng với mọin N chỉcần hai bước nhưsau :
Chứng minh Pn đúng vớin =N,
Cho k là một số nguyên dương kN. Giảsử Pk đúng, chứng minh Pk+1cũngđúng.
Các kỹthuật quan trọng trong phép qui nạp :
Không dùng cùng một ký hiệu cho hai sự việc có thểkhác nhau (QTGT 4).
Đưa các dữ kiện của Pn+1vềdạng các dữkiện của Pn
153
Bài toán 6. Cho m và n là hai sốnguyên dương. Giả sử có một đơn ánh f từ {1, . . . ,m} vào {1, . . . ,n}.
Chứng minh m n.
Ta có thểdùng phép qui nạp toán học theomhoặc theon. Ta lựa chọn phương hướng nhưsau.
Qui nạp theom :
Giảsửkết quả đúng khi m= k : Nếu có mộtđơn ánh f từ {1, . . . , k} vào{1, . . . , n} . Thì k n
Cho mộtđơn ánh g từ {1,. . . , k+1} vào{1,. . . , p}.
Chứng minh k+1p.
154
1. Qui nạp theom :
Giảsửkết quả đúng khim= k : Nếu có mộtđơn ánh f từ{1, . . . , k} vào{1, . . . , n} . Thì k n
Cho mộtđơn ánh g từ {1,. . . , k+1} vào{1,. . . , p}.
Chứng minh k+1p.
2. Qui nạp theon :
Giảsửkết quả đúng khin= q : Nếu có mộtđơn ánh f từ{1, . . . , k} vào{1, . . . , q} . Thì k q
Cho mộtđơn ánh g từ {1,. . . , r} vào{1,. . . , q+1}.
Chứng minh r q+1.
155
Trong cách 1, thu hẹp củagtrên tập {1, . . . , k} cho ta một liên quanđến trường hợpm =k . Trong cách 2, ta không thấy có cách nào nối hai trường hợp n= q vàn= q+1. Vậy ta chọn cách 1.
Qui nạp theom : hiển nhiên kết quả đúng khim= 1.
Giảsửkết quả đúng khim= k : Nếu có mộtđơn ánh f từ{1, . . . , k} vào{1, . . . , n} . Thì k n
Cho mộtđơn ánh g từ {1,. . . , k+1} vào{1,. . . , p}.
Chứng minh k+1p.
156
Nếu cóđơn ánh f từ {1,..., k} vào{1,...,n}. Thì k n Chođơn ánh g từ {1, . . . , k+1} vào {1, . . . , p} . Chứng minh k+1p.
Chođơn ánh g từ {1,. . . , k+1} vào {1, . . . , p} . Chứng minh k p -1.
Theo QTGT 6, ta tập trung vào các khác biệt giữa giả thiết và kết luận. Ta đểý các khác biệt hình nhưcó liên hệvới nhau: kvà k+1. Xét cặp khác biệt dễlàm giống nhau trước : k n và k+1p. Ta viết lại bài toán.
Nếu cóđơn ánh f từ {1,..., k} vào{1,...,n}. Thì k n
157
Chođơn ánh g từ {1,. . . , k+1} vào {1, . . . , p} . Chứng minh k p -1.
Nếu cóđơn ánh f từ {1,..., k} vào{1,...,n}. Thì k n
Theo QTGT 6, ta tập trung vào các khác biệt giữa giả thiết và kết luận. Ta đểý các khác biệt hình như có liên hệvới nhau: kvàk+1. Đểkhắc phục sự khác biệt này, ta dùng ánh xạthu hẹp của gtrên {1,..., k} . Ta có các trường hợp sau:
g({1,...,k}){1,..., p-1 }
g({1, . . . , k}) không chứa trong {1, . . . , p -1} . Trường hợp 1, cókvà p-1, nên hi vọng giải được. Ta xét trường hợp 1 trước.
158
g({1,...,k}){1,..., p-1 }
Nối kết trường hợp k+1 với trường hợp k : xét h là ánh xạthu hẹp của gtrên {1,..., k}.
Chođơn ánh g từ {1,. . . , k+1} vào {1, . . . , p} . Chứng minh k p -1.
Nếu cóđơn ánh f từ{1,..., k} vào{1,...,n}. Thì k n
h là mộtđơn ánh từ{1,..., k} vào {1,..., p-1 }
Nếu cóđơn ánh f từ{1,..., k} vào{1,...,n}. Thì k n k p -1
159
Chođơn ánh g từ {1,. . . , k+1} vào {1, . . . , p} . Chứng minh k p -1.
Nếu cóđơn ánh f từ {1,..., k} vào{1,...,n}. Thì k n
g({1, . . . , k}) không chứa trong {1, . . . , p -1} . Theo QTGT 1, ta làm rõg: cói trong {1, . . . , k} sao chog(i) = p. Vìgđơn ánh, g(k+1) p. Vậy cój trong {1, . . . , p -1} sao cho g(k+1) = j .
1 2 3 i k k+1
1 2 3 J p-1 p
g
160
1 2 3 i k k+1
1 2 3 J p-1 p
g
1 2 3 i k k+1
1 2 3 J p-1 p
g
1 2 3 J p-1 p
v h
Đặtvnhưtrong hình vẽ. Đặth= vg cói trong {1, . . . , k} sao chog(i) = p g(k+1) = j trong {1, . . . , p -1} .
h(i) = j, h(k+1)= p
h(s) = g(s)
s ≠i, k+1
h({1,...,k}){1,..., p-1 } , h đơn ánh k p -1 161
Bài toán 7. Cho m và n là hai sốnguyên dương. Giả sử có một song ánh f từ {1, . . . ,m}vào{1, . . . ,n}.
Chứng minh m =n.
f là mộtđơn ánh từ{1, . . . ,m} vào{1, . . . , n}. Do đó m n
f -1là mộtđơn ánh từ{1, . . . , n} vào{1, . . . , m}. Do đó n m
Dùng kết quảnày, ta có thể định nghĩa “hữu hạn”
162
Dùng kết quảnày, ta có thể định nghĩa “hữu hạn”
Định nghĩa. Cho Alà một tập hợp khác trống, ta nói A có m phần tử nếu và chỉnếu có một song ánh f từ tập hợp 1, 2, 3, , m vàoA. Lúc đó ta nói tập hợp A có hữu hạn phần tử
{1,..., } m {1,...,n}
f A
g g-1 g f-1 o
163
Định nghĩa. Cho Alà một tập hợp khác trống, ta nói
A có n phần tử nếu và chỉnếu có một song ánh f từ tập hợp 1, 2, 3, , n vàoA. Lúc đó ta nói tập hợp A có hữu hạn phần tử.
A là một tập hợpvô hạnđếm được(hoặc vắn tắt là đếmđược) nếu và chỉ nếu có một song ánhf từ Õ vào A.
A là một tập hợpquá lắmđếmđược nếu và chỉnếu A có hữu hạn phần tử hoặc vô hạnđếm được .
A là một tập hợpvô hạn khôngđếm được nếu và chỉnếu Akhông hữu hạn và không vô hạnđếm được .
164
Bài toán 8. Đặt P(Õ) là họ tất cả các tập con của Õ. Chứng minh P(Õ) là một tập vô hạn khôngđếmđược.
Theo QTGT 1, ta làm rõ “tập vô hạn khôngđếm được”: A là vô hạn khôngđếm được nếu và chỉnếu Akhông hữu hạn và không vô hạnđếm được . Theo QTGT 7, ta chia bài toán thành hai phần:
Akhông hữu hạn (1)
Akhông vô hạnđếm được (2)
Ta thấy “hữu hạn” dễhơn “vô hạnđếm được”, nên ta chứng minh (1) trước.
Akhông hữu hạn (1)
P (Õ) { {1}, {2}, . . . , {n} , . . .} : không hữu hạn 165
A = P (Õ) không vô hạnđếm được (2)
Vìđịnh nghĩa “không vô hạnđếm được” không rõ ràng về“vô hạnđếm được”, theo QTGT 8, ta dùng phản chứng với giảthiết phản chứng :
Giảsửcó một song ánh f từ Õ vào A. (3) Theo QTGT 1, ta làm rõ (3). Đặt Bk= f(k) kÕ.
P(Õ) = {B1, B2, B3, . . ., Bk, . . .} (3’) Theo QTGT 1, ta làm rõ (3’) : vì {B1,. . ., Bk, . . .}
luôn luôn chứa trong P(Õ). Nên thực chất (3’) chính là P(Õ) {B1, B2, B3, . . ., Bk, . . .}
Cho E Õ, cói sao choE = Bi (3”)
166
i D nếu i Bi i D nếu i Bi
D ≠Bi với mọi iÕ: mâu thuẩn với (3”)
Theo QTGT 8, ta tìm một DÕmàD Bi với mọi i trong Õ. Đặt tập con Dcủa Õ như sau : cho i trong Õ
Cho E Õ, cói sao cho E = Bi (3”)
167
C. Các tập hợpŸ và–
Cho m và n trong Ù, xét phương trình n= x +m.
n > m : theođịnh nghĩa ta có một sốnguyênr sao chon= m + r . Vậy ta chọn x = r .
n < m : theođịnh nghĩa ta có một sốnguyêns sao chom= n + s. Vậy “m bớt đi s” = n . Trong toán học ta ký hiệu “bớt đi s” là –s .
Phương trình này làm nảy sinh tập hợp cácsốnguyên âm -q : q Õ
ĐặtŸ = - q : q Õ 0 Ù và gọiŸ là tập các sốnguyên.
168
3= x + 1 4=x + 2 5 = x + 3 6=x + 4 7 = x + 5
2 = z + 5 3=z + 6 4 = z + 7 169
Đặt 0.m= m.0 = 0 với mọi mŸ
Mọi số nguyên m có thể viết thành sign(m)m’ với một m’ trongÕ.
Nếu m -q : q Ù ta nóim làmộtsốnguyên âm và viết m < 0, nếum Ùta nóim làmộtsố nguyên dương và viết m > 0.
Với sốnguyên m tađặt sign(m)như sau và gọi đó là dấu của m
1 neáu 0
sign( ) 0 neáu 0
1 neáu 0
m ,
m m ,
m .
170
Trên Ÿ ta có cácđịnh nghĩa sau đây : với mọi m,n,p và qtrongŸ
-m = - sign(m)|m|, m + (-m) = 0, 0 +m =m
m+n= sign(n)[|n|-|m|] nếu sign(m)sign(n), |n||m|
m+n= sign(m)[|m| + |n|] nếu sign(m) = sign(n)
m+n=sign(m)[|m|-|n|] nếu sign(m)sign(n), |m| |n|
0.m = 0
n.m = |m|. |n| nếu sign(m) = sign(n)
n.m = - |m|. |n| nếu sign(m)sign(n)
m > n nếu và chỉ nếu m -n Õ
m n nếu và chỉnếu m =n hoặcm > n. 171
Định lý. Định nghĩa các phép cộng+ và nhân. và quan hệ trongŸ nhưtrên. Ta có với mọi m,n,p, và q trong Ÿ.
(i) m+n=n+m,n.m=m.n và m.(n+p) =m.n+m.p, (ii) là một quan hệthứtự toàn phần trênŸ.
(iii) nếu m n, p q và r 0, thì
m +p n +q và mr nr.
(iv) |m| m
172
Cho n Ÿ\0và m Ÿ, xét phương trình nx =m.
-6.p = 3 -4.p =2 1.q = 2 2q = 4 4.r =2 6.r =3 Phương trình này có thểkhông có nghiệm trongŸ (thí dụ4x =2). Nhưng ta có thểcoi (n,m) nhưlà một nghiệm của nó và xét tập hợp– xác định như sau
m
n
12 34 56
1 2 3 4 5 6 78
-1 -2 -3 -4 -5 -6
y v z
r
173
XétX = (Ÿ \0)Ÿ = (n,m) :nŸ\0và mŸ TrênX tađịnh nghĩa quan hệ R như
sau (n,m)R(n’,m’) n.m’=n’.m
-6.x = 3 -4.x =2
2.y = 2 4.y =4
4.z =2 6.z = 3
Ta chứng minh được R là quan hệtương đương.
Ta đặt – là tập thương X/R.
Ta ký hiệu lớp tươngđương của (n,m) là
và ta gọiđó là một sốhữu tỉ.
m n m
n
12 34 56
1 2 3 4 5 6 78
-1 -2 -3 -4 -5 -6
y v z
r
174
Vì 2.6 =3.4 nên (4,2)R(6,3). Do
đó và
chỉlà một số hữu tỉz.
2 4
3 6
Như vậy một số hữu tỉ có thể được viết ra nhiều dạng khác nhau, mỗi dạng của nó là mộtphân số , trongđómđược gọi làtửsố vànđược gọi làmẫu số.
m n m
n
12 34 56
1 2 3 4 5 6 78
-1 -2 -3 -4 -5 -6
y v z
r
3 , 2 , 1 , 1
2 2 2
r y z v
175
với mọi sốhữu tỉ và với mọi k Õ.
đồng nhất m với với mọimŸ, ta cóŸ–.
nếu thì m Ÿ\0 và ta có thể
xét sốhữu tỉ , ta ký hiệu là p -1. m km
n kn
1 m
m 0 p n n
m n
m
vì (n,m)R (|n|, sign(n)m), ta có thểviết các sốhữu tỉ ởdạng rvới s Õ vàr Ÿ.
s
176
Định nghĩa. Cho các sốhữu tỉ và vớin vàs Õ và m vàr Ÿ. Ta định nghĩa
,
m n
r s
m r ms nr
n s ns m r mr. n s ns m | m |
| |n | n |
nếu và chỉnếu ms nr m r
n s
nếu và chỉnếu ms >nr m r
n s
177
Định lý . Định nghĩa các phép cộng+và nhân. và quan hệ trong– nhưtrên.Ta có với mọi m,n, p và q trong – và p 0
(i) m +n = n +m và m.(n+p) = m.n+m.p, (ii) n.m = m.n và p.p-1 = 1,
(iii)nếu m n và n m, thì m = n,
(iv) nếu m n, p q và r 0, thì m +p n +q và mr nr. Nếu m >n và r > 0, thì mr > nr.
(v) |m| m.
178