можно то же самое показать в любой другой, но в этой проще всего Нет, нельзя. Возьмем десятичную стсьемы и будем превращать цифры меньше пяти в восемь, остальные в два.
Ваше "опровержение" зависит от выбора системы счисления. Рассуждение Кантора существенно использует то, что цифр больше 4, его модификация для систем счисления меньших по объему, возможна, но никому не интересна.
Не, не зависит. Я стёр эту часть разъяснения, поскольку она получилась длинной, а обещалось короткое, однако общий смысл в том, что функция нумерации может нумеровать двоичные представления чисел. Поэтому манипуляции с иным представлением ничего не поменяют. Фокус в том, что конечная десятичная дробь в двоичном представлении может быть бесконечной. Поэтому исключить строки из нумерации мы таким образом не сможем.
Ну и в целом, странно было бы думать, что можно пронумеровать числа из одного и того же множества в двоичном представлении, но вот в десятичном нельзя.
Кроме того, классическая версия «диагонального аргумента», она как раз в двоичном представлении. И вот там как раз точно сабжевое утверждение неверно.
Существуют бесконечные множества, не равномощные множеству натуральных чисел (то есть не существует сюръективного отображения из множества натуральных на данное множество). Например, это множество бесконечных строк из двух символов.
Доказывается оно как раз диагональным аргументом, и такие опровержения там не сработают, потому что нельзя построить нумерацию строк, чтобы на диагонали никогда не встречался 1. Уже из этого утверждения несложно показать, что не существует сюръективного отображения множества натуральных на множество действительных, а отсюда - что N не равномощно [0, 1).
> Доказывается оно как раз диагональным аргументом, и такие опровержения там не сработают, потому что нельзя построить нумерацию строк, чтобы на диагонали никогда не встречался 1.
Это по какой-такой особой уличной магии нельзя построить такую нумерацию? Можно, причём ещё и вариантов таковой будет бесконечно много.
Да, если брать несколько цифр, то сработает. Хотя и для них можно подобрать такой способ сортировки, что будет получаться 0,(1), нельзя подобрать способ, при котором для любого выбранного количества цифр одновременно не будет срабатывать, поэтому, таки да, с этой модификацией построить можно.
Поэтому изложенное мной соображение исключает только случай с выбором одной цифры на диагонали, а не вообще все.
Правда, его исключение всё равно критично, но в таком коротком виде, да, доказательство не полное.
> Хотя и для них можно подобрать такой способ сортировки, что будет получаться 0,(1)
Нельзя, я ж написал, что цифры берём отличные от 11.
> Поэтому изложенное мной соображение исключает только случай с выбором одной цифры на диагонали, а не вообще все. > Правда, его исключение всё равно критично, но в таком коротком виде, да, доказательство не полное.
Нет, не критичное. То, что при некотором способе записи чисел, процедура из классического диагонального аргумента может давать объект не принадлежащий рассматриваемому множеству - означает только, что в каждом конкретном случае применения этой процедуры надо доказывать, что построенный объект принадлежит рассматриваемому множеству независимо от нумерации.
> Нельзя, я ж написал, что цифры берём отличные от 11.
Да, пожалуй, действительно нельзя.
> Нет, не критичное.
Оно критичное для других рассуждений: только в случае двоичного представления и выбора одной позиции на диагонали не получится указать растущее с каждым шагом подмножество совершенно точно перечислимых, но совершенно точно ещё не исключённых к этому шагу элементов списка. Во всех остальных случаях это подмножество неограниченно растёт с ростом n, что приводит к противоречию: предполагается, что в пределе исключены все строки, но одновременно с тем в этом же пределе должно быть бесконечно много не исключённых строк. То же, что этот особый случай тоже приводит к противоречию (пусть и другому), делает доказательство противоречивости диагонального аргумента полным. Вот в этом смысле оно критично.
Comments 394
Нет, нельзя.
Возьмем десятичную стсьемы и будем превращать цифры меньше пяти в восемь, остальные в два.
Reply
Но таки да, сформулировано неточно, согласен.
Reply
Reply
Ну и в целом, странно было бы думать, что можно пронумеровать числа из одного и того же множества в двоичном представлении, но вот в десятичном нельзя.
Кроме того, классическая версия «диагонального аргумента», она как раз в двоичном представлении. И вот там как раз точно сабжевое утверждение неверно.
Reply
0,(1)=1 (строго) - это точно? Там же вроде опять пределы и бесконечности вылезают? (Если что - я не математик).
Reply
Reply
Существуют бесконечные множества, не равномощные множеству натуральных чисел (то есть не существует сюръективного отображения из множества натуральных на данное множество). Например, это множество бесконечных строк из двух символов.
Доказывается оно как раз диагональным аргументом, и такие опровержения там не сработают, потому что нельзя построить нумерацию строк, чтобы на диагонали никогда не встречался 1.
Уже из этого утверждения несложно показать, что не существует сюръективного отображения множества натуральных на множество действительных, а отсюда - что N не равномощно [0, 1).
Reply
Это по какой-такой особой уличной магии нельзя построить такую нумерацию? Можно, причём ещё и вариантов таковой будет бесконечно много.
Reply
Потому что есть строка из одних единиц и один из её элементов попадает на диагональ.
Reply
Reply
Reply
Reply
Reply
Поэтому изложенное мной соображение исключает только случай с выбором одной цифры на диагонали, а не вообще все.
Правда, его исключение всё равно критично, но в таком коротком виде, да, доказательство не полное.
Reply
Нельзя, я ж написал, что цифры берём отличные от 11.
> Поэтому изложенное мной соображение исключает только случай с выбором одной цифры на диагонали, а не вообще все.
> Правда, его исключение всё равно критично, но в таком коротком виде, да, доказательство не полное.
Нет, не критичное.
То, что при некотором способе записи чисел, процедура из классического диагонального аргумента может давать объект не принадлежащий рассматриваемому множеству - означает только, что в каждом конкретном случае применения этой процедуры надо доказывать, что построенный объект принадлежит рассматриваемому множеству независимо от нумерации.
Reply
Да, пожалуй, действительно нельзя.
> Нет, не критичное.
Оно критичное для других рассуждений: только в случае двоичного представления и выбора одной позиции на диагонали не получится указать растущее с каждым шагом подмножество совершенно точно перечислимых, но совершенно точно ещё не исключённых к этому шагу элементов списка. Во всех остальных случаях это подмножество неограниченно растёт с ростом n, что приводит к противоречию: предполагается, что в пределе исключены все строки, но одновременно с тем в этом же пределе должно быть бесконечно много не исключённых строк. То же, что этот особый случай тоже приводит к противоречию (пусть и другому), делает доказательство противоречивости диагонального аргумента полным. Вот в этом смысле оно критично.
Reply
Leave a comment