Развернуть
Пункт 1. Пусть A={a1,a2,…} (нумерация n↦an — биекция N→A), B⊂A бесконечно. Положим n1=min{n: an∈B} и рекуррентно nk+1=min{n>nk: an∈B}. Минимумы существуют по принципу наименьшего элемента: множества непусты, так как иначе B⊂{a1,…,ank} было бы конечно. По построению n1<n2<…, и индукцией nk≥k.
Отображение φ(k)=ank из N в B инъективно, так как номера nk различны, а нумерация A инъективна. Докажем сюръективность. Пусть b∈B, b=am. Множество K={k: nk≥m} непусто (nm≥m); пусть k=minK. Если k=1, то n1≤m по минимальности n1 (так как am∈B). Если k>1, то nk−1<m, и m входит в множество {n>nk−1: an∈B}, поэтому nk≤m. С другой стороны, nk≥m, так как k∈K. Итак, nk=m и b=φ(k). Итак, φ — биекция, B счётно. Подмножество счётного множества либо конечно, либо бесконечно и тогда счётно.
Пункт 2. Пусть g:A→C — инъекция, C счётно. Тогда g:A→g(A) — биекция, и g(A) бесконечно (иначе бесконечное A было бы равномощно конечному множеству, а значит, конечно). По пункту 1 g(A)∼N, и по транзитивности равномощности A∼N.
Пункт 3. Отображение (k,m)↦2k3m из N×N в N инъективно по единственности разложения натурального числа на простые множители. Множество N×N бесконечно (содержит различные пары (k,1)). По пункту 2 оно счётно.
Пункт 4. Отбросим пустые множества (не все они пусты). Для каждого непустого не более чем счётного Ak зададим сюръекцию m↦akm из N на Ak: для счётного — нумерацию, для Ak={x1,…,xr} — akm=xmin(m,r). Если множеств конечное число A1,…,Ap, положим akm=apm при k>p. Тогда отображение (k,m)↦akm из N×N на A=⋃Ak сюръективно.
Пусть ψ:N→N×N — биекция (пункт 3). Для x∈A положим ν(x)=min{j∈N: aψ(j)=x} (множество непусто по сюръективности). Отображение ν:A→N инъективно: из ν(x)=ν(x′)=j следует x=aψ(j)=x′. Множество A бесконечно, так как содержит бесконечное Ak. По пункту 2 A счётно.
Пункт 5. Отображение N→Z, n↦2n при чётном n и n↦−2n−1 при нечётном n, — биекция (нумерация 0,1,−1,2,−2,…), поэтому Z счётно. Далее Q=⋃q∈NQq, где Qq={qp: p∈Z}; отображение p↦qp — биекция Z→Qq, так что все Qq счётны. По пункту 4 Q счётно. ■