Khác biệt giữa bản sửa đổi của “Tập hợp đếm được”

Tập hợp số tự nhiên và các tập con của nó đếm được, vì tập hợp này tương đương với chính nó (xét ánhdãy xạlogic: đồng nhất ánh - song ánh - đơn ánh - đếm được).

:''f'': '''Z''' → '''N'''

:''f''(''z'') = 2z2''z'', nếu ''z'' ≥ 0

:''f''(''z'') = 2|''z''| + 1, nếu ''z'' < 0.

''f'' là song ánh. Điều đó chứng tỏ '''Z''' và '''N''' có cùng lực lượng.

Thật vậy, mỗi số hữu tỉ có thể biểu diễn duy nhất bởi {{frac|''m/''|''n''}} là phân số tối giản, với ''m'' là số nguyên và ''n'' là số nguyên dương. Xét ánh xạ từ tập hợp ''Q'' (tập các số hữu tỉ) lên tích Descartes ZxN'''Z''' &times; '''Z\{0}''':

:''f'': '''Q''' → ZxN'''Z''' &times; '''Z'''\{0}

:<math>\textstyle f\left(\frac{m}{n} \right) = (m,n) </math>

ánh xạ này là đơn ánh, điều đó chứng tỏ ''Q'' là tập hợp con của tập ZxN'''Z''' &times; '''Z\{0}''', và do đó có lực lượng đếm được.

Cho ''A'' là tập hợp các số thực trong khoảng (0,1); ta chứng minh tập hợp ''A'' không đếm được.

Chứng minh phản chứng. Giả sử ''A'' đếm được, khi đó tồn tại song ánh:

Xét số thực ''r'' thuộc ''A''.

Kí hiệu ''r''_i là chữ số thứ i của r sau dấu phẩy (trong hệ thập phân). Như vậy ''r'' = 0,''r''₁,''r''₂,''r''₃...,''r''_i....

Ta xây dựng ''r'' bằng cách đưa ra quy tắc tính từng chữ số trong biểu diễn thập phân của ''r'':

:Tính ''r''_i

:Kí hiệu ''f''^-1(''i'') là tạo ảnh của ''i''. Tức là ''f'' (''f''^-1(''i'')) = ''i'',

::''r''_i = 9 - ''Chữ số thứ ''i'' của ''f''^-1(''i)'').

Do ''r'' thuộc ''A'', nên tồn tại ''n'' thuộc ''N'' sao cho: ''f''(''r'') = ''n''.

''r''_n = 9 - ''r''_n, suy ra 2r2''r''_n = 9 (vô lí vì 9 là số lẻ).

Vậy điều giả sử là sai, suy ra tập ''A'' không đếm được. Bổ đề chứng minh xong.

Mặt khác, tập ''A'' là tập con của ''R'' (tập số thực), suy ra ''R'' là tập không đếm được.

Do ''R'' là tập con của tập ''C'' (tập số phức), ''R'' không đếm được, suy ra c''C'' không đếm được.

Tập các số thực thuộc các khoảng, đoạn, và nửa khoảng (''a'',''b''), [''a'',''b''], [''a'',''b''), (''a'',''b''] với ''a'' < ''b'' là số thực, là tập không đếm được (xem chứng minh ở phần tập hợp số thực).