Для всех тех, у кого несчётность R вызывает сомнения

[vek88]

AlexDem в сообщении #279456 писал(а):

Да, видимо, у меня зачастую нет метода составления таблицы, а вот алгоритм есть - это сама таблица. Или запрограммированная машина Тьюринга (пускай и неполноценная в виде конечного автомата) уже не является алгоритмом?..

Я же сказал спать. Алгоритм, программа или таблица с незаполненными элементами - это уже не "конкретное предписание", т.е. не алгоритм и не программа - такой "алгоритм" и/или "программа" не будет работать, т.е. выдавать конкретный результат на конкретные входные данные.

И повторяю свой большой вопрос. Неужто Вы умеете писать программы для решения алгоритмически неразрешимых проблем?

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

И у меня конструктивное предложение. Поскольку нам тут уже правильно напоминали, что мы не в теме, начните, если хотите, новую тему типа вычислимость и программирование. Я поддержу Вашу тему участием. А то ведь и правда, унесло нас от счетности/несчетности и диагонального метода Кантора.

[AlexDem]

vek88 в сообщении #279476 писал(а):

Я же сказал спать.

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

[vek88]

Итак, счетно или несчетно $R$!? Выше я уже ответил на этот вопрос полушутя-полусерьезно.

vek88 в сообщении #279168 писал(а):

Вот еще пример на мою любимую тему Могут ли люди мыслить?

