Недоказуемое

[mihaild]

Mikhail_K в сообщении #1567623 писал(а):

Нет ли в этом предложении противоречия?

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

[Mikhail_K]

mihaild в сообщении #1567624 писал(а):

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

Не вижу никакой неточности: ведь ТС постулирует, что "при построении" используются все простые числа. Так что нет никакого "простого множителя, не использовавшегося при построении".

-- 25.10.2022, 01:27 --

Хотя, наверное, это просто вопрос вкуса - где именно получить противоречие.

[mihaild]

Mikhail_K в сообщении #1567592 писал(а):

Потому что это число плюс один, с одной стороны, будет простым

Вот тут неточность. Почему оно обязательно будет простым?

[Skipper]

Потому что это число плюс один, с одной стороны, будет простым (либо содержащим больший простой множитель чем любое из рассмотренных чисел из $A$ ), а с другой стороны, будет больше всех простых.

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

Это как в аналоге, с парадоксом бесконечной гостиницы. Допустим я - владелец гостиницы с бесконечных количеством номеров-комнат. Они пронумерованы натуральными числами, 1,2,3,4, ... и т.д. В какой то момент гостиница оказалась заселённой так, что во всех комнатах живут туристы.
Но тут приехал ещё один турист, и попросил и его заселить в комнату.
Так если количество номеров в гостинице конечное, то я его уже не смогу заселить (аналог рассмотрения числа - которое есть произведение конечного количества простых множителей). Но если их бесконечное количество, то вот пишут, что нет парадокса якобы -

мне надо в гостинице, "попросить подвинуться", всем жильцам. Жильцу 1-й комнаты - собрать свои вещи и переселится во 2-ю комнату, а жильца 2-й - переселится в 3-ю комнату, и так далее когда все жильцы переселятся, то я нового туриста заселю в 1-ю комнату и всем хватит места.

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

"Потому что это число плюс один, с одной стороны, будет простым (либо содержащим больший простой множитель чем любое из рассмотренных чисел из $A$ ), а с другой стороны, будет больше всех простых",

-- Вт окт 25, 2022 05:48:03 --

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

[Mikhail_K]

mihaild в сообщении #1567633 писал(а):

Вот тут неточность. Почему оно обязательно будет простым?

Впрочем да, Вы правы.

Skipper в сообщении #1567639 писал(а):

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

"Потому что это число плюс один, с одной стороны, будет простым (либо содержащим больший простой множитель чем любое из рассмотренных чисел из $A$ ), а с другой стороны, будет больше всех простых",

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

Конечно, эти вот рассуждения про бесконечные гостиницы - это просто научно-популярное изложении теории. Если оно Вам не нравится, то и ладно, в математике никаких бесконечных гостиниц нет.

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

А совсем без бесконечных множеств в математике обойтись сложно. Попробуйте даже самый обычный математический анализ без бесконечных множеств построить.

[Skipper]

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

Попробую построить такое множество. Пусть
1) это множество - подмножество комплексных чисел, и такое что:
2) в него входят все обычные рациональные числа (т.е. если представить плоскость компл.чисел - они на оси расположены),
3) существует алгоритм, который для каждого существующего рационального числа (если подставить его на вход в алгоритм) - выдаёт одну мнимую часть, или какое то множество мнимых частей. Если алгоритм выдал одну мнимую часть, то просуммировали её с входящим рациональным числом - и получили одно комплексное число на выходе,

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

Нельзя определить (проблема остановки), как долго будет работать алгоритм, для каждого входного рационального числа-параметра, и как много подходящих мнимых частей алгоритм выдаст в конечном итоге. А значит, нельзя построить биективное соответствие с множеством $N$ - натуральных чисел, значит, множество наших комплексных чисел, выдаваемых алгоритмом с вычислением этих мнимых частей - имеет мощность больше чем у счётного множества.

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

[mihaild]

Гипотеза континуума ничего не говорит о вычислимых биекциях. Она говорит просто о биекциях.
А вычислить биекцию нельзя даже между множеством натуральных чисел и множеством не останавливающихся программ, чего огород-то с комплексными числами городить?

[hurtsy]

Skipper в сообщении #1567915 писал(а):

Попробую построить такое множество.

Очень хорошее начало для программы.

Skipper в сообщении #1567915 писал(а):

Если это доказать, то мы получили множество с промежуточной мощностью, и для себя опровергли континуум гипотезу?

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

mihaild в сообщении #1567923 писал(а):

А вычислить биекцию нельзя даже между множеством натуральных чисел и множеством не останавливающихся программ

Согласен. А где мне найти хотя бы намек на доказательство невозможности помянутой биекции? Прошу прощения за "занудство".

[mihaild]

hurtsy в сообщении #1568042 писал(а):

А где мне найти хотя бы намек на доказательство невозможности помянутой биекции?

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

[hurtsy]

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

Mikhail_K в сообщении #1567645 писал(а):

А совсем без бесконечных множеств в математике обойтись сложно.

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

[mihaild]

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

[manul91]

mihaild в сообщении #1568082 писал(а):

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

Квантовость дает возможность создать такой вполне конечной физической железки (закрытой коробке) "во плоти" реализирующую невычислимую последовательность (однозначное невычислимое отображение натуральных чисел напр. на {0,1}):
1) На вход подаем натуральное число (и ничего больше!) - номер разряда
2) "Коробка" выдает численное значение этого разряда (напр. 0 или 1) за конечное время
3) "Коробка" соответствует конкретной невычислимой последовательности (последовательность невычислима "почти всегда", с вероятностью = 1, это станет понятным ниже)
4) Последовательность представляемая "коробкой" разумеется детерминирована, т.е. если подаст повторно на вход одно и то же натуральное число, то она выдаст то же самое значение
5) Наподобие машины Тьюринга, коробка требует конечную, но неограниченную память (ленту).

Что в коробке:
1) Тривиальный алгоритм: он проверяет свою память (ленту) если там записано значение для натурального числа - то он его выдает
2) Если значение там не записано супротив натурального номера на входе - то алгоритм подкидывает "квантовую монетку" чтобы получить значение, записывает соответствие нат. номера -> значение в памяти, и выдает значение

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

Без квантовой "абсолютной случайности", такой конечный девайс "в железе" был бы невозможен. Съемулиравать такое на "классическом компьютере"-коробки невозможно.

[Dan B-Yallay]

manul91 в сообщении #1568101 писал(а):

Без квантовой "абсолютной случайности", такой конечный девайс "в железе" был бы невозможен. Съемулиравать такое на "классическом компьютере"-коробки невозможно.

А чем квантовая "абсолютная случайность" отличается от аппаратного генератора истинно случайных чисел?

Я не в теме, просто интересно.

[manul91]

Dan B-Yallay в сообщении #1568102 писал(а):

А чем квантовая "абсолютная случайность" отличается от аппаратного генератора истинно случайных чисел?

Без квантовой "абсолютной случайности" нет аппаратного генератора "истинно случайных чисел", в лучшем случае только псевдослучайных (т.е. вычислимых). Откуда классическому аппаратному генератору (замкнутого физически = Тьюринг машины без "случайном" входом извне) брать "истинно случайных чисел"? Я тоже "не особо в теме", выдумал это походу в связи с моей недавнешней "проблемы" которой мы с вами обсуждали и тут как раз подвернулось.

[mihaild]

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