Mối liên 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 xem là có tính bắc cầu (hoặc tính chuyển tiếp, truyền ứng) nếu và chỉ nếu điều kiện sau được thỏa mãn: nếu một phần tử a liên kết với phần tử b, và phần tử b liên kết với phần tử c, thì phần tử a phải liên kết với phần tử c.

Khái niệm

Một quan hệ thuần nhất R trên tập hợp X được coi là quan hệ bắc cầu nếu:

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

Khi diễn đạt bằng ngôn ngữ logic bậc nhất, ta có thể viết như sau:

$\mathrm{\forall <!--\; \forall \; -->}a,b,$

c ∈ X : ( a R b ∧ b R c ) ⇒ a R c {displaystyle orall a,b,cin X:(aRbwedge bRc)Rightarrow aRc} ,

Các ví dụ minh họa

Ví dụ không sử dụng toán học: mối quan hệ 'là tổ tiên của' là một quan hệ bắc cầu. Chẳng hạn, 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.

Ngược lại, mối quan hệ 'là người sinh ra' không phải là quan hệ bắc cầu, vì dù An sinh ra Bình và Bình sinh ra Cường, điều đó không có nghĩa An cũng sinh ra Cường. Tính chất này còn được gọi là phản bắc cầu, vì An sẽ không bao giờ sinh ra Cường.

Các mối quan hệ như 'lớn hơn', 'lớn hơn hoặc bằng', và 'bằng với' đều là các quan hệ bắc cầu trên nhiều tập hợp, bao gồm cả 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 chất bắc cầu:

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

Các ví dụ về các mối quan hệ không bắc cầu bao gồm:

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

Quan hệ rỗng trên bất kỳ tập $X$ đều có tính bắc cầu vì không tồn tại ba phần tử $a,b,c\in <!--\; \in \; -->X$ sao cho $aRb$ và $bRc$. Quan hệ R chỉ chứa một cặp được sắp xếp cũng được coi là có tính bắc cầu vì: nếu cặp đó có dạng $(x,x)$ với $x\in <!--\; \in \; -->X$ thì chỉ có một bộ có quan hệ là $a=b=c=x$, và do đó $aRc$. Nếu cặp đó không có dạng $(x,\mathrm{x\; <mo>)</mo>}$ thì không có bộ nào sao cho $aRb$ và $bRc$, do đó quan hệ đó vẫn được coi là bắc cầu vì chưa đủ số phần tử để kiểm tra.

Các tính chất

Các tính chất bao đóng

• Quan hệ nghịch đảo của một quan hệ bắc cầu cũng là bắc cầu. Ví dụ, mối quan hệ 'là tập con của' có tính bắc cầu và mối quan hệ 'là tập mẹ của' là nghịch đảo của nó, vì vậy quan hệ này cũng có tính bắc cầu.
• Giao của hai quan hệ bắc cầu vẫn là bắc cầu. Ví dụ, mối quan hệ 'sinh trước' và 'cùng tên với' đều có tính bắc cầu, do đó mối 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ụ, 'sinh trước hoặc có cùng tên' không phải là bắc cầu; chẳng hạn, Herbert Hoover có quan hệ với Franklin D. Roosevelt, và Franklin D. Roosevelt có quan hệ với Franklin Pierce, nhưng Hoover không có quan hệ gì với Franklin Pierce.
• Bù của một quan hệ bắc cầu không nhất thiết phải là bắc cầu. Ví dụ, mặc dù 'bằng với' là bắc cầu, 'không bằng với' chỉ có tính bắc cầu trên các tập có tối đa một phần tử.

Các thuộc tính khác

Một quan hệ bắc cầu là bất đối xứng chỉ khi nó hoàn toàn không có tính phản xạ.

Một quan hệ bắc cầu không nhất thiết phải có tính phản xạ. Tuy nhiên, nếu có, nó được gọi là tiền thứ tự. Ví dụ, với 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 vì thiếu cặ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 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 là tiền thứ tự.

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

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

Khi một quan hệ đã có tính bắc cầu, thì mở rộng bắc cầu của nó chính là chính nó. Nói cách khác, nếu R đã là quan hệ bắc cầu, thì R₁ = R.

Mở rộng bắc cầu của R₁ là R₂, và quá trình này tiếp tục, tức là mở rộng bắc cầu của R_i là R_{i + 1}. Bao đóng bắc cầu của R, ký hiệu là R* hoặc R, là hợp của các tập R, R₁, R₂, ... .

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

Ví dụ, quan hệ 'là cha mẹ của' trong tập con người không phải là bắc cầu. Tuy nhiên, trong sinh học, để xét tính chất tổ tiên qua nhiều thế hệ, chúng ta thường sử 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'.

Với ví dụ sử dụng các xã và đường đã nêu, (A, C) ∈ R* có nghĩa là bạn có thể đi từ A đến C bằng bất kỳ số lượng đường nào.

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

• Quan hệ tiền thứ tự – bao gồm tính phản xạ và bắc cầu
• Quan hệ thứ tự riêng phần – tiền thứ tự không đối xứng
• Quan hệ 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 – bao gồm tính bắc cầu, liên thông và đối xứng

Đếm số lượng quan hệ bắc cầu

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

Ghi chú

• Ralph P. Grimaldi, Toán Rời Rạc và Tổ Hợp, ISBN 0-201-19912-2.
• Gunther Schmidt, 2010. Toán Quan Hệ. Nhà Xuất Bản Cambridge, ISBN 978-0-521-76268-7.
• Hoàng Xuân Sính, 1972, Đại Số Đại Cương

Các liên kết bên ngoài

• Chuyển tiếp trong hành động tại cut-the-knot