Tập con, hai tập hợp bằng nhau, đếm số tập con

Tính chất:

• $A \subset A$ với mọi tập $A$.
• $\varnothing \subset A$ với mọi tập $A$ (quy ước, hợp lí vì không có phần tử nào của $\varnothing$ nằm ngoài $A$).
• Bắc cầu: $A \subset B$ và $B \subset C$ thì $A \subset C$.

Muốn chứng minh $A = B$, ta chứng minh hai chiều: lấy $x \in A$ chứng tỏ $x \in B$, rồi lấy $x \in B$ chứng tỏ $x \in A$.

Xét $A$ có $n$ phần tử. Để lập một tập con của $A$, ta lần lượt quyết định cho từng phần tử: lấy hoặc không lấy. Có $2$ lựa chọn cho mỗi phần tử, độc lập nhau, nên:

Ví dụ: $A = \{1; 2; 3\}$ có $2^3 = 8$ tập con:

$$\varnothing,\ \{1\},\ \{2\},\ \{3\},\ \{1; 2\},\ \{1; 3\},\ \{2; 3\},\ \{1; 2; 3\}.$$

Khi cố định $k$ phần tử (bắt buộc lấy hoặc bắt buộc không lấy) thì $n - k$ phần tử còn lại tự do, được $2^{n-k}$ tập con.

Số tập con có đúng $k$ phần tử của tập $n$ phần tử kí hiệu $\binom{n}{k}$ (sẽ học ở chương Đại số tổ hợp). Với $n$ nhỏ ta đếm trực tiếp. Chẳng hạn $\{a; b; c; d; e\}$ có $\binom52 = 10$ tập con hai phần tử: ghép $a$ với $4$ chữ còn lại, $b$ với $3$ chữ sau nó, $c$ với $2$, $d$ với $1$: $4 + 3 + 2 + 1 = 10$.

Nội dung	Kết quả
$A \subset B$	Mọi phần tử của $A$ thuộc $B$
$A = B$	$A \subset B$ và $B \subset A$
Luôn đúng	$A \subset A$, $\varnothing \subset A$
Số tập con của tập $n$ phần tử	$2^n$
Cố định $k$ phần tử	$2^{n-k}$
Không có hai số liên tiếp trong $\{1; \dots; n\}$	$a_n = a_{n-1} + a_{n-2}$ ($a_1 = 2$, $a_2 = 3$)
Tập con $k$ phần tử không liên tiếp	$\dbinom{n-k+1}{k}$