Quan hệ (toán học) – Wikipedia tiếng Việt

: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ệ.

Quan hệ trong toán học là khái quát các quan hệ giữa các số như quan hệ bằng, nhỏ hơn, lớn hơn, đồng dư... Bài này chỉ nói về các quan hệ hai ngôi.

Định nghĩa[sửa | sửa mã nguồn]

Ví dụ[sửa | sửa mã nguồn]

• 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ệ ${displaystyle {mathcal {R}}}$={ (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[sửa | sửa mã nguồn]

Cho tập A có m phần tử

A = {a₁,a₂,...,a_m}

và tập B có n phần tử

B = {b₁,b₂,...,b_n}

Ma trận logic của quan hệ ${displaystyle {mathcal {R}}}$ ${displaystyle subset }$ A x B là ma trận cấp m ${displaystyle times }$ 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}}}$

Ví dụ ma trận biểu diễn quan hệ ${displaystyle {mathcal {R}}}$ ở trên là

Quan hệ tương đương và quan hệ thứ tự[sửa | sửa mã nguồn]

Một số tính chất của quan hệ trên một tập[sửa | sửa mã nguồn]

Cho ${displaystyle {mathcal {R}}}$ là một quan hệ trên tập A:

Quan hệ tương đương[sửa | sửa mã nguồn]

Quan hệ ${displaystyle {mathcal {R}}}$ 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 ${displaystyle {mathcal {R}}}$ là quan hệ tương đương trên tập A và phần tử ${displaystyle ain A}$. Tập con của A gồm các phần tử b có quan hệ ${displaystyle {mathcal {R}}}$ với a được gọi là lớp tương đương của phần tử a, ký hiệu là ${displaystyle {[a]}_{mathcal {R}}}$.

Cho ${displaystyle a,bin A}$ và quan hệ tương đương ${displaystyle {mathcal {R}}}$.
Khi đó

1. ${displaystyle {[a]}_{mathcal {R}}neq emptyset }$,${displaystyle {[b]}_{mathcal {R}}neq emptyset }$


2. hoặc ${displaystyle {[a]}_{mathcal {R}}cap {[b]}_{mathcal {R}}=emptyset }$,hoặc ${displaystyle {[a]}_{mathcal {R}}={[b]}_{mathcal {R}}}$.

Từ đó tập các lớp tương đương của ${displaystyle {mathcal {R}}}$ tạo thành một phân hoạch 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 ${displaystyle mathbb {Z} }$(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ự[sửa | sửa mã nguồn]

• Quan hệ ${\displaystyle \mathcal{R}}$ 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.

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 "${displaystyle subset }$" (quan hệ tập con) trong các tập hợp cũng là các quan hệ thứ tự.

Các phần tử đặc biệt trong tập được sắp[sửa | sửa mã nguồn]

• Trong tập A được sắp theo quan hệ ${displaystyle sqsubseteq }$, một phần tử m được gọi là nhỏ nhất nếu ${displaystyle msqsubseteq a}$ với mọi ${displaystyle ain A}$. 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ệ ${displaystyle msqsubseteq a}$. 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 ${displaystyle msqsubseteq a}$ với mọi ${displaystyle ain S}$ và nếu ${displaystyle forall ain S:nsqsubseteq a}$ thì ${displaystyle nsqsubseteq m}$.


• Nếu S= {a, b} ${displaystyle subset A}$ 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 ${displaystyle Acap B}$.


• 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[sửa | sửa mã nguồn]

Quan hệ tích[sửa | sửa mã nguồn]

Cho quan hệ ${displaystyle {mathcal {R}}}$ từ tập A vào tập B và quan hệ ${displaystyle {mathcal {S}}}$ từ B vào C. Quan hệ tích ${displaystyle ({mathcal {RS}})}$ là quan hệ từ A vào C, xác định bởi ${displaystyle a({mathcal {RS}})c}$ khi và chỉ khi tồn tại ${displaystyle bin B}$ sao cho ${displaystyle a{mathcal {R}}b}$ và ${displaystyle b{mathcal {S}}c}$

Tính chất của quan hệ bắc cầu[sửa | sửa mã nguồn]

• Quan hệ ${displaystyle {mathcal {R}}}$ là quan hệ có tính chất bắc cầu khi và chỉ khi

${displaystyle {mathcal {RR}}}$=${displaystyle {mathcal {R}}^{2}subset {mathcal {R}}}$.

• Quan hệ ${displaystyle {mathcal {S}}}$ nhỏ nhất có tính chất bắc cầu chứa quan hệ ${displaystyle {mathcal {R}}}$ đượ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ệ ${displaystyle {mathcal {R}}}$ ký hiệu là ${displaystyle [{mathcal {R}}]}$.


• Nếu tập A hữu hạn gồm n phần tử thì

${\displaystyle [\mathcal{R}]=\mathcal{R}\cup <!--\; \cup \; -->{\mathcal{R}}^2\cup <!--\; \cup \; -->{\mathcal{R}}^3...\cup <!--\; \cup \; -->{\mathcal{R}}^n}$

Biểu diễn đồ thị của quan hệ hai ngôi[sửa | sửa mã nguồn]

Ta có thể biểu diễn quan hệ ${displaystyle {mathcal {R}}}$ từ tập X và tập Y bằng một đồ thị có hướng như hình bên. Nếu A ${displaystyle cap B}$ = ${displaystyle emptyset }$ thì đồ thị biểu diễn ${displaystyle {mathcal {R}}}$ 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.

Biểu diễn đồ thị của quan hệ

Ánh xạ là một loại quan hệ trong đó tất cả các phần tử của tập chủ động đều có quan hệ và chỉ quan hệ với một phần tử thuộc tập bị động

Từ biểu diễn đồ thị của quan hệ ${\displaystyle \mathcal{R}}$ 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.

Ánh xạ f : A ${displaystyle to }$ B là một quan hệ từ A vào B thoả mãn điều kiện sau:

Mỗi phần tử a ${displaystyle in }$ A đều có quan hệ f với đúng một phần tử b ${displaystyle in }$ B.

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ử ${displaystyle bin B}$