Множество алгебраических чисел счетно и эффективно перечислимо

Доказательство

Доказательство построим привычным образом, а именно предложим процедуру нумерации всех алгебраических чисел числами натурального ряда. При этом каждое число будем задавать через образующее его алгебраическое уравнение. Так, для линейных уравнений будем иметь упорядоченные пары рациональных чисел, для квадратных уравнений – тройки, в общем случае получаем упорядоченную n-ку рациональных чисел: (a_i1,a_i2…a_in) для каждого i-ого алгебраического уравнения (n-1)-ой степени. Располагать элементы будем в двусторонне бесконечной матрице.

Выпишем на первой строке будущей матрицы все упорядоченные пары рациональных чисел. Это возможно, т.к. пары рациональных чисел эффективно перечислимы (рациональные числа эффективно перечисляются, их можно записать в матрицу и перечислить пары чисел диагональным способом). Такие пары рациональных чисел соответствуют линейным уравнениям и имеют по одному корню: т.о. каждая пара однозначно определяет корень линейного уравнения.

На второй строке выпишем все упорядоченные тройки рациональных чисел. Это возможно, т.к. тройки рациональных чисел эффективно перечислимы (рациональные числа эффективно перечисляются, их пары тоже эффективно перечисляются, значит можно записать в матрицу по строкам пары, по столбцам числа и перечислить тройки чисел диагональным способом). Такие тройки соответствуют квадратным уравнениям и имеют максимум по два корня: таким образом, в процессе формирования матрицы каждую тройку рациональных чисел нужно будет повторить два раза для обеспечения процесса получения соответствующего номера для двух чисел, являющихся решением соответствующего уравнения.

На третьей строке – по три числа на каждое кубическое уравнение соотв. упорядоченным четверкам и т.д.

Т.о. получим матрицу, которую можно обойти при помощи диагонального процесса Кантора. Если часть корней алгебраического уравнения комплексная, при нумерации их просто пропускаем. Т.о. каждое алгебраическое число получит соответствующий номер, и это подтверждает тот факт, что множество алгебраических действительных чисел счетно.

Факт эффективной перечислимости множества А напрямую следует из приведенного способа нумерации элементов натуральными числами, т.к. попутно указана эффективная процедура нумерации наборов рациональных чисел, однозначно задающих алгебраические уравнения соответствующей степени. При этом важно то, что алгебраическое уравнение n-ой степени имеет эффективный алгоритм решения, т.о. процедура полностью эффективна. Итак, множество алгебраических действительных чиселсчетно и эффективно перечислимо, Q.E.D.

Т.8.1. (1) Теорема

Множество действительных чисел несчётно.

Доказательство

Предположим противное, пусть множество действительных чисел счетное. Тогда любое подмножество счетного множества тоже счетное. Возьмём на множестве действительных чисел подмножество R₁ - интервал (0,1) и выкинем из этого отрезка числа, содержащие хотя бы в одном своём разряде нули или девятки (примеры таких чисел: 0.9, 0.0001 и т.д.). Множество R₂, составленное из оставшихся чисел, является подмножеством множества R₁. Это означает, что R₂ – счетное.

Из того факта, что R₂ – счетное, напрямую следует, что возможен какой-либо способ перечисления его элементов для установления взаимно-однозначного соответствия между элементами R₂ и элементами множества натуральных чисел. Это следует из самого определения мощности множества, согласно которому предполагается, что в равномощных множествах каждый элемент одного множества имеет парный элемент из другого множества и наоборот. Обратите внимание, фундаментальное отличие данного определения от определения эффективной перечислимости состоит в том, что в данном случае мы даже не говорим о наличии какого-либо алгоритма перечисления, мы просто утверждаем, что можно привести список действительных чисел из множества R₂ и список соответствующих им натуральных чисел из множества N. Алгоритм построения связи N ↔ R₂ нас в данном случае не интересует, достаточно того, что такое соответствие возможно.

Построим такой список чисел из множества R₂ и пронумеруем числа в разрядах:

0.a₁₁a₁₂a₁₃…

0.a₂₁a₂₂a₂₃…

……………

0.a_n1a_n2a_n3…

Теперь построим число b=0.b₁b₂…, причём

b_i=a_ii+1, где + обозначает операцию сложения, результатом которого не могут быть числа 0 и 9, т.е. если a_ii=1, то b_i=2; если а_ii=2, то b_i=3, …., если a_ii=8, то b_i=1).

Таким образом, построенное число b будет отличаться от каждого из чисел множества R₂ хотя бы в одном разряде, и, следовательно, не попадёт в составленный список. Однако по своей структуре число b должно содержаться в множестве R₂. Получили противоречие, значит исходное предположение неверно и множество R₂ - несчётно.

Так как множество R₂ является по условию подмножеством множества R₁, то R₁ – несчетно, а т.к. R₁ несчетно – то значит и множество R несчётно, Q.E.D.

Т.8.2.(1) Теорема