Quan hệ hai ngôi

Trong toán học, một quan hệ hai ngôi (hay còn gọi là quan hệ nhị phân) trên hai tập AB là một tập các cặp được sắp (a, b), chứa các phần tử a thuộc A và các phần tử b thuộc B. Đó là một tập con của tích Descartes A × B. Nó mã hóa thông tin quan hệ: một phần tử a có liên quan với một phần tử b khi và chỉ khi cặp (a, b) thuộc về một tập hợp. Quan hệ hai ngôi là một dạng quan hệ được nghiên cứu nhiều nhất trong số các quan hệ toán học.[1][2]

Một ví dụ trong quan hệ hai ngôi thường thấy là phép chia hết trên tập số nguyên tố và tập số nguyên ,trong đó mỗi số nguyên p quan hệ với mỗi số nguyên z là bội của p, và không quan hệ với số không chia hết p. Ví dụ như số 2 có quan hệ với -4, 0, 6 nhưng không có quan hệ với các số -1, 9.

Quan hệ hai ngôi được sử dụng trong các lĩnh vực toán học để làm mẫu rất nhiều khái niệm. Ta có các ví dụ như:

Một hàm số cũng có thể được coi là một dạng đặc biệt trong quan hệ hai ngôi [3]. Quan hệ hai ngôi được sử dụng phổ biến trong Khoa học máy tính.

Một quan hệ hai 2 ngôi trên 2 tập XY là một phần tử trong tập lũy thừa X × Y. Bởi tập lũy thừa được xếp thứ tự theo phép chứa. Mỗi mối quan hệ có vị trí trong lưới [4] của các tập con của X × Y.

Bởi các quan hệ là các tập hợp. Ta có thể biến đổi chúng bằng các phép toán trong tập hợp như phép hợp, phép giao và phép bù, thỏa mãn các định luật trong đại số tập hợp. Hơn nữa, ta còn có phép nghịch đảo của quan hệ và phép hợp hàm của quan hệ, thỏa mãn các định luật trong giải tích của quan hệ.[5] Ngoài ra còn có quan hệ ngược và phép hợp quan hệ, hình thành nên giải tích quan hệ, được nghiên cứu trong các sách của Ernst Schroder, Clarence LewisGunther Schmidt.[6]

Trong một số hệ thống trong lý thuyết tiên đề tập hợp, các quan hệ hai ngôi được mở rộng thành các lớp (lớp là dạng tổng quát của tập hợp). Việc mở rộng này cần thiết cho việc mô tả khái niệm "là một phần tử của" hay "là tập con của" trong lý thuyết tập hợp mà không bị vướng với các mâu thuẫn logic như Nghịch lý Russell.

Định nghĩaSửa đổi

Cho hai tập XY, Tích đề các   được định nghĩa   và các phần tử của nó là các cặp được sắp.

Quan hệ hai ngôi R trên tập X và tập Y là tập con của  [2][7] Tập X được gọi là miền[2] hoặc tập đi củaR, tập Y thì được gọi là đối miền hoặc tập đích của R. Tập G biểu diễn quan hệ là tập con của   được gọi là đồ thị của quan hệ hai ngôi. Câu   được đọc là "x có quan hệ R với y" và ký hiệu là xRy.[5][6][8][note 1] Miền xác định[2] của R là tập các giá trị x sao cho xRy với ít nhất 1 giá trị y. Đối miền xác định hay còn được gọi là [2] ảnh hoặc miền giá trị của R là tập các giá trị y sao cho xRy với ít nhất 1 giá trị x. Trường của R là hội của miền xác định và đối miền xác định.[10][11][12]

Khi   thì quan hệ hai ngôi được gọi là quan hệ thuần nhất. Ngược lại thì quan hệ được gọi là quan hệ không thuần nhất.[13][14][15]

Cần để ý đến thứ tự của phần tử trong quan hệ hai ngôi bởi nếu   thì giá trị đúng sai của yRx không phụ thuộc vào xRy. Để lấy ví dụ: 9 chia hết cho 3 nhưng 3 không có chia hết cho 9.

Các ví dụSửa đổi