Да ничего здесь доказывать не надо! Поясню на примере анекдота (знак ' обозначает ударение).

Вопрос. Как правильно писать: портф'ель, или п'ортфель?

Ответ. Можно и так и так. Но при этом надо знать, что в портф'ель кладут документы, а в п'ортфель л'ожат док'ументы.

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

Теорема.
Пусть $A$ - произвольное бесконечное множество. Для любого множества подмножеств множества $A$ существует большее по включению множество подмножеств множества $A$.

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

На более строгом уровне этот вопрос рассмотрен в теме topic29047.html.

P.S. Данный опрос иллюстрирует беду многих формализованных опросов. Она состоит в том, что в список возможных ответов не включают правильный ответ!!!

А в данном случае правильный ответ - можно считать счетным, а можно - несчетным.

[EvgenyGR]

А можно посмотреть на этот вопрос немного с другой стороны.
На сколько я понимаю теорема Кантора относиться не к рационным и действительным числам, а к некому более общему абстрактному объекту - множеству, а само доказательство оперирует лишь с некими идентификаторами элементов абстрактного множества. Причем сами идентификаторы продукт некой процедуры (алгоритма). Фактически сравнивая мощности множеств через возможность взаимно однозначного отображения, мы рассуждаем об эквивалентности процедур (алгоритмов). Или по другому алгоритмы порождающие множества идентификаторов счетной мощности не эквивалентны (в каком-то смысле) алгоритмам порождающим множества идентификатором мощности континуум. Эта не эквивалентность может выражаться например вот в чем. Множество идентификатор счетной мощности может быть порождено конечным алгоритмом за бесконечное число шагов, а вот множество идентификаторов мощности континуум так не получишь. Интуитивно это выглядит очень правдоподобно. Идентификаторы для обозначения действительных чисел можно сравнить с бесконечно ветвящимся деревом. Для десятичной системы из каждого узла выходит десять веточек. Или по другому бесконечно ветвящийся процесс не может быть подобен последовательному процессу.

[vek88]

Уважаемый EvgenyGR!

Если честно, я ничего не понял из сказанного Вами. В частности, как можно говорить об алгоритме в связи с несчетными множествами? Хотя и сам в последнем сообщении сказал что-то ... что и сам не понял. Так вот уточняю - у нас две возможности:

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

2. Классическая: здесь все как обычно - и множество всех ДЧ существует и, естественно, несчетно.

Подробности см. в теме topic29047.html

Хотелось бы и от Вас услышать более понятное изложение Вашей точки зрения.

С уважением,
vek88

P.S. А правильный вариант ответа для опроса, видимо, звучит так: либо $R$ несчетно, либо $R$ не является множеством?

Или: либо $R$ несчетно, либо любое множество ДЧ счетно (в последнем случае доказывается, что множество всех ДЧ не существует).

[EvgenyGR]

Наверно говорить об алгоритме в обычном понимании (определение в википедии) нельзя уже для счетных множеств. Но что мешает предположить что алгоритм «работает бесконечно», совершает бесконечное число шагов? Если результат работы алгоритма это формирование неких идентификаторов, например N/M то в результате мы получим некое бесконечное множество (бесконечную последовательность) очевидно счетную. На самом деле мы конечно никакого БЕСКОНЕЧНОГО множества не получим. У нас будет некая конечно записанная процедура описания объекта «рациональные числа». В дальнейшем если мы захотим выяснить какие-то свойства объекта «рациональные числа» мы будем оперировать именно с описанием (с аксиоматикой). Получается мы работаем с помощью конечно описываемых процедур над конечно описываемыми объектами. Но всегда ли так? Тут видимо надо как-то определить что значит конечно описываемый объект. Дело в том что мы действительно можем записать все мыслимые нами объекты например в книгу, в виде какого-то конечного описания и вполне возможно что другой человек никогда нечего не читавший на эту тему прочтя эту книгу все поймет. Но можно ли считать книгу конечным описанием? Вполне может быть так, что разум человека писавшего книгу и разум человека читающего книгу содержат в себе некие не конечно описываемые объекты, а книга лишь сопоставляет эти «бесконечные объекты». Поэтому более чистое определение конечно описываемого объекта и конечно описываемой процедуры это инструкция понятная неодушевленному предмету (алгоритм). У меня есть интуитивное ощущение, что описание множество мощности континуум как раз и содержит в себе эти самые не конечно описываемы объекты (объекты нашего сознания).

[vek88]

Очень приближенно и исключительно на интуитивном уровне попытаюсь в меру своего понимания формализовать сказанное Вами. Думаю, что в своем мышлении человек может представить не больше, чем конечное число аксиом и правил вывода. В качестве такой системы аксиом и правил я предпочитаю использовать полные К-системы (выше я привел ссылку на соотв-ю тему).

Соответственно, в полной К-системе мы можем представить только счетные множества, но не можем представить все ДЧ (это уже математический факт). На мой взгляд, счетные множества соответствуют понятию "конечно описываемого объекта". А множество всех ДЧ - пример "не конечно описываемого объекта", поскольку "не влезает" в полную К-систему".

Для описания всех ДЧ мы расширяем К-систему понятием оракула (устройство связи с внешним миром). А чтобы остаться в рамках приличий в плане конструктивизма, мы все-таки требуем, чтобы при любом конечном описании ДЧ мы не выходили за рамки полных К-систем. Разумеется, здесь мы говорим о конечном описании каких-то подмножеств множества всех ДЧ, поскольку все множество ДЧ, как мы уже поняли, мы описать конечно не можем.

Тут я вспомнил вопрос из фильма Men in black: Так лучше?

[EvgenyGR]

ДЧ это двоичные числа? Допустим нам надо как-то описать множество идентификаторов которое можно получить используя ту или иную процедуру. Пусть в качестве идентификатора как раз и используются те самые ДЧ. А в качестве процедуры берется некое множество алгоритмов (видимо можно взять бесконечное множество различных алгоритмов) совершающих бесконечное число шагов. В этом случае множество ДЧ, которое можно получить счетное. Но изменим процедуру, пусть последовательность нулей и единиц формируется случайным образом. Как я понимаю, множество все таких последовательностей будет уже континуум.
Что сейчас произошло я написал «случайное» и Вы скорее всего поняли, что я имею ввиду говоря «случайное». У Вас и у меня есть абстракция «случайного». Возможно эта та самая конечно не описываемая процедура? Сколько еще таких абстракций в нашем сознании?
Первый вывод, который можно сделать из таких рассуждений это то, что конструктивизм может быть уже чем теоретикомножественное основание математики.

[vek88]

Мне кажется, что интуитивно я Вас понимаю. Кажется, т.к. Вы рассуждаете на интуитивном уровне. А интуиция - это очень неформально и не всегда однозначно.

А чтобы продвинуться в понимании (хотя бы математической) интуиции, все-таки желательно использовать какой-нибудь формализм. Вот я и пытаюсь для этих целей использовать полные К-системы. И так оно и есть - все только что сказанное Вами о случайности, влегкую представляется в К-системах. Уточню только, что все можно упростить, если говорить о произвольности вместо случайности. А тогда сказанное Вами просто означает, что ДЧ - это произвольная двоичная (или десятичная) дробь. И это элементарно определяется в полной К-системе. А вот для представления множества всех ДЧ пондобится уже К-система с оракулом для ДЧ.

[EvgenyGR]

Я не занимаюсь профессионально математикой и по мне лучше просто читать чем высказываться , и в частности а что такое «полные К-системы с оракулом».

Что касается замены «случайное» на «произвольное», можно конечно, но «произвольное» это все та же алгоритмически не описываемая абстракция.


По поводу интуиции, о ее природе и ее отличие от математического формализма. Опять же рассуждаю интуитивно.

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

А что же в этом случае можно понимать под интуитивностью? Возможно это способ сопоставления не конечно описываемых объектов. Каким образом организовано это сопоставление? Возможно, это то, что называется аналогией. Природа сопоставления через аналогию распространена в физике. Это когда из соответствия частностей делается вывод о соответствии во всем. В свое время было такое направление аналоговые вычислительные машины, там шло сопоставление схем составленных из усилителей и поведения, например, таковой трансмиссии.

[vek88]

EvgenyGR в сообщении #286260 писал(а):

(1) Я не занимаюсь профессионально математикой и по мне лучше просто читать чем высказываться , и в частности а что такое «полные К-системы с оракулом».

(2) Что касается замены «случайное» на «произвольное», можно конечно, но «произвольное» это все та же алгоритмически не описываемая абстракция.

По поводу интуиции, о ее природе и ее отличие от математического формализма. Опять же рассуждаю интуитивно.

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

(4) А что же в этом случае можно понимать под интуитивностью? Возможно это способ сопоставления не конечно описываемых объектов. Каким образом организовано это сопоставление? Возможно, это то, что называется аналогией. Природа сопоставления через аналогию распространена в физике. Это когда из соответствия частностей делается вывод о соответствии во всем. В свое время было такое направление аналоговые вычислительные машины, там шло сопоставление схем составленных из усилителей и поведения, например, таковой трансмиссии.

Для удобства ссылок вставил нумерацию. Отвечаю по пунктам.

1. По поводу профессионалов. У меня к ним двойственное отношение. Возьмем для примера докторов (см. в связи с этим мой сайт, указанный в моем профиле). Когда мы серьезно болеем, мы обычно идем к докторам. И доктора нас лечат. Но зададимся вопросом: хотят ли и могут ли доктора нас вылечить и сделать здоровыми? Мое мнение, подкрепленное реальной жизнью (моей, моих родных и знакомых), в целом, нет не хотят, нет не могут!

То же самое и с профессионалами, работающими в области оснований математики. У них свои личные проблемы и интересы, как правило, не совпадающие с созданием реальных оснований математики. Они, как и доктора, всего лишь люди.

2. Здесь хотел бы уточнить, что есть две стороны определения объектов, подобных ДЧ. Конструктивная сторона - это значит построить все такие объекты. Хотя бы потенциально. Ясно, что с ДЧ этого сделать мы не можем, а с натуральными числами - можем.

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

3. Не будем про полные К-системы с оракулом. Рассмотрим то же самое на Вашем языке. Представьте себе, что мы смотрим на не описываемый конечно объект через "узкую щель" конечно описываемых объектов. Другими словами, мы можем изучать только его какие-то "конечно опис-е" фрагменты. Мое предложение сводится к тому, что давайте делать любые, удобные для нас, предположения/гипотезы об этом не конечно оп-м объекте. Но так, чтобы они не приводили к противоречию при рассмотрении этого не конечно оп-го объекта через нашу "узкую щель".

4. По поводу интуиции не берусь говорить в общем. А про математическую уже высказывался - основу ее составляет что-то близкое К-системам Это подтверждается и физиологией нервной системы - например, обратите внимание на два вида синапсов - возбуждающие и тормозящие! Это аналог обычных посылок правил и посылок, помеченных служебным знаком $\ominus$.

Так что нервная система - это К-система с миллиардами правил(!), причем эта система правил может настраиваться на реальную жизнь в процессе обучения и/или развития.

[tapos]

Cosinus в сообщении #162183 писал(а):

Вопрос.
И, (если мой тезис верен,) как всё таки доказать несчётность множества на [0..1)

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

[infoliokrat]

tapos в сообщении #289893 писал(а):

Cosinus в сообщении #162183 писал(а):

Вопрос.
И, (если мой тезис верен,) как всё таки доказать несчётность множества на [0..1)

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

Вы что, шутите? Разве сложно их упорядочить в т.н. 1математике (или в двоичной, или в десятиричной, или в шестнадцатиричной или в любой другой - 256 или 256! - факториалоричной? Достаточно только записать их в соответствии с инфолиономерами (которые получаются при записи всех значащих цифр в обратном порядке). Хотите верьте, хотите проверьте. (Кстати, 256! естественно меньше, чем 256 в 256 степени).

Как по мне, то счетность- дело добровольное (выше в постах это уже говорилось), хотите - считайте все счетным, хотите - не считайте...

[Boris_grinevich]

Поддерживаю автора темы. Сколько бы мы ни искали диагональный элемент, мы никогда его не найдём в силу бесконечности десятичной дроби. Более того, проводя подобные рассуждения, можно доказать, что множество всех действительных чисел отрезка счётно, что автор и сделал, повторяя методику Кантора и переходя от одного знака после запятой к всё большему числу. Поскольку результаты доказательств Кантора и автора темы противоречивы, остаётся только заключить, что диагональный метод не корректен. Доказательство несчётности методом вложенных отрезков вообще странновато. Зачем разбивать отрезок на три части если при этом число точек, по мнению автора не уменьшается. Переход же к пределу вообще непонятен. Число точек при таком переходе уменьшается от бесконечного до единицы.
Вообще, вопрос о точках в отрезке, по-моему, некорректен. Точка не является мельчайшей частицей прямой, как, скажем, молекула является мельчайшей частицей вещества, поскольку не обладает таким свойством прямой, как размерность. Образно говоря, точка имеет такое же отношение к прямой, как километровый столб к дороге. Прямая состоит из отрезков. Отрезок имеет длину, чего не имеет точка. Сколько бы вы точек ни взяли, длины вы не получите, так как это новое качество, которое не создаётся количеством. Естественно, что число отрезков, сколь малы бы они не были, в отрезки 0-1 конечно, а в прямой – счётно. Если кому-нибудь кажется, что бесконечное множество создаёт новое качество, пусть попробует ответить на вопрос – множество точек, какой мощности, создаст килограмм.

[Lia]

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