Несчётное множество

[Manticore]

Здравствуйте. Никак не могу понять, что такое несчётное множество - то есть понимаю, что между элементами этого множества и множеством натуральных чисел нельзя построить биекцию, но не понимаю, почему, ведь множество натуральных чисел - бесконечно.
То есть например какому-нибудь $\sqrt[319] {0.87512482597}$ вполне можно сопоставить порядковый номер, который будет натуральным числом. Почему нет?

-- 21.09.2013, 14:56 --

Читал пример с построением дроби диагональной процедурой Кантора. Построили. Дробь не совпадает ни с одной из дробей, которые у нас "лежали" на отрезке $[0,1]$.
Вывод из книги: "таким образом, никакое счётное множество действительных чисел, лежащих на выбранном отрезке, не исчерпывает его".
Может, я глупый, но никак не могу осознать это. Может, есть более очевидные примеры?

[Legioner93]

Manticore
Что конкретно вам непонятно в диагональном методе Кантора? Грамотно поставленный вопрос - это уже половина ответа.
Выписали мы "все" числа подряд? Выписали. Нашли число, которого нет в нашем списке? Нашли.

[Manticore]

Legioner93 в сообщении #766203 писал(а):

Что конкретно вам непонятно в диагональном методе Кантора?

Пусть у нас есть натуральные числа: $1, 2, ... , 10, ... , 20, ...$ (без нуля)
И, скажем, если взять действительные числа, то число $10$ не будет иметь порядкового номера $10$. Это к тому, что какое бы число из натурального ряда мы не взяли, оно будет содержаться во множестве действительных чисел с очень большим натуральным порядковым номером, который, в свою очередь, так же должен содержаться в натуральном ряде, и т.д. Но это ведь говорит только об их бесконечности.

Legioner93 в сообщении #766203 писал(а):

Выписали мы "все" числа подряд? Выписали. Нашли число, которого нет в нашем списке? Нашли.

У нас было $n$ чисел, а это будет $n+1$.

-- 21.09.2013, 15:21 --

Мы занумеровали все действительные числа. Допустим, их ровно $n$. Мы предъявляем число, отличное от всех имеющихся, но почему ему нельзя сопоставить натуральный номер? Ведь в этом случае получается, что натуральных чисел ровно $n$, т.е. это конечное множество, и действительные числа сосчитать нельзя.

[Legioner93]

Ещё раз: какие у вас вопросы по доказательству Кантора?
Предлагаю такой план действий: вы приводите сюда доказательство, которое пытаетесь понять. Или даете на него ссылку. Потом говорите, начиная с какого символа вам становится непонятно (хотя бы так). Или с чем вы не согласны.

А комментировать эту чепуху из предыдущего поста я не буду, может кто другой сподобится.

-- Сб сен 21, 2013 16:37:36 --

Manticore в сообщении #766205 писал(а):

Мы занумеровали все действительные числа. Допустим, их ровно $n$.

Мы точно об одном и том же множестве говорим? Моё всё-таки малость помощнее, чем конечное.

[Manticore]

Legioner93 в сообщении #766217 писал(а):

Мы точно об одном и том же множестве говорим? Моё всё-таки малость помощнее, чем конечное.

Так и множество натуральных чисел разве конечно?

Ладно, лучше последую Вашему совету. Вот доказательство:
Пусть есть какое-что счётное множество (всех или некоторых) действительных чисел $\alpha$, лежащих на отрезке $[0,1]$. Создаём "список" этих чисел. Далее образуем дробь, которая содержится в заданном отрезке, но не является элементом нашего списка. Таким образом, никакое счётное множество действительных чисел, лежащих на отрезке $[0,1]$, не исчерпывает этого отрезка.
Я понимаю, что мы можем бесконечно искать такие дроби, но почему мы не можем каждой дроби сопоставить натуральное число?

[provincialka]

