Cặp được sắp

Hình học giải tích gán mỗi điểm trong mặt phẳng Euclid một cặp được sắp. Đường elip đỏ tương ứng với tập các cặp (x,y) sao chox²/4+y²=1.

Trong toán học, cặp được sắp (hay cặp có sắp) (a, b) là cặp của hai đối tượng mà thứ tự các đối tượng xuất hiện có ảnh hưởng tới giá trị. Nói cách khác, cặp được sắp (a, b) khác với cặp được sắp (b, a) trừ phi a = b. (Ngược lại, cặp không sắp {a, b} bằng với cặp không sắp {b, a}.)

Cặp được sắp cũng được gọi là bộ 2, hoặc dãy (còn gọi là chuỗi trong khoa học máy tính) có độ dài 2. Cặp được sắp của các scalar được gọi là vector 2 chiều. (Song, lưu ý, do phần tử của cặp được sắp có thể là đối tượng toán học tuỳ ý, nên cặp được sắp không nhất thiết phải là phần tử của một không gian vectơ) Phần tử của cặp được sắp có thể là cặp được sắp khác, cho phép ta định nghĩa đệ quy bộ n phần tử (danh sách có thứ tự của n đối tượng. Ví dụ chẳng hạn bộ 3 phần tử (a,b,c) có thể định nghĩa là (a, (b,c)) (chứa cặp được sắp (b, c)).

Trong cặp được sắp (a, b), đối tượng a được gọi là phần tử đầu, còn đối tượng b được gọi là phần tử thứ hai của cặp. Ngoài ra ta cũng có thể gọi là thành phần đầu và thứ hai, hoặc giá trị trái và giá trị phải của cặp.

Tích đề các và quan hệ hai ngôi (và cùng với đó là các hàm số) đều được định nghĩa theo cặp được sắp.

Tổng quát

Gọi ${\displaystyle (a_{1},b_{1})}$ và ${\displaystyle (a_{2},b_{2})}$ là hai cặp được sắp. Khi đó tính chất đặc trưng (hoặc tính chất định nghĩa) của cặp được sắp là:

${\displaystyle (a_{1},b_{1})=(a_{2},b_{2}){\text{ khi và chỉ khi }}a_{1}=a_{2}{\text{ và }}b_{1}=b_{2}.}$

Tập hợp của tất cả các cặp có phần tử đầu thuộc tập hợp A và phần tử thứ hai thuộc tập hợp B được gọi là tích Descartes của A và B, được viết là A × B. Quan hệ hai ngôi giữa tập hợp A và B là tập con của A × B.

Ký hiệu (a, b) có thể sử dụng cho các đối tượng khác, ví dụ như khoảng mở trên đường số thực. Trong các tình huống như vậy, ta cần phân biệt rõ ràng giữa hai ký hiệu định dùng.^[1][2] Đôi khi để làm phân biệt rõ, có thể dùng ${\textstyle \langle a,b\rangle }$ thay vì thế song ký hiệu này cũng có thể sử dụng cho những cái khác.

Phần tử đầu tiên và phần tử thứ hai của cặp p thường được ký hiệu là π₁(p) và π₂(p), hoặc là π_ℓ(p) và π_r(p), tương ứng. Khi xét các bộ n phần tử, ta thường dùng πⁿ
_i(t) để ký hiệu cho phần tử thứ i trong bộ t.

Định nghĩa không hình thức và định nghĩa hình thức

Một số sách giới thiệu chủ đề này thường dùng định nghĩa sau

Cho bất kỳ hai đối tượng a và b, cặp được ký hiệu (a, b) ký hiệu hai đối tượng a và b, theo thứ tự đó.^[3]

Sau đó thường là so sánh hai tập hợp hai phần tử; và chỉ ra rằng trong tập hợp thì a và b phải khác nhau nhưng trong cặp được sắp thì chúng có thể bằng nhau và thay đổi thứ tự các phần tử trong tập hợp không làm thay đổi nó, trong khi thay đổi thứ tự các phần tử trong cặp được sắp sẽ thay đổi cặp được sắp đó.

"Định nghĩa này" chưa được coi là định nghĩa hình thức bởi nó mới chỉ mô tả cặp được sắp và đều dựa trên cách hiểu trực giác của thứ tự. Tuy nhiên, thường không có vấn đề gì từ cách hiểu này và hầu như mọi người đều hiểu nó theo cách này.^[4]

Một cách tiếp cận chính thức khác là quan sát rằng tính chất đặc trưng là tất cả những gì cần để hiểu vai trò của cặp được sắp trong toán học. Do đó, có thể coi thuật ngữ cặp được sắp là thuật ngữ nguyên thuỷ, trong đó tiên đề gắn liền với nó là tính chất đặc trưng. Phương pháp tiếp cận này được thực hiện bởi nhóm N. Bourbaki trong cuốn sách Theory of Sets (dịch: Lý thuyết các tập hợp) được xuất bản vào năm 1954. Tuy nhiên, điểm yếu của phương pháp này là ta phải coi sự tồn tại của cặp được sắp và tính chất đặc trưng là các tiên đề.^[3]

Một cách chính thức hơn đó là tiếp cận định nghĩa này bằng lý thuyết tập hợp. Có nhiều cách để định nghĩa cặp được sắp theo phương pháp tiếp cận này và lợi thế của nó là sự tồn tại và tính chất đặc trưng đều có thể được chứng minh từ các tiên đề định nghĩa lý thuyết tập hợp. Một trong những định nghĩa hay được dẫn nhất là của Kuratowski (xem dưới) và định nghĩa của ông được dùng trong bản thứ hai của cuốn Theory of Sets của Bourbaki, xuất bản vào năm 1970. Kể cả các sách toán học khác có chứa định nghĩa chưa chính thức của cặp được sắp thường dùng định nghĩa hình thức của Kuratowski làm bài tập.

Định nghĩa cặp được sắp bằng lý thuyết tập hợp

Nếu thống nhất rằng lý thuyết tập hợp có thể dùng làm nền tảng của toán học, thì mọi đối tượng toán học đều phải định nghĩa là một dạng tập hợp nào đó.Do đó, nếu không coi cặp được sắp là tiên đề, thì nó phải là một tập hợp.^[5] Từ đó sinh ra một số định nghĩa sau ( xem thêm ^[6]).

Định nghĩa của Wiener

Năm 1914, Norbert Wiener là người đầu tiên đề xuất định nghĩa cặp được sắp theo lý thuyết tập hợp:^[7]

${\displaystyle \left(a,b\right):=\left\{\left\{\left\{a\right\},\,\emptyset \right\},\,\left\{\left\{b\right\}\right\}\right\}.}$

Ông quan sát rằng định nghĩa giúp ta có thể định nghĩa các kiểu trong cuốn Principia Mathematica thành các tập hợp. Cuốn Principia Mathematica coi các kiểu và các quan hệ n-ngôi là thuật ngữ nguyên thuỷ.

Wiener sử dụng {{b}} thay vì {b} để khiến định nghĩa này tương thích với lý thuyết kiểu trong đó tất cả các phần tử cùng một lớp cũng phải đều cùng một "kiểu". Với b nằm trong tập khác, kiểu của nó bằng với ${\displaystyle \{\{a\},\emptyset \}}$.

Định nghĩa của Hausdorff

Cùng thời gian đó với Wiener (1914), Felix Hausdorff đề xuất định nghĩa sau:

${\displaystyle (a,b):=\left\{\{a,1\},\{b,2\}\right\}}$

"trong đó 1 và 2 là hai đối tượng phân biệt khác a và b."^[8]

Định nghĩa của Kuratowski

Trong 1921 Kazimierz Kuratowski đề xuất định nghĩa nay được chấp nhận rộng rãi sau^[9][10] :

${\displaystyle (a,\ b)_{K}\;:=\ \{\{a\},\ \{a,\ b\}\}.}$

Định nghĩa vẫn dùng được kể cả khi phần tử thứ nhất và phần tử thứ hai bằng nhau

${\displaystyle (x,\ x)_{K}=\{\{x\},\{x,\ x\}\}=\{\{x\},\ \{x\}\}=\{\{x\}\}}$

Cho cặp được sắp p, tính chất "x là phần tử đầu của p" có thể viết thành công thức:

${\displaystyle \forall Y\in p:x\in Y.}$

Tính chất "x là phần tử thứ hai của p" có thể viết thành:

${\displaystyle (\exists Y\in p:x\in Y)\land (\forall Y_{1},Y_{2}\in p:Y_{1}\neq Y_{2}\rightarrow (x\notin Y_{1}\lor x\notin Y_{2})).}$

Công thức sau lấy phần tử đầu tiên của cặp (công thức này sử dụng các ký hiệu toán tử tuần tự cho giao tuỳ ý và hợp tuỳ ý):

${\displaystyle \pi _{1}(p)=\bigcup \bigcap p.}$

Đây là công thức cho phần tử thứ hai:

${\displaystyle \pi _{2}(p)=\bigcup \left\{\left.x\in \bigcup p\,\right|\,\bigcup p\neq \bigcap p\rightarrow x\notin \bigcap p\right\}.}$

Các dạng khác

Định nghĩa trên của Kuratowski "ổn hơn" là bởi nó thoả mãn tính chất đặc trưng mà cặp được sắp phải thoả mãn, tức là ${\displaystyle (a,b)=(x,y)\leftrightarrow (a=x)\land (b=y)}$.Ngoài ra, nó cũng ổn hơn khi dùng để biển diễn 'thứ tự', tức là ${\displaystyle (a,b)=(b,a)}$ sai trừ khi ${\displaystyle b=a}$. Có một số định nghĩa khác tương tự hoặc kém phức tạp hơn sau:

• ${\displaystyle (a,b)_{\text{reverse}}:=\{\{b\},\{a,b\}\};}$
• ${\displaystyle (a,b)_{\text{short}}:=\{a,\{a,b\}\};}$
• ${\displaystyle (a,b)_{\text{01}}:=\{\{0,a\},\{1,b\}\}.}$^[11]

Định nghĩa reverse dễ thấy từ định nghĩa gốc, do đó không có gì đặc biệt cả. Định nghĩa short (ngắn) được gọi như vậy vì nó chỉ cần hai thay vì ba cặp ngoặc nhọn. Chứng minh rằng định nghĩa short thoả mãn tính chất đặc trưng yêu cầu phải dùng tiên đề chính quy trong hệ tiên đề của Zermelo–Fraenkel.^[12] Hơn nữa, nếu dùng phương pháp xây dựng số tự nhiên bằng lý thuyết tập hợp của von Neumann, thì số 2 được định nghĩa là tập {0, 1} = {0, {0}}, không phân biệt với (0, 0)_short. Một bất lợi thế khác của các cặp theo định nghĩa short là: kể cả khi a và b có cùng kiểu, thì các phần tử trong cặp short không nhất thiết cũng phải. (Song, nếu a = b thì phiên bản short vẫn giữ số lực lượng 2)

Chứng minh các định nghĩa này thoả mãn tính chất đặc trưng

Chứng minh: (a, b) = (c, d) khi và chỉ khi a = c và b = d.

Kuratowski:
Ngược. Nếu a = c và b = d, thì {{a}, {a, b}} = {{c}, {c, d}}. Do đó (a, b)_K = (c, d)_K.

Xuôi. Hai trường hợp: a = b, và a ≠ b.

Nếu a = b:

(a, b)_K = {{a}, {a, b}} = {{a}, {a, a}} = {{a}}.

{{c}, {c, d}} = (c, d)_K = (a, b)_K = {{a}}.

Do vậy, {c} = {c, d} = {a}, suy ra a = c và a = d. Theo giả thuyết, a = b nên b = d.

Nếu a ≠ b, thì (a, b)_K = (c, d)_K suy ra {{a}, {a, b}} = {{c}, {c, d}}.

Giả sử {c, d} = {a}. Khi đó c = d = a, và {{c}, {c, d}} = {{a}, {a, a}} = {{a}, {a}} = {{a}}. Nhưng vì {{a}, {a, b}} sẽ bằng {{a}}, dẫn tới b = a, mâu thuẫn với a ≠ b.

Giả sử {c} = {a, b}. Khi đó a = b = c, do vậy vẫn mâu thuẫn với a ≠ b.

Do đó {c} = {a}, khi đó c = a và {c, d} = {a, b}.

Nếu d = a đúng thì {c, d} = {a, a} = {a} ≠ {a, b}, mâu thuẫn với giả thuyết. Do vậy d = b, nên ta được a = c và b = d.

Reverse:
(a, b)_reverse = {{b}, {a, b}} = {{b}, {b, a}} = (b, a)_K.

Xuôi. Nếu (a, b)_reverse = (c, d)_reverse, (b, a)_K = (d, c)_K. Do vậy, b = d và a = c.

Ngược. Nếu a = c and b = d, thì {{b}, {a, b}} = {{d}, {c, d}}. Do đó (a, b)_reverse = (c, d)_reverse.

Short:^[13]

Ngược: Nếu a = c và b = d, thì {a, {a, b}} = {c, {c, d}}. Do đó (a, b)_short = (c, d)_short.

Xuôi: Giả sử {a, {a, b}} = {c, {c, d}}. Khi đó bởi a nằm trong vế trái nên cũng phải nằm trong vế phải bởi vì hai cặp bằng nhau phải có các phần tử bằng nhau, do đó hoặc a = c hoặc a = {c, d}

Nếu a = {c, d}, thì sử dụng lý luận như trên, {a, b} nằm trong vế phải do đó, {a, b} = c hoặc {a, b} = {c, d}.

Nếu {a, b} = c thì c nằm trong {c, d} = a và a thuộc c, và phép phối hợp nào mâu thuẫn với tiên đề chính quy bởi {a, c} không có phần tử tối thiểu nào dưới quan hệ "là phần tử của."

Nếu {a, b} = {c, d}, thì a là phần tử của a, lấy từ a = {c, d} = {a, b}, một lần nữa mâu thuẫn với tiên đề chính quy.

Do vậy trường hợp a = c phải đúng.

Khi đó,nhận thấy rằng chỉ có thể {a, b} = c hoặc {a, b} = {c, d}.

Lựa chọn {a, b} = c và a = c sẽ suy ra c là phần tử của c, trái ngược với tiên đề chính quy.

Do vậy a = c và {a, b} = {c, d}, và khi đó: {b} = {a, b} \ {a} = {c, d} \ {c} = {d}, nên b = d.

Định nghĩa của Quine–Rosser

Rosser (1953)^[14] đặt ra một định nghĩa khác dựa trên phương pháp của Quine, trong đó yêu cầu ta cần định nghĩa trước các số tự nhiên. Gọi ${\displaystyle \mathbb {N} }$ là tập hợp của các số tự nhiên và định nghĩa trước hàm sau

${\displaystyle \sigma (x):={\begin{cases}x,&{\text{nếu }}x\not \in \mathbb {N} ,\\x+1,&{\text{nếu }}x\in \mathbb {N} .\end{cases}}}$

Hàm ${\displaystyle \sigma }$ thêm một vào giá trị tham số nếu nó là số tự nhiên và giữ nó nếu nó không phải. Do vậy số 0 không phải là giá trị của ${\displaystyle \sigma }$ Gọi tập ${\displaystyle x\smallsetminus \mathbb {N} }$ là tập các phần tử ${\displaystyle x}$ không thuộc ${\displaystyle \mathbb {N} }$. Khi đó

${\displaystyle \varphi (x):=\sigma [x]=\{\sigma (\alpha )\mid \alpha \in x\}=(x\smallsetminus \mathbb {N} )\cup \{n+1:n\in (x\cap \mathbb {N} )\}.}$

Đây là tập ảnh của tập hợp ${\displaystyle x}$ dưới ${\displaystyle \sigma }$, đôi khi cũng được ký hiệu là ${\displaystyle \sigma ''x}$. Áp dụng hàm ${\displaystyle \varphi }$ cho tập x chỉ cộng thêm một cho mọi số tự nhiên trong đó.Cụ thể hơn, ${\displaystyle \varphi (x)}$ không bao giờ chứa số 0, nên cho bất kỳ tập x và tập y,

${\displaystyle \varphi (x)\neq \{0\}\cup \varphi (y).}$

Định nghĩa thêm hàm

${\displaystyle \psi (x):=\sigma [x]\cup \{0\}=\varphi (x)\cup \{0\}.}$

Bằng cách này, ${\displaystyle \psi (x)}$ luôn chứa số 0.

Cuối cùng, ta định nghĩa cặp được sắp (A, B) là hợp không giao nhau sau

${\displaystyle (A,B):=\varphi [A]\cup \psi [B]=\{\varphi (a):a\in A\}\cup \{\varphi (b)\cup \{0\}:b\in B\}.}$

(tức là ${\displaystyle \varphi ''A\cup \psi ''B}$ trong ký hiệu thay phiên).

Lấy tất cả các phần tử trong cặp không chứa 0 và đảo ngược ${\displaystyle \varphi }$ sẽ ra A.Tương tự như vậy, B có thể thu về được từ các phần tử có chứa số 0.^[15]

Ví dụ chẳng hạn, cặp được sắp ${\displaystyle (\{\{a,0\},\{b,c,1\}\},\{\{d,2\},\{e,f,3\}\})}$ sẽ được mã hoá thành ${\displaystyle \{\{a,1\},\{b,c,2\},\{d,3,0\},\{e,f,4,0\}\}}$ nếu như ${\displaystyle a,b,c,d,e,f\notin \mathbb {N} }$.

Tham khảo

1. Lay, Steven R. (2005), Analysis / With an Introduction to Proof (ấn bản thứ 4), Pearson / Prentice Hall, tr. 50, ISBN 978-0-13-148101-5
2. Devlin, Keith (2004), Sets, Functions and Logic / An Introduction to Abstract Mathematics (ấn bản thứ 3), Chapman & Hall / CRC, tr. 79, ISBN 978-1-58488-449-1
3. ^ Wolf, Robert S. (1998), Proof, Logic, and Conjecture / The Mathematician's Toolbox, W. H. Freeman and Co., tr. 164, ISBN 978-0-7167-3050-7
4. Fletcher, Peter; Patty, C. Wayne (1988), Foundations of Higher Mathematics, PWS-Kent, tr. 80, ISBN 0-87150-164-3
5. Quine đã cho rằng các cách áp dụng lý thuyết tập hợp cho khái niệm cặp được sắp là mẫu hình để hiểu rõ các ý tưởng triết học (xem "Word and Object" (dịch: "từ và vật", mục 53)). Phương pháp chung cho cách định nghĩa hay hay áp dụng đều được thảo luận trong cuốn "Reasoning about theoretical entities" (dịch: "lập luận về các thực thể trong lý thuyết") của Thomas Forster.
6. Dipert, Randall. “Set-Theoretical Representations of Ordered Pairs and Their Adequacy for the Logic of Relations”.
7. Bài viết của Wiener "A Simplification of the logic of relations" (dịch: "giản hóa của logic các quan hệ") được in lại, cùng với một bình luận đáng chú ý trong trang 224ff trong van Heijenoort, Jean (1967), From Frege to Gödel: A Source Book in Mathematical Logic, 1979–1931, Harvard University Press, Cambridge MA, ISBN 0-674-32449-8 (pbk.). van Heijenoort phát biểu cách giản hóa như sau: "By giving a definition of the ordered pair of two elements in terms of class operations, the note reduced the theory of relations to that of classes" (dịch: "Bằng việc định nghĩa cặp được sắp của hai phần tử theo các phép toán cho lớp, ta đã rút gọn lý thuyết các quan hệ về lý thuyết các lớp).
8. cf introduction to Wiener's paper in van Heijenoort 1967:224
9. chú thích từ giới thiệu trong bài của Wiener trong van Heijenoort 1967:224. van Heijenoort quan sát rằng tập thu được mà biểu diễn cặp được sắp "có kiểu lớn hơn 2 so với các phần tử (khi chúng thuộc cùng 1 kiểu)"; ông thường chú thích điều này để cho thấy rằng, dưới một số trường hợp, ta có thể rút gọn kiểu về 1 hoặc 0.
10. Kuratowski, Casimir (1921). “Sur la notion de l'ordre dans la Théorie des Ensembles” (PDF). Fundamenta Mathematicae. 2 (1): 161–171. doi:10.4064/fm-2-1-161-171. Bản gốc (PDF) lưu trữ ngày 29 tháng 4 năm 2019. Truy cập ngày 29 tháng 5 năm 2013.
11. Khác với định nghĩa của Hausdorff ở chỗ không yêu cầu hai phần tử 0 và 1 phải khác với a và b.
12. Tourlakis, George (2003) Lectures in Logic and Set Theory. Vol. 2: Set Theory. Cambridge Univ. Press. Proposition III.10.1.
13. For a formal Metamath proof of the adequacy of short, see here (opthreg). Also see Tourlakis (2003), Proposition III.10.1.
14. J. Barkley Rosser, 1953. Logic for Mathematicians. McGraw–Hill.
15. Holmes, M. Randall: On Ordered Pairs, on: Boise State, March 29, 2009. The author uses ${\displaystyle \sigma _{1}}$ for ${\displaystyle \varphi }$ and ${\displaystyle \sigma _{2}}$ for ${\displaystyle \psi }$.