Wikipedia

Quan hệ bắc cầu

Trong toán học, một quan hệ hai ngôi R trên tập hợp X được gọi là có tính bắc cầu (hay còn đựoc gọi là tính chuyển tiếp, tính truyền ứng) khi và chỉ khi điều kiện sau đây được thỏa mãn: nếu một phần tử a có quan hệ với một phần tử b, và phần tử b có quan hệ với phần tử c; thì phần tử a có quan hệ với phần tử c.[1]

Định nghĩa sửa

Quan hệ thuần nhất R trên tập hợp X là quan hệ bắc cầu nếu:[2]

với mọi a, b, c ∈ X, nếu a R b và b R c, thì a R c.

Nếu viết theo ngôn ngữ logic bậc nhất thì:

 ,

Các ví dụ sửa

Ví dụ không dùng toán học sau: quan hệ "là tổ tiên của" là quan hệ bắc cầu. Ví dụ, nếu An là tổ tiên của Bình, và Bình là tổ tiên của Cường, thì An cũng là tổ tiên của Cường.

Mặt khác, "là người đẻ ra" không phải là quan hệ bắc cầu, vì kể cả An đẻ ra Bình, Bình đẻ ra Cường, thì không có nghĩa An là người đẻ ra Bình. Hơn nữa, tính chất này còn được gọi là phản bắc cầu bởi An sẽ không bao giờ đẻ ra Cường.

Các quan hệ "lớn hơn", "lớn hơn hoặc bằng", và "bằng với" là các quan hệ bắc cầu trên rất nhiều tập, trong đó bao gồm tập số thực và số hữu tỉ:

nếu x > y và y > z, thì x > z
nếu x ≥ y và y ≥ z, thì x ≥ z
nếu x = y và y = z, thì x = z.

Các ví dụ khác về tính bắc cầu:

Các ví dụ của quan hệ không bắc cầu là:

Quan hệ rỗng trên bất cứ tập   đều có tính bắc cầu [4][5] bởi không có 3 phần tử   sao cho   và  . Quan hệ R chỉ chứa duy nhất một cặp được sắp cũng được coi là có tính bắc cầu bởi: nếu cặp đó có dạng   với   thì chỉ có đúng một bộ   có quan hệ là  , và do vậy  , nếu cặp đó không có dạng   thì không có bộ   sao cho   và  , do vậy quan hệ đó vẫn được coi là tính bắc cầu vì chưa đủ số phần tử để xét.

Tính chất sửa

