2.1. Một số tính chất của quan hệ hai ngôi Định nghĩa 2. Quan hệ hai ngôi S trên tập X gọi là có tính chất: Show
a. Trên tập X 2,3,4,5 xác định các quan hệ sau:S 1 (2,2),(2,3),(3,3),(3,5),(4,2),(4,4),(5,3),(5,5) 2 3 (2,3),(2,4),(3,2),(3,5),(4,2),(4,5),(5,3),(5,4)(2,2),(2,3),(2,4),(3,2),(3,3),(3,4),(4,3),(4,4)SSBiểu diễn các quan hệ đó dưới dạng bảng như sau: S 1 2 3 4 5 2 x x 3 x x 4 x x 5 x x S 1 có tính chất phản xạ, không có tính chất đối xứng vì (4,2) S 1 nhưng (2,4) S 1 , không có tính chất bắc cầu vì (2,3),(3,5) S 1 nhưng (2,5) S 1. S 2 2 3 4 5 2 x x 3 x x 4 x x 5 x x S 2 có tính chất đối xứng, không có tính chất phản xạ vì (2,2) S 2 , không có tính chất bắc cầu vì (2,3),(3,2) S 2 nhưng (2,2) S 2. S 3 2 3 4 5 2 x x x 3 x x x 4 x x 5 S 3 không có tính chất phản xạ vì (5,5) S 3 , không có tính chất đối xứng vì (2,4) S 3 nhưng (4,2) S 3 , không có tính chất bắc cầu vì (4,3),(3,2) S 3 nhưng (4,2) S 3. b. Quan hệ “bằng nhau” trên tập số thực có tất cả các tính chất nói ℝ trên. Thật vậy: Tính chất phản xạ: x , ta luôn có x = xℝ Tính chất đối xứng: x, y , từ x = y kéo theo y = xℝ Tính chất phản đối xứng: hiển nhiên Tính chất bắc cầu: x, y, z , từ x = y và y = z kéo theo x = zℝ c. Quan hệ “có cùng chữ số hàng đơn vị” trên tập hợp có các tínhℕ chất phản xạ, đối xứng, bắc cầu và không có tính chất phản đối xứng. Thật vậy: Có tính chất phản xạ: x , ta luôn có x có cùng chữ số hàng đơn vị với x.ℕ Có tính chất đối xứng: x, y ℕ, x có cùng chữ số hàng đơn vị với y y có cùng chữ số hàng đơn vị với x. Không có tính chất phản đối xứng: Vì với x, y , x = 13, y = 23 là hai sốℕ có cùng chữ số hàng đơn vị nhưng 13 ≠ 23. Có tính chất bắc cầu: x, y, z , xSy và ySz, ta cóℕ xSy x có cùng chữ số hàng đơn vị y (1) và ySz y có cùng chữ số hàng đơn vị z (2) Từ (1) và (2) x có cùng chữ số hàng đơn vị với z xSz d. Quan hệ hai ngôi “” thông thường trên các tập hợp , , , đều có các tính chất phản xạ, phản đối xứng, bắc cầu. e. Trên tập ℕ* định nghĩa quan hệ chia hết “|”: a, b ℕ*, a | b q ℕ, b = aq Quan hệ chia hết trên ℕ* có tính chất phản xạ, phản đối xứng, bắc cầu. Tuy nhiên không có tính chất đối xứng vì 1|2 nhưng 2 | 1. f. Quan hệ bao hàm “” trên tập hợp ( ) X gồm các tập hợp con của tập hợp X tuỳ ý, có ba tính chất: phản xạ, phản đối xứng và bắc cầu. g. Trong tập D gồm các đường thẳng trong một mặt phẳng cho trước, quan hệ “cùng phương” xác định bởi: d 1 , d 2 D, d 1 Sd 2 d 1 cùng phương với d 2 Quan hệ cùng phương trên tập D gồm các đường thẳng trong một mặt phẳng cho trước có tính chất phản xạ, đối xứng và bắc cầu. h. Trong tập D gồm các đường thẳng trong một mặt phẳng cho trước, quan hệ “vuông góc” xác định bởi: d 1 , d 2 D, d 1 Sd 2 d 1 d 2 của X đều thuộc và chỉ thuộc một trong các tập con ấy và các phần tử trong cùng một tập con thì tương đương với nhau. Nghĩa là: 1. a X, [a] ; 2. a, b X, [a] = [b] a ~ b; 3. a, b X, [a] = [b] hoặc [a] [b] = . Chứng minh: 1. a X, a ~ a. Do đó a [a], suy ra [a] . 2. () Giả sử [a] = [b], do a [a] = [b] suy ra a ~ b (1). () Ngược lại, giả sử a ~ b. Khi đó, x [a], x ~ a. Do tính bắc cầu nên suy ra x ~ b, vậy x [b]. Suy ra [a] [b]. Tương tự ta cũng chứng minh được [b] [a]. Do đó, [a ] = [b] (2). Vậy a ~ b suy ra [a] = [b]. 3. Giả sử [a] [b] . Khi đó, c [a] [b], do đó c ~ a và c ~ b. Mà ~ có tính chất đối xứng nên suy ra a ~ c và c ~ b. Áp dụng tính chất bắc cầu của ~, ta có a ~ b. Vậy [a] = [b] (theo Định lý 2.(2) ). Định nghĩa 2. Tập hợp các lớp tương đương xác định bởi quan hệ tương đương ~ gọi là tập thương của tập hợp X và kí hiệu là X /. X / a a X | Ví dụ 2. a. Quan hệ “cùng chữ số hàng đơn vị” trên là quan hệ tương đương ℕ ở Ví dụ 2(b). Quan hệ này có các lớp tương đương sau: 0 = {x | x có chữ số hàng đơn vị là 0}ℕ 1 = {x | x có chữ số hàng đơn vị là 1}ℕ ........................................................ 9 = {x | x có chữ số hàng đơn vị là 9}ℕ và tập thương / “cùng chữ số hàng đơn vị” = { ℕ 0 , 1 ,..., 9 }. b. Với số nguyên n 2 , quan hệ “đồng dư theo modulo n ” là một quan hệ tương đương theo Ví dụ 2(d). Quan hệ này có các lớp tương đương: 0 x | 0(mod ) x n nk k | 1 | 1(mod ) 1| 1 | 1(mod ) 1| x x n nk k n x x n n nk n k Tập thương của tập số nguyên đối với quan hệ “đồng dư theo modun ℤ n ” là / (mod ) n a a | 0,1,2, , 1 n .Qua các ví dụ trên ta có nhận xét rằng: Xuất phát từ một tập hợp đã cho và một quan hệ tương đương trên tập ấy ta xây dựng được một tập hợp mới mà các phần tử là các lớp tương đương. 2. Quan hệ thứ tự 2.3. Quan hệ thứ tự Định nghĩa 2. Quan hệ hai ngôi S trên tập hợp X gọi là quan hệ thứ tự nếu có các tính chất
x A, a x kéo theo a = x (x a kéo theo x = a) Chú ý 2. Nếu phần tử a là phần tử tối đại (tối tiểu) của X mà a A thì a cũng là phần tử tối đại (tối tiểu) của A. Nhưng điều ngược lại không đúng. Tập A có thể có nhiều hoặc không có phần tử tối đại (tối tiểu). Định lý 2. Nếu A là tập con khác rỗng của tập sắp thứ tự X có phần tử lớn nhất (nhỏ nhất) a thì a là phần tử tối đại (tối tiểu) duy nhất của A. Chứng minh: Giả sử a là phần tử lớn nhất (nhỏ nhất) của A. Khi đó, x A, x a (a x). Với x A, giả sử a x (x a) vì có x a (a x) nên x = a. Vậy a là phần tử tối đại (tối tiểu) của A. Giả sử A có 2 phần tử tối đại (tối tiểu) là a và a’. Khi đó do a là phần tử lớn nhất (nhỏ nhất) nên a’ a (a a’). Mặt khác do a’ là phần tử tối đại của A nên từ a’ a (a a’) kéo theo a = a’. Vậy a là phần tử tối đại (tối tiểu) duy nhất. Định lý 2. A là tập con khác rỗng của tập sắp thứ tự toàn phần X có phần tử lớn nhất (nhỏ nhất) a khi và chỉ khi a là phần tử tối đại (tối tiểu) của A. Chứng minh: Theo định lý 2 nếu a là phần tử lớn nhất (nhỏ nhất) thì a là phần tử tối đại ( tối tiểu) Ta chứng minh mệnh đề đảo: Giả sử, a A là phần tử tối đại (tối tiểu) của A. Vì X là tập sắp thứ tự toàn phần nên A cũng là tập sắp thứ tự toàn phần. x A, giả sử a < x ( x < a). Khi đó, với a x (x a) ta suy ra x = a. Mâu thuẫn với a < x (x < a). Vậy x a ( a x). Nghĩa là a là phần tử lớn nhất (nhỏ nhất). Ví dụ 2. a. Trong tập hợp sắp thứ tự với quan hệ ℕ , phần tử 0 là phần tử tối tiểu duy nhất, không có phần tử tối đại. b. Xét tập sắp thứ tự ℕ* với quan hệ “chia hết” phần tử 1 phần tử tối tiểu duy nhất, không có phần tử tối đại. Cho A = {2, 3, 5, 6} và B = {2, 4, 6} là các tập con của tập hợp ℕ* với quan hệ thứ tự là quan hệ chia hết. Tập A có các phần tử tối đại là 5 và 6, các phần tử tối tiểu là 2, 3 và 5. Tập B có phần tử tổi tiểu là 2, các phần tử tối đại là 4 và 6. c. Với tập hợp X tùy ý, tập hợp các tập con (X) của X với quan hệ thứ tự “” X là phần tử tối đại, là phần tử tối tiểu. Các quan hệ nào có tính chất phản xạ, đối xứng, phản đối xứng, bắc cầu? Viết ma trận và vẽ các đồ thị tương ứng. 2. Cho ma trận của các quan hệ sau: 1 1 0 1 0 1 0 0 1 ) 0 1 1 ) 0 1 0 ) 0 1 0 1 0 1 1 0 1 1 0 0 a b c Vẽ đồ thị của các quan hệ trên. Quan hệ nào có tính chất bắc cầu? 2. Quan hệ S trên được định nghĩa bởi: mSn nếu và chỉ nếu m + n = 0 (mod 3) S có tính chất phản xạ, đối xứng, phản đối xứng, bắc cầu không? Vì sao? 2. Với m n , , định nghĩa quan hệ S : mSn nếu m – n lẻ. S có tính chất phản xạ, đối xứng, phản đối xứng, bắc cầu không? Vì sao? 2. Xác định xem quan hệ S trên tập mọi người có tính chất phản xạ, đối xứng, phản đối xứng, bắc cầu không, trong đó ( , ) a b S nếu và chỉ nếu: a) a cao hơn b. b) a và b có cùng ngày sinh. c) a và b cùng tên. d) a và b có cùng một ông. 2. Trên tâp X tất cả các trẻ em xác định quan hệ như sau: ̣ℛ ∀a, b ∈ X, a b ℛ ⇔ a, b có cùng bố và cùng mẹ. a) Chứng minh là quan hêℛ tương đương.̣ b) Kết luân trên có còn đúng không với quan hệ ’ xác định sau đây:̣ℛ ∀a, b ∈ X, a ’b ℛ ⇔ a, b có cùng bố hoăc cùng mẹ.̣ 2. Trong tập x xác định một quan hệ hai ngôi ℝ ℝ S như sau: (x 1 , y 1 ), (x 2 , y 2 ) xℝ ℝ, (x 1 , y 1 ) S (x 2 , y 2 ) x 1 = x 2 a) Chứng minh rằng S là quan hệ tương đương trên xℝ ℝ. b) Xác định lớp tương đương [(a, b)], (a, b) ℝ 2 và tập thương ℝ 2 / S? Hãy biểu diễn hình học tập thương này. 2. Cho X là tập các điểm trên mặt phẳng, O là một điểm trước thuộc X. Trên tập X xác định các quan hệ S 1 , S 2 và S 3 như sau: M, N X, M S 1 N OM = ON M, N X, M S 2 N O, M, N thẳng hàng M, N X \ {O}, M S 3 N O, M, N thẳng hàng Trong các quan hệ ở trên, quan hệ nào là quan hệ tương đương? Tìm tập thương. 2. Trên tập các số tự nhiên xác định các quan hệ S như sau:ℕ a, b ℕ, a S 1 b a, b có ước số chung là p (p không đổi, p 1) a, b ℕ, a S 2 b a + b là số tự nhiên chẵn. Trong các quan hệ ở trên, quan hệ nào là quan hệ thứ tự, quan hệ nào là quan hệ tương đương? Tìm tập thương của các quan hệ tương đương. 2. Trên tâp ̣ ℤ các số nguyên, xác định quan hê * và ̣ ℛ như sau: ∀a, b ∈ ℤ, a * b ⇔ a = b = 0 hoăc a, b cùng dấu.̣ ∀a, b ∈ ℤ, a ℛ b a b (mod 3) (a – b) chia hết cho 3 a) Chứng minh * là quan hê tương đương. Tìm tậ p thương ̣ ℤ /* b) Chứng minh ℛ là quan hê tương đương. Tìm tậ p thương ̣ ℤ / .ℛ 2. Xét quan hệ ≡ (mod 4) trên tập : ℤ a, b ℤ, a ≡ b (mod 4) (a – b) 4 a) Chứng minh ≡ (mod 4) là một quan hệ tương đương trên .ℤ b) Tìm lớp tương đương 3. c) Tìm tập thương của theo ≡ (mod 4).ℤ 2. Xét quan hệ ≡ (mod 7) trên tập : ℤ a, b ℤ, a ≡ b (mod 7) (a – b) 7 a) Chứng minh ≡ (mod 7) là một quan hệ tương đương trên .ℤ b) Tìm lớp tương đương 3. c) Tìm tập thương của theo ≡ (mod 7).ℤ 2. Xét quan hệ hai ngôi ~ trên tập *:
2. Xét quan hệ hai ngôi ~ trên tập :
|
