Tập hợp gồm 5 phần tử có bao nhiêu tập con

Khi học tới phần tập hợp, các bạn được giới thiệu với một tập hợp có n phần tử thì nó có 2^n tập con. Nhưng tại sao là 2^n?

Trước khi giải quyết bài toán, chúng ta cần ôn lại một số kiến thức cơ bản về tập hợp

Tập hợp là gì?

Tập hợp là một khái niệm nguyên thủy của toán học, không định nghĩa. Nhưng hiểu một cách đơn giản, tập hợp là sự quần tụ của hữu hạn hoặc vô hạn các đối tượng có cùng một thuộc tính nào đó. Các đối tượng này được gọi là phần tử của tập hợp. Và trong bài viết này, mình chỉ xét với những tập hợp hữu hạn phần tử như

Ví dụ về tập hợp có hữu hạn phần tử

Lí do vì sao lại không đề cập tới những tập hợp có vô hạn phần tử vì với những tập hợp như vậy thì số phần tử của nó không thể được chỉ ra bởi một con số nhất định dù cho đó là vô hạn đếm được hay vô hạn không đếm được.

Tập con là gì?

Tập con hay tập hợp con bản thân của nó cũng là một tập hợp. Tập hợp A được gọi là tập con của B nếu như trong B có A (B chứa A). Quan hệ như vậy được gọi là quan hệ bao hàm. Và dĩ nhiên với mọi tập A thì ta luôn có A chính là tập con của A vì trong A có A.

Ví dụ về tập A là tập con của tập B

Nhìn chung thì kí hiệu và được mọi người ngầm hiểu là như nhau. Tuy nhiên với A B ta có thể hiểu tập A là con của tập B hoặc có thể hai tập bằng nhau A = B

Tập rỗng là gì?

Tập này là một tập đặc biệt, và duy chỉ có mình nó là có khả năng không chứa phần tử nào. Và theo lý thuyết tập hợp tiên đề thì mọi tập hợp hữu hạn đều được xây dựng từ tập rỗng, vậy nên tập rỗng là tập con của mọi tập hợp. Từ đây ta có thể rút ra một nhận xét là tập rỗng có duy nhất một tập con là chính nó.

2 kí hiệu được sử dụng để biểu diễn tập hợp rỗng

Kiểm tra mệnh đề

Những khái niệm cơ bản đã xong, giờ ta sẽ bắt tay vào việc đếm số tập con của một tập hợp bằng việc xét một toy example.
Đếm số tập con của tập A={1, 2, 3}.
Tập hợp này dĩ nhiên là một tập hữu hạn với n = 3 phần tử. Vì n nhỏ, nên ta có thể đếm số tập con bằng cách liệt kê.
Đầu tiên phải nhắc tới đó chính là tập rỗng {} (1 tập), tiếp theo là những tập hợp gồm 1 phần tử {1}, {2}, {3} (3 tập), tập gồm 2 phần tử {1, 2}, {1, 3}, {2, 3} (3 tập). Ở đây ta cần lưu ý một điểm là hai tập {1, 2} và {2, 1} như nhau và chúng ta sẽ chỉ đếm 1 lần. Tập con cuối cùng là chính nó {1, 2, 3} (1 tập). Vậy ta có tổng cộng 1 + 3 + 3 + 1 = 8 tập con, đúng bằng 2³.

Các bạn hoàn toàn có thể thử với những tập hợp có n = 4, 5, 6, để kiểm tra lại xem số tập con có bằng 2^n hay không. Tuy nhiên việc kiểm tra sẽ khó khăn khi n lớn. Vậy có cách nào chúng ta có thể chắc chắn rằng điều trên đúng với mọi n?

Chứng minh bằng quy nạp (induction)

Ở toán trung học phổ thông (hoặc trung học cơ sở) chúng ta đã làm quen với một cách để kiểm tra điều này, chính là quy nạp. Ta sẽ nhắc lại các bước để chứng minh quy nạp. Đầu tiên là bước cơ sở (base case), ta cần phải chứng minh mệnh đề đúng với n = 0 (đối lúc có thể là n = 1). Bước tiếp theo là bước quy nạp (inductive step), ta chứng minh rằng với n = k đúng thì n = k + 1 cũng đúng. Áp dụng vào bài toán của chúng ta.

Gọi n là số phần tử của tập hợp A
Với n = 0, tập A là tập rỗng, và số tập con của A là 1 = 2
Giả sử đúng với n = k, thì tập A có 2^k tập con
Ta cần chứng minh với n = k + 1 thì tập A có 2^(k+1) tập con
Thật vậy, với k + 1 phần tử của A, ta chọn ra bất kì k phần tử. Từ k phần tử này ta có thể lập ra được 2^k tập con. Tiếp theo ta lấy phần tử còn lại, sau khi lấy k phần tử ra trước đó, đưa vào 2^k tập con vừa lập thì ta sẽ được 2^k tập con mới. Vậy tổng số tập con của A là 2^k + 2^k = 2.2^k = 2^(k+1). Vậy với n = k + 1 cũng đúng, suy ra mệnh đề đúng với mọi số tự nhiên n.

Chứng minh bằng tổng hệ số nhị thức (binomial coefficient)

Ngoài cách đó ra, mình cũng tự nghĩ ra một cách chứng minh sử dụng kiến thức xác suất thông kế.
Với tập A có n phần tử, ta tạo ra các tập con của A bằng cách lấy k ( k = 0, 1, , n) phần tử ra. Vậy ta sẽ tính số tập con được tạo ra bằng cách đếm tổng số cách lấy.
Với k = 0, ta có nC0 cách lấy. (trường hợp này tạo ra tập rỗng)
Với k = 1, ta có nC1 cách lấy.
Với k = 2, ta có nC2 cách lấy.

Với k = n, ta có nCn cách lấy. (trường hợp này tạo ra chính tập đó)
Vậy tổng số cách là nC0 + nC1 + nC2 + + nCn. Đây là một tổng vô cùng quen thuộc mà các bạn đã biết khi học về nhị thức Newton hay định lí nhị thức (Binomial theorem), và tổng này đúng bằng 2^n.

Chứng minh bằng quy tắc nhân (multiplication rule)

Cuối cùng, mình sẽ giới thiệu với các bạn một cách nữa. Đây cũng là cách mà mình học được từ thầy Joseph Blitzstein và là cách mình thấy hay nhất.
Cách này sử dụng quy tắc nhân trong xác suất thông kê. Với mỗi phần tử trong tập hợp, ta có thể cho giữ nó lại hoặc quăng nó ra để tạo ra được một tập con. Vậy theo quy tắc nhân ta được 2.2.2.2.22 = 2^n. Đơn giản, ngắn gọn. Nếu bạn chưa hiểu lắm ta có thể xét một toy example đơn giản như sau
Với tập A = {1, 2}.
TH1: bỏ 1, bỏ 2, ta được {}
TH2: giữ 1, bỏ 2, ta được {1}
TH3: bỏ 1, giữ 2, ta được {2}
TH4: giữ 1, giữ 2, ta được {1, 2}
Ta có thể dễ dàng đếm ra 4 trường hợp bằng quy tắc nhân 2.2=2²=4

Tham khảo:

- Tập hợp
- Tập con
- Tập rỗng
- Quy nạp
- Chứng minh quy nạp