Не надо "бесконечно искать". Достаточно один раз найти.
Вы знаете, что такое "доказательство от противного"?. Мы предположили, что можем пронумеровать все числа из отрезка. Но оказалось, что не все - противоречие. Значит, предположение было неверным. Искать еще какое-нибудь непронумерованное число уже не надо! Всё. Лом проплыл. Поздно пить боржоми.

[Manticore]

provincialka в сообщении #766227 писал(а):

Мы предположили, что можем пронумеровать все числа из отрезка. Но оказалось, что не все - противоречие.

Если мы пронумеровали все числа, то мы предположили, что данное множество конечно (и в итоге доказали, что это не так). Чтобы доказать, что оно несчётно, нужно предположить, что мы пронумеровали дроби всеми натуральными числами, но ведь это невозможно.

[ewert]

Manticore в сообщении #766228 писал(а):

Если мы пронумеровали все числа, то мы предположили, что данное множество конечно

Можно ли пронумеровать все натуральные числа?...

[Manticore]

ewert в сообщении #766231 писал(а):

Можно ли пронумеровать все натуральные числа?...

Ну по идее каждому натуральному числу соответствует равный ему номер. Но если мы сказали, что мы пронумеровали все натуральные числа, и больше просто нет, но вдруг показали, что всё-таки есть - это лишь скажет о том, что натуральные числа бесконечны, а не о том, что натуральным числам нельзя сопоставить натуральный номер.

[ewert]

Что такое счётное множество -- и что такое несчётное?...

[Manticore]

Счётное множество - множество, элементы которого можно сосчитать, т.е. сопоставить им числа из натурального ряда. Такое множество равномощно множеству натуральных чисел, и оно бесконечно.
А несчётное множество - то, элементы которого нельзя сосчитать. То есть их больше, чем натуральных чисел, количество которых бесконечно.
В частности я не понимаю, когда же тогда начинается эта несчётность? Или есть множество действительных чисел, а что тогда делать с количеством всех подмножеств действительных чисел?

Нашёл доказательство через лемму о вложенных отрезках, там вроде немного понятнее.

[XXR]

Цитата:

Вы знаете, что такое "доказательство от противного"?. Мы предположили, что можем пронумеровать все числа из отрезка. Но оказалось, что не все - противоречие. Значит, предположение было неверным. Искать еще какое-нибудь непронумерованное число уже не надо! Всё. Лом проплыл. Поздно пить боржоми.

В общем-то, правильно.

Если Вы это рассуждение принимаете, как здравое, обоснованное, соответствующее ДЕЙСТВИТЕЛЬНОСТИ (во всех ее проявлениях), то Вам деваться некуда.

Выход, конечно, есть (как всегда).

Выход состоит в том, чтобы, вот это вот рассуждение, об доказательстве от противного, не признать верным (примеров людей "настроенных" на эту ДЕЙСТВИТЕЛЬНОСТЬ полно, пассионарии, из них проявились в виде интуиционистов, конструктивистов и прочее).

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

