Как доказать несчетность множества точек

Sergey79

Как доказать несчетность множества точек на (0,1). То есть какие аксиомы теории множеств необходимы чтобы было верно утверждение "множество точек на (0,1) мощнее множества натуральных чисел"
:confused:

shale60

Простое школьное доказательство: http://kvant.mccme.ru/pdf/2005-04.pdf
страница 3

incwizitor

Простое школьное доказательство
неужели школьное док-во прокатит на форуме МГУ :confused: :grin: :grin: :grin:

Vikuschechka9

ровно такое же вроде как было на мехматских лекциях

Sergey79

Простое школьное доказательство:
это замечательное доказательство опирается на некие аксиомы. Ибо там часть утверждений "доказывается", а часть утверждений приводится без малейшего обоснования.
Например, Доказательство1 строится по схеме
Что значит: нельзя пересчитать числа интервала? Это значит, что если мы выберем любую последовательность чисел x_1,x_2,x_n... из интервала, то всегда найдется число из интервала, не совпадающее с этими выписанными

Далее идет подробное построение этого числа.
Доказательство2 строится по той же схеме:
Предположим что мы занумеровали все числа отрезка. Предъявим число, которое мы не смогли занумеровать. Предъявили, получили противоречие, значит наше предположение не верно.

Так вот поясните мне почему "мы не смогли занумеровать числа на отрезке" = "невозможно занумеровать числа на отрезке". Может быть у нас просто руки кривые, и всего лишь предложенные нами методы нумерации не позволяют это сделать?

Sergey79

Вот мы пронумеровали числа на отрезке неким алгоритмом. Нашли числа на отрезке не вписывающиеся в этот алгоритм. Ну так доработаем наш алгоритм - добавим к нему алгоритм, описывающий вот эти новые числа. Даже если у нас в итоге будет счетное количество алгоритмов, как гласит википедия
2.Объединение конечного или счётного числа счётных множеств счётно

spiritmc

Если у тебя есть нумерация, ты можешь "построить" число, которое не занумеровано.
Отсюда следует, что нумерации нет.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."

Sergey79

1. Если у тебя есть нумерация, ты можешь "построить" число, которое не занумеровано.
2.Отсюда следует, что нумерации нет.

Что такое "нумерация"?

spiritmc

Отображение из множества натуральных чисел в заданное.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."

Vlad128

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

Sergey79

ну а кто сказал, что ты отделаешься счетным множеством алгоритмов? Это ведь надо доказать.
А вот именно это я и спрашиваю! Я не умею это доказать, как не умею доказать и обратное.
В "школьных" доказательствах это положение (что счетным не отделаешься) почему-то полагается доказанным (или принятым за аксиому?). Мне хочется прояснить этот вопрос.

Vlad128

Никто доказывать про количество алгоритмов ничего не будет.
Нету просто нумерации, все. Зачем еще подсчитывать количество алгоритмов, которые пытались ее построить, но не смогли? Да еще как-то эволюционировали и видоизменялись. Множество точек на отрезке никуда от тебя не бежит, тебе не нужен алгоритм, чтобы его занумеровать. Просто покажи нам нумерацию, если не можешь — gtfo. (это не лично тебе, это я как бэ объясняю схему доказательства).

Sergey79

отлично. Теперь проясним что значит "есть" (применительно к нумерации)

Sergey79

Просто покажи нам нумерацию, если не можешь — gtfo
Почему gtfo?
В этом суть вопроса.

Vlad128

Предположим, вы говорите ребенку: “Львы существуют, а единороги нет"; вы можете доказать это в отношении львов, приведя ребенка в зоопарк и сказав: “Смотри, это лев". Вы не добавите, если вы не философ: “И ты можешь видеть, что это существует". Если, будучи философом, вы все-таки это добавите, вы скажете вздор. Сказать “львы существуют" означает “львы имеются", то есть предложение x есть лев" истинно, для подходящего “X". Но вы не можете сказать о подходящем “X", что он “существует": мы можем применить этот глагол лишь к описанию независимо от того, является ли оно полным или неполным. “Лев" есть неполное описание, потому что оно относится ко многим объектам: “Самый большой лев в зоопарке" есть полное описание, потому что оно применимо только к одному объекту.

