Quan hệ (toán học)

Trong toán học, quan hệ là một khái niệm khái quát hóa các quan hệ thường gặp, ví dụ như các quan hệ bằng, nhỏ hơn, lớn hơn, đồng dư giữa các số, hay các quan hệ bằng nhau, đồng dạng giữa các hình tam giác. Tất cả các ví dụ này đều là các quan hệ hai ngôi.

== Khái niệm ==
=== Định nghĩa ===
- Cho hai tập hợp A,B. Mỗi tập con formula_1 của tích Descartes A x B được gọi là quan hệ hai ngôi từ A vào B. Nếu formula_1 là quan hệ từ A vào B và cặp (a,b)formula_3 thì ta ký hiệu formula_4.
- Nếu A = B thì một tập con formula_1 của tích Descartes AxA được gọi là quan hệ trên A.
- Mở rộng của quan hệ hai ngôi là quan hệ "n" ngôi dẫn đến cấu trúc bảng trong cơ sở dữ liệu quan hệ.
- Lưu ý rằng tập tích Descarter là tập các cặp có thứ tự nên quan hệ định nghĩa ở đây là quan hệ "có hướng từ A vào B". Ta hình dung như các phần tử thuộc tập A là các phần tử ""chủ động"" trong quan hệ, còn các phần tử của B (nếu có mặt trong quan hệ) là các phần tử ""bị động"". Điều lưu ý này rất hữu ích cho các quan hệ xã hội như "quý" và "được quý", "hâm mộ" và "bị hâm mộ", hay trong quan hệ bao hàm:"chứa" và "được chứa trong"...

=== Ví dụ ===
- Các quan hệ trong đời sống xã hội đều là các quan hệ theo nghĩa toán học: quan hệ hôn nhân (khác giới) là quan hệ từ tập người là nam vào tập người là nữ, quan hệ bạn bè, quan hệ đồng nghiệp, đồng hương, quan hệ chống đối... đều là các quan hệ giữa các tập người.
- Các quan hệ trong toán như quan hệ bằng nhau, lớn hơn, nhỏ hơn giữa các số thực, quan hệ chia hết giữa các số tự nhiên...
- Các quan hệ tuỳ ý giữa các tập hữu hạn có thể dẫn ra làm ví dụ rất nhiều, chẳng hạn cho A = {a, b, c, d}; B= {1, 2, 3}.

Quan hệ formula_1={ (a,1), (a, 2), (b, 2), (c, 2)}.
Để biểu diễn quan hệ (trên các tập hữu hạn), nhất là khi phải giải quyết các bài toán về quan hệ trên máy tính, ta có biểu diễn bằng ma trận logic hoặc bằng đồ thị
=== Ma trận logic của quan hệ hai ngôi ===
Cho tập A có m phần tử 
và tập B có n phần tử
Ma trận logic của quan hệ formula_1 formula_8 A x B là ma trận cấp m formula_9 n với các phần tử r xác định như sau:
Ví dụ ma trận biểu diễn quan hệ formula_1 ở trên là 

=== Quan hệ n ngôi ===
Một quan hệ formula_13 ngôi giữa các tập hợp formula_14 là một tập hợp con của tích Descartes formula_15.

== Quan hệ tương đương và quan hệ thứ tự ==
=== Một số tính chất của quan hệ trên một tập ===
Cho formula_1 là một quan hệ trên tập A:
- formula_1 được gọi là quan hệ có tính chất phản xạ nếu formula_18:formula_19
- formula_1 được gọi là quan hệ có tính chất đối xứng nếu formula_21:nếu formula_22 thì formula_23
- formula_1 được gọi là quan hệ có tính chất phản đối xứng nếu formula_21:nếu formula_22 và formula_23 thì formula_28
- formula_1 được gọi là quan hệ có tính chất bắc cầu nếu formula_30:nếu formula_22 và formula_32 thì formula_33

=== Quan hệ tương đương ===
Quan hệ formula_1 trên A được gọi là quan hệ tương đương nếu nó có ba tính chất phản xạ, đối xứng, bắc cầu.

Cho formula_1 là quan hệ tương đương trên tập A và phần tử formula_36. Tập con của A gồm các phần tử b có quan hệ formula_1 với a được gọi là lớp tương đương của phần tử a, ký hiệu là formula_38.

Cho formula_39 và quan hệ tương đương formula_1.
Khi đó
1. formula_41,formula_42
2. hoặc formula_43,hoặc formula_44.

Từ đó tập các lớp tương đương của formula_1 tạo thành một "phân hoạch" (hay một "sự chia lớp") của tập A.

