Xem mã nguồn của 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 hợp (toán học)|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]] {{nowrap|''A'' × ''B''}}. 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)|quan hệ]] toán học.<ref>{{chú thích web|url=https://mathvault.ca/math-glossary/#relation|title=The Definitive Glossary of Higher Mathematical Jargon — Relation|last=|first=|date = ngày 1 tháng 8 năm 2019 |website=Math Vault|language=en|archive-url=|archive-date=|access-date = ngày 11 tháng 12 năm 2019}}</ref><ref name="Codd1970">{{chú thích tạp chí |last1=Codd |first1=Edgar Frank 
|authorlink=Edgar F. Codd|date=June 1970 |title=A Relational Model of Data for Large Shared Data Banks |url=https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf |journal=Communications of the ACM |volume=13 |issue=6 |pages=377–387 |doi=10.1145/362384.362685 |s2cid=207549016 |access-date=2020-04-29}}</ref>

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ố <math>\mathbb{P}</math> và tập số nguyên <math>\mathbb{Z}</math>,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.<ref>{{Chú thích web|url=https://mathinsight.org/definition/relation|tựa đề=Relation definition - Math insight|website=mathinsight.org|ngày truy cập=2019-12-11}}</ref> 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 <ref>Không nhầm lẫn với lưới trong lý thuyết nhóm.</ref> 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ệ.<ref name="Schroder.1895">[[Ernst Schröder (nhà toán học)|Ernst Schröder]] (1895) [[iarchive:vorlesungenberd03mlgoog|Algebra und Logic der Relative]], qua [[Internet Archive]]</ref> Ngoài ra còn có [[quan hệ ngược]] và phép [[Phép hợp thành quan hệ|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]].<ref name="Lewis.1918">[[C. I. Lewis]] (1918) [[iarchive:asurveyofsymboli00lewiuoft|A Survey of Symbolic Logic]] , pages 269 to 279, via internet Archive</ref>

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 Descartes|Tích đề các]] <math>X \times Y</math> được định nghĩa <math>\{ (x, y) : x \in X \text{ và } y \in Y \},</math> và các phần tử của nó là các cặp được sắp.