Сделать это не так уж трудно.
Они (конформисты) рассуждают следующим образом.
Если Вы предположили, что "занумеровали" все действительные числа, то из предъявления диагональной процедурой не занумерованного числа следует его не занумерованность в принципе (никогда и ничем).
Хотя Ежу ясно, что это возражение касается конкретной процедуры именно Вашего способа нумерования, а не самого числа (якобы в принципе не занумеруемого никогда и ничем .

Они опровергают это тем, что конкретная процедура нумерования всегда ущербна, всегда есть такое число. Вот именно это – ложь. Нет такого доказательства (без порочного круга, ссылающегося на само такое доказательство).

Вам следует обратить на это "доказательство" пристальное внимание, т.к. оно неверно (или противоречиво).

Достаточно осознать, что они (конформисты) никогда и никак не смогут доказать, что все процедуры нумерования (какие бы они не были), исключают возможность нумерации некого числа, о котором они говорят, как о существующем, хотя никогда и никак его предъявить не могут (и не смогут никогда и никак).

Почему ?

Потому, что именно такой способ ("диагонализация") доказательства они и используют применительно к действительным числам.

Вам достаточно указать, что Ваш способ нумерации является тем, что они считают действительным числом и это приведет к противоречию.
Способ нумерации не может быть действительным числом, скажут они, т.к. все способы конечны.
А Вы спросите, что они понимают под конечностью ? Ничего внятного сказать они не смогут (без ссылки на "диагонализацию").
Им (конформистам) нечего будет сказать, кроме веры в существование некого деления между "много и много, конечно и бесконечно", типа 5 – это мало, а 6 – уже много. Вот только конкретного числа (5,6,7.."конечно", "бесконечно") никто и никогда не скажет. Если скажут, что не существует, ну так значит и грани между конечным и бесконечным не существует. А если скажут, что существует, ну значит и способ нумерации есть такой, который "диагональный" метод не охватывает (из-за своей внутренней противоречивости).

А потому и все рассуждения о том, что нумерация "способа нумерации" является действительным или натуральным числом, не является предметом, какого бы то ни было "доказательства", а целиком и полностью – предмет веры, более или менее согласованный со свойствами объектов теории на этой вере основанной.

[Joker_vD]

О боже, еще один Cantor freak.

[Xaositect]

Так, раз тут начали появляться безграмотные утверждения, которые могут топикстартеру помешать разобраться с диагональным методом, придется написать подробное объяснение.

Как тут уже писали (не совсем точно, но все же), множество $A$ называется счетным, если существует взаимно-однозначное соответствие между элементами множества $A$ и натуральными числами. То есть если мы можем каждому натуральному числу $n$ приписать элемент $f(n)\in A$ с номером $n$, и при этом каждый элемент будет пронумерован ровно один раз, то есть для каждого $a\in A$ найдется ровно одно число $n$ такое, что $f(n) = a$.

Соответственно, для того, чтобы доказать, что множество несчетно, нужно доказать, что такой нумерации не существует.

Для этого используется метод доказательства от противного. Который формулируется таким образом: для того, чтобы доказать несуществование объекта, нужно предположить его существование и вывести из этого предположения что-нибудь абсурдное.

(Об интуиционизме)

Стоит отметить, что метод доказательства от противного признается, насколько мне известно, всеми течениями интуиционизма и коструктивизма, хотя XXR и утверждает обратное. Теорема Кантора таже доказывается в различных интуиционистсиких и конструктивных теориях. Доказательство от противного и закон исключенного третьего - это совершенно разные вещи, и интуиционисты отказываются именно от закона исключенного третьего.

Итак, предположим, что есть хорошая нумерация $f$, которая каждому натуральному $n$ ставит в соответствие действительное $f(n)$, причем любое действительное соответствует какому-то натуральному. Тогда с использованием диагонального метода можно построить бесконечную дробь, которая отличается от $f(n)$ в $n$-м знаке. Эта дробь означает какое-то действительное число $x$, которое по построению отличается от каждого $f(n)$ (я здесь опустил обязательное замечание о нулях и девятках, но с ним тоже все хорошо). Это значит, что наша исходная нумерация не содержала $x$, то есть никакому номеру $n$ не было поставлено в соответствие число $x$. Однако мы предположили, что любое число, а значит, и число $x$, в нумерации содержалось. Противоречие.

-- Сб сен 21, 2013 19:02:05 --

Manticore в сообщении #766237 писал(а):

Или есть множество действительных чисел, а что тогда делать с количеством всех подмножеств действительных чисел?

А множество всех подмножеств множества действительных чисел еще мощнее, чем само множество действительных чисел, то есть его нельзя "перенумеровать" не только натуральными числами, но даже действительными.

[Joker_vD]

(Об интуиционизме)

Ну, $\neg B,A\to B\vdash \neg A$ в интуиционизме, безусловно, выводимо: $k\colon \neg B,f\colon A\to B\vdash \left(\lambda x\colon A. k(fx)\right) \colon \neg A$. Проблемы со второй ипостасью: с $\neg B,\neg A\to B\vdash A$. Впрочем, к данной проблеме она отношения не имеет.