Ví dụ 2
A
B
cốc bát đũa thìa
W +
X +
Z +
Ví dụ 1
A
B
cốc bát đũa thìa
W +
X +
Y
Z +

1) Ví dụ sau cho thấy tầm quan trọng trong việc chọn đối miền. Giả sử ta có tập 4 vật thể   và tập 4 bạn   Giả sử quan hệ giữa AB là "được sở hữu bởi" cho như sau:   Nghĩa là W sở hữu cái cốc, X thì có cái bát còn Z thì sở hữu cái thìa. Không ai sở hữu cái đũa và Y thì không sở hữu cái gì cả, xem ví dụ 1. Bởi trong tập R không có Y nên tập R có thể được xem là tập con của   hay nói cách khác mối quan hệ giữa A  xem ví dụ 2. Ví dụ 2 có tính toàn ánh (xem dưới) trong khi ví dụ 1 thì không.

 
Các đại dương và châu lục (ẩn các đảo)
Đại dương kề châu lục
NA SA AF EU AS AU AA
Ấn độ dương 0 0 1 0 1 1 1
Nam đại dương 1 0 0 1 1 0 0
Bắc băng dương 1 1 1 1 0 0 1
Thái bình dương 1 1 0 0 1 1 1

2) Đặt A = {Ấn độ dương, Nam đại dương, Bắc băng dương, Thái bình dương} là tập đại dươngB = { NA, SA, AF, EU, AS, AU, AA }, tập các châu lục. Giả sử aRb là quan hệ a kề với b. Khi đó ma trận logic của quan hệ này là:

 

Tính kết nối của trái đất có thể xem qua R RTRT R, cái đầu là quan hệ phổ dụng   trên A (  hoặc ma trận logic bao gồm toàn giá trị 1). Quan hệ phổ dụng này phản ánh mỗi đại dương đều cách các đại dương khác ít nhất 1 châu lục. Mặt khác, RT R là quan hệ trên   nhưng không phổ dụng bởi phải đi qua ít nhất hai đại dương để đi từ châu Âu đến châu Úc.

3) Ta có thể biểu diễn các quan hệ hai ngôi bằng đồ thị: Đối với các quan hệ trên cùng 1 tập (quan hệ thuần nhất), đồ thị có hướng thường được dùng để mô tả quan hệ , trong trường hợp quan hệ đó là quan hệ đối xứng thì có thể dùng đồ thị không hướng. Đối với quan hệ không thuần nhất, siêu đồ thị có cạnh có thể nối nhiều hơn hai nút có thể biểu diễn bằng đồ thị hai phía.

Clique là phần không thể thiếu khi xét các quan hệ thuần nhất, còn clique hai chiều thì được dùng khi xét các quan hệ không thuần nhất; thật vậy, "dựa vào" đó ta có thể sinh ra lưới của quan hệ.

 
Các trục t biểu diễn thời gian cho người xem đang trong trạng thái di chuyển, các trục x tương ứng là các dòng xảy ra đồng thời

4) Trực giao hyperbol: Thời gian và không gian là hai phạm trù khác nhau với các tính chất thời gian phân biệt với không gian. Ý tưởng của việc sự việc đồng thời khá đơn giản trong không gian và thời gian tuyệt đối bởi mỗi thời điểm t ta xác định đồng thời một siêu phẳng trong vũ trụ đó. Herman Minkowski thay đổi ý tưởng trên bằng việc đưa ra khái niệm đồng thời tương đối, cái mà chỉ tồn tại khi các sự kiện không gian "chuẩn tắc" với thời gian được đặc trưng bởi vận tốc. Ông sử dụng một tích nội không giới hạn và chỉ ra rằng vecto thời gian chuẩn tắc với vecto không gian khi tích đó bằng không. Tích nội không giới hạn trong đại số hợp được tính như sau:

  trong đó thanh ngang trên đầu hiển thị liên hợp.

Nếu ta xét quan hệ hai ngôi giữa sự kiện thời gian và sự kiện không gian, trực giao hyperbol (cũng được tìm thấy trong số tách phức) là quan hệ không thuần nhất [16]

Các dạng đặc biệt của quan hệSửa đổi

 
Ví dụ của 4 dạng quan hệ hai ngôi trên tập số thực: 1-1 (màu xanh lá cây), 1-nhiều (xanh dương), nhiều-1 (màu đỏ), nhiều-nhiều (màu đen).

