Презентация Несчетные множества. (Лекция 8) онлайн

Содержание слайда:

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

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

Содержание слайда: Построим такой список чисел из множества R2 и пронумеруем числа в разрядах: Построим такой список чисел из множества R2 и пронумеруем числа в разрядах: 0.a11a12a13… 0.a21a22a23… …………… 0.an1an2an3… Теперь построим число b=0.b1b2…, причём bi=aii+1, где + обозначает операцию сложения, результатом которого не могут быть числа 0 и 9, т.е. если aii=1, то bi=2; если аii=2, то bi=3, …., если aii=8, то bi=1. Таким образом, построенное число b будет отличаться от каждого из чисел множества R2 хотя бы в одном разряде, и, следовательно, не попадёт в составленный список. Однако по своей структуре число b должно содержаться в множестве R2. Получили противоречие, значит исходное предположение неверно и множество R2 - несчётно. Так как множество R2 является по условию подмножеством множества R1, то R1 – несчетно, а т.к. R1 несчетно – то значит и множество R несчётно, Q.E.D.

Содержание слайда: Можно и не выбрасывать числа, содержащие 0 и 9. Таким образом, в наш ряд некоторые числа войдут дважды. Это связано с тем, что конечные дроби могут быть превращены в бесконечные. Например ½=0,5=0,5(0)=0,4(9). В общем случае это могло стать причиной того, что не удалось сосчитать множество действительных чисел. Но множество чисел, представимых двояким образом (конечные дроби) – это множество рациональных чисел. Как было доказано ранее, их счетное количество. Можно даже показать, что это множество эффективно перечислимо. Т.о. даже двойное представление множества таких чисел образует счетное множество, следовательно, доказательство верно даже без такого упрощения.

Содержание слайда: Алеф ( א ) – второе трансфинитное число. По определению это мощность континуума (всех действительных чисел). Это вторая по величине бесконечная мощность. Алеф ( א ) – второе трансфинитное число. По определению это мощность континуума (всех действительных чисел). Это вторая по величине бесконечная мощность. Доказанная только что теорема о несчетности множества действительных чисел является убедительным доказательством того, что мощность этого множества больше, чем алеф-ноль (больше множества натуральных чисел). И это весьма важный результат после череды доказательства счетности разнообразных множеств чисел. Если оперировать понятием кардинального числа (мощности), то получим, что, так как каждое число сегмента (0,1) может быть представлено десятичной дробью вида 0.a1a2a3… не менее одного раза и не более двух, то: а т.к. , то получим что . Те же рассуждения справедливы в случае, если мы будем разлагать числа не в десятичные, а, например, в двоичные дроби, дроби с основанием 3, 15, 10005 или даже א0 (если вы можете такое себе представить).

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда: Теорема Теорема Множество комплексных чисел несчетно. Доказательство: Так как множество действительных чисел R несчётное, является подмножеством множества комплексных чисел С, то множество комплексных чисел также несчётно, Q.E.D.

Содержание слайда: Теорема Теорема Множество иррациональных чисел несчетно. Доказательство: Поскольку действительных чисел – несчетное множество, а рациональных – счетное, то иррациональных чисел – несчетное множество, Q.E.D.

Содержание слайда: Теорема Теорема Множество трансцендентных чисел несчетно. Доказательство: Поскольку действительных чисел – несчетное множество, а алгебраических – счетное, и при этом множество A является подмножеством R, то R \ А (множество трансцендентных чисел) представляет собой несчетное множество, Q.E.D.

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда: Все рациональные числа вычислимы, так как существует алгоритм их вычисления до любого знака, то есть с любой степенью точности. Все рациональные числа вычислимы, так как существует алгоритм их вычисления до любого знака, то есть с любой степенью точности. Алгебраические числа являются вычислимыми, так как существуют численные методы их вычисления (алгоритм Ньютона), позволяющие их вычислить с любой степенью точности. Все рациональные числа суть алгебраические, т.к. они могут быть представлены как корни уравнения a0+a1x=0, где a0 , a1 – целые числа.

Содержание слайда: Множество вычислимых действительных чисел счетно. Доказательство: Вычислимые числа включают в себя все алгебраические и некоторые трансцендентные числа. Так как каждому вычислимому действительному числу соответствует хотя бы одна машина Тьюринга, а машин Тьюринга - א 0, то значит вычислимых чисел никак не больше, чем א 0. С другой стороны, поскольку все алгебраические числа вычислимы, а их тоже א 0, то вычислимых действительных чисел никак не меньше, чем א 0. Значит мощность множества вычислимых действительных чисел равна א 0 и, следовательно, это множество счетно, Q.E.D.

Содержание слайда: Существуют невычислимые действительные числа и их несчетное множество. Существуют невычислимые действительные числа и их несчетное множество. Доказательство: Существование невычислимых чисел следует хотя бы из того факта, что всего действительных чисел несчетное множество, а вычислимых – счетное. Значит должно существовать несчетное множество невычислимых действительных чисел, Q.E.D.

Содержание слайда: Пусть имеются Тi,……,Тn,…, где Т i – i-ая машина Тьюринга. Действительное число Х можно представить так: Х= 0,a1,……,an…., где: 1, если Тi останавливается на чистой ленте ai= 0, в противном случае Такое число является невычислимым, так как задача об остановке машины Тi на чистой ленте алгоритмически не разрешима.