Cặp được sắp

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.

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.

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} }$ .