Vlad128

нумерация существует => это не нумерация. Эта импликация верна только в одном случае. В каком?

spiritmc

> Так вот поясните мне почему "мы не смогли занумеровать числа на отрезке" =
> "невозможно занумеровать числа на отрезке". Может быть у нас просто руки кривые,
> и всего лишь предложенные нами методы нумерации не позволяют это сделать?
Да, у вас руки кривые:

Г |- P(t)
-------------------
Г |- \forall x P(x)

---
"Нахер нужны выпускники мехмата, если они за третий класс
математику не знают... Мозг высшей геометрией разрушен."

vsjshnikova

Из теории множеств в доказательстве нужна вроде только аксиома выделения, а вот для того, чтобы определить, что такое (0,1) и что такое "мощнее", нужна куча остальных.

Sergey79

я не знаю ответ на твой вопрос. Ответь, пожалуйста, сам

BSCurt

Что бы доказать несчетность отрезка (ты хочешь правда доказать, что мощность отрезка больше чем у натуральных чисел доказывают от противного - предполагают что отрезок счетен, т.е. существует биекция между натуральными числами и отрезком и дальше приходя к противоречию при предъявляя число из отрезка которому не соответствует никакое натуральное число. Но да ты хочешь доказать не совсем это.

spiritmc

> предполагают что отрезок счетен, т.е. существует биекция
Биекция не обязательна, достаточно сюръекции.
---
...Я работаю антинаучным аферистом...

Sergey79

обычно приходят к противоречию относительно одной единственной предъявленной биекции - что она (и по факту только она) биекцией не является.

Vlad128

там же рассматривается произвольная биекция, а не одна.
у тебя сложности со схемой доказательства от противного или в чем?
Давай менее противно. Рассмотрим отображение. Оно не является биекцией, потому что [строим число, которое никуда не отображено].

BSCurt

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

BSCurt

Биекция не обязательна, достаточно сюръекции.
Да в его случае достаточно сюръекции.

Sergey79

Из теории множеств в доказательстве нужна вроде только аксиома выделения
Вопрос был не в том какой аксиомы достаточно, а какая необходима и достаточна. Понятно что AC достаточно. Но в том вопрос, что необходима, я так понимаю, ACw. А вот достаточно ли ее, или нужна DC именно исходя из того что мы работаем с такой конструкцией как (0,1) и с таким понятием как "мощнее"

Прошу прощения, если терминология кривая, я ей не вполне владею.

BSCurt

Вообще чего тебя потянуло на такие материи?

Sergey79

Суть в том что ты приходишь к противоречию для любой биекции
нет, только для каких-то конкретных.

Sergey79

я не знаю

spiritmc

Если пытаешься разобраться с аксиоматизацией теории множеств,
то тебе надо отложить числа в сторону и разобраться
с доказательством того, что |A| < |2^A|.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."

Sergey79

с этим я разобрался уже

BSCurt

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

Sergey79

проделаем диагональный процесс
он же проделывается для "любой конкретной" биекции, а не для "любой"

spiritmc

> он же проделывается для "любой конкретной" биекции, а не для "любой"
Тебе надо срочно вспомнить логику. А именно, правило обобщения.
---
"Нахер нужны выпускники мехмата, если они за третий класс
математику не знают... Мозг высшей геометрией разрушен."

BSCurt

он же проделывается для "любой конкретной" биекции, а не для "любой"
не понимаю что в твоем понимание такое "любая" биекция.

Sergey79

это означает что я записываю биекцию не для компилятора, а для интерпретатора
Например, вот такая Программа:
1. Берем биекцию "из учебника такого-то страница такая-то", только для нумерации используем нечетные числа. Также запоминаем число n=2.
2. Если <нам предъявляют число X, не пронумерованное нашей биекцией>, то <присваиваем ему номер n; n=n+2>

BSCurt

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

spiritmc

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

Sergey79

у тебя есть множество всех отображений из натуральных числе в отрезок, тебе надо доказать что ни один его элемент не удовлетворяет некоторому свойству (не является сюръецией или биекцией
Да, у меня есть счетное множество всех отображений из натуральных числе в отрезок, мне надо доказать что ни один его элемент не удовлетворяет некоторому свойству (не является сюръецией или биекцией)
Как это сделать?

spiritmc

> Ничего не понял
Я считаю, что это не связано с теорией множеств,
у него беда с правилом обобщения.
---
"Нахер нужны выпускники мехмата, если они за третий класс
математику не знают... Мозг высшей геометрией разрушен."

spiritmc

> Да, у меня есть счетное множество всех отображений из натуральных числе в отрезок,
> мне надо доказать что ни один его элемент не удовлетворяет некоторому свойству
> (не является сюръецией или биекцией)
> Как это сделать?
Для начала, надо осознать тот простой факт, что множество отображений
из натуральных чисел в отрезок не является счётным.
Хотя бы потому, что множество отображений натуральных чисел
в два элемента уже несчётно: |N| < |2^N|.
Это частный случай теоремы Бернштайна, с которой ты якобы разобрался.
---
"Нахер нужны выпускники мехмата, если они за третий класс
математику не знают... Мозг высшей геометрией разрушен."

Sergey79

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

spiritmc

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

BSCurt

Как это сделать?
Предположим что такое элемент существует... ну ты понял.

Sergey79

а их там таких несчётное множество
этого мы как раз заранее не знаем

spiritmc

Заранее не знаем, но зато знаем не заранее.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."

Sergey79

Предположим что такое элемент существует... ну ты понял.
не понял именно это. Чтобы на множестве можно было реализовать процедуру <доказательство от противного>, нужно чтобы множество обладало какими-то свойствами. Какими?

vsjshnikova

не понял именно это. Чтобы на множестве можно было реализовать процедуру <доказательство от противного>, нужно чтобы множество обладало какими-то свойствами. Какими?
Доказательство от противного - это не процедура на множестве. Это логическая конструкция: если из какого утверждения мы можем вывести противоречие, то тем самым мы доказываем отрицание этого утверждения.
Почитай, правда, что нибудь по логике предикатов.

spiritmc

> Чтобы на множестве можно было реализовать процедуру
> <доказательство от противного>, нужно чтобы множество
> обладало какими-то свойствами. Какими?
Тут ты лезешь в основания математики, а это требует знания твоих
философских установок. Если ты не воспринимаешь метод доказательства
от противного как очевидный, то ты сближаешься с интуиционистами
и конструктивистами. Тогда тебе и множества придётся определять
способом, не обязательно совпадающим с традиционным.
В целом, ты можешь считать, что множество должно быть конечным.
Или, если ты "правильно" определишь множества, любым, просто
у тебя все множества будут конечными в классическом понимании.
---
"Математика --- лучший способ водить самого себя за нос."

incwizitor

ровно такое же вроде как было на мехматских лекциях
как там обыгрывается неоднозначность записи вещественного числа в виде десятичной дроби? это довольно важный момент имхо. в школьном док-ве это прикрывается фразой
Определим это понятие не совсем строго: веществен-
ное число – это бесконечная десятичная дробь. Чтобы
определение было совсем строгим, нужны некоторые
уточнения. Мы не будем здесь излагать теорию веще-
ственных чисел со всей подробностью

avgustinka

это как раз ерунда.
например, попытаемся занумеровать хотя бы все числа без 0 и 9 в десятичной записи.

incwizitor

это как раз ерунда.
например, попытаемся занумеровать хотя бы все числа без 0 и 9 в десятичной записи.
а как объяснить, что именно из-за 0 и 9 всплывает неоднозначность ? есть ли гарантия, что других "коллизий" не существует?

spiritmc

> например, попытаемся занумеровать хотя бы все числа без 0 и 9 в десятичной записи.
Можно поступить ещё проще: построить незанумерованное число
без использования "9" в десятичной записи (или, для патриотов,
без "2" в троичной).
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."

spiritmc

> а как объяснить, что именно из-за 0 и 9 всплывает неоднозначность ?
> есть ли гарантия, что других "коллизий" не существует?
Определение не является гарантией?
---
"Математика --- лучший способ водить самого себя за нос."

Sergey79

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

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

tester1

помнится, я тоже когда-то заводил обсуждение про аксиому выбора на флокале
все, я разобрался. Спасибо.
Просто операции с множествами мне не очевидны,
и правильно. если интересно, ещё погугли по ключевым словам "(не)перечислимые множества", "(не)вычислимые функции", "дескриптивная теория множеств"
например, первые две страницы выдачи http://yandex.ru/yandsearch?lr=213&text=%D0%B4%D0%B5%D1%...
вот и применение к ним логики для меня выглядело не очевидным.
метод доказательства "от противного", насколько я понимаю, основан на вере в то, что противоречия (парадоксы) не могут возникнуть на ровном месте, т.е. аксиоматика математики непротиворечива. парадокс, противоречие - это ситуация, когда кажутся доказанными (выведенными из аксиом по допустимым правилам вывода) два утверждения, являющиеся отрицаниями друг друга
рассуждение, обосновывающее метод "от противного", вроде, такое: в математике самой по себе противоречия не возникают. добавим к математике утверждение А, считая его выводимым из аксиом, т.е. как бы верным. опираясь на него, будем выводить из него и из аксиом по правилам вывода новые утверждения. если получили парадокс, значит, утверждение А не является выводимым, потому что если бы оно было выводимым, то парадокс возникнуть бы не мог. таким образом, А не выводимо. считать ли при этом, то выводимо отрицание утверждения А - зависит от того, веришь ли ты в принцип исключенного третьего применительно к А, и не подпадает ли А под теоремы Гёделя. впрочем, кажется, я тут как раз только что использовал, что для каждого утверждения А утверждение о том, что А выводимо, является выводимым, что не есть хорошо, так как я вроде как сейчас применил как раз метод "от противного", по идее. хз.
кто шарит, поправьте/дополните, плиз

spiritmc

Парадокс и противоречие --- разные вещи.
Про метод доказательства от противного лучше прочитать в учебнике по логике,
а про его обоснование --- в каком-нибудь учебнике по основаниям математики.
Там, между прочим, будет ещё упомянуто, что обоснование у этого метода
довольно шаткое. А каким образом здесь теоремы Гёделя нужны, не очень понятно.
---
"Математика --- лучший способ водить самого себя за нос."

tester1

обоснование у этого метода
довольно шаткое
это точно

vsjshnikova

 кто шарит, поправьте/дополните, плиз
Метод доказательства от противного и закон исключенного третьего - это разные вещи. Из закона исключенного третьего следует принцип доказательства от противного, а наоборот - нет. Например, интуиционистские системы допускают доказательство от противного, отказываясь от закона исключенного третьего.
К теореме Геделя доказательство от противного тоже мало отношения имеет, в том смысле, что в интуиционизме и конструктивизме недоказуемые и неопровержимые утверждения вполне естественны, из-за этого там существуют разные конструкции типа "не может не существовать" для того случая, когда ни существование, ни несуществование доказать нельзя.
В принципе, доказательство от противного - это определение отрицания (для того, чтобы доказать отрицание утверждение, необходимо опровергнуть это утверждение). В интуиционизме это особенно видно, там доказательство от противного является правилом введения отрицания и аналогично правилам введения остальных логических связок. Можно еще переформулировать теорию доказательств, отказавшись от отрицания, но зато введя наряду с понятием вывода понятие опровержения, получится то же самое.
Оставить комментарий
Имя или ник:
Комментарий: