✨Quan hệ hai ngôi

Trong toán học, một quan hệ hai ngôi (hay còn gọi là quan hệ nhị phân) trên hai tập A và B là một tập các cặp được sắp (a, b), chứa các phần tử a thuộc A và các phần tử b thuộc B. Đó là một tập con của tích Descartes . Nó mã hóa thông tin quan hệ: một phần tử a có liên quan với một phần tử b khi và chỉ khi cặp (a, b) thuộc về một tập hợp. Quan hệ hai ngôi là một dạng quan hệ được nghiên cứu nhiều nhất trong số các quan hệ toán học.

Một ví dụ trong quan hệ hai ngôi thường thấy là phép chia hết trên tập số nguyên tố $\backslash mathbb\{P\}$ và tập số nguyên $\backslash mathbb\{Z\}$,trong đó mỗi số nguyên p quan hệ với mỗi số nguyên z là bội của p, và không quan hệ với số không chia hết p. Ví dụ như số 2 có quan hệ với -4, 0, 6 nhưng không có quan hệ với các số -1, 9.

Quan hệ hai ngôi được sử dụng trong các lĩnh vực toán học để làm mẫu rất nhiều khái niệm. Ta có các ví dụ như:

• Quan hệ "lớn hơn", "bằng", "chia hết" trong Số học.
• Quan hệ "tương đẳng" trong Hình học.
• Quan hệ "kề nhau" trong Lý thuyết đồ thị.
• Quan hệ "trực giao" trong Đại số tuyến tính.

Một hàm số cũng có thể được coi là một dạng đặc biệt trong quan hệ hai ngôi . Quan hệ hai ngôi được sử dụng phổ biến trong Khoa học máy tính.

Một quan hệ hai 2 ngôi trên 2 tập X và Y là một phần tử trong tập lũy thừa X × Y. Bởi tập lũy thừa được xếp thứ tự theo phép chứa. Mỗi mối quan hệ có vị trí trong lưới của các tập con của X × Y.

Bởi các quan hệ là các tập hợp. Ta có thể biến đổi chúng bằng các phép toán trong tập hợp như phép hội, phép giao và phép bù, thỏa mãn các định luật trong đại số tập hợp. Hơn nữa, ta còn có phép nghịch đảo của quan hệ và phép hợp hàm của quan hệ, thỏa mãn các định luật trong giải tích của quan hệ. Ngoài ra còn có quan hệ ngược và phép hợp thành quan hệ, hình thành nên giải tích quan hệ, được nghiên cứu trong các cuốn sách của Ernst Schroder, Clarence Lewis và Gunther Schmidt.

Trong một số hệ thống trong lý thuyết tiên đề tập hợp, các quan hệ hai ngôi được mở rộng thành các lớp (lớp là dạng tổng quát của tập hợp). Việc mở rộng này cần thiết cho việc mô tả khái niệm "là một phần tử của" hay "là tập con của" trong lý thuyết tập hợp mà không bị vướng với các mâu thuẫn logic như Nghịch lý Russell.

Định nghĩa

Cho hai tập X và Y, Tích đề các $X\; \backslash times\; Y$ được định nghĩa $\{\; (x,\; y)\; :\; x\; \backslash in\; X\; \backslash text\{\; và\; \}\; y\; \backslash in\; Y\; \},$ và các phần tử của nó là các cặp được sắp.

R trên tập X và tập Y là tập con của $X\; \backslash times\; Y.$ Tập X được gọi là

Khi $X\; =\; Y,$ thì quan hệ hai ngôi được gọi là . Ngược lại thì quan hệ được gọi là quan hệ không thuần nhất.

Cần để ý đến thứ tự của phần tử trong quan hệ hai ngôi bởi nếu $x\; \backslash neq\; y$ thì giá trị đúng sai của yRx không phụ thuộc vào xRy. Để lấy ví dụ: 9 chia hết cho 3 nhưng 3 không có chia hết cho 9.

Các ví dụ

1. Ví dụ sau cho thấy tầm quan trọng trong việc chọn đối miền. Giả sử ta có tập 4 vật thể $A\; =\; \{\; \backslash text\{cốc,\; bát,\; đũa,\; thìa\}\; \}$ và tập 4 bạn $B\; =\; \{\; \backslash text\{W,\; X,\; Y,\; Z\}\; \}.$ Giả sử quan hệ giữa A và B là "được sở hữu bởi" cho như sau: $R\; =\; \{\; (\backslash text\{cốc,\; W\}),\; (\backslash text\{bát,\; X\}),\; (\backslash text\{thìa,\; Z\})\; \}.$ Nghĩa là W sở hữu cái cốc, X thì có cái bát còn Z thì sở hữu cái thìa. Không ai sở hữu cái đũa và Y thì không sở hữu cái gì cả, xem ví dụ 1. Bởi trong tập R không có Y nên tập R có thể được xem là tập con của $A\; \backslash times\; \{\; \backslash text\{W,\; X,\; Z\}\; \},$ hay nói cách khác mối quan hệ giữa A và $\{\; \backslash text\{W,\; X,\; Z\}\; \},$ xem ví dụ 2. Ví dụ 2 có tính toàn ánh (xem dưới) trong khi ví dụ 1 thì không.

thumb|right|Các đại dương và châu lục (ẩn các đảo)

2. Đặt A = {Ấn Độ dương, Nam đại dương, Bắc băng dương, Thái bình dương} là tập đại dương và B = { NA, SA, AF, EU, AS, AU, AA }, tập các châu lục. Giả sử aRb là quan hệ a kề với b. Khi đó ma trận logic của quan hệ này là: : Tính kết nối của trái đất có thể xem qua R R^T và R^T R, cái đầu là quan hệ phổ dụng $4\; \backslash times\; 4$ trên A ($A\; \backslash times\; A$ hoặc ma trận logic bao gồm toàn giá trị 1). Quan hệ phổ dụng này phản ánh mỗi đại dương đều cách các đại dương khác ít nhất 1 châu lục. Mặt khác, R^T R là quan hệ trên $B\; \backslash times\; B$ nhưng không phổ dụng bởi phải đi qua ít nhất hai đại dương để đi từ châu Âu đến châu Úc.

3. Ta có thể biểu diễn các quan hệ hai ngôi bằng đồ thị: Đối với các quan hệ trên cùng 1 tập (quan hệ thuần nhất), đồ thị có hướng thường được dùng để mô tả quan hệ , trong trường hợp quan hệ đó là quan hệ đối xứng thì có thể dùng đồ thị không hướng. Đối với quan hệ không thuần nhất, siêu đồ thị có cạnh có thể nối nhiều hơn hai nút có thể biểu diễn bằng đồ thị hai phía.

Clique là phần không thể thiếu khi xét các quan hệ thuần nhất, còn clique hai chiều thì được dùng khi xét các quan hệ không thuần nhất; thật vậy, "dựa vào" đó ta có thể sinh ra lưới của quan hệ. right|thumb|Các trục t biểu diễn thời gian cho người xem đang trong trạng thái di chuyển, các trục x tương ứng là các dòng xảy ra đồng thời 4) Trực giao hyperbol: Thời gian và không gian là hai phạm trù khác nhau với các tính chất thời gian phân biệt với không gian. Ý tưởng của việc khá đơn giản trong không gian và thời gian tuyệt đối bởi mỗi thời điểm t ta xác định đồng thời một siêu phẳng trong vũ trụ đó. Herman Minkowski thay đổi ý tưởng trên bằng việc đưa ra khái niệm , cái mà chỉ tồn tại khi các sự kiện không gian "chuẩn tắc" với thời gian được đặc trưng bởi vận tốc. Ông sử dụng một tích nội không giới hạn và chỉ ra rằng vecto thời gian chuẩn tắc với vecto không gian khi tích đó bằng không. Tích nội không giới hạn trong đại số hợp được tính như sau: : trong đó thanh ngang trên đầu hiển thị liên hợp. Nếu ta xét quan hệ hai ngôi giữa sự kiện thời gian và sự kiện không gian, trực giao hyperbol (cũng được tìm thấy trong số tách phức) là quan hệ không thuần nhất

Các phép toán trên quan hệ hai ngôi

Phép hợp

Nếu R và S là các quan hệ hai ngôi trên tập X và Y thì $R\; \backslash cup\; S\; =\; \{\; (x,\; y)\; :\; xRy\; \backslash text\{\; hay\; \}\; xSy\; \}$ là của R và S trên X và Y.

