Quan hệ phản xạ

Quan hệ hai ngôi
Đối xứng Phản đối xứng Toàn phần Lập tốt Có nối Có gặp Quan hệ tương đương ✓ ✗ ✗ ✗ ✗ ✗ Tiền thứ tự (giả thứ tự) ✗ ✗ ✗ ✗ ✗ ✗ Thứ tự riêng phần ✗ ✓ ✗ ✗ ✗ ✗ Tiền thứ tự toàn phần ✗ ✗ ✓ ✗ ✗ ✗ Thứ tự toàn phần ✗ ✓ ✓ ✗ ✗ ✗ Tiền thứ tự tốt ✗ ✗ ✓ ✓ ✗ ✗ Giả thứ tự tốt ✗ ✗ ✗ ✓ ✗ ✗ Thứ tự tốt ✗ ✓ ✓ ✓ ✗ ✗ Dàn ✗ ✓ ✗ ✗ ✓ ✓ Nửa dàn có nối ✗ ✓ ✗ ✗ ✓ ✗ Nửa dàn có gặp ✗ ✓ ✗ ✗ ✗ ✓
Dấu "✓" chỉ tính chất trong cột đó cần phải có trong định nghĩa của hàng đó. Ví dụ, định nghĩa của quan hệ tương đương buộc nó phải có tính đối xứng. Tất cả định nghĩa đều yêu cầu tính bắc cầu và tính phản xạ.

Trong toán học, quan hệ hai ngôi R trên tập X có tính phản xạ nếu nó quan hệ mỗi phần tử của X tới chính phần tử đó.^[1][2]. Nếu quan hệ có tính phản xạ thì ta gọi quan hệ đó là quan hệ phản xạ.

Một ví dụ của quan hệ phản xạ là quan hệ "bằng với" trên tập các số, bởi mỗi số đều bằng với chính nó. Cùng với tính đối xứng và tính bắc cầu, 3 tính chất lập thành quan hệ tương đương

Định nghĩa

Gọi ${\displaystyle R}$ là quan hệ hai ngôi trên tập ${\displaystyle X,}$, theo định nghĩa tức là tập con của ${\displaystyle X\times X.}$ Cho bất kỳ ${\displaystyle x,y\in X,}$ ký hiệu ${\displaystyle xRy}$ nghĩa là ${\displaystyle (x,y)\in R}$ trong khi "không ${\displaystyle xRy}$" nghĩa là ${\displaystyle (x,y)\not \in R.}$

Quan hệ ${\displaystyle R}$ được gọi là có tính phản xạ nếu ${\displaystyle xRx}$ với mọi ${\displaystyle x\in X}$ hoặc tương đương: nếu ${\displaystyle \operatorname {I} _{X}\subseteq R}$ trong đó ${\displaystyle \operatorname {I} _{X}:=\{(x,x)~:~x\in X\}}$ ký hiệu quan hệ đơn vị trên ${\displaystyle X.}$ Bao đóng phản xạ của ${\displaystyle R}$ là hợp ${\displaystyle R\cup \operatorname {I} _{X},}$, hay định nghĩa tương đương của nó là quan hệ phản xạ nhỏ nhất đối với ${\displaystyle \subseteq }$) trên tập ${\displaystyle X}$ là tập chứa của ${\displaystyle R.}$ Quan hệ ${\displaystyle R}$ có tính phản xạ khi và chỉ khi nó bằng với bao đóng phản xạ của nó,

Rút gọn phản xạ hay hạt nhân không phản xạ của ${\displaystyle R}$ là quan hệ nhỏ nhất (đối với ${\displaystyle \subseteq }$) trên ${\displaystyle X}$ có bao đóng phản xạ của nó bằng với ${\displaystyle R.}$ Nó bằng với ${\displaystyle R\setminus \operatorname {I} _{X}=\{(x,y)\in R~:~x\neq y\}.}$ Hạt nhân không phản xạ của ${\displaystyle R}$ có thể hiểu là cách xây "ngược lại" với bao đóng phản xạ ${\displaystyle R.}$ Lấy ví dụ, bao đóng phản xạ của quan hệ chặt chính tắc ${\displaystyle <}$ trên các số thực ${\displaystyle \mathbb {R} }$ là quan hệ không chặt ${\displaystyle \leq }$ trong khi rút gọn phản xạ của ${\displaystyle \leq }$ là ${\displaystyle <.}$