Một số dạng quan trọng của quan hệ R trên tập XY là:

  • Nội xạ (cũng được gọi là duy nhất trái):[17] với mọi    nếu xRyzRy thì x = z. Đối với quan hệ như vậy, {Y} được gọi là khóa chính của R.[2] Ví dụ như, quan hệ xanh lá và xanh dương trong biểu đồ có tính nội xạ, nhưng màu đỏ thì không (bởi −1 và 1 quan hệ với 1), và màu đen cũng không bởi (−1 và 1 quan hệ với 0).
  • Phiếm hàm (cũng được gọi là duy nhất phải,[17][18]):[8] với mọi   và tất cả   nếu xRyxRz thì y = z. Quan hệ hai ngôi như vậy được gọi là bán hàm. Trong quan hệ đó,   được gọi là khóa chính của R.[2] Ví dụ như, quan hệ màu xanh là và màu đỏ có tính phiếm hàm nhưng không phải màu xanh dương bởi (1 quan hệ với cả −1 và 1) và màu đen cũng không bởi (0 quan hệ với −1 và 1).
  • 1-1: nội xạ và phiếm hàm.
  • 1-Nhiều: nội xạ nhưng không phiếm hàm.
  • Nhiều-1: phiếm hàm nhưng không nội xạ.
  • Nhiều-nhiều: không phiếm hàm cũng không nội xạ.

Quan hệ thuần nhấtSửa đổi

Quan hệ thuần nhất trên tập X là quan hệ hai ngôi giữa X với chính nó hay tập quan hệ là tập con của tích decac  [15][19][20] Người ta thường gọi ngắn đi là quan hệ trên X.

Quan hệ thuần nhất R trên tập X có thể được xét bằng đồ thị có hướng cho phép vòng, với X là tập đỉnh và R là tập các cạnh (có cạnh giữa đỉnh x với đỉnh y nếu xRy). Tập tất cả các quan hệ hai ngôi   trên tập Xtập lũy thừa  , hay còn là đại số Boolean đi kèm với hàm tự nghịch đảo ánh xạ một quan hệ sang quan hệ ngược của nó. Xét việc hợp quan hệ làm phép toán hai ngôi trên  , nó tạo thành nửa nhóm với hàm tự nghịch đảo.

Một số tính chất quan trọng của quan hệ thuần nhất R trên tập X là:

  • Phản xạ: với   xRx. Ví dụ,   là quan hệ phản xạ nhưng > thì không.
  • Không phản xạ: với mọi   không xRx.Ví dụ,   là quan hệ không phản xạ nhưng   thì phản xạ.
  • Đối xứng: với mọi   nếu xRy thì yRx. Ví dụ, "là họ hàng của" là quan hệ đối xứng.
  • Phản đối xứng: với mọi   nếu xRyyRx thì   Ví dụ,   là quan hệ phản đối xứng.[21]
  • Không đối xứng: với mọi   nếu xRy thì không yRx. Quan hệ không đối xứng khi và chỉ khi nó không phản xạ và phản đối xứng.[22] Ví dụ, > là quan hệ không đối xứng, nhưng   thì không.
  • Bắc cầu: với mọi   nếu xRyyRz thì xRz. Quan hệ có tính bắc cầu mang thêm tính không phán xạ khi và chỉ khi nó bán đối xứng.[23] Ví dụ, "là tổ tiên của" là quan hệ bắc cầu nhưng "là cha mẹ của" thì không.
  • Liên thông: với mọi   nếu   thì xRy hoặc yRx.
  • Liên thông mạnh: với   xRy hoặc yRx.

Chú thíchSửa đổi

  1. ^ Trong một số ngữ cảnh khi tác giả phải xét quan hệ hai ngôi là trường hợp đặc biệt của quan hệ n-ngôi với n tùy ý thường viết Rxy là trường hợp đặc biệt của Rx1...xn (Kí pháp Ba Lan).[9]

