Cặp được sắp

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 formula_1 và formula_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à:
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 formula_4 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à 1("p") và 2("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 đề.
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. 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:
Ô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 formula_6.
Định nghĩa của Hausdorff.
Cùng thời gian đó với Wiener (1914), Felix Hausdorff đề xuất định nghĩa sau:
"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
Đị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
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:
Tính chất "x" là phần tử thứ hai của "p"" có thể viết thành:
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ỳ ý):
Đây là công thức cho phần tử thứ hai:
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à formula_14.Ngoài ra, nó cũng ổn hơn khi dùng để biển diễn 'thứ tự', tức là formula_15 sai trừ khi formula_16. Có một số định nghĩa khác tương tự hoặc kém phức tạp hơn sau:
Đị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:&lt;br&gt;
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":
Nếu "a" ≠ "b", thì ("a, b")K = ("c, d")K suy ra = .
Reverse:&lt;br&gt;
("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 
Khi đó,nhận thấy rằng chỉ có thể {"a, b"} = "c hoặc" {"a, b"} = {"c, 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 formula_20 là tập hợp của các số tự nhiên và định nghĩa trước hàm sau
Hàm formula_22 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 formula_22 
Gọi tập formula_24 là tập các phần tử formula_25 không thuộc formula_20. Khi đó
Đây là tập ảnh của tập hợp formula_25 dưới formula_22, đôi khi cũng được ký hiệu là formula_30. Áp dụng hàm formula_31 cho tập "x" chỉ cộng thêm một cho mọi số tự nhiên trong đó.Cụ thể hơn, formula_32 không bao giờ chứa số 0, nên cho bất kỳ tập "x" và tập "y",
Định nghĩa thêm hàm
Bằng cách này, formula_35 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
(tức là formula_37 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 formula_31 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 formula_39 sẽ được mã hoá thành formula_40 nếu như formula_41.