Cách Chứng Minh Một Số Tập đếm được | Ghi Chép Toán Học

Có thể bạn quan tâm

Ta quan tâm tới chứng minh các tập sau là đếm được:

Tập $\mathbb{Z},$ tập $\mathbb{Q}$ và tích Descartes hữu hạn các tập đếm được là đếm được.

Ta có song ánh $f\colon \mathbb{N}\to \mathbb{Z},$ được định nghĩa như sau: $f(2n) = n$ với mọi $n\in \mathbb{N}$ và $f(2n+1)= -n-1$ với mọi $n\in \mathbb{N}.$ Tức là ta phân hoạch tập $\mathbb{N}$ thành hai tập rời nhau, trên mỗi tập rời nhau đó ta xác định giá trị ảnh của từng phần tử theo công thức như đã đưa ra.

Để chứng minh tích Descartes hữu hạn các tập đếm được là đếm được, ta trước tiên chứng minh tích Descartes $\mathbb{N}\times\mathbb{N}$ là đếm được.

Đầu tiên ta có song ánh $\mathbb{N}\to \mathbb{N}^{\ast}$ cho bởi $n\mapsto n+1$ với mọi $n\in\mathbb{N}.$ Như vậy ta chỉ cần chứng minh tập $\mathbb{N}^{\ast}\times \mathbb{N}^{\ast}$ là đếm được là đủ.

Ta có song ánh sau $\mathbb{N}^{\ast}\times \mathbb{N}^{\ast}\to \mathbb{N}^{\ast}$ cho bởi công thức $(m,n)\mapsto 2^{m-1}(2n-1).$

Để chứng minh tích Descartes $\mathbf{\mathbb{N}^n}$ là đếm được với mọi $n$ là số nguyên dương, ta chỉ cần chứng minh bằng quy nạp: cụ thể là ta có $\mathbb{N}^n = \mathbb{N}^{n-1}\times\mathbb{N}.$ Tới đây câu chuyện trở nên đơn giản rồi.

Để chứng minh $\mathbf{\mathbb{Q}}$ là đếm được, ta cần sử dụng định lý Bernstein-Cantor-Schröder. Cụ thể: nếu $X, Y$ là hai tập hợp thỏa mãn tồn tại đơn ánh từ $X\to Y$ và đơn ánh từ $Y\to X$ thì tồn tại song ánh giữa $X$ và $Y.$ Tuy nhiên, một chứng minh đầy đủ không phụ thuộc vào tiên đề Chọn thì tôi lại chưa có được, nên đành tạm thời bỏ trống chỗ chứng minh này. Còn nếu sử dụng tiên đề chọn thì điều này có thể làm được nhanh chóng bằng cách chỉ ra một đơn ánh từ $\mathbb{N}\to \mathbb{Q}$ và một toàn ánh từ $\mathbb{Z}\times \mathbb{N}^{\ast}\to \mathbb{Q}.$