✨Cặp được sắp

thumb|[[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 cho+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 $(a\_1,\; b\_1)$ và $(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à:

:$(a\_1,\; b\_1)\; =\; (a\_2,\; b\_2)\backslash text\{\; khi\; và\; chỉ\; khi\; \}\; a\_1\; =\; a\_2\backslash 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 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. Đôi khi để làm phân biệt rõ, có thể dùng $\backslash langle\; a,b\backslash 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 (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 và , cặp được ký hiệu ký hiệu hai đối tượng và , theo thứ tự đó.

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ì và 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.

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 đề. Từ đó sinh ra một số định nghĩa sau ( xem thêm ).

Đị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: :$\backslash left(\; a,\; b\; \backslash right)\; :=\; \backslash left\{\backslash left\{\; \backslash left\{a\backslash right\},\backslash ,\; \backslash emptyset\; \backslash right\},\backslash ,\; \backslash left\{\backslash left\{b\backslash right\}\backslash right\}\backslash 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 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 $\{\{a\},\; \backslash emptyset\}$.

Định nghĩa của Hausdorff

Cùng thời gian đó với Wiener (1914), Felix Hausdorff đề xuất định nghĩa sau: : $(a,\; b)\; :=\; \backslash left\{\; \{a,\; 1\},\; \{b,\; 2\}\; \backslash right\}$ "trong đó 1 và 2 là hai đối tượng phân biệt khác a và b."

Đị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

: :$(a,\; \backslash \; b)\_K\; \backslash ;\; :=\; \backslash \; \backslash \{\; \backslash \{\; a\; \backslash \},\; \backslash \; \backslash \{\; a,\; \backslash \; b\; \backslash \}\; \backslash \}.$ Đị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 : $(x,\backslash \; x)\_K\; =\; \backslash \{\backslash \{x\backslash \},\backslash \{x,\; \backslash \; x\backslash \}\backslash \}\; =\; \backslash \{\backslash \{x\backslash \},\backslash \; \backslash \{x\backslash \}\backslash \}\; =\; \backslash \{\backslash \{x\backslash \}\backslash \}$

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: :$\backslash forall\; Y\backslash in\; p:x\backslash in\; Y.$ Tính chất "x là phần tử thứ hai của p" có thể viết thành: :$(\backslash exist\; Y\backslash in\; p:x\backslash in\; Y)\backslash land(\backslash forall\; Y\_1,Y\_2\backslash in\; p:Y\_1\backslash ne\; Y\_2\backslash rarr\; (x\backslash notin\; Y\_1\backslash lor\; x\; \backslash 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ỳ ý):

:$\backslash pi\_1(p)\; =\; \backslash bigcup\backslash bigcap\; p.$

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

:$\backslash pi\_2(p)\; =\; \backslash bigcup\backslash left\{\backslash left.\; x\; \backslash in\; \backslash bigcup\; p\backslash ,\backslash right|\backslash ,\backslash bigcup\; p\; \backslash neq\; \backslash bigcap\; p\; \backslash rarr\; x\; \backslash notin\; \backslash bigcap\; p\; \backslash 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à $(a,b)\; =\; (x,y)\; \backslash leftrightarrow\; (a=x)\; \backslash land\; (b=y)$.Ngoài ra, nó cũng ổn hơn khi dùng để biển diễn 'thứ tự', tức là $(a,b)\; =\; (b,a)$ sai trừ khi $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:

• $(\; a,\; b\; )\_\{\backslash text\{reverse\; :=\; \backslash \{\; \backslash \{\; b\; \backslash \},\; \backslash \{a,\; b\backslash \}\backslash \};$
• $(\; a,\; b\; )\_\{\backslash text\{short\; :=\; \backslash \{\; a,\; \backslash \{a,\; b\backslash \}\backslash \};$
• $(\; a,\; b\; )\_\{\backslash text\{01\; :=\; \backslash \{\backslash \{0,\; a\; \backslash \},\; \backslash \{1,\; b\; \backslash \}\backslash \}.$ Đị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. 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ì = . 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 = = = . : = (c, d)_K = (a, b)_K = . :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 = .

:Giả sử {c, d} = {a}. Khi đó c = d = a, và = = = . Nhưng vì sẽ bằng , 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)_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ì = . Do đó (a, b)_reverse = (c, d)_reverse.

Short:

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) đặ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 $\backslash N$ là tập hợp của các số tự nhiên và định nghĩa trước hàm sau : Hàm $\backslash 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 $\backslash sigma$ Gọi tập $x\; \backslash smallsetminus\; \backslash N$ là tập các phần tử $x$ không thuộc $\backslash N$. Khi đó :$\backslash varphi(x)\; :=\; \backslash sigma[x]\; =\; \{\backslash sigma(\backslash alpha)\backslash mid\backslash alpha\; \backslash in\; x\}\; =\; (x\; \backslash smallsetminus\; \backslash N)\; \backslash cup\; \{n+1\; :\; n\; \backslash in\; (x\; \backslash cap\; \backslash N)\; \}.$ Đây là tập ảnh của tập hợp $x$ dưới $\backslash sigma$, đôi khi cũng được ký hiệu là $\backslash sigma\_x$. Áp dụng hàm $\backslash varphi$ cho tập x chỉ cộng thêm một cho mọi số tự nhiên trong đó.Cụ thể hơn, $\backslash varphi(x)$ không bao giờ chứa số 0, nên cho bất kỳ tập x và tập _y'', :$\backslash varphi(x)\; \backslash neq\; \{0\}\; \backslash cup\; \backslash varphi(y).$ Định nghĩa thêm hàm :$\backslash psi(x)\; :=\; \backslash sigma[x]\; \backslash cup\; \{0\}\; =\; \backslash varphi(x)\; \backslash cup\; \{0\}.$ Bằng cách này, $\backslash 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 :$(A,\; B)\; :=\; \backslash varphi[A]\; \backslash cup\; \backslash psi[B]\; =\; \{\backslash varphi(a)\; :\; a\; \backslash in\; A\}\; \backslash cup\; \{\backslash varphi(b)\; \backslash cup\; \{0\}\; :\; b\; \backslash in\; B\; \}.$ (tức là $\backslash varphi\_A\; \backslash cup\; \backslash 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 $\backslash 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.

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