Tính bao đóng sửa

  • Quan hệ ngược (hay nghịch đảo) của quan hệ bắc cầu là quan hệ bắc cầu. Áp dụng ví du, bởi quan hệ "là tập con của" có tính bắc cầu và quan hệ "là tập mẹ của" là ngược của nó, nên ta có thể kết luận quan hệ sau cũng có tính bắc cầu.
  • Giao của hai quan hệ bắc cầu thì cũng bắc cầu[6]. Quan hệ "sinh trước" và "cùng tên với" có tính bắc cầu, nên quan hệ "sinh trước và có cùng tên" cũng có tính bắc cầu.
  • Hợp của hai quan hệ bắc cầu không nhất thiết phải bắc cầu. Ví dụ chẳng hạn, "sinh trước hoặc có cùng tên" không có tính bắc cầu, (Herbert Hoover có quan hệ với Franklin D. Roosevelt, và Franklin D.Roosevelt có quan hệ với Franklin Pierce, nhưng Hoover thì không có quan hệ gì với Franklin Pierce.
  • Bù của quan hệ bắc cầu không nhất thiết phải bắc cầu.[7] Ví dụ chẳng hạn, mặc dù "bằng với" là quan hệ bắc cầu, "không bằng với" chỉ bắc cầu trên các tập có tối đa một phần tử.

Các tính chất khác sửa

Quan hệ bắc cầu bất đối xứng khi và chỉ khi nó hoàn toàn không phản xạ.[8]

Quan hệ bắc cầu không nhất thiết phải phản xạ. Nhưng khi nó có, thì nó được gọi là tiền thứ tự. Ví dụ chẳng hạn, trên tập X = {1,2,3}:

  • R = { (1,1), (2,2), (3,3), (1,3), (3,2) } có tính phản xạ nhưng không bắc cầu, bởi thiếu tập (1,2),
  • R = { (1,1), (2,2), (3,3), (1,3) } vừa phản xạ vừa bắc cầu nên nó là tiền thứ tự,
  • R = { (1,1), (2,2), (3,3) } vừa phản xạ vừa bắc cầu nên nó là tiền thứ tự.

Mở rộng bắc cầu và bao đóng bắc cầu sửa

Bài chi tiết: Bao đóng bắc cầu

Gọi R là quan hệ hai ngôi trên tập hợp X. Mở rộng bắc cầu của R, được ký hiệu là R1, là quan hệ hai ngôi nhỏ nhất trên X sao cho R1 chứa R, và nếu (a, b) ∈ R và (b, c) ∈ R thì (a, c) ∈ R1.[9] Lấy ví dụ sau, giả sử X là tập hợp các xã được nối với nhau bởi các đường đi. Gọi R là quan hệ (A, B) ∈ R nếu có đường đi giữa xã A và xã B. Quan hệ này không nhất thiết phải bắc cầu, mở rộng bắc cầu của nó được định nghĩa như sau: (A, C) ∈ R1 nếu ta có từ di chuyển từ xã A sang xã C tối đa hai đường. Mở rộng này không nhất thiết phải bắc cầu.

Nếu quan hệ có tính bắc cầu thì mở rộng bắc cầu của nó là chính nó, nghĩa là, nếu R là quan hệ bắc cầu thì R1 = R.

Mở rộng bắc cầu của R1 sẽ là R2, và cứ tiếp tục như vậy, mở rộng bắc cầu của Ri sẽ là Ri + 1. Bao đóng bắc cầu của R, ký hiệu bởi R* hay R∞ là hợp của các tập R, R1, R2, ... .[10]

Bao đóng bắc cầu của quan hệ luôn có tính bắc cầu.[10]

Ví dụ: quan hệ "là cha mẹ của" trên tập con người không phải là quan hệ bắc cầu. Tuy nhiên, trong sinh học ta thường cần phải xét tính chất tổ tiên qua nhiều thế hệ và do đó ta thường dùng quan hệ "là tổ tiên của". Quan hệ này có tính bắc cầu và là bao đóng bắc cầu của quan hệ "là cha mẹ của".

Đối với ví dụ dùng các xã và đường ở trên, (A, C) ∈ R* có nghĩa là ta có thể di chuyển từ A sang C dùng bất kỳ số đường nào.

Các loại quan hệ yêu cầu tính chất bắc cầu sửa

Đếm số quan hệ bắc cầu sửa

Chưa tìm được công thức chung để đếm số quan hệ bắc cầu trên tập (dãy số A006905 trong bảng OEIS).[11] Tuy nhiên, có các công thức có thể đếm số quan hệ vừa phản xạ, đối xứng và bắc cầu, hay nói cách khác đếm số quan hệ tương đương – (dãy số A000110 trong bảng OEIS), và đếm số quan hệ đối xứng và bắc cầu, số quan hệ đối xứng, bắc cầu toàn phần, bắc cầu và phản đối xứng.Pfeiffer[12] là người tiến bộ nhiều nhất theo hướng này bằng cách biểu diễn các quan hệ trên tổ hợp các tính chất bằng các phần tử của mỗi tính chất đó, song việc tìm ra công thức để tính ra chúng vẫn còn nhiều trở ngại. Xem thêm cả Brinkmann và McKay (2005).[13] Mala đã chứng minh rằng không có đa thức hệ số nguyên có thể biểu diễn thành công thức đếm số quan hệ bắc cầu trên một tập hợp ,[14] và tìm một số hàm đệ quy cho biết cận dưới của số đó.

Số các quan hệ từng loại của tập hợp có n phần tử
Số phần tử Bất kì Bắc cầu Phản xạ Đối xứng Tiền thứ tự Thứ tự bộ phận Tiền thứ tự toàn phần Thứ tự toàn phần Quan hệ tương đương
0 1 1 1 1 1 1 1 1 1
1 2 2 1 2 1 1 1 1 1
2 16 13 4 8 4 3 3 2 2
3 512 171 64 64 29 19 13 6 5
4 65536 3994 4096 1024 355 219 75 24 15
n 2n2 2n2−n 2n(n+1)/2   n!  
OEIS A002416 A006905 A053763 A006125 A000798 A001035 A000670 A000142 A000110

Trong đó S(n, k) là số Stirling loại thứ hai.

Ghi chú sửa

  1. ^ Hoàng Xuân Sính (1972), tr. 26
  2. ^ Smith, Eggen & St. Andre 2006, p. 145
  3. ^ However, the class of von Neumann ordinals is constructed in a way such that ∈ is transitive when restricted to that class.
  4. ^ Smith, Eggen & St. Andre 2006, p. 146
  5. ^ https://courses.engr.illinois.edu/cs173/sp2011/Lectures/relations.pdf [liên kết URL chỉ có mỗi PDF]
  6. ^ Bianchi, Mariagrazia; Mauri, Anna Gillio Berta; Herzog, Marcel; Verardi, Libero (12 tháng 1 năm 2000). “On finite solvable groups in which normality is a transitive relation”. Journal of Group Theory. 3 (2). doi:10.1515/jgth.2000.012. ISSN 1433-5883.
  7. ^ Robinson, Derek J. S. (tháng 1 năm 1964). “Groups in which normality is a transitive relation”. Mathematical Proceedings of the Cambridge Philosophical Society (bằng tiếng Anh). 60 (1): 21–38. doi:10.1017/S0305004100037403. ISSN 0305-0041.
  8. ^ 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). Note that this source refers to asymmetric relations as "strictly antisymmetric".
  9. ^ Liu 1985, p. 111
  10. ^ a b Liu 1985, p. 112
  11. ^ Steven R. Finch, "Transitive relations, topologies and partial orders" Lưu trữ 2016-03-04 tại Wayback Machine, 2003.
  12. ^ Götz Pfeiffer, "Counting Transitive Relations", Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
  13. ^ Gunnar Brinkmann and Brendan D. McKay,"Counting unlabelled topologies and transitive relations"
  14. ^ Mala, Firdous Ahmad (14 tháng 6 năm 2021). “On the number of transitive relations on a set”. Indian Journal of Pure and Applied Mathematics (bằng tiếng Anh). doi:10.1007/s13226-021-00100-0. ISSN 0975-7465.

Tham khảo sửa

Liên kết ngoài sửa

Lấy từ “https://vi.wikipedia.org/w/index.php?title=Quan_hệ_bắc_cầu&oldid=70565454”