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". 
Định nghĩa.
Quan hệ thuần nhất trên tập hợp là "quan hệ bắc cầu" nếu:
Nếu viết theo ngôn ngữ logic bậc nhất thì:
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ỉ:
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 formula_2 đều có tính bắc cầu bởi không có 3 phần tử formula_3 sao cho formula_4 và formula_5. Quan hệ 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 formula_6 với formula_7 thì chỉ có đúng một bộ formula_3 có quan hệ là formula_9, và do vậy formula_10, nếu cặp đó không có dạng formula_6 thì không có bộ formula_3 sao cho formula_4 và formula_5, 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.
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}:
Mở rộng bắc cầu và bao đóng bắc cầu.
Gọi là quan hệ hai ngôi trên tập hợp . Mở rộng bắc cầu của , được ký hiệu là , là quan hệ hai ngôi nhỏ nhất trên sao cho chứa , và nếu và thì . Lấy ví dụ sau, giả sử là tập hợp các xã được nối với nhau bởi các đường đi. Gọi là quan hệ nếu có đường đi giữa xã và xã . 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: nếu ta có từ di chuyển từ xã sang xã 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 là quan hệ bắc cầu thì .
Mở rộng bắc cầu của sẽ là , và cứ tiếp tục như vậy, mở rộng bắc cầu của sẽ là . Bao đóng bắc cầu của , ký hiệu bởi hay là hợp của các tập , , , ... .
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, có nghĩa là ta có thể di chuyển từ sang dùng bất kỳ số đường nào.
Đế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 . 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 – , 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ố đó.