Một ví dụ minh hoạ cho quan hệ tương đương là quan hệ đồng dư theo môđun m trên tập hợp các số nguyên formula_46(m là số tự nhiên lớn hơn 1), mỗi lớp tương đương là tập các số nguyên có cùng số dư theo môđun m. Trong số học nó còn được gọi là các lớp thặng dư theo môdun m.

=== Quan hệ thứ tự ===
- Quan hệ formula_1 trên tập A được gọi là quan hệ thứ tự trên A nếu nó có ba tính chất phản xạ, phản đối xứng và bắc cầu.
- Sau đây ta dùng ký hiệu formula_49 để chỉ một quan hệ thứ tự trong trường hợp tổng quát.
- Quan hệ thứ tự formula_49 được gọi là quan hệ thứ tự toàn phần trên tập A nếu với hai phần tử bất kỳ formula_51 một trong hai quan hệ formula_52 hoặc formula_53 sẽ xảy ra. Trong trường hợp ngược lại nó được gọi là quan hệ thứ tự bộ phận. Khi đó, tương ứng ta nói tập A được sắp thứ tự toàn phần/bộ phận. Khi không muốn nói vào chi tiết ta đơn giản gọi chúng là tập được sắp. Các quan hệ "≤" và "≥" trên tập số thực là quan hệ thứ tự toàn phần. Quan hệ chia hết trên tập số nguyên, quan hệ bao hàm trên các tập hợp là các quan hệ thứ tự bộ phận.

=== Các phần tử đặc biệt trong tập được sắp ===
- Trong tập A được sắp theo quan hệ formula_49, một phần tử m được gọi là nhỏ nhất nếu formula_55 với mọi formula_36. Ví dụ như phần tử nhỏ nhất của tập các số tự nhiên dương là 1, phần tử nhỏ nhất theo quan hệ bao hàm trên các tập hợp là tập rỗng, theo quan hệ chia hết trên tập các số tự nhiên phần tử nhỏ nhất là số 1.
- Cho S là tập con của tập được sắp A theo quan hệ formula_55. Phần tử m (nếu có) được gọi là infimum của S, ký hiệu là inf(S) hay ^S, nếu formula_55 với mọi formula_59 và nếu formula_60 thì formula_61.
- Nếu S= {a, b} formula_62 thì inf({x,y}) được ký hiệu là x^y. Trong quan hệ chia hết trên tập các số tự nhiên, x^y chính là ƯCNN(x,y), còn theo quan hệ bao hàm giữa các tập hợp, A^B chính là tập formula_63.
- Khái niệm tương tự theo chiều ngược lại là khái niệm supremum, ký hiệu là sub(S)

== Tích các quan hệ và bao đóng bắc cầu ==
=== Quan hệ tích ===
Cho quan hệ formula_1 từ tập A vào tập B và quan hệ formula_65 từ B vào C. Quan hệ tích formula_66 là quan hệ từ A vào C, xác định bởi formula_67 khi và chỉ khi tồn tại formula_68 sao cho formula_4 và formula_70

=== Tính chất của quan hệ bắc cầu ===
- Quan hệ formula_1 là quan hệ có tính chất bắc cầu khi và chỉ khi
- Quan hệ formula_65 nhỏ nhất có tính chất bắc cầu chứa quan hệ formula_1 được gọi là bao đóng bắc cầu (một số người gọi là bao đóng truyền ứng) của quan hệ formula_1 ký hiệu là formula_77.
- Nếu tập A hữu hạn gồm n phần tử thì

== Biểu diễn đồ thị của quan hệ hai ngôi ==
Ta có thể biểu diễn quan hệ formula_1 từ tập X và tập Y bằng một đồ thị có hướng như hình bên. Nếu A formula_80 = formula_81 thì đồ thị biểu diễn formula_1 là đồ thị hai phía.

Trong hình bên phần tử A có thể "chủ động" quan hệ với ba phần tử 1, 2, 5 của Y, còn B "chủ động" không quan hệ với phần tử nào. Về phía Y, phần tử 2 và 5 bị hai phần tử cùng quan tâm, còn 3, 4 không được phần tử nào của X quan hệ tới.

== Quan hệ và ánh xạ ==
Từ biểu diễn đồ thị của quan hệ formula_1 và biểu diễn ánh xạ, có thể nhận ra rằng ánh xạ (hay hàm) là một quan hệ đặc biệt, mà ta gọi là quan hệ hàm. 
Chú ý rằng trong định nghĩa này không loại trừ khả năng hai (hoặc nhiều hơn) phần tử của A cùng có quan hệ f với một phần tử formula_68

== Quan hệ như là cấu xạ ==
Trong phạm trù các quan hệ Rel, một quan hệ cũng là một cấu xạ giữa các tập hợp.

==Thư mục==
- Hoàng Xuân Sính, 1972, "Đại số đại cương (tái bản lần thứ tám)", Nhà xuất bản giáo dục