Quan hệ - Quan hệ 2 ngôi

Quan hệQuan hệ 2 ngôiCho một tập hợp X khác rỗng. Một quan hệ 2 ngôi trên X là một tập hợp con R của X2. Cho 2 phần tử x và y của X, ta nói x có quan hệ R với y khi và chỉ khi (x,y)  R, và viết là x R y x R y  (x,y)  RKhi x không có quan hệ R với y, ta viết:Ví dụTrên tập hợp X = { 1,2,3,4} , xét quan hệ 2 ngôi R được định nghĩa bởi: R = { (1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (4,2), (4,4)} Trên tập hợp các số nguyên Z ta định nghĩa một quan hệ 2 ngôi R như sau: x R y nếu và chỉ nếu x-y là số chẳn. (R = { (x,y)  Z2 : x-y = 2k với k  Z } )∀x, y ∈ R, xRy ⇔ |x| = |y|∀x, y ∈ Q, xRy ⇔ x ≤ y∀x, y ∈ Z, xRy ⇔ a – b chia hết cho n x ≡ y (mod n). Quan hệNgười ta còn định nghĩa một quan hệ (2 ngôi) giữa một tập hợp A và một tập hợp B là một tập hợp con của AxB.Tổng quát hơn, ta có thể định nghĩa một quan hệ giữa các tập hợp A1, A2, . . ., An là một tập hợp con của A1 x A2 x . . . x An. Như vậy, khi R là một quan hệ giữa các tập A1, A2, . . ., An thì mỗi phần tử của R là một bộ n (a1, a2, . . ., an) với ai  Ai (i=1, , n).Xác định một quan hệLiệt kê: liệt kê tất cả các cặp hay bộ phần tử có quan hệ R (tức là thuộc R)Nêu tính chất đặc trưng cho quan hệ R, tức là tính chất hay tiêu chuẩn để xác định các phần tử thuộc R hay khôngCác tính chất của quan hệ 2 ngôiGiả sử R là một quan hệ 2 ngôi trên một tập hợp XTa nói quan hệ R có tính phản xạ (reflexive) nếu và chỉ nếu x R x với mọi x  X.Ta nói quan hệ R có tính đối xứng (symmetric) nếu và chỉ nếu x R y  y R x với mọi x,y  XTa nói quan hệ R có tính phản xứng (antisymmetric) nếu và chỉ nếu (x R y và y R x)  x = y với mọi x,y  X.Ta nói quan hệ R có tính truyền hay bắc cầu (transitive) nếu và chỉ nếu (x R y và y R z)  x R z với mọi x,y,z  XVí dụQuan hệ  trên tập hợp các số thựcTrên tập hợp X = { 1,2,3,4} , xét quan hệ 2 ngôi R được định nghĩa bởi: R = { (1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (4,2), (4,4)} Trên tập hợp các số nguyên Z ta định nghĩa một quan hệ 2 ngôi R như sau: x R y nếu và chỉ nếu x-y là số chẳnBiểu diễn quan hệ 2 ngôi dưới dạng ma trậnGiả sử R là một quan hệ 2 ngôi giữa một tập hợp hữu hạn A = { a1, a2, ... , am} và một tập hữu hạn B = { b1, b2, ... , bm}Quan hệ R có thể được biểu diễn bởi ma trận MR = [mij] gồm m dòng và n cột (tức là ma trận cấp mxn):mij = 1 nếu (ai , bj)  Rmij = 0 nếu (ai , bj) Ï RQuan hệ tương đươngMột quan hệ 2 ngôi R trên một tập hợp X được gọi là một quan hệ tương đương nếu và chỉ nếu nó thỏa 3 tính chất: phản xạ, đối xứng, truyền.Lớp tương đương và tập hợp thươngVới mỗi phần tử xX, ta định nghĩa lớp tương đương chứa x, ký hiệu , là tập hợp tất cả những phần tử (thuộc X) có quan hệ R với xTập hợp các lớp tương đương của quan hệ tương đương R trên X này (là một tập con của P(X)) được gọi là tập hợp thương (của quan hệ tương đương R trên X)Quan hệ thứ tựMột quan hệ 2 ngôi R trên một tập hợp X (khác rỗng) được gọi là một quan hệ thứ tự (hay vắn tắt, là một thứ tự) nếu và chỉ nếu nó có 3 tính chất: phản xạ, phản xứng, truyềnKhi đó ta cũng nói tập hợp X là một tập có thứ tựNếu có thêm tính chất: với mọi x, y  X ta có xRy hay yRx thì ta nói R là một quan hệ thứ tự toàn phần trên X.Quan hệ thứ tựNếu trên X có nhiều quan hệ thứ tự thì khi xét đến thứ tự trên X ta phải nói rõ thứ tự nào, và ta thường viết tập hợp X có thứ tự dưới dạng một cặp (X,R); trong đó R là quan hệ thứ tự đang xét trên XNếu (X,R) là một tập hợp có thứ tự và A  X thì quan hệ thứ R thu hẹp trên tập A, cũng được ký hiệu là R (nếu không gây ra nhầm lẫn), là một quan hệ thứ tự trên A (X,R) thứ tự và A  X (A,R) thứ tựVí dụQuan hệ nhỏ hơn hay bằng ≤ Cho tập hợp E ≠ ∅. Trên tập hợp P(E) ta xét quan hệ: ∀A, B ∈ P(E), A R B ⇔ A ⊂ B Trên tập N các số tự nhiên ta định nghĩa quan hệ ước số xRy ⇔ x|y x|y có nghĩa x là một ước của y, hay y chia hết cho xVí dụUn= {aN: a|n} với quan hệ R: xRy  x|yUn={ .. }R={.}Ví dụUn= {aN: a|n} với quan hệ R: xRy  x|yU12={ 1,2,3,4,6,12}R={{1,1},{1,2} ,{1,3} ,{1,4} ,{1,6} ,{1,12}, {2,2},{2,4},{2,6},{2,12},{3,3},{3,6}, {3,12},{4,4},{4,12},(6,6}{6,12}, {12,12}}Trội, trội trực tiếpXét một tập hợp có thứ tự (X, ) và x, y là 2 phần tử bất kỳ của X. Khi đó ta nói:y trội x hay x được trội bởi y nếu x ≤ y y là trội trực tiếp của x nếu y ≠ x, y trội x và không tồn tại một trội z của x sao cho x < z < yQuan hệ thứ tựCho (X,  ) là một tập hợp có thứ tự, và A  Xa  A là một phần tử nhỏ nhất của tập hợp A  x  A ta có : a  xa  A là một phần tử lớn nhất của tập hợp A  x  A ta có : x  aa  A là một phần tử tối tiểu của tập hợp A  không tồn tại x  A sao cho x  a và x  aa  A là một phần tử tối đại của tập hợp A  không tồn tại x  A sao cho x  a và a  xQuan hệ thứ tựXet tập A = {1,2,3,4} với quan hệ R: xRy  x|yPhần tử nhỏ nhất là 1 (vì 1 là ước của tất cả các phần tử của A)Phần tử tối tiểu là 1 (vì không có phần tử nào là ước của 1)Phần tử tối đại là 3, 4 (vì 3, 4 không là ước của phần tử nào khác nó trong A)Phần tử lớn nhất không có Ví dụxét tập hợp X = { 1,2,3} với quan hệ 2 ngôi r được cho bởi r = { (1,1), (2,2), (3,3), (1,2), (3,2)}Trong tập hợp có thứ tự (Z ,  ),  tập hợp A = { m Z| m2 < 100}Trong tập hợp có thứ tự (R,  ), tập hợp A = { x  R| x2 < 100}Quan hệ thứ tựPhần tử nhỏ nhất (lớn nhất) của một tập hợp, nếu có, là duy nhất.Ta ký hiệu phần tử nhỏ nhất của một tập hợp A là min A hay min (A), và ký hiệu phần tử lớn nhất của A là max A hay max (A).Phần tử tối tiểu (tối đại) của một tập hợp có thứ tự không nhất thiết là duy nhấtPhần tử lớn nhất (nhỏ nhất) của một tập hợp, nếu có, là phần tử tối đại (tối tiểu) duy nhất của tập hợp đóQuan hệ thứ tự - chận dướiCho (X,  ) là một tập hợp có thứ tự, và A  XTa gọi một phần tử x  X là một chận dưới của tập hợp A nếu và chỉ nếu với mọi a  A ta có : x  aChận dưới lớn nhất (nếu có), tức là phần tử lớn nhất trong tập hợp tất cả những chận dưới của A được ký hiệu là inf (A)Quan hệ thứ tự - chận trênCho (X,  ) là một tập hợp có thứ tự, và A  XTa gọi một phần tử x  X là một chận trên của tập hợp A nếu và chỉ nếu với mọi a  A ta có : a  xChận trên nhỏ nhất (nếu có), tức là phần tử nhỏ nhất trong tập hợp tất cả những chận trên, của A được ký hiệu là sup (A)Thứ tự tốtMột tập hợp có thứ tự được gọi là có thứ tự tốt (hay được sắp tốt) nếu và chỉ nếu mọi tập con khác rỗng đều có phần tử nhỏ nhất.Tập hợp có thứ tự (N,  ) là một tập hợp được sắp tốt.Tập hợp có thứ tự (Z,  ) không phải là một tập hợp được sắp tốt vì Z không có phần tử nhỏ nhất.Biểu đồ Hasse Biểu đồ Hasse của một tập hợp hữu hạn có thứ tự (X, ≤) bao gồm:Một tập hợp các điểm trong mặt phẳng tương ứng 1-1 với X, gọi là các đỉnh.Một tập hợp các cung có hướng nối một số đỉnh: hai đỉnh x, y được nối lại bởi một cung có hướng từ x tới y nếu y là trội trực tiếp của xBiểu đồ Hasse của U12 = {x ∈ N : x|n} Với E = {a, b, c} thì biểu đồ Hasse của (P(E), ⊂) có dạng:Biểu đồ Hasse của {1, 2, 3, 4, 5} với thứ tự thông thường có dạng của một dây chuyền:DànCho (L,  ) là một tập hợp có thứ tự. Ta nói (L,  ) là một dàn nếu và chỉ nếu với mọi a, b  L, tập hợp { a,b} có chận dưới lớn nhất và có chận trên nhỏ nhất; tức là tồn tại sup(a,b) và inf(a,b)Ký hiệu ab và a  b để chỉ sup(a,b) và inf(a,b)a  b = sup(a,b)a  b = inf(a,b)Ví dụTập hợp có thứ tự toàn phần là một dàn, với a  b = max(a,b) và a  b = min(a,b).Trong dàn (L,  ), phần tử sup(a,b) = a  b được đặc trưng bởi 2 tính chất sau:a  a  b và b  a  b  c L : (a  c và b  c)  (a  b  c)Trong dàn (L,  ), phần tử inf(a,b) = a  b được đặc trưng bởi 2 tính chất sau:a  b  a và a  b  b c L : (c  a và c  b)  (c  a  b )Ví dụCho E là một tập hợpTập hợp (P(E),  ) là một dàn.Với mọi A, B  P(E), ta thấy A B và A B lần lượt chính là chận trên nhỏ nhất và chận dưới lớn nhất theo thứ tự  A  B = A B A  B = A B Ví dụ(N,| ) là một tập hợp có thứ tự (|: chia hết)Với 2 số tự nhiên a và b:chận trên nhỏ nhất chính là bội số chung nhỏ nhất của chúngchận dưới lớn nhất chính là ước số chung lớn nhất của chúngVậy (N,| ) là một dànVí dụ 3Các tập hợp có thứ tự được biểu diễn bởi các biểu đồ Hasse trong hình dưới đây có phải là dàn hay không:Dàn conCho (L,  ) là một dàn và B là một tập hợp con của LB là một dàn con của L khi và chỉ khi với mọi a,b  B ta có a  b  B và a  b  BVí dụXem dàn L có biểu đồ Hasse như sau:Đồng cấu dànCho (L,  ) và (M,  ) là các dànMột ánh xạ f : L  M được gọi là một đồng cấu dàn nếu và chỉ nếu " x,y  L : x  y  f(x)  f(y)Trường hợp f có thêm tính chất song ánh thì ta nói f là một đẳng cấu dànf : L  M là một đẳng cấu dàn thì với mọi x, y  L:f (x  y) = f(x)  f(y)f (x  y) = f(x)  f(y)Ví dụXem hai dàn L và M có biểu đố Hasse:Ánh xạ f : L  M được định nghĩa bởi : f(1) = b, f(2) = e, f(3) = c, f(4) = v là một đồng cấu dàn.Ánh xạ g : L  M được định nghĩa bởi :g(1) = a, g(2) = b, g(3) = d, g(4) = vkhông phải là một đồng cấu dàn vì g(2)  g(3) = b  d = c, mà g(23) = g(4) = v  c.Tính chất của dàn 1Với mọi phần tử x, y, z thuộc dàn (L,  ) ta cóx  x = x , x  x = x (tính lũy đẳng)x  y = y  x , x  y = y  x (tính giao hoán)x  (y  z) = (x  y)  z (tính kết hợp) x  (y  z) = (x  y)  zx  y  (x  y = y)  (x  y = x)x  (x  y) = x = x  (x L y)Tính chất của dàn 2Với mọi phần tử a, b, c, d thuộc dàn (L,  ) ta có (a  b)  (a  c  b  c và a  c  b  c)(a  b và c  d)  (a  c  b  d và a  c  b  d)Tính chất của dàn 3Với mọi phần tử x, y, z thuộc dàn (L,  ) ta có :x  (y  z)  (x  y)  (x  z)x  (y  z)  (x  y)  (x  z)(x  z)  x (y  z)  (x  y)  z Tóm lạiMột quan hệ 2 ngôi trên X là một tập hợp con R của X2 Quan hệ tương đương: phản xạ, đối xứng và truyền hay bắc cầu.Quan hệ thứ tự: phạn xạ, phản xứng và bắc cầu.Cho (L,  ) là một tập hợp có thứ tự. Ta nói (L,  ) là một dàn nếu và chỉ nếu với mọi a, b  L, tập hợp { a,b} có chận dưới lớn nhất và có chận trên nhỏ nhất; tức là tồn tại sup(a,b) và inf(a,b)Câu hỏiTập các số tự nhiên N với quan hệ đồng dư có phải là quan hệ tương đương hay không tại sao?U12= {aN: a|12} với quan hệ R: xRy  x|y có phải là tập sắp thứ tự hay không tại sao?Vẽ biều đồ Hasse của tập hợp U12 trên.Cho biết tập hợp U12 trên có phải là một dàn không tại sao?