Tập đếm được

Tính đếm được của tập hợp là một cách thay thế cho số phần tử của tập hợp, vì với tập hợp vô hạn ta không thể đếm số phần tử: số phần tử, thật bất ngờ, là… vô hạn. Độ lớn của tập hợp theo nghĩa này còn được gọi là lực lượng của tập hợp.

Độ lớn của một tập hợp vô hạn

Xác định độ lớn của một tập hợp hữu hạn thì đơn giản: ta đếm số phần tử. Chẳng hạn tập hợp M = {a; b; c; d; e} có 5 phần tử, ta viết |M| = 5.

Với tập hợp vô hạn, mọi chuyện phức tạp hơn nhiều. Làm sao so sánh độ lớn của các tập hợp vô hạn? Liệu có so sánh được không, hay mọi tập hợp vô hạn đều “lớn như nhau”?

Ta xét ví dụ tập hợp các số nguyên dương và tập hợp các số nguyên dương chẵn. Đó là các tập hợp ℕ^* = {1; 2; 3; 4; 5; 6; …} và S = {2; 4; 6; …}. Ta dễ nghĩ rằng tập các số nguyên dương lớn hơn tập các số chẵn, vì nó chứa tất cả các số chẵn và còn thêm một số phần tử nữa là các số lẻ.

Ta có thể viết S ⊂ ℕ^*: tập hợp S là tập con thực sự của tập hợp ℕ^*. Và có thể nói rằng nếu S ⊂ ℕ^* thì tập hợp ℕ^* lớn hơn, vì nó chứa nhiều phần tử hơn tập hợp S.

Một trong các lí do khiến ta không thể so sánh độ lớn của tập hợp bằng quan hệ tập con là: hai tập hợp có thể có độ lớn khác nhau dù không tập nào là tập con của tập kia. Điều này thấy ngay với các tập hợp hữu hạn: A = {1; 3; 4; 9} và B = {b; u; r; z; m}. Ta có |A| = 4 và |B| = 5. Tập hợp B lớn hơn tập hợp A, nhưng A ⊂ B không đúng. Với tập hợp vô hạn, ta thấy điều này ở tập các số chẵn và tập các số lẻ: không tập nào là tập con của tập kia.

Vì vậy quan hệ tập con không phải là công cụ thích hợp để quyết định một tập hợp có lớn hơn tập kia hay không.

Song ánh

Ta thử cách khác. Cho hai tập hợp A và B. Ta nói chúng có cùng độ lớn nếu giữa chúng tồn tại một song ánh. Điều đó có nghĩa là gì? Ta lấy một phần tử của tập hợp A, một phần tử của tập hợp B và tạo thành cặp (a; b). Ta bỏ hai phần tử này ra khỏi hai tập hợp rồi tiếp tục. Nếu làm “rỗng” được cả hai tập hợp thì ta đã tìm được một song ánh.

Ví dụ với tập hợp hữu hạn: A = {a; b; c} và B = {1; 2; 3}. Cặp thứ nhất có thể là (a; 1), cặp tiếp theo (b; 2) và cuối cùng (c; 3). Ta đã dùng hết các phần tử của cả hai tập hợp, tức là đã tìm được một song ánh. Điều quan trọng là đây không phải song ánh duy nhất. Cách ghép sau cũng hợp lệ: (a; 3), (b; 1), (c; 2).

Với tập hợp vô hạn thì thú vị hơn. Ta thử với các số nguyên dương lẻ và chẵn. Trực giác mách bảo rằng số lượng của chúng phải như nhau. Ta thử xem. Lấy số lẻ thứ nhất và cho tương ứng với số chẵn thứ nhất: (1; 2). Tiếp theo là số lẻ thứ hai và số chẵn thứ hai: (3; 4). Cứ thế tiếp tục. Ta được các cặp: (1; 2), (3; 4), (5; 6), (7; 8), … Có thể nói rằng mỗi số lẻ l tương ứng với số chẵn l + 1, và mỗi số chẵn s là ảnh của số lẻ s − 1. Như vậy mỗi số lẻ và mỗi số chẵn đều nằm trong một cặp nào đó. Do đó tập các số lẻ và tập các số chẵn có cùng độ lớn.

