Бутем пользоваться терминологией мощности множества.
Множество A называется счетным, если можно построить взаимооднозначное соответствие его элементов с элементами множества натуральных чисел и несчетным, если его построить нельзя.
Утверждение 1. Объединение двух счетных множеств счетно. Доказательство: Пусть есть множества
Запишем их объединение как
И пронумеруем их: Номер равен 2i-1 Номер равен 2i Если в этих множествах есть повторяющиеся - уберем повторения и уменьшим номера последующих Построили взаимооднозначное соответствие и доказали утверждение.
Утверждение 2. Объединение конечного и счетного множества счетно. Доказательство еще более очевидно, чем в первом - поставим сначала все элементы конечного множества (которых нет в счетном), а затем все из счетного и пронумеруем.
Утверждение 3. Множество рациональных чисел счетно. Докажем, что множество неотрицательных рациональных чисел счетно. Тогда множество неположительных рациональных чисел также счетно и их объединение будет счетным. Доказательство: Выпишем таблицу в которой в строке i будут находиться числа со знаменателем i, а в столбце j будут находиться числа с числителем j-1
Пронумеруем "по диагоналям" Сначала левый верхний элемент, затем элемент, стоящий справа от него, затем по диагонали влево вниз все элементы, затем элемент стоящий в первой строке на 3 месте и вниз по диагонали и так далее. Получили последовательность 0/1 1/1 0/2 2/1 1/2 0/3 3/1 ... Пронумеровали все элементы, но есть повторяющиеся - выкинем их. Осталось 0 1 2 1/2 3 1/3 4 3/2 2/3 1/4 ... Опять таки пронумеровали, только уже все множество неотрицательных рациональных чисел без повторений, чем доказали его счетность
Утверждение 4. Можно построить взаимозначное соответствие элементов множеств действительных чисел сегмента [0;1] и бесконечных последовательностей из 0 и 1. Доказательство заключается в том, что действительное число можно представить как в виде бесконечной десятичной дроби, так и бесконечной двоичной.
Теорема. Множество бесконечных последовательностей 0 и 1 несчетно. Доказательство: Допустим обратное. Тогда можно записать в виде последовательности
каждый элемент этой последовательности - последовательность 0 и 1, то есть можно записать в виде
Тогда число, составленное из элементов, стоящих на главной диагонали и число обратное к нему (обратное в смысле, что если на некоторой позиции у элемента стоит k, то у обратного 1-k) тоже здесь есть, но у обратного:
На позиции t стоит стоит обратный. Противоречие.
Отсюда множество рациональных чисел счетно, а действительных от 0 до 1 - несчетно. В терминах условия "множество реальных чисел от 0 до 1 больше, чем множество рациональных чисел"
Множество A называется счетным, если можно построить взаимооднозначное соответствие его элементов с элементами множества натуральных чисел и несчетным, если его построить нельзя.
Утверждение 1. Объединение двух счетных множеств счетно.
Доказательство:
Пусть есть множества
Запишем их объединение как
И пронумеруем их:
Номер равен 2i-1
Номер равен 2i
Если в этих множествах есть повторяющиеся - уберем повторения и уменьшим номера последующих
Построили взаимооднозначное соответствие и доказали утверждение.
Утверждение 2. Объединение конечного и счетного множества счетно.
Доказательство еще более очевидно, чем в первом - поставим сначала все элементы конечного множества (которых нет в счетном), а затем все из счетного и пронумеруем.
Утверждение 3. Множество рациональных чисел счетно.
Докажем, что множество неотрицательных рациональных чисел счетно. Тогда множество неположительных рациональных чисел также счетно и их объединение будет счетным.
Доказательство:
Выпишем таблицу в которой в строке i будут находиться числа со знаменателем i, а в столбце j будут находиться числа с числителем j-1
Пронумеруем "по диагоналям"
Сначала левый верхний элемент, затем элемент, стоящий справа от него, затем по диагонали влево вниз все элементы, затем элемент стоящий в первой строке на 3 месте и вниз по диагонали и так далее.
Получили последовательность
0/1 1/1 0/2 2/1 1/2 0/3 3/1 ...
Пронумеровали все элементы, но есть повторяющиеся - выкинем их. Осталось
0 1 2 1/2 3 1/3 4 3/2 2/3 1/4 ...
Опять таки пронумеровали, только уже все множество неотрицательных рациональных чисел без повторений, чем доказали его счетность
Утверждение 4. Можно построить взаимозначное соответствие элементов множеств действительных чисел сегмента [0;1] и бесконечных последовательностей из 0 и 1.
Доказательство заключается в том, что действительное число можно представить как в виде бесконечной десятичной дроби, так и бесконечной двоичной.
Теорема. Множество бесконечных последовательностей 0 и 1 несчетно.
Доказательство:
Допустим обратное. Тогда можно записать в виде последовательности
каждый элемент этой последовательности - последовательность 0 и 1, то есть можно записать в виде
Тогда число, составленное из элементов, стоящих на главной диагонали и число обратное к нему (обратное в смысле, что если на некоторой позиции у элемента стоит k, то у обратного 1-k) тоже здесь есть, но у обратного:
На позиции t стоит стоит обратный. Противоречие.
Отсюда множество рациональных чисел счетно, а действительных от 0 до 1 - несчетно.
В терминах условия "множество реальных чисел от 0 до 1 больше, чем множество рациональных чисел"