Các định nghĩa gần với tính phản xạ

Có một số định nghĩa gần với tính phản xạ. Quan hệ ${\displaystyle R}$ được gọi là có tính:

Hoàn toàn không phản xạ ^[3]

Nếu nó không quan hệ bất cứ phần tử nào với chính nó; nghĩa là không ${\displaystyle xRx}$ với mọi ${\displaystyle x\in X.}$ Quan hệ hoàn toàn không phản xạ khi và chỉ khi phần bù của nó trong ${\displaystyle X\times X}$ có tính phản xạ. Quan hệ không đối xứng thì cũng sẽ không phản xạ. Quan hệ bắc cầu và hoàn toàn không phản xạ thì sẽ không đối xứng.

Tựa phản xạ trái

Bất cứ khi nào có ${\displaystyle x,y\in X}$ sao cho ${\displaystyle xRy,}$ thì ${\displaystyle xRx.}$^[4]

Tựa phản xạ phải

Bất cứ khi nào có ${\displaystyle x,y\in X}$ sao cho ${\displaystyle xRy,}$ thì ${\displaystyle yRy.}$

Tựa phản xạ

Nếu hai phần tử có quan hệ với nhau, thì mỗi phần tử trong cặp quan hệ đó có quan hệ với chính nó. Cụ thể hơn, nghĩa là bất cứ khi nào có ${\displaystyle x,y\in X}$ sao cho ${\displaystyle xRy,}$ thì ${\displaystyle xRx}$ và ${\displaystyle yRy.}$ Một định nghĩa tương đương khác là, quan hệ hai ngôi có tính tựa phản xạ khi và chỉ khi nó vừa tựa phản xạ trái vừa tựa phản xạ phải. Một quan hệ ${\displaystyle R}$ có tính tựa phản xạ khi và chỉ khi bao đóng phản xạ ${\displaystyle R\cup R^{\operatorname {T} }}$ có tính tựa phản xạ trái hoặc phải.

Phản xứng

Bất cứ khi nào ${\displaystyle x,y\in X}$ sao cho ${\displaystyle xRy{\text{ và }}yRx,}$ thì ${\displaystyle x=y.}$

Đối phản xạ

Bất cứ khi nào ${\displaystyle x,y\in X}$ sao cho ${\displaystyle xRy,}$ thì ${\displaystyle x=y.}$^[5] Quan hệ ${\displaystyle R}$ có tính đối phản xạ khi và chỉ khi bao đóng phản xạ của nó có tính phản đối xứng.

Quan hệ phản xạ trên tập khác rỗng ${\displaystyle X}$ không thể hoàn toàn không phản xạ, không đối xứng (${\displaystyle R}$ được gọi là không đối xứng nếu ${\displaystyle xRy}$ thì không ${\displaystyle yRx}$), và không bắc cầu (${\displaystyle R}$ được gọi là không bắc cầu nếu ${\displaystyle xRy{\text{ và }}yRz}$ thì không ${\displaystyle xRz}$).

Các ví dụ

Các ví dụ của quan hệ phản xạ bao gồm:

• "bằng với" (đẳng thức)
• "là tập con của" (bao hàm tập hợp)
• "là ước của" (Tính chia hết)
• "lớn hơn hoặc bằng với"
• "nhỏ hơn hoặc bằng với"

Các ví dụ của quan hệ không phản xạ bao gồm:

• "không bằng với"
• "nguyên tố cùng nhau" trên các số nguyên lớn hơn 1
• "là tập con thực sự của"
• "lớn hơn"
• "nhỏ hơn"

