Quan hệ bắc cầu

Bản mẫu:Unreferenced Bản mẫu:Stack 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.

Định nghĩa

Quan hệ thuần nhất Bản mẫu:Mvar trên tập hợp Bản mẫu:Mvar là quan hệ bắc cầu nếu:

với mọi Bản mẫu:Math, nếu Bản mẫu:Math và Bản mẫu:Math, thì Bản mẫu:Math.

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

$\mathrm{\forall }a,b,c\in X:(aRb\wedge bRc)\Rightarrow aRc$,

Các ví dụ

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:

• "là tập con của" (trên tập của các tập hợp)
• "chia hết" (tính chia hết trên tập các số tự nhiên)
• "suy ra" (phép kéo theo, ký hiệu bởi "⇒", là quan hệ trên các mệnh đề)

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

• "là số tiếp theo của" (trên tập các số tự nhiên)
• "là phần tử của tập" (ký hiệu bởi "∈")
• "vuông góc với" (quan hệ trên các đường thẳng trong hình học Euclid)

Quan hệ rỗng trên bất cứ tập $X$ đều có tính bắc cầu bởi không có 3 phần tử $a,b,c\in X$ sao cho $aRb$ và $bRc$. Quan hệ Bản mẫu:Math 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 $(x,x)$ với $x\in X$ thì chỉ có đúng một bộ $a,b,c\in X$ có quan hệ là $a=b=c=x$, và do vậy $aRc$, nếu cặp đó không có dạng $(x,x)$ thì không có bộ $a,b,c\in X$ sao cho $aRb$ và $bRc$, 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

Tính bao đóng

• 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. 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. 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

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ạ.

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 = {Bản mẫu:Hair space(1,1), (2,2), (3,3), (1,3), (3,2)Bản mẫu:Hair space} có tính phản xạ nhưng không bắc cầu, bởi thiếu tập (1,2),
• R = {Bản mẫu:Hair space(1,1), (2,2), (3,3), (1,3)Bản mẫu:Hair space} vừa phản xạ vừa bắc cầu nên nó là tiền thứ tự,
• R = {Bản mẫu:Hair space(1,1), (2,2), (3,3)Bản mẫu:Hair space} 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

Gọi Bản mẫu:Mvar là quan hệ hai ngôi trên tập hợp Bản mẫu:Mvar. Mở rộng bắc cầu của Bản mẫu:Mvar, được ký hiệu là Bản mẫu:Math, là quan hệ hai ngôi nhỏ nhất trên Bản mẫu:Mvar sao cho Bản mẫu:Math chứa Bản mẫu:Mvar, và nếu Bản mẫu:Math và Bản mẫu:Math thì Bản mẫu:Math. Lấy ví dụ sau, giả sử Bản mẫu:Mvar là tập hợp các xã được nối với nhau bởi các đường đi. Gọi Bản mẫu:Mvar là quan hệ Bản mẫu:Math nếu có đường đi giữa xã Bản mẫu:Mvar và xã Bản mẫu:Mvar. 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: Bản mẫu:Math nếu ta có từ di chuyển từ xã Bản mẫu:Mvar sang xã Bản mẫu:Mvar 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 Bản mẫu:Mvar là quan hệ bắc cầu thì Bản mẫu:Math.

Mở rộng bắc cầu của Bản mẫu:Math sẽ là Bản mẫu:Math, và cứ tiếp tục như vậy, mở rộng bắc cầu của Bản mẫu:Math sẽ là Bản mẫu:Math. Bao đóng bắc cầu của Bản mẫu:Mvar, ký hiệu bởi Bản mẫu:Math hay Bản mẫu:Math là hợp của các tập Bản mẫu:Mvar, Bản mẫu:Math, Bản mẫu:Math, ... .

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

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, Bản mẫu:Math có nghĩa là ta có thể di chuyển từ Bản mẫu:Mvar sang Bản mẫu:Mvar 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

• Tiền thứ tự – quan hệ phản xạ và bắc cầu
• Quan hệ thứ tự riêng phần – tiền thứ tự phản đối xứng
• Tiền thứ tự toàn phần – tiền thứ tự có tính liên thông
• Quan hệ tương đương - tiền thứ tự đối xứng
• Quan hệ thứ tự yếu nghiêm ngặt – quan hệ thứ tự riêng phần nghiêm ngặt trong đó tính không so sánh được là quan hệ tương đương
• Quan hệ thứ tự toàn phần – Quan hệ bắc cầu, liên thông và phản đối xứng

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

Chưa tìm được công thức chung để đếm số quan hệ bắc cầu trên tập Bản mẫu:OEIS. 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 – Bản mẫu: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 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). 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 , 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	Bản mẫu:Val	Bản mẫu:Val	Bản mẫu:Val	Bản mẫu:Val	355	219	75	24	15
n	2n2		2n2−n	2n(n+1)/2			${\sum }_{k=0}^{n}k!S(n,k)$	n!	${\sum }_{k=0}^{n}S(n,k)$
OEIS	Bản mẫu:OEIS link	Bản mẫu:OEIS link	Bản mẫu:OEIS link	Bản mẫu:OEIS link	Bản mẫu:OEIS link	Bản mẫu:OEIS link	Bản mẫu:OEIS link	Bản mẫu:OEIS link	Bản mẫu:OEIS link

Trong đó Bản mẫu:Math là số Stirling loại thứ hai.

Tham khảo

• Ralph P. Grimaldi, Discrete and Combinatorial Mathematics, ISBN 0-201-19912-2.
• Gunther Schmidt, 2010. Relational Mathematics. Cambridge University Press, ISBN 978-0-521-76268-7.
• Hoàng Xuân Sính, 1972, Đại số đại cương

Liên kết ngoài

• Transitivity in Action at cut-the-knot