Phần tử đơn vị là quan hệ rỗng. Lấy ví dụ, $\backslash ,\backslash leq\backslash ,$ là hội của < và =, hoặc $\backslash ,\backslash geq\backslash ,$ là hợp của > và =.

Phép giao

Nếu R và S là các quan hệ hai ngôi trên tập X và Y thì $R\; \backslash cap\; S\; =\; \{\; (x,\; y)\; :\; xRy\; \backslash text\{\; và\; \}\; xSy\; \}$ là của R và S trên X và Y.

Phần tử đơn vị là quan hệ phổ quát. Lấy ví dụ, trên tập số nguyên dương, quan hệ "tổng a + b là số nguyên tố chia 3 dư 1" là giao của hai quan hệ "tổng a + b là số nguyên tố" và "tổng a + b là số chia 3 dư 1".

Phép hợp thành

Nếu R là quan hệ hai ngôi trên tập X và Y, và S là quan hệ hai ngôi trên tập Y và Z thì $S\; \backslash circ\; R\; =\; \{\; (x,\; z)\; :\; \backslash text\{\; tồn\; tại\; \}\; y\; \backslash in\; Y\; \backslash text\{\; sao\; cho\; \}\; xRy\; \backslash text\{\; và\; \}\; ySz\; \}$ (được ký hiệu là ) là của R và S trên X và Z.

Phần tử đơn vị là quan hệ đơn vị. Thứ tự của R và S trong ký hiệu $S\; \backslash circ\; R,$ tương tự với phép hợp hàm của hàm số. Ví dụ chẳng hạn, hợp thành của (là phụ huynh của)$\backslash ,\backslash circ\backslash ,$(là mẹ của) là (là ông/bà ngoại của), trong khi đó, hợp thành của (là mẹ của)$\backslash ,\backslash circ\backslash ,$(là phụ huynh của) là (là bà của). Đối với trường hợp trước, nếu x là phụ huynh của y và y là mẹ của z, thì x là ông/bà ngoại của z.

Quan hệ ngược

Nếu R là quan hệ hai ngôi trên tập hợp X và Y thì $R^\backslash textsf\{T\}\; =\; \{\; (y,\; x)\; :\; xRy\; \}$ là của R trên Y và X.

Lấy ví dụ, $\backslash ,=\backslash ,$ là ngược của chính nó, quan hệ $\backslash ,\backslash neq,\backslash ,$ cũng tương tự như vậy. Quan hệ và $\backslash ,>\backslash ,$ là ngược của nhau, tương tự như vậy với $\backslash ,\backslash leq\backslash ,$ và $\backslash ,\backslash geq.\backslash ,$ Quan hệ hai ngôi là quan hệ ngược của chính nó khi và chỉ khi nó đối xứng.

Quan hệ bù

Nếu R là quan hệ hai ngôi trên tập hợp X và Y thì $\backslash overline\{R\}\; =\; \{\; (x,\; y)\; :\; \backslash text\{\; không\; \}\; xRy\; \}$ (đôi khi được ký hiệu bên Anh là hoặc ) là (hoặc gọi ngắn đi là bù) của R trên X và Y.

Lấy ví dụ, $\backslash ,=\backslash ,$ và $\backslash ,\backslash neq\backslash ,$ là bù của nhau, tương tự như vậy với $\backslash ,\backslash subseteq\backslash ,$ và $\backslash ,\backslash not\backslash subseteq,\backslash ,$ $\backslash ,\backslash supseteq\backslash ,$ và $\backslash ,\backslash not\backslash supseteq,\backslash ,$ và $\backslash ,\backslash in\backslash ,$ và $\backslash ,\backslash not\backslash in,\backslash ,$. Đối với các thứ tự toàn phần, quan hệ và $\backslash ,\backslash geq,\backslash ,$ là bù của nhau, quan hệ $\backslash ,>\backslash ,$ và $\backslash ,\backslash leq\backslash ,$ cũng là bù của nhau.