Nếu quan hệ không có tính phản xạ thì không nhất thiết nó hoàn toàn không phản xạ; ta có thể định nghĩa quan hệ sao cho một số phần tử có quan hệ với chính nó nhưng các phần tử khác thì không (nghĩa là không phải tất cả đều phải có tính phản xạ) . Lấy ví dụ, quan hệ hai ngôi "tích của ${\displaystyle x}$ và ${\displaystyle y}$ là số chẵn" có tính phản xạ trên tập các số chẵn, hoàn toàn không phản xạ trên tập các số lẻ, và không có tính phản xạ hay hoàn toàn không phản xạ trên tập các số tự nhiên.

Số các quan hệ phản xạ

Số các quan hệ phản xạ trên tập có ${\displaystyle n}$ phần tử là ${\displaystyle 2^{n^{2}-n}.}$^[6]

Số các quan hệ từng loại của tập hợp có n phần tử

Số phần tử	Bất kì	Bắc cầu	Phản xạ	Đối xứng	Tiền thứ tự	Thứ tự bộ phận	Tiền thứ tự toàn phần	Thứ tự toàn phần	Quan hệ tương đương
0	1	1	1	1	1	1	1	1	1
1	2	2	1	2	1	1	1	1	1
2	16	13	4	8	4	3	3	2	2
3	512	171	64	64	29	19	13	6	5
4	65536	3994	4096	1024	355	219	75	24	15
n	2^n2		2^n2−n	2^n(n+1)/2			${\textstyle \sum _{k=0}^{n}k!S(n,k)}$	n!	${\textstyle \sum _{k=0}^{n}S(n,k)}$
OEIS	A002416	A006905	A053763	A006125	A000798	A001035	A000670	A000142	A000110

Trong đó S(n, k) là số Stirling loại thứ hai.

Logic triết học

Các tác giả trong logic triết học thường sử dụng thuật ngữ khác so với toán học. Quan hệ phản xạ trong toán học thì sẽ được gọi là phản xạ toàn phần trong logic triết học, còn quan hệ tựa phản xạ thì sẽ được gọi là quan hệ phản xạ.^[7][8]

Chú thích

1. Levy 1979:74
2. Relational Mathematics, 2010
3. Ngoài ra còn có tên phản phản xạ và alioreflexive, thuật ngữ được đưa bởi C S Peirce, xem Bertrand Russell (tháng 4 năm 1920). Introduction to Mathematical Philosophy (PDF) (ấn bản thứ 2). London: George Allen & Unwin, Ltd. (Online corrected edition, Feb 2010). Here: p. 32. Russel also introduces two equivalent terms to be contained in or imply diversity.
4. Quyển Encyclopedia Britannica gọi tính chất này là tựa phản xạ.
5. Fonseca de Oliveira, J. N., & Pereira Cunha Rodrigues, C. D. J. (2004). Transposing Relations: From Maybe Functions to Hash Tables. In Mathematics of Program Construction (p. 337).
6. On-Line Encyclopedia of Integer Sequences A053763
7. Alan Hausman; Howard Kahane; Paul Tidman (2013). Logic and Philosophy — A Modern Introduction. Wadsworth. ISBN 1-133-05000-X. Here: p.327-328
8. D.S. Clarke; Richard Behling (1998). Deductive Logic — An Introduction to Evaluation Techniques and Logical Theory. University Press of America. ISBN 0-7618-0922-8. Here: p.187

Tham khảo

• Levy, A. (1979) Basic Set Theory, Perspectives in Mathematical Logic, Springer-Verlag. Reprinted 2002, Dover. ISBN 0-486-42079-5
• Lidl, R. and Pilz, G. (1998). Applied abstract algebra, Undergraduate Texts in Mathematics, Springer-Verlag. ISBN 0-387-98290-6
• Quine, W. V. (1951). Mathematical Logic, Revised Edition. Reprinted 2003, Harvard University Press. ISBN 0-674-55451-5
• Gunther Schmidt, 2010. Relational Mathematics. Cambridge University Press, ISBN 978-0-521-76268-7.

Liên kết ngoài

• Hazewinkel, Michiel biên tập (2001), “Reflexivity”, Bách khoa toàn thư Toán học, Springer, ISBN 978-1-55608-010-4