Số chẵn và số nguyên dương

Bây giờ ta dùng cách làm tương tự để so sánh tập các số nguyên dương với tập các số chẵn. Ta có các tập hợp ℕ^* = {1; 2; 3; 4; 5; 6; …} và S = {2; 4; 6; …}. Trực giác cho rằng tập các số nguyên dương sẽ lớn hơn.

Nhưng ta hãy thử tìm một song ánh. Có thể cho mỗi số nguyên dương n tương ứng với số gấp đôi nó, tức là 2n. Ta được các cặp (1; 2), (2; 4), (3; 6), (4; 8), (5; 10), … Như vậy với mỗi số nguyên dương n có cặp (n; 2n), và với mỗi số chẵn s có cặp (s/2; s). Ta đã tìm được một song ánh, nên tập các số chẵn và tập các số nguyên dương có cùng độ lớn, tức là có cùng lực lượng.

Điều này có vẻ khó hiểu, vì các số nguyên dương rõ ràng có nhiều phần tử hơn các số chẵn: chúng gồm tất cả các số chẵn và thêm tất cả các số lẻ. Tuy nhiên ta tìm được một song ánh, nên hai tập hợp có cùng độ lớn.

So sánh với tập các số nguyên dương

Thực ra tập các số nguyên dương có độ lớn nhỏ nhất trong các tập hợp vô hạn. Muốn biết một tập hợp khác có cùng độ lớn với tập các số nguyên dương hay không, thường khá dễ: chỉ cần tìm một song ánh lên tập các số nguyên dương, mà trong thực hành điều đó có nghĩa là chỉ cần đánh số được, sắp xếp được các phần tử của tập hợp M.

Nói cách khác, nếu ta sắp xếp được các phần tử của tập hợp sao cho xác định được phần tử nào là thứ nhất, thứ hai, thứ ba, thứ tư, thứ mười, v.v., thì tập hợp đó có cùng độ lớn với ℕ^*. Tập hợp như vậy gọi là tập đếm được.

Dễ thấy rằng tập các số nguyên dương chẵn và tập các số nguyên dương lẻ đều đếm được, vì ta xác định được số chẵn (số lẻ) thứ nhất, thứ hai, thứ ba, v.v. Còn các số nguyên chẵn thì sao? Tức là tập hợp S = {…; −4; −2; 0; 2; 4; …}. Có sắp xếp được không? Được: chỉ cần lấy cách sắp xếp như trước, và ngay sau mỗi số chẵn dương thì viết số đối của nó: S = {0; 2; −2; 4; −4; 6; −6; …}. Với tập các số nguyên cũng làm tương tự.

Độ lớn của tập các số hữu tỉ

Một ví dụ thú vị hơn là các số hữu tỉ, tức là các phân số. Có sắp xếp được chúng không? Được, nhưng phức tạp hơn một chút. Ta lập một bảng có vô số dòng và vô số cột. Mỗi ô chứa một phân số. Ở cột thứ n và dòng thứ m là phân số n/m. Như vậy ở cột 1, dòng 2 là $\frac{1}{2}$, còn ở cột 3, dòng 4 là 3/4.

$$\begin{array}{ccccc}1/1& 2/1& 3/1& 4/1& \dots \\ 1/2& 2/2& 3/2& 4/2& \dots \\ 1/3& 2/3& 3/3& 4/3& \dots \\ 1/4& 2/4& 3/4& 4/4& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}$$

