§ 2. Các cặp có thứ tự · Lý thuyết tập hợp

2. Các cặp có thứ tự

1. Tiên đề về cặp có thứ tự

Như chúng ta đã nói ở §1, no. 1, ký hiệu $\supset$ là một ký hiệu tạo số hạng có trọng số 2 trong lý thuyết tập hợp. Nếu T, U là các số hạng, thì $\supset$ TU là một số hạng, trên thực tế được ký hiệu bởi (T, U). Trong ký hiệu này, tiên đề về cặp có thứ tự là như sau :

A3. $(\forall x)(\forall x')(\forall y)(\forall y')(((x, y) = (x', y')) \Rightarrow (x = x' \quad \text{và} \quad y = y'))$ .

Vì quan hệ " $x = x'$ và $y = y'$ " kéo theo $(x, y) = (x', y')$ theo C44 (Chương I, § 5, no. 2), nên quan hệ $(x, y) = (x', y')$ là tương đương với " $x = x'$ và $y = y'$ ".

¶ Quan hệ $(\exists x)(\exists y)(z=(x,y))$ được viết là “ $z$ là một cặp có thứ tự”. Nếu $z$ là một cặp có thứ tự, thì các quan hệ

(\exists y)(z=(x,y)),\qquad(\exists x)(z=(x,y))

là các phiếm hàm đối với $x$ và $y$ tương ứng; đây là một hệ quả ngay lập tức của A3. Các số hạng

\tau_x((\exists y)(z=(x,y)))\qquad\text{và}\qquad\tau_y((\exists x)(z=(x,y)))

được ký hiệu bởi $\operatorname{pr}_1z$ và $\operatorname{pr}_2z$ , tương ứng, và được gọi là tọa độ thứ nhất (hay phép chiếu thứ nhất) và tọa độ thứ hai (hay phép chiếu thứ hai) của $z$ . Nếu $z$ là một cặp có thứ tự, quan hệ $(\exists y)(z=(x,y))$ tương đương với $x=\operatorname{pr}_1z$ , và quan hệ $(\exists x)(z=(x,y))$ với $y=\operatorname{pr}_2z$ (Chương I, §5, no. 3).

¶ Quan hệ $z=(x,y)$ tương đương với “ $z$ là một cặp có thứ tự, và $x=\operatorname{pr}_1z$ và $y=\operatorname{pr}_2z$ ”; vì quan hệ sau tương đương với

(\exists x')(\exists y')(\exists x'')(\exists y'')(z=(x',y')\text{ và }z=(x,y'')\text{ và }z=(x'',y));

theo A3, “ $z=(x',y')$ và $z=(x,y'')$ và $z=(x'',y)$ ” tương đương với “ $z=(x,y)$ và $x=x'$ và $x=x''$ và $y=y'$ và $y=y''$ ”; do đó theo C33 (Chương I, §4, no. 3), “ $z$ là một cặp có thứ tự, và $x=\operatorname{pr}_1z$ và $y=\operatorname{pr}_2z$ ” tương đương với

z=(x,y)\text{ và }(\exists x')(\exists y')(\exists x'')(\exists y'')(x=x'\text{ và }x=x''\text{ và }y=y'\text{ và }y=y''),

điều này chứng minh mệnh đề của chúng ta. Hiển nhiên ta có

\operatorname{pr}_1(x,y)=x,\qquad \operatorname{pr}_2(x,y)=y,

và quan hệ $z=(\operatorname{pr}_1(z),\operatorname{pr}_2(z))$ tương đương với “ $z$ là một cặp có thứ tự”.

¶ Cho $R\{x,y\}$ là một quan hệ, trong đó các chữ $x$ và $y$ là phân biệt và xuất hiện trong $R$ . Cho $z$ là một chữ, phân biệt với $x$ và $y$ , không xuất hiện trong $R$ . Gọi $S\{z\}$ là quan hệ

(\exists x)(\exists y)(z=(x,y)\text{ và }R\{x,y\});

đây là một quan hệ chứa ít hơn một chữ cái so với $R$ , và tương đương với “ $z$ là một cặp có thứ tự và $R\{\operatorname{pr}_1z,\operatorname{pr}_2z\}$ ”, điều này suy ra từ sự kiện rằng $z=(x,y)$ tương đương với “ $z$ là một cặp có thứ tự và $x=\operatorname{pr}_1z$ và $y=\operatorname{pr}_2z$ ”, và từ các tiêu chuẩn C33 (Chương I, §4, no. 3) và C47 (Chương I, §5, no. 3). Suy ra ngay lập tức rằng $R\{x, y\}$ tương đương với $S\{(x, y)\}$ , và cũng tương đương với

(\exists z)(z = (x, y) \text{ và } S\{z\})

theo C47.

Điều này có nghĩa là ta có thể hiểu một quan hệ giữa các đối tượng $x$ và $y$ như một tính chất của cặp có thứ tự được tạo thành bởi các đối tượng này.

