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:
- phản xạ nếu với mọi x X , ta có xSx
- đối xứng nếu với mọi x y X xSy , , kéo theo ySx.
- phản đối xứng nếu với mọi x y X xSy , , và ySx kéo theo x y .
- bắc cầu nếu với mọi x y z X xSy , , , và ySz kéo theo xSz. Ví dụ 2.
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]
S
S
Biể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
- Phản xạ: x X, x S x
- Phản đối xứng: x, y X, x S y và y S x x = y
- Bắc cầu: x, y, z X, x S y và y S z x S z. Ví dụ 2.
- Quan hệ hai ngôi “” thông thường trên các tập hợp , , , ở Ví dụ 2[c] là một quan hệ thứ tự. b. Quan hệ chia hết “|” ở Ví dụ 2[d] là quan hệ thứ tự trên tập ℕ*. c. 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ỳ ý ở Ví dụ 2[e] là quan hệ thứ tự. Chú ý 2. Quan hệ chia hết là quan hệ thứ tự trên * nhưng không phải là quan hệ thứ tựℕ trên [vì 0 không thể là ước của 0 nên quan hệ chia hết trên khôngℕ ℕ có tính chất phản xạ] và cũng không phải là quan hệ thứ tự trên .ℤ Quan hệ ≤ [nhỏ hơn hay bằng] thông thường trong các tập hợp số là quan hệ thứ tự. Đây là một quan hệ thứ tự điển hình đến nỗi người ta mượn kí hiệu “≤” để chỉ thứ tự ngay cả trong trường hợp tổng quát. Trong trường hợp tổng quát x ≤ y không nhất thiết mang ý nghĩa thông thường. Vì vậy, quan hệ thứ tự thường kí hiệu là “” [đọc là “nhỏ hơn hoặc bằng”]. Để tránh nhầm lẫn, khi nào quan hệ “≤” mang ý nghĩa thông thường thì ta sẽ nói rõ. x, y X, kí hiệu: x y y x và đọc là “y lớn hơn hoặc bằng x” x < y x y và x y và đọc là “x nhỏ hơn y”, “x đứng trước y” hay “x thực sự nhỏ hơn y” Nếu có x < y ta còn có y > x và đọc là ”y lớn hơn x” Chú ý rằng quan hệ “