Tham khảoSửa đổi

  1. ^ “The Definitive Glossary of Higher Mathematical Jargon — Relation”. Math Vault (bằng tiếng Anh). ngày 1 tháng 8 năm 2019. Truy cập ngày 11 tháng 12 năm 2019.
  2. ^ a b c d e f g Codd, Edgar Frank (tháng 6 năm 1970). “A Relational Model of Data for Large Shared Data Banks” (PDF). Communications of the ACM. 13 (6): 377–387. doi:10.1145/362384.362685. S2CID 207549016. Truy cập ngày 29 tháng 4 năm 2020.
  3. ^ “Relation definition - Math insight”. mathinsight.org. Truy cập ngày 11 tháng 12 năm 2019.
  4. ^ Không nhầm lẫn với lưới trong lý thuyết nhóm.
  5. ^ a b Ernst Schröder (1895) Algebra und Logic der Relative, via Internet Archive
  6. ^ a b C. I. Lewis (1918) A Survey of Symbolic Logic , pages 269 to 279, via internet Archive
  7. ^ Enderton 1977, Ch 3. pg. 40
  8. ^ a b Gunther Schmidt, 2010. Relational Mathematics. Cambridge University Press, ISBN 978-0-521-76268-7, Chapt. 5
  9. ^ Hans Hermes (1973). Introduction to Mathematical Logic. Hochschultext (Springer-Verlag). London: Springer. ISBN 3540058192. ISSN 1431-4657. Sect.II.§1.1.4
  10. ^ Suppes, Patrick (1972) [originally published by D. van Nostrand Company in 1960]. Axiomatic Set Theory. Dover. ISBN 0-486-61630-4.
  11. ^ Smullyan, Raymond M.; Fitting, Melvin (2010) [revised and corrected republication of the work originally published in 1996 by Oxford University Press, New York]. Set Theory and the Continuum Problem. Dover. ISBN 978-0-486-47484-7.
  12. ^ Levy, Azriel (2002) [republication of the work published by Springer-Verlag, Berlin, Heidelberg and New York in 1979]. Basic Set Theory. Dover. ISBN 0-486-42079-5.
  13. ^ Schmidt, Gunther; Ströhlein, Thomas (2012). Relations and Graphs: Discrete Mathematics for Computer Scientists. Springer Science & Business Media. Definition 4.1.1. ISBN 978-3-642-77968-8.
  14. ^ Christodoulos A. Floudas; Panos M. Pardalos (2008). Encyclopedia of Optimization (ấn bản 2). Springer Science & Business Media. tr. 299–300. ISBN 978-0-387-74758-3.
  15. ^ a b Michael Winter (2007). Goguen Categories: A Categorical Approach to L-fuzzy Relations. Springer. tr. x–xi. ISBN 978-1-4020-6164-6.
  16. ^   Relative simultaneity tại Wikibooks
  17. ^ a b Lỗi chú thích: Thẻ <ref> sai; không có nội dung trong thẻ ref có tên kkm
  18. ^ Mäs, Stephan (2007), “Reasoning on Spatial Semantic Integrity Constraints”, Spatial Information Theory: 8th International Conference, COSIT 2007, Melbourne, Australia, September 19–23, 2007, Proceedings, Lecture Notes in Computer Science, 4736, Springer, tr. 285–302, doi:10.1007/978-3-540-74788-8_18
  19. ^ M. E. Müller (2012). Relational Knowledge Discovery. Cambridge University Press. tr. 22. ISBN 978-0-521-19021-3.
  20. ^ Peter J. Pahl; Rudolf Damrath (2001). Mathematical Foundations of Computational Engineering: A Handbook. Springer Science & Business Media. tr. 496. ISBN 978-3-540-67995-0.
  21. ^ Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2006), A Transition to Advanced Mathematics (ấn bản 6), Brooks/Cole, tr. 160, ISBN 0-534-39900-2
  22. ^ Nievergelt, Yves (2002), Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography, Springer-Verlag, tr. 158.
  23. ^ Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Transitive Closures of Binary Relations I (PDF). Prague: School of Mathematics – Physics Charles University. tr. 1. Bản gốc (PDF) lưu trữ ngày 2 tháng 11 năm 2013. Lemma 1.1 (iv). This source refers to asymmetric relations as "strictly antisymmetric".

SáchSửa đổi

Liên kết ngoàiSửa đổi