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.
- Mục từ này nói về quan hệ trong toán học. Để xem các nghĩa khác, xem Quan hệ.
Định nghĩa
- Cho hai tập hợp A,B. Mỗi tập con
của tích Descartes A x B được gọi là quan hệ hai ngôi từ A vào B. Nếu
là quan hệ từ A vào B và cặp (a,b)
thì ta ký hiệu
.[1]
- Nếu A = B thì một tập con
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ệ
={ (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ử
- A = {a1,a2,...,am}
và tập B có n phần tử
- B = {b1,b2,...,bn}
Ma trận logic của quan hệ
A x B là ma trận cấp m
n với các phần tử r i,j xác định như sau:
![{\displaystyle r_{i,j}={\begin{cases}1&{\mbox{khi }}a_{i}{\mathcal {R}}b_{j}\\0&{\mbox{khi }}a_{i}{\overline {\mathcal {R}}}b_{j}\end{cases}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/e7bc32be56ec22790c398b2d4a984826e06f4b85)
Ví dụ ma trận biểu diễn quan hệ
ở trên là
![{\displaystyle M_{\mathcal {R}}={\begin{pmatrix}1&1&0\\0&1&0\\0&1&0\\0&0&0\ \end{pmatrix}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/04e2947f6f1e941d2f032d07163f94783e5ca3bf)
Quan hệ thứ tự
- Quan hệ
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.[3]
- Ví dụ về các quan hệ thứ tự là các quan hệ "≤", "≥" trên các tập hợp số. Một ví dụ khác là quan hệ chia hết "\" trên tập số tự nhiên, quan hệ bao hàm "
" (quan hệ tập con) trong các tập hợp cũng là các quan hệ thứ tự.
- Sau đây ta dùng ký hiệu
để chỉ một quan hệ thứ tự trong trường hợp tổng quát.
- Quan hệ thứ tự
đượ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ỳ
một trong hai quan hệ
hoặc
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
Xem thêm: Infimum và supremum
- Trong tập A được sắp theo quan hệ
, một phần tử m được gọi là nhỏ nhất nếu
với mọi
. 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ệ
. 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
với mọi
và nếu
thì
.
- Nếu S= {a, b}
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
.
- 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ính chất của quan hệ bắc cầu
- Quan hệ
là quan hệ có tính chất bắc cầu khi và chỉ khi
=
.
- Quan hệ
nhỏ nhất có tính chất bắc cầu chứa quan hệ
đượ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ệ
ký hiệu là
.
- Nếu tập A hữu hạn gồm n phần tử thì
![{\displaystyle [{\mathcal {R}}]={\mathcal {R}}\cup {\mathcal {R}}^{2}\cup {\mathcal {R}}^{3}...\cup {\mathcal {R}}^{n}}](//wikimedia.org/api/rest_v1/media/math/render/svg/62ddb218bb43bede26e161943fcc94c8e2438753)
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.
Hoàng Xuân Sính (1972), Định nghĩa 1, tr.23
Hoàng Xuân Sính (1972), Định nghĩa 2, tr. 24
Hoàng Xuân Sính (1972), Định nghĩa 6, tr. 26
Hoàng Xuân Sính (1972), Định nghĩa 3, tr. 25
Hoàng Xuân Sính (1972), Định nghĩa 4 và Định lí 1, tr. 25
- 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