Làm sao sắp xếp, đánh số các số này? Ta không thể đánh số theo từng dòng hay từng cột, vì sẽ bị mắc kẹt mãi trong dòng (cột) đầu tiên. Thay vào đó ta lấy các số theo các đường chéo: (đường chéo thứ nhất:) 1/1, (đường chéo thứ hai:) 2/1, 1/2, (đường chéo thứ ba:) 3/1, 2/2, 1/3, (đường chéo thứ tư:) 4/1, 3/2, 2/3, 1/4, … Trong đó còn nhiều phân số lặp lại (bằng nhau), nhưng điều đó không sao. Vấn đề lớn hơn là chưa có các số âm. Điều này dễ khắc phục: mỗi khi viết một phân số, ta viết ngay sau nó số đối của nó. Cuối cùng chỉ còn thiếu số 0 ở đầu dãy. Thế là xong, ta đã xếp tất cả các số hữu tỉ thành một dãy.

Tóm lại ta được dãy: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

Độ lớn của tập các số thực

Tập các số thực có cùng độ lớn với tập các số nguyên dương không? Câu trả lời còn khó hơn so với trường hợp số hữu tỉ. Ta dùng phương pháp chứng minh phản chứng. Giả sử tập các số thực đếm được, tức là tồn tại một song ánh lên tập các số nguyên dương. Như vậy ta giả sử rằng các số thực sắp xếp được. Giả sử cách sắp xếp đó như sau:

$$\begin{array}{ccccccccc}0,& 3& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& 9& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& 3& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& 7& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& 7& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& 6& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& 0& \dots \\ \dots \end{array}$$

Bảng trên gồm 7 số thực đầu tiên theo cách sắp xếp của ta. Tất nhiên cách sắp xếp này có thể tuỳ ý, không nhất thiết theo thứ tự lớn nhỏ.

Theo giả thiết, bảng vô hạn này chứa tất cả các số thực. (Bảng cũng vô hạn, ở đây chỉ ghi 7 dòng đầu.) Bây giờ ta sẽ tìm (dựng) một số thực không có mặt trong bảng. Nếu tìm được số như vậy thì điều đó mâu thuẫn với giả thiết rằng bảng chứa mọi số thực, và từ đó suy ra tập các số thực không đếm được.

Số không có trong bảng được dựng như sau:

$$\begin{array}{ccccccccc}0,& \boxed{\text{3}}& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& \boxed{\text{9}}& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& \boxed{\text{3}}& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& \boxed{\text{7}}& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& \boxed{\text{7}}& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& \boxed{\text{6}}& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& \boxed{\text{0}}& \dots \\ \dots \end{array}$$

Ta bắt đầu bằng cách viết 0,… Đó là phần đầu của số thực mới. Chữ số thập phân thứ nhất của nó là một chữ số khác với chữ số thập phân thứ nhất của số thực thứ nhất trong cách sắp xếp (trong bảng, chữ số đó được đóng khung). Ở đó là chữ số 3, nên ta chọn chẳng hạn 1 và được số 0,1…

Tiếp tục. Chữ số thứ hai là một chữ số khác với chữ số thứ hai của số thực thứ hai. Ở đó là 9, nên ta chọn chẳng hạn 2. Ta được số 0,12… Chữ số thứ ba khác với chữ số thứ ba của số thực thứ ba. Ở đó là 3, nên ta chọn chẳng hạn 7. Ta được 0, 127…

Cứ tiếp tục như vậy. Ở vị trí thứ n của số mới luôn là một chữ số khác với chữ số ở vị trí thứ n của số thứ n trong cách sắp xếp.

Ta được gì? Ta được một số khác với mọi số trong cách sắp xếp ít nhất ở một chữ số. Xét kết quả tạm thời cuối cùng: 0,127… Số này chắc chắn khác số thứ nhất trong cách sắp xếp ít nhất ở chữ số thứ nhất, vì ta đã dựng nó như vậy. Nó khác số thứ hai ít nhất ở chữ số thứ hai, khác số thứ ba ở chữ số thứ ba. Tổng quát, số mới này khác số đứng ở vị trí thứ n trong cách sắp xếp ít nhất ở chữ số thứ n.

Như vậy số mới dựng này không có trong bảng, mà bảng được cho là biểu diễn một song ánh giữa tập các số nguyên dương và tập các số thực. Vậy tập các số thực lớn hơn tập các số nguyên dương. Tập các số thực không đếm được.

Tài liệu tham khảo

• Are there more odd or even numbers?