2. Tích của hai tập hợp

Định lý 1 03PC

Quan hệ

Trích dẫn đến 2

Trích dẫn đến II § 1. Các quan hệ xác định tập, I § 4. Các lý thuyết có lượng từ

(\forall X)(\forall Y)(\exists Z)(\forall z)((z \in Z) \Leftrightarrow (\exists x)(\exists y)(z = (x, y) \text{ và } x \in X \text{ và } y \in Y)

là đúng. Nói cách khác, với mọi X và mọi Y thì quan hệ " $z$ là một cặp có thứ tự và $\mathrm{pr}_1 z \in X$ và $\mathrm{pr}_2 z \in Y$ " xác định tập theo $z$ .

Ký hiệu $A_y$ là tập hợp của mọi đối tượng dạng $(x, y)$ với $x \in X$ (xem §1, no. 6, tiêu chuẩn C53). Gọi R là quan hệ $z \in A_y$ , tương đương với $(\exists x)(z = (x, y)$ and $x \in X)$ . Hiển nhiên quan hệ

(\forall y)(\exists A)(\forall z)(R \Rightarrow (z \in A))

đúng, theo S5 (Chương I, §4, no. 2). Khi đó suy ra từ S8 rằng quan hệ $(\exists y)(y \in Y$ và R $)$ là xác định tập theo $z$ . Nhưng quan hệ này tương đương với $(\exists x)(\exists y)(y \in Y$ và $x \in X$ và $z = (x, y))$ ; do đó có kết quả.

Định nghĩa 1 03PD

Cho hai tập hợp* X và Y, *tập hợp

\mathscr{E}_z((\exists x)(\exists y)(z = (x, y) \text{ và } x \in X \text{ và } y \in Y))

được gọi là tích của X và Y và được ký hiệu là X $\times$ Y.

Quan hệ $z \in X \times Y$ do đó tương đương với " $z$ là một cặp có thứ tự và $\mathrm{pr}_1 z \in X$ và $\mathrm{pr}_2 z \in Y$ ". Các tập hợp X và Y được gọi là thừa số thứ nhất và thừa số thứ hai của X $\times$ Y.

Mệnh đề 1 03PE

Nếu* A $'$ , B $'$ là các tập hợp không rỗng, quan hệ A $' \times$ B $' \subset$ A $\times$ B tương đương với "A $' \subset$ A và B $' \subset$ B".

Trước hết, quan hệ $z \in A' \times B'$ tương đương với " $z$ là một cặp có thứ tự và $\mathrm{pr}_1 z \in A'$ và $\mathrm{pr}_2 z \in B'$ "; do đó, không có bất kỳ hạn chế nào đối với A $'$ và B $'$ , quan hệ "A $' \subset$ A và B $' \subset$ B" suy ra

A' \times B' \subset A \times B.

Ngược lại, trước hết ta hãy chỉ ra rằng nếu $B' \neq \emptyset$ (không có hạn chế nào đối với $A'$ ), quan hệ $A' \times B' \subset A \times B$ suy ra $A' \subset A$ . Lấy $x$ là một phần tử của $A'$ ; vì $B' \neq \emptyset$ , tồn tại một đối tượng $y$ là một phần tử của $B'$ ; ta có $(x, y) \in A' \times B'$ , do đó $(x, y) \in A \times B$ , và do đó $x \in A$ ; vậy $A' \subset A$ . Tương tự, nếu $A' \neq \emptyset$ , quan hệ $A' \times B' \subset A \times B$ suy ra $B' \subset B$ . Do đó có kết quả phải chứng minh.

Mệnh đề 2 03PF

Cho* A và B là hai tập hợp. Quan hệ $A \times B = \emptyset$ tương đương với " $A = \emptyset$ hoặc $B = \emptyset$ ".

Được trích dẫn bởi 1

Được trích dẫn bởi Mệnh đề 1, II § 3

Thật vậy, quan hệ $z \in A \times B$ kéo theo $\mathrm{pr}_1 z \in A$ và $\mathrm{pr}_2 z \in B$ ; do đó $A \neq \emptyset$ và $B \neq \emptyset$ . Ngược lại, quan hệ " $x \in A$ và $y \in B$ " kéo theo $(x, y) \in A \times B$ và do đó $A \times B \neq \emptyset$ . Nói cách khác, quan hệ $A \times B \neq \emptyset$ tương đương với " $A \neq \emptyset$ và $B \neq \emptyset$ "; do đó suy ra kết quả.

Nếu A, B, C là các tập hợp, ta viết

(A \times B) \times C = A \times B \times C;

một phần tử $((x, y), z)$ của $A \times B \times C$ được viết là $(x, y, z)$ và được gọi là một bộ ba. Tương tự, nếu A, B, C, D là các tập hợp, ta viết

(A \times B \times C) \times D = A \times B \times C \times D;

vân vân.

Bài tập

Xem bài tập của § 2.