Bù của quan hệ ngược $R^\backslash textsf\{T\}$ là ngược của quan hệ bù: $\backslash overline\{R^\backslash mathsf\{T\; =\; \backslash bar\{R\}^\backslash mathsf\{T\}.$

Nếu $X\; =\; Y,$ thì quan hệ bù có các tính chất sau:

• Nếu quan hệ đối xứng, thì bù của nó cũng đối xứng.
• Bù của quan hệ phản xạ sẽ hoàn toàn không phản xạ và ngược lại.
• Bù của thứ tự yếu nghiêm ngặt là tiền thứ tự toàn phần và ngược lại.

Thu hẹp

Nếu R là quan hệ hai ngôi thuần nhất trên tập hợp X và S là tập hợp con của X thì $R\_\{\backslash vert\; S\}\; =\; \{\; (x,\; y)\; \backslash mid\; xRy\; \backslash text\{\; và\; \}\; x\; \backslash in\; S\; \backslash text\{\; và\; \}\; y\; \backslash in\; S\; \}$ là của R về S trên X.

Nếu R là quan hệ hai ngôi trên tập hợp X và Y và nếu S là tập con của X thì $R\_\{\backslash vert\; S\}\; =\; \{\; (x,\; y)\; \backslash mid\; xRy\; \backslash text\{\; và\; \}\; x\; \backslash in\; S\; \}$ là của R về S trên X và Y.

Nếu R là quan hệ hai ngôi trên tập hợp X và Y và nếu S là tập con của Y thì $R^\{\backslash vert\; S\}\; =\; \{\; (x,\; y)\; \backslash mid\; xRy\; \backslash text\{\; và\; \}\; y\; \backslash in\; S\; \}$ là của R về S trên X và Y.

Nếu quan hệ có tính phản xạ, hoàn toàn không phản xạ, đối xứng, bất đối xứng, bắc cầu, toàn phần, phân tam hoặc là thứ tự riêng phần, thứ tự toàn phần, thứ tự yếu nghiêm ngặt, tiền thứ tự toàn phần hoặc quan hệ tương đương, thì quan hệ thu hẹp của nó cũng tương tự như vậy.

Tuy nhiên, bao đóng bắc cầu của quan hệ thu hẹp là tập con của thu hẹp của bao đóng bắc cầu của , tức là nó thường không bằng nhau. Ví dụ chẳng hạn, khi thu hẹp quan hệ "x là cha mẹ của y" về giới nữ thành quan hệ "x là mẹ của phụ nữ y"; bao đóng bắc cầu của nó sẽ không quan hệ người phụ nữ với bà nội của cô ấy. Mặt khác, bao đóng bắc cầu của "là cha mẹ của" là "là tổ tiên của"; và khi chỉ xét giới nữ, quan hệ này có quan hệ giữa một người vụ nữ với bà nội của cô ấy.

Bên cạnh đó, nhiều khái niệm của đầy đủ cũng không còn đúng khi bị thu hẹp lại. Ví dụ chẳng hạn, trên tập các số thực, có một tính chất của quan hệ hai ngôi $\backslash ,\backslash leq\backslash ,$ rằng mọi tập hợp con khác rỗng $S\; \backslash subseteq\; \backslash R$ có cận trên thuộc $\backslash R$ thì sẽ có cận trên nhỏ nhất (hay còn gọi là supremum) thuộc $\backslash R.$ Tuy nhiên khi bị thu hẹp về các số hữu tỉ thì nó không còn đúng nữa vì giá trị supremum không nhất thiết phải là số hữu tỉ. Do đó, tính chất này không còn được giữ nguyên khi thu hẹp quan hệ $\backslash ,\backslash leq\backslash ,$ về các số hữu tỉ.

Quan hệ hai ngôi R trên tập hợp X và Y được gọi là (hay nằm trong) quan hệ S trên X và Y, được ký hiệu là $R\; \backslash subseteq\; S,$ nếu R là tập con của S, nghĩa là, với mọi $x\; \backslash in\; X$ và $y\; \backslash in\; Y,$ nếu xRy, thì xSy. Nếu R chứa trong S và S chứa trong R, thì R và S là và được viết là R = S. Nếu R chứa trong S nhưng S không chứa trong R, thì R được gọi là S, và được viết là $R\; \backslash subsetneq\; S.$ . Lấy ví dụ từ các số hữu tỉ, quan hệ $\backslash ,>\backslash ,$ nhỏ hơn $\backslash ,\backslash geq,\backslash ,$ và bằng với quan hệ hợp thành $\backslash ,>\backslash ,\backslash circ\backslash ,>.\backslash ,$

Các loại quan hệ

thumb|Ví dụ của 4 dạng quan hệ hai ngôi trên tập [[số thực: 1-1 (màu xanh lá cây), 1-nhiều (xanh dương), nhiều-1 (màu đỏ), nhiều-nhiều (màu đen).]]

Một số tính chất quan trọng của quan hệ R trên tập X và Y là:

Tính duy nhất:

• Nội xạ (cũng được gọi là duy nhất trái):): với mọi $x\; \backslash in\; X$ và tất cả $y,\; z\; \backslash in\; Y,$ nếu và thì . Quan hệ hai ngôi như vậy được gọi là . Trong quan hệ đó, $\{\; X\; \}$ được gọi là của R. với mọi x thuộc X, tồn tại y thuộc Y sao cho .Nói cách khác, miền xác định của R bằng X. Quan hệ này thường được dùng cho hàm đa giá trị. Lấy ví dụ, quan hệ màu đỏ và màu xanh lá ở trên có tính toàn phần, nhưng quan hệ màu xanh dương thì không (bởi số -1 không có quan hệ với bất cứ số thực nào theo quan hệ đó), tương tự như vậy với quan hệ màu đen (ví dụ như số 2 chẳng hạn). Ví dụ khác, quan hệ lớn hơn thông thường > là quan hệ toàn phần trên tập số nguyên, nhưng không toàn phần khi định nghĩa trên tập số nguyên dương , bởi không có giá trị nguyên dương nào sao cho . Ngược lại, < là quan hệ toàn phần trên tập số nguyên dương, số hữu tỉ và số thực. Quan hệ phản xạ thì nghiễm nhiên toàn phần bởi: cho , chỉ cần chọn .
• Toàn ánh (hay còn gọi là toàn phần phải Người ta thường gọi ngắn đi là quan hệ trên X.

Quan hệ thuần nhất R trên tập X có thể được xét bằng đồ thị có hướng cho phép vòng, với X là tập đỉnh và R là tập các cạnh (có cạnh giữa đỉnh x với đỉnh y nếu ). Tập tất cả các quan hệ hai ngôi $\backslash mathcal\{B\}(X)$ trên tập X là tập lũy thừa $2^\{X\; \backslash times\; X\}$, hay còn là đại số Boolean đi kèm với hàm tự nghịch đảo ánh xạ một quan hệ sang quan hệ ngược của nó. Xét việc hợp thành quan hệ làm phép toán hai ngôi trên $\backslash mathcal\{B\}(X)$, nó tạo thành nửa nhóm với hàm tự nghịch đảo.

Một số tính chất quan trọng của quan hệ thuần nhất trên tập là:

• : với $x\; \backslash in\; X,$ . Ví dụ, $\backslash ,\backslash geq\backslash ,$ là quan hệ phản xạ nhưng > thì không.
• : với mọi $x\; \backslash in\; X,$ không . Ví dụ, $\backslash ,>\backslash ,$ là quan hệ hoàn toàn không phản xạ nhưng$\backslash ,\backslash geq\backslash ,$ thì phản xạ.
• : với mọi $x,\; y\; \backslash in\; X,$ nếu thì . Ví dụ, "là họ hàng của" là quan hệ đối xứng.
• : với mọi $x,\; y\; \backslash in\; X,$ nếu và thì $x\; =\; y.$ Ví dụ, $\backslash ,\backslash geq\backslash ,$ là quan hệ phản đối xứng.
• : với mọi $x,\; y\; \backslash in\; X,$ nếu thì không . Quan hệ bất đối xứng khi và chỉ khi nó hoàn toàn không phản xạ và phản đối xứng. Ví dụ, > là quan hệ bất đối xứng nhưng $\backslash ,\backslash geq\backslash ,$ thì không.
• : với mọi $x,\; y,\; z\; \backslash in\; X,$ nếu và thì . Quan hệ bắc cầu có tính hoàn toàn không phản xạ khi và chỉ khi nó bất đối xứng. Ví dụ, "là tổ tiên của" là quan hệ bắc cầu nhưng "là cha mẹ của" thì không.
• : với mọi $x,\; y\; \backslash in\; X,$ nếu $x\; \backslash neq\; y$ thì hoặc .
• : với $x,\; y\; \backslash in\; X,$ hoặc .