{{em|Quan hệ hai ngôi}} ''R'' trên tập ''X'' và tập ''Y'' là tập con của <math>X \times Y.</math><ref name="Codd1970" /><ref>{{harvnb|Enderton|1977|loc=Ch 3. pg. 40}}</ref> Tập ''X'' được gọi là {{em|miền}}<ref name="Codd1970" /> hoặc {{em|tập đi}} của''R'', tập ''Y'' thì được gọi là {{em|đối miền}} hoặc {{em|tập đích}} của ''R''. Tập ''G'' biểu diễn quan hệ là tập con của <math>X \times Y</math> được gọi là {{em|đồ thị}} của quan hệ hai ngôi. Câu <math>(x, y) \in R</math> được đọc là "''x'' có quan hệ ''R'' với ''y''" và ký hiệu là ''xRy''.<ref name="Schroder.1895"/><ref name="Lewis.1918"/><ref name=gs/>{{#tag:ref|Trong một số ngữ cảnh khi tác giả phải xét quan hệ hai ngôi là trường hợp đặc biệt của quan hệ ''n''-ngôi với ''n'' tùy ý thường viết ''Rxy'' là trường hợp đặc biệt của ''Rx''<sub>1</sub>...''x''<sub>''n''</sub> ([[Kí pháp Ba Lan]]).<ref>{{chú thích sách | issn=1431-4657 | isbn=3540058192 | author=Hans Hermes | title=Introduction to Mathematical Logic | url=https://archive.org/details/introductiontoma0000herm | location=London | publisher=Springer | series=Hochschultext (Springer-Verlag) | year=1973 }} Sect.II.§1.1.4</ref>|group=note}} {{em|Miền xác định}}<ref name="Codd1970" /> của ''R'' là tập các giá trị ''x'' sao cho ''xRy'' với ít nhất 1 giá trị ''y''. ''Đối miền xác định'' hay còn được gọi là <ref name="Codd1970" /> {{em|ảnh}} hoặc {{em|miền giá trị}} của ''R'' là tập các giá trị ''y'' sao cho ''xRy'' với ít nhất 1 giá trị ''x''. {{em|Trường}} của ''R'' là hội của miền xác định và đối miền xác định.<ref name="suppes">
{{chú thích sách
|title=Axiomatic Set Theory
|last=Suppes
|first=Patrick
|author-link=Patrick Suppes
|publisher=Dover
|year=1972
|orig-year=originally published by D. van Nostrand Company in 1960
|isbn=0-486-61630-4
|url-access=registration
|url=https://archive.org/details/axiomaticsettheo00supp_0
}}
</ref><ref name="smullyan">
{{chú thích sách
|title=Set Theory and the Continuum Problem
|url=https://archive.org/details/settheorycontinu0000smul
|last1=Smullyan
|first1=Raymond M.
|author-link=Raymond Smullyan
|last2=Fitting
|first2=Melvin
|publisher=Dover
|year=2010
|orig-year=revised and corrected republication of the work originally published in 1996 by Oxford University Press, New York
|isbn=978-0-486-47484-7
}}
</ref><ref name="levy">
{{chú thích sách
|title=Basic Set Theory
|last=Levy
|first=Azriel
|author-link=Azriel Levy
|publisher=Dover
|year=2002
|orig-year=republication of the work published by Springer-Verlag, Berlin, Heidelberg and New York in 1979
|isbn=0-486-42079-5
}}
</ref>

Khi <math>X = Y,</math> thì quan hệ hai ngôi được gọi là {{em|[[quan hệ thuần nhất]]}}. Ngược lại thì quan hệ được gọi là quan hệ không thuần nhất.<ref name="Schmidt">{{chú thích sách|last1=Schmidt|first1=Gunther|last2=Ströhlein|first2=Thomas|title=Relations and Graphs: Discrete Mathematics for Computer Scientists|url={{google books |plainurl=y |id=ZgarCAAAQBAJ|paged=277}}|date=2012|publisher=Springer Science & Business Media|isbn=978-3-642-77968-8|author-link1=Gunther Schmidt |at=Definition 4.1.1.}}</ref><ref name="FloudasPardalos2008">{{chú thích sách|author1=Christodoulos A. Floudas|author-link1=Christodoulos Floudas|author2=Panos M. Pardalos|title=Encyclopedia of Optimization|year=2008|publisher=Springer Science & Business Media|isbn=978-0-387-74758-3|pages=299–300|edition=2nd|url=https://books.google.com/books?id=1a6lSRbQ4YsC&q=relation}}</ref><ref name="Winter2007">{{chú thích sách|author=Michael Winter|title=Goguen Categories: A Categorical Approach to L-fuzzy Relations|url=https://archive.org/details/goguencategories0000mich|year=2007|publisher=Springer|isbn=978-1-4020-6164-6|pages=x-xi}}</ref>

Cần để ý đến thứ tự của phần tử trong quan hệ hai ngôi bởi  nếu <math>x \neq y</math> 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ụ==
{| class="wikitable" style="float: right; margin-left:1em; text-align:center;"
|+ Ví dụ 2
! {{diagonal split header|{{math|''B''{{prime}}}}|{{math|''A''}}}}
! scope="col" | cốc
! scope="col" | bát
! scope="col" | đũa
! scope="col" | thìa
|-
! scope="row" | W
| '''+''' || − || − || −
|-
! scope="row" | X
| − || − || '''+''' || −
|-
! scope="row" | Z
| − || '''+''' || − || −
|}
{| class="wikitable" style="float: right; margin-left:1em; text-align:center;"
|+ Ví dụ 1
! {{diagonal split header|{{math|''B''}}|{{math|''A''}}}}
! scope="col" | cốc
! scope="col" | bát
! scope="col" | đũa
! scope="col" | thìa
|-
! scope="row" | W 
| '''+''' || − || − || −
|-
! scope="row" | X
| − || − || '''+''' || −
|-
! scope="row" | Y
| − || − || − || −
|-
! scope="row" | Z
| − || '''+''' || − || −
|}

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ể <math>A = \{ \text{cốc, bát, đũa, thìa} \}</math> và tập 4 bạn <math>B = \{ \text{W, X, Y, Z} \}.</math> Giả sử quan hệ giữa ''A'' và ''B'' là "được sở hữu bởi" cho như sau: <math>R = \{ (\text{cốc, W}), (\text{bát, X}), (\text{thìa, Z}) \}.</math> 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 <math>A \times \{ \text{W, X, Z} \},</math> hay nói cách khác mối quan hệ giữa ''A'' và <math>\{ \text{W, X, Z} \},</math> xem ví dụ 2. Ví dụ 2 có tính toàn ánh (xem [[#Các dạng đặc biệt của quan hệ|dưới]]) trong khi ví dụ 1 thì không.

[[Tập tin:Oceans and continents coarse.png|thumb|250px|right|Các đại dương và châu lục (ẩn các đảo)]]
{|  class="wikitable" style="float: right; margin-left:1em; text-align:center;"
|+Đại dương kề châu lục
!
! scope="col" | NA
! scope="col"      | SA
! scope="col"            | AF
! scope="col"                 | EU
! scope="col"                       | AS
! scope="col"                             | AU
! scope="col"                                  | AA
|-
! scope="row" | Ấn Độ dương
|0||0||1||0||1||1||1
|-  
! scope="row" | Nam đại dương
|1||0||0||1||1||0||0 
|-
! scope="row" | Bắc băng dương
|1||1||1||1||0||0||1
|-
! scope="row" | Thái bình dương
|1||1||0||0||1||1||1
|}

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à:
:<math>R = \begin{pmatrix} 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 1 \end{pmatrix} .</math>
Tính kết nối của trái đất có thể xem qua ''R R''<sup>T</sup> và ''R''<sup>T</sup> ''R'', cái đầu là quan hệ phổ dụng <math>4 \times 4</math> trên ''A'' (<math>A \times A</math> 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''<sup>T</sup> ''R'' là quan hệ trên <math>B \times B</math> 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 [[lý thuyết đồ thị|đồ 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ệ.
[[Tập tin:Add_velocity_ark_POV.svg|right|thumb|200px|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 {{em|sự việc đồng thời}} 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 {{em|đồng thời tương đối}}, 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:
:<math><x, z> \ =\ x \bar{z} + \bar{x}z\;</math> 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 <ref>{{wikibooks-inline|Calculus/Hyperbolic angle#Split-complex theory|Relative simultaneity}}</ref>

== Các phép toán trên quan hệ hai ngôi ==<!-- This section is linked from [[Tiền thứ tự]] -->

=== Phép hợp ===
<!---This definition should appear before the closure defs, which refer to it:--->
Nếu ''R'' và ''S'' là các quan hệ hai ngôi trên tập ''X'' và ''Y'' thì <math>R \cup S = \{ (x, y) : xRy \text{ hay } xSy \}</math> là {{em|quan hệ hợp}} của ''R'' và ''S'' trên ''X'' và ''Y''.

Phần tử đơn vị là quan hệ rỗng. Lấy ví dụ, <math>\,\leq\,</math> là hội của < và =, hoặc <math>\,\geq\,</math> 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ì <math>R \cap S = \{ (x, y) : xRy \text{ và } xSy \}</math> là {{em|quan hệ giao}} 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 ===
{{main|Phép hợp thành quan hệ}}
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ì <math>S \circ R = \{ (x, z) : \text{ tồn tại } y \in Y \text{ sao cho } xRy \text{ và } ySz \}</math> (được ký hiệu là {{math|''R''; ''S''}}) là {{em|quan hệ hợp thành}} 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 <math>S \circ R,</math> tương tự với [[hàm hợp|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)<math>\,\circ\,</math>(là mẹ của) là (là ông/bà ngoại của), trong khi đó, hợp thành của (là mẹ của)<math>\,\circ\,</math>(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 ===
{{main|Quan hệ ngược}}
{{see also|Đối ngẫu (lý thuyết thứ tự)}}
Nếu ''R'' là quan hệ hai ngôi trên tập hợp ''X'' và ''Y'' thì <math>R^\textsf{T} = \{ (y, x) : xRy \}</math> là {{em|quan hệ ngược}} của ''R'' trên ''Y'' và ''X''.

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

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

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

Bù của [[quan hệ ngược]] <math>R^\textsf{T}</math> là ngược của quan hệ bù: <math>\overline{R^\mathsf{T}} = \bar{R}^\mathsf{T}.</math>

Nếu <math>X = Y,</math> 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 ===
{{main|Thu hẹp (toán học)}}
Nếu ''R'' là quan hệ hai ngôi [[quan hệ thuần nhất|thuần nhất]] trên tập hợp ''X'' và ''S'' là tập hợp con của ''X'' thì <math>R_{\vert S} = \{ (x, y) \mid xRy \text{ và } x \in S \text{ và } y \in S \}</math> là {{em|{{visible anchor|quan hệ thu hẹp|Quan hệ thu hẹp}}}} 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ì <math>R_{\vert S} = \{ (x, y) \mid xRy \text{ và } x \in S \}</math> là {{em|{{visible anchor|quan hệ thu hẹp trái|Quan hệ thu hẹp trái}}}} của ''R'' về ''S'' trên ''X'' và ''Y''.{{clarify|reason=Introduce notational distinction between restriction and left restriction.|date=November 2022}}

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ì <math>R^{\vert S} = \{ (x, y) \mid xRy \text{ và } y \in S \}</math> là {{em|{{visible anchor|quan hệ thu hẹp phải|Quan hệ thu hẹp phải}}}} của ''R'' về ''S'' trên ''X'' và ''Y''.

Nếu quan hệ có tính [[quan hệ phản xạ|phản xạ]], hoàn toàn không phản xạ, [[quan hệ đối xứng|đối xứng]], [[quan hệ bất đối xứng|bất đối xứng]], [[Quan hệ bắc cầu|bắc cầu]], [[Quan hệ toàn phần|toàn phần]], [[Phân tam (toán học)|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]], [[Thứ tự yếu#Tiền thứ tự toàn phần|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 [[tính đầy đủ (lý thuyết thứ tự)|đầ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 <math>\,\leq\,</math> rằng mọi tập hợp con [[tập hợp rỗng|khác rỗng]] <math>S \subseteq \R</math> có cận trên thuộc <math>\R</math> thì sẽ có [[Supremum|cận trên nhỏ nhất]] (hay còn gọi là supremum) thuộc <math>\R.</math> 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ệ <math>\,\leq\,</math> về các số hữu tỉ.

<!---This definition is needed by the closure defs, too, but maybe should better given in an earlier section(?):--->
Quan hệ hai ngôi ''R'' trên tập hợp ''X'' và ''Y'' được gọi là {{em|{{visible anchor|chứa trong|Containment of relations}}}} (hay ''nằm trong'') quan hệ ''S'' trên ''X'' và ''Y'', được ký hiệu là <math>R \subseteq S,</math> nếu ''R'' là tập con của ''S'', nghĩa là, với mọi <math>x \in X</math> và <math>y \in Y,</math> nếu ''xRy'', thì ''xSy''. Nếu ''R'' chứa trong ''S'' và ''S'' chứa trong ''R'', thì ''R'' và ''S'' là {{em|bằng nhau}} 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à {{em|{{visible anchor|quan hệ nhỏ hơn|Quan hệ nhỏ hơn}}}} ''S'', và được viết là <math>R \subsetneq S.</math> . Lấy ví dụ từ các [[số hữu tỉ]], quan hệ <math>\,>\,</math> nhỏ hơn <math>\,\geq,\,</math> và bằng với quan hệ hợp thành <math>\,>\,\circ\,>.\,</math>

== Các loại quan hệ ==
[[Tập tin:The four types of binary relations.png|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'''):<!---[[Left-unique relation]]---><ref name=kkm/> với mọi <math>x, z \in X</math> và <math>y \in Y,</math> nếu {{math|''xRy''}} và {{math|''zRy''}} thì {{math|1=''x'' = ''z''}}. Đối với quan hệ như vậy, {''Y''} được gọi là ''khóa [[khóa chính|chính]]'' của ''R''.<ref name="Codd1970" /> Ví dụ như, quan hệ xanh lá và xanh dương trong biểu đồ có tính nội xạ, nhưng màu đỏ thì không (bởi −1 và 1 quan hệ với 1), và màu đen cũng không bởi (−1 và 1 quan hệ với 0).
* '''Phiếm hàm'''<!---[[Functional relation]]---> (cũng được gọi là '''duy nhất phải'''<!---[[Right-unique relation]]--->,<ref name=kkm/><!---[[Right-definite relation]]---><ref>{{citation|title=Spatial Information Theory: 8th International Conference, COSIT 2007, Melbourne, Australia, September 19–23, 2007, Proceedings|series=Lecture Notes in Computer Science|publisher=Springer|volume=4736|year=2007|pages=285–302|contribution=Reasoning on Spatial Semantic Integrity Constraints|first=Stephan|last=Mäs|doi=10.1007/978-3-540-74788-8_18}}</ref>):<!---[[Univalent relation]]---><ref name="gs">[[Gunther Schmidt]], 2010. ''Relational Mathematics''. Cambridge University Press, {{ISBN|978-0-521-76268-7}}, Chapt. 5</ref> với mọi <math>x \in X</math> và tất cả <math>y, z \in Y,</math> nếu {{math|''xRy''}} và {{math|''xRz''}} thì {{math|1=''y'' = ''z''}}. Quan hệ hai ngôi như vậy được gọi là {{em|[[hàm riêng phần]]}}. Trong quan hệ đó, <math>\{ X \}</math> được gọi là {{em|khóa chính}} của ''R''.<ref name="Codd1970" /> Ví dụ như, quan hệ màu xanh lá và màu đỏ có tính phiếm hàm nhưng không phải màu xanh dương bởi (1 quan hệ với cả −1 và 1) và màu đen cũng không bởi (0 quan hệ với −1 và 1).
* '''1-1'''<!---[[Quan hệ một-một]]--->: nội xạ và phiếm hàm.
* '''1-Nhiều'''<!---[Quan hệ một-nhiều]]--->: nội xạ nhưng không phiếm hàm.
* '''Nhiều-1'''<!---[[Quan hệ nhiều-một]]--->: phiếm hàm nhưng không nội xạ.
* '''Nhiều-nhiều'''<!---[Quan hệ nhiều-nhiều]]--->: không phiếm hàm cũng không nội xạ.

Tính toàn phần (chỉ định nghĩa được khi biết miền xác định ''X'' và miền giá trị ''Y'':
* '''[[Quan hệ toàn phần|Toàn phần]]''' (hay còn gọi là '''toàn phần trái'''):<ref name=kkm>Kilp, Knauer and Mikhalev: p.&nbsp;3. cả 4 định nghĩa đều có trong:
* {{chú thích sách
 | author1=Peter J. Pahl
 | author2=Rudolf Damrath
 | title=Mathematical Foundations of Computational Engineering: A Handbook
 | year=2001
 | publisher=Springer Science & Business Media|isbn=978-3-540-67995-0
 | page=506
}}
* {{chú thích sách
 | author=Eike Best
 | title=Semantics of Sequential and Parallel Programs
 | url=https://archive.org/details/semanticsofseque0000best
 | author-link=Eike Best
 | year=1996
 | publisher=Prentice Hall
 | isbn=978-0-13-460643-9
 | pages=[https://archive.org/details/semanticsofseque0000best/page/n32 19]–21
}}
* {{chú thích sách
 | author=Robert-Christoph Riemann
 | title=Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus
 | year=1999
 | publisher=Herbert Utz Verlag
 | isbn=978-3-89675-629-9
 | pages=21–22
}}</ref> với mọi ''x'' thuộc ''X'', tồn tại ''y'' thuộc ''Y'' sao cho {{math|''xRy''}}.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ị {{mvar|y}} nguyên dương nào sao cho {{math|1 > ''y''}}.<ref>{{chú thích tạp chí|last = Yao|first = Y.Y.|author2=Wong, S.K.M.|title = Generalization of rough sets using relationships between attribute values|journal = Proceedings of the 2nd Annual Joint Conference on Information Sciences|year = 1995|pages = 30–33|url = http://www2.cs.uregina.ca/~yyao/PAPERS/relation.pdf}}.</ref> 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 {{mvar|x}}, chỉ cần chọn {{math|1=''y'' = ''x''}}. 
* '''Toàn ánh'''<!---[[Quan hệ toàn ánh]]---> (hay còn gọi là '''toàn phần phải'''<!---[[Right-total relation]]---><ref name=kkm/>): với mọi ''y'' thuộc ''Y'', tồn tại ''x'' thuộc ''X'' sao cho ''xRy''. Nói cách khác, miền giá trị của ''R'' bằng ''Y''. Lấy ví dụ, quan hệ xanh lá và xanh dương trong hình có tính toàn ánh, nhưng cái màu đỏ và màu đen thì không (trong quan hệ màu đỏ, không có số thực nào quan hệ với -1, còn trong màu đen không có số thực nào quan hệ với 2).

Tính duy nhất và toàn phần (chỉ định nghĩa được khi biết miền xác định ''X'' và miền giá trị ''Y''):
* {{em|[[Hàm số]]}}: quan hệ phiếm hàm và toàn phần. Lấy ví dụ, quan hệ màu xanh lá và màu đỏ là hàm số, còn quan hệ màu xanh dương và đỏ thì không.
* {{em|[[Hàm đơn ánh|Đơn ánh]]}}: Quan hệ hàm số có tính đơn ánh. Lấy ví dụ, quan hệ màu xanh lá là hàm đơn ánh, còn lại thì không.
* {{em|[[Hàm toàn ánh|Toàn ánh]]}}: Quan hệ hàm số có tính toàn ánh. Lấy ví dụ, quan hệ màu xanh lá là hàm toàn ánh, còn lại thì không.
* {{em|[[Song ánh]]}}: Quan hệ hàm số vừa toàn ánh vừa đơn ánh. Lấy ví dụ, bởi quan hệ màu xanh lá vừa là đơn ánh vừa là toàn ánh, nên nó là quan hệ song ánh. Các quan hệ còn lại thì không

== Quan hệ thuần nhất ==
{{main|Quan hệ thuần nhất}}
'''Quan hệ thuần nhất'''<!---keep boldface: [[Homogeneous relation]] redirects to here---> trên tập ''X'' là quan hệ hai ngôi giữa ''X'' với chính nó hay tập quan hệ là tập con của tích decac <math>X \times X.</math><ref name="Winter2007"/><ref name="Müller2012">{{chú thích sách|author=M. E. Müller|title=Relational Knowledge Discovery|year=2012|publisher=Cambridge University Press|isbn=978-0-521-19021-3|page=22}}</ref><ref name="PahlDamrath2001-p496">{{chú thích sách|author1=Peter J. Pahl|author2=Rudolf Damrath|title=Mathematical Foundations of Computational Engineering: A Handbook|year=2001|publisher=Springer Science & Business Media|isbn=978-3-540-67995-0|page=496}}</ref> 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|đồ 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 {{math|''xRy''}}).
Tập tất cả các quan hệ hai ngôi <math>\mathcal{B}(X)</math> trên tập ''X'' là [[tập lũy thừa]] <math>2^{X \times X}</math>, hay còn là [[đại số Boole]]an  đ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 <math>\mathcal{B}(X)</math>, 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 {{mvar|R}} trên tập {{mvar|X}} là:
* {{em|[[Quan hệ phản xạ|Phản xạ]]}}: với <math>x \in X,</math> {{math|''xRx''}}. Ví dụ, <math>\,\geq\,</math> là quan hệ phản xạ nhưng > thì không.
* {{em|[[Quan hệ bất phản xạ|Hoàn toàn không phản xạ]]}}: với mọi <math>x \in X,</math> không {{math|''xRx''}}. Ví dụ, <math>\,>\,</math> là quan hệ hoàn toàn không phản xạ nhưng<math>\,\geq\,</math> thì phản xạ.
* {{em|[[Quan hệ đối xứng|Đối xứng]]}}: với mọi <math>x, y \in X,</math> nếu {{math|''xRy''}} thì {{math|''yRx''}}. Ví dụ, "là họ hàng của" là quan hệ đối xứng.
* {{em|[[Quan hệ phản đối xứng|Phản đối xứng]]}}: với mọi <math>x, y \in X,</math> nếu {{math|''xRy''}} và {{math|''yRx''}} thì <math>x = y.</math> Ví dụ, <math>\,\geq\,</math> là quan hệ phản đối xứng.<ref>{{citation|first1=Douglas|last1=Smith|first2=Maurice|last2=Eggen|first3=Richard|last3=St. Andre|title=A Transition to Advanced Mathematics|edition=6th|publisher=Brooks/Cole|year=2006|isbn=0-534-39900-2|page=160}}</ref>
* {{em|[[Quan hệ bất đối xứng|Bất đối xứng]]}}: với mọi <math>x, y \in X,</math> nếu {{math|''xRy''}} thì không {{math|''yRx''}}. 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.<ref>{{citation|first1=Yves|last1=Nievergelt|title=Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography|publisher=Springer-Verlag|year=2002|page=[https://books.google.com/books?id=_H_nJdagqL8C&pg=PA158 158]}}.</ref> Ví dụ, > là quan hệ bất đối xứng nhưng <math>\,\geq\,</math> thì không.
* {{em|[[Quan hệ bắc cầu|Bắc cầu]]}}: với mọi <math>x, y, z \in X,</math> nếu {{math|''xRy''}} và {{math|''yRz''}} thì {{math|''xRz''}}. 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.<ref>{{chú thích sách|last1=Flaška|first1=V.|last2=Ježek|first2=J.|last3=Kepka|first3=T.|last4=Kortelainen|first4=J.|title=Transitive Closures of Binary Relations I|year=2007|publisher=School of Mathematics&nbsp;– Physics Charles University|location=Prague|page=1|url=http://www.karlin.mff.cuni.cz/~jezek/120/transitive1.pdf|url-status=dead|archive-url=https://web.archive.org/web/20131102214049/http://www.karlin.mff.cuni.cz/~jezek/120/transitive1.pdf|archive-date=2013-11-02}} Lemma 1.1 (iv). This source refers to asymmetric relations as "strictly antisymmetric".</ref> 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.
* {{em|[[Quan hệ liên thông|Liên thông]]}}: với mọi <math>x, y \in X,</math> nếu <math>x \neq y</math> thì {{math|''xRy''}} hoặc {{math|''yRx''}}.
* {{em|[[Quan hệ liên thông|Liên thông mạnh]]}}: với <math>x, y \in X,</math> {{math|''xRy''}} hoặc {{math|''yRx''}}.

== Chú thích ==
{{Tham khảo|group=note}}

== Tham khảo ==
{{Tham khảo}}

== Sách ==
* {{Citation | last1=Enderton | first1=Herbert | title=Elements of set theory | publisher=[[Academic Press]] | location=Boston, MA | isbn=978-0-12-238440-0 | year=1977}}.
* M. Kilp, U. Knauer, A.V. Mikhalev (2000) ''Monoids, Acts and Categories: with Applications to Wreath Products and Graphs'', De Gruyter Expositions in Mathematics vol. 29, Walter de Gruyter, {{ISBN|3-11-015248-7}}.
* [[Charles Sanders Peirce]] (1870) [https://books.google.ca/books?id=fFnWmf5oLaoC&pg=PP7&source=gbs_selected_pages&cad=2#v=onepage&q&f=false Description of a Notation for the Logic of Relatives] from [[Google Books]]
* [[Gunther Schmidt]] (2010) ''Relational Mathematics'' [[Cambridge University Press]] {{ISBN|978-0-521-76268-7}}.

== Liên kết ngoài ==
* {{Thể loại Commonsinline|Binary relations}}
* {{springer|title=Binary relation|id=p/b016380}}

[[Thể loại:Quan hệ hai ngôi| ]]