верность аксиомы выбора не очевидна

svetik5623190

natunchik

Красиво, однако!

svetik5623190

Красиво, однако!
Согласен. Спасибо. Мне тоже понравилось это с педагогической точки зрения. Но красота - дело субъективное. Ты лучше по сути скажи: есть тут лажа или нет?
Просто все, кого я ни спрашивал, говорят или "что-то тут не так, но что - не знаю" или "сорее всего, всё чисто. но надо подумать".
Вот я и выложил на форум для широкого обсуждения.

FieryRush

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

svetik5623190

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

svetik5623190

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

Lene81

Все-таки есть в этом рассуждении... некоторая червоточина. Ведь как используют аксиому выбора "на практике"? Например, во фразе "возьмем epsilon >0..."? Эта фраза, как нетрудно понять из приведенных выше определений не фиксирует ни конечно определяемого, ни конечно неопределяемого числа, но лишь некоторое множество, так? Более того, множество несчетное, т.е. в нем есть как те, так и другие числа. И указав _случайное_ число из этого множества можно получить как конечно определяемое, так и не определяемое конечно число. Более того, не требуется никакого алгоритма, предполагающего завершения через конечное или счетное число шагов.

natunchik

Насчёт введения в заблуждение — вначале мне показалось, что всё чётко, но потом я подумал и теперь не так уверен.
Проблема в том, что твоё множество "конечно определяемых чисел" тоже тот ещё подарок. Например, оно не перечислимо. Задача "построить алгоритм, перебирающий все конечно-определяемые числа", кажется, нерешаема, из-за halting problem. Более того, когда некто говорит, вот, типа, зацени какое у меня клёвое конечно-определяемое число есть, ты никак не можешь проверить, что он не гонит, что это действительно число.
То есть поинт аргумента от этого не исчезает, но несколько затупляется. Ну как бы да, дополнение его до континуума непусто, но ни одного элемента из него мы привести не можем. Но при этом "существование" самого множества тоже выглядит достаточно сомнительным, типа существовать-то оно существует, да только явно не в том же смысле, в каком существуют натуральные числа.
То есть смотри, есть невычислимые числа, типа чайтиновской константы, что ли (вероятность найти останавливающуюся машину Тьюринга, кажется которая в общем-то существует на тех же правах, что и твоё множество (но в него не входит). Поэтому можно аргументировать: если ты позволяешь себе говорить об этом множестве, приводить его в качестве примера, то почему я не могу привести в качестве примера её?

natunchik

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

svetik5623190

Ведь как используют аксиому выбора "на практике"? Например, во фразе "возьмем epsilon >0..."?
Нет. На практике аксиому выбора в явном виде используют редко. Но зато на практике удобно пользоваться логически эквивалентными аксиоме выбора утверждениями:
Теорма Хаусдорфа: В (частично) упорядоченном множестве всякая цепь содержится в некоторой максимальной цепи.
Теорема Цермело: Всякое множество можно вполне упорядочить.
Лемма Цорна: Если в (частично) упорядоченном множестве каждая цепь имеет верхнюю грань, то каждый элемент подчинён некоторому максимальному элементу.

Sergey79

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

svetik5623190

Например, во фразе "возьмем epsilon >0..."? Эта фраза, как нетрудно понять из приведенных выше определений не фиксирует ни конечно определяемого, ни конечно неопределяемого числа, но лишь некоторое множество, так?
Так.
Более того, множество несчетное, т.е. в нем есть как те, так и другие числа.
Да.
И указав _случайное_ число из этого множества можно получить как конечно определяемое, так и не определяемое конечно число.
Каким образом указав? В этом-то и вся соль аксиомы выбора.

svetik5623190

То есть смотри, есть невычислимые числа, типа чайтиновской константы, что ли (вероятность найти останавливающуюся машину Тьюринга, кажется которая в общем-то существует на тех же правах, что и твоё множество (но в него не входит). Поэтому можно аргументировать: если ты позволяешь себе говорить об этом множестве, приводить его в качестве примера, то почему я не могу привести в качестве примера её?
Я в логике полный чайник. Что такое машина Тьюринга - знаю. Про вычислимые числа и функции, про перечислимые множества - не знаю ничего.
Если видишь лажу в моём примере - укажи на неё пожалуйста. Если получится - ещё и такими словами, чтобы я понял :)
О себе: закончил мехмат, кафедра ТФФА. В логике - профан. При написании методички использовался творческий метод Литлвуда, последстивия очевидны :)

Lene81

Каким образом указав? В этом-то и вся соль аксиомы выбора.
Недетерминистическим способом, ака генератором случайных чисел. Он, как я полагаю, не реализуется никакой машиной Тьюринга.

svetik5623190

Более того, когда некто говорит, вот, типа, зацени какое у меня клёвое конечно-определяемое число есть, ты никак не можешь проверить, что он не гонит, что это действительно число.
Не никак, а никак за конечное число шагов, если число произвольное.
Ну и что, что мы не можем за конечное число шагов сказать, является ли то или иное число конечно определяемым или конечно неопределяемым? За бесконечное-то сможем. Перебор по всему счётному множеству строк символов. На самом деле, даже задача о том, определяет ли та или инача строка символов какое-то число - уже жутко сложная (остановится ли программа) и вроде как не то P, не то NP полная. Но кого эти алгоритмические сложности волнуют? Я просто пользуюсь принципом исключенного третьего: данная строка символов либо определяет однозначно число, либо нет, а третьего не дано.
То есть для любого числа (в принципе) существут ответ на вопрос: принадлежит ли это число множеству конечно неопределяемых чисел. А раз так, то множество задано корректно. Другое дело, что в некоторых случаях ответить на вопрос о принадлежности того или иного элемента множеству легко, а в некоторых - нет.
Главное, что множество не пусто - доказано выше рассуждениями про счётность и несчётность. А раз так, то из него хочется выбрать элемент. А как это сделать - не очевидно. То есть верность аксиомы выбора не очевидна. Ради этой демонстрации и построен пример.

svetik5623190

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

svetik5623190

Недетерминистическим способом, ака генератором случайных чисел.
Что это такое? Физический объект, то есть например такая железяка с лампами и катушками индуктивности, питающаяся электричеством от сети? Какое отношение эта железяка имеет к строчке символов? Она их печатает на бумаге? Если её два раза подряд попросить вычислить 125ю цифру какого-нибудь конечно неопределяемого числа - она даст один и тот же результат?
И последнее: допустим, что машина может работать бесконечное число часов. Где гарантия, что те цифры, которые она напечатает за конечное число часов, действительно принадлежат конечно неопределяемому числу?
Генератор случайных чисел - может и бывает. Но вот генератор случайных конечно неопределяемых чисел я не понимаю как сделать с помощью паяльника и радиодеталей.

Sergey79

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

Lene81

Если её два раза подряд попросить вычислить 125ю цифру какого-нибудь конечно неопределяемого числа - она даст один и тот же результат?
Нет конечно, не обязательно! На то оно и неопределяемое, чтобы нельзя было указать _всех_ его цифр, в противном случае оно — определяемое.

svetik5623190

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

Sergey79

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

natunchik

Чайтиновская константа вот: http://en.wikipedia.org/wiki/Chaitin_constant
Простыми словами: ты используешь двойные стандарты (хорошо, что не принуждение к миру, лол!). Числа, входящие в твоё множество, ты отбираешь по одному стандарту: если есть программа на С++, которая генерирует n-тую цифру за конечное время. Само же множество этому стандарту не соответствует: ты не можешь написать программу на С++, генерирующую элементы этого множества (программы, очевидно) по порядку (причём так, чтобы она гарантированно перебирала именно это множество, а не какое-нибудь его подмножество).
Это в принципе должно быть понятно из нерешаемости проблемы останова, и, кстати, одно из её доказательств выглядит очень похожим образом: предполагается, что ты такую программу построил, тогда ты можешь сделать из неё программу, генерирующую n-тую цифру n-того числа (за конечное время, естественно а потом другую, возвращающую вместо этой цифры какую-нибудь другую (её плюс 1 по модулю 10, например). Тогда эта программа должна входить в твоё множество на каком-то конечном месте, но этого не может быть, потому что она на этом месте возвращает не ту цифру, которую она возвращает!
То есть с одной стороны ты говоришь, дескать, давайте смотреть именно на хорошо определённые числа, а не на какую-то невычислимую фигню, с другой — твоё множество не является "хорошо определённым" в этом же смысле.
(я не уверен, но может быть можно вообще прямо так сказать: если поставить в соответствие каждому счёному множеству вещественное число, то число, соответствующее множеству хорошо определённых чисел не будет хорошо определённым).
Причём учитывай, что эта проблема с определённостью, это не нечто умозрительное, встречающееся только в стрёмных штуках типа чайтиновской константы. Смотри, я пишу прогу, выводящую первое чётное число, не являющееся суммой двух простых, простым перебором. На С++ получится длинная и стрёмная прога, на лиспе или питоне — короткая и приятная в силу наличия встроенной длинной арифметики, ну и вот, то, что я написал — это хорошо определённое число или нет? Если прога остановится, то да, очевидно. Если нет, то нет. А остановится она или нет, неизвестно (пока). Более того, таких штук крайне много (включая и гораздо менее осмысленные почитай статью про http://en.wikipedia.org/wiki/Busy_Beaver (тоже невычислимая функция для которой неизвестно значение уже для n=5, потому что есть порядка 40 машин тьюринга с 5 состояниями и двоичным алфавитом, про которые непонятно, останавливаются ли они или нет.

svetik5623190

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

Lene81

Если так, то твоя машина вообще никакого числа не определяет, если она каждый раз выдаёт в качестве его 125й цифры разные символы.
Неправда твоя. Ведь условие типа epsilon>0 обязывает выдавать мою машину однозначно только первый бит (знака, если мыслить в терминах машинного представления чисел). Остальные-то могут быть произвольные. Но в каждый момент времени (если угодно, в любой наперед заданный раз) она выдаст _какое-то_ число, которое меня, впрочем устроит полностью.
Если сделать философское отступление, то мне кажется, что математики прямо-таки настаивают на детерминистичности, которая во многих их рассуждениях, в общем-то, не требуется. Отсюда и логические трудности с аксиомой выбора, в частности. Впрочем, сразу оговорюсь, что это мое частное, любительское, мнение, которое, возможно, не стоит дальнейшего обсуждения.

svetik5623190

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

natunchik

За бесконечное-то сможем
Лол, кто-то из великих в похожей ситуации что-то говорил про то, что скромнее надо быть, а не примеривать на себя одежды Господа.
Видишь ли, если ты разрешаешь себе проверять что-нибудь за бесконечное количество шагов, то у тебя такой п-дец настаёт, что вопрос об осмысленности аксиомы выбора как-то даже странно поднимать.
Например, тогда ты можешь таки чётко и дерзко сказать, противоречива ли ZF.

FieryRush

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

svetik5623190

По ссылкам сходить к сожалению не могу: нет инета.
ты используешь двойные стандарты (хорошо, что не принуждение к миру, лол!). Числа, входящие в твоё множество, ты отбираешь по одному стандарту: если есть программа на С++, которая генерирует n-тую цифру за конечное время. Само же множество этому стандарту не соответствует: ты не можешь написать программу на С++, генерирующую элементы этого множества (программы, очевидно) по порядку (причём так, чтобы она гарантированно перебирала именно это множество, а не какое-нибудь его подмножество).
Не вижу в этом ничего плохого. Кроме того, как я уже отмечал, возможность вполне упорядочить произвольное множество эквивалентна аксиоме выбора. Так что неудивительно, что перебирать элементы этого множества по порядку затруднительно.

Sergey79

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

svetik5623190

Неправда твоя. Ведь условие типа epsilon>0 обязывает выдавать мою машину однозначно только первый бит (знака, если мыслить в терминах машинного представления чисел). Остальные-то могут быть произвольные. Но в каждый момент времени (если угодно, в любой наперед заданный раз) она выдаст _какое-то_ число, которое меня, впрочем устроит полностью.
Минуточку. Что значит "выбрать элемент из множества"? Это значит предоставить доступ ко всем свойствам этого элемента, отделить его от других. Если речь идёт о числе, то всё зависит от того, какую модель вещественного числа мы выбираем: если бесконечные эм-ичные дроби, то я хочу иметь способ узнать любую цифру в разложении этого числа; если последовательности рациональных чисел, то я хочу иметь способ узнать какой захочу член последовательности, и т.д. для других моделей вещественных чисел.
А если твоя машина мне говорит то одно, то другое, то как я могу ею пользоваться? Как я могу послать её по почте коллеге и сказать - смотри какое классное число она делает, пользуйся этим числом наздоровье?

svetik5623190

Видишь ли, если ты разрешаешь себе проверять что-нибудь за бесконечное количество шагов, то у тебя такой п-дец настаёт, что вопрос об осмысленности аксиомы выбора как-то даже странно поднимать.
Например, тогда ты можешь таки чётко и дерзко сказать, противоречива ли ZF.
Да я не проверяю за бесконечное время. Наверное я зря такие слова употребил.
Я просто пользуюсь принципом исключённого третьего: каждое число либо конечно неопределяемое, либо конечно определяемое. Множество конечно неопределяемых чисел не пусто. Только и всего.

Sergey79

Вообше я полностью согласен с
это в точности вопрос про курицу и яйцо. В данной реализации: "может ли абсолютный выбиратель выбрать принципиально невыбираемое". Каждый сам решает какими определениями пользоваться.

svetik5623190

И чего. Еще раз. Если ты пытаешься найти какие-то алгоритмы, конечные построения, ты идешь по пути конструктивизма. Если ты не хочешь по нему идти, то принимаешь аксиому выбора как данность (это же аксиома в конце концов).
Я ничего не пытаюсь. Я не занимаюсь сейчас ни философией, ни математической логикой, ти функаном :) Я просто построил пример для детей, показывающий, что аксиома выбора - штука очевидная только для конечных множеств. Поэтому вопрос о том, верить в неё для множеств вообще или нет - вопрос не праздный. Вот и всё. Ну и заметил между делом, что в аксиому выбора принято (подавляющим большинством математиков) сейчас верить, потому что если не верить, то хрен докажешь теорему Хана-Банаха, а без этой теоремы капец функану и всему, что на функан опирается.
А потом я попросил форум указать мне на ошибки в построении примера, если они есть :)

Sergey79

Можно вообще начать с первой аксиомы: "аксиомы существуют". Это кстати совершенно не очевидная аксиома.
Можно сказать "я не согласен" и жить в таком мире где нет аксиом. А можно жить в мире с аксиомами.

Sergey79

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

natunchik

Не вижу в этом ничего плохого.
Ну, я ж с самого начала сказал: если ты считаешь, что у тебя есть право предъявить такое вот множество (в виде словесного описания, с заранее известной невозможностью продвинуться дальше то не очень понятно, почему я в ответ не могу предъявить чайтиновскую константу, как пример элемента множества "не хорошо определённых чисел". Она существует, она ему принадлежит, а то, что я не могу ни одного её бита назвать — так это фигня, "за бесконечное время-то смогу".
Понимаешь?
возможность вполне упорядочить произвольное множество эквивалентна аксиоме выбора.
Это ж про континуум, нет? Счётные множества потому и называются счётными, что их элементы можно пересчитывать. И проблема вовсе не в упорядочивании как таковом: сортируешь свои программы лексикографически и всё, вот тебе порядок, а в том, что про подавляющее большинство программ (серьёзно, именно про подавляющее большинство!) ты не можешь сказать, принадлежат ли они твоему множеству.

svetik5623190

это в точности вопрос про курицу и яйцо.
Что первично - курица или яйцо? Не спрашивай, а кушай.
Я ж и не спорю. Я ж и сам верю в аксиому выбора - потому что как же я иначе без функана. Просто подчёркиваю, что аксиома выбора - это не очевидная банальщина.

svetik5623190

В статье явно показано что множество не пусто.
В примере. Какая это, блин, статья, ты чего? :) Пример для школьников :)
Для меня "очевидно", что в нем есть элемент, а значит, его можно выбрать.
Можно выбрать? А как?
рассмотрим множество, состоящее из элементов, которые человек не может указать явно.
Аккуратнее с терминами. Может быть, это такой большой класс, что он даже и не множество.

svetik5623190

нет. Ты показал, что для твоего понимания "очевидности" есть неочевидный пример. У каждого свое понимание очевидности.
Ну может хоть у кого-то такое же понимание как у меня? Тогда я ему подкинул пищу для размышлений. ;)

svetik5623190

Ну, я ж с самого начала сказал: если ты считаешь, что у тебя есть право предъявить такое вот множество (в виде словесного описания, с заранее известной невозможностью продвинуться дальше то не очень понятно, почему я в ответ не могу предъявить чайтиновскую константу, как пример элемента множества "не хорошо определённых чисел". Она существует, она ему принадлежит, а то, что я не могу ни одного её бита назвать — так это фигня, "за бесконечное время-то смогу".
Понимаешь?
Мужики.
Что-то разговор не туда идёт. :)
Я просто придумал пример для детей и говорю вам - нет ли в нём косяка? :) Я что, говорю, что это единственно возможный пример? Или что самый лучший? Или что он всё ставит на свои места в математической логике? Это - просто пример для школьников :)

svetik5623190

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

natunchik

Я просто пользуюсь принципом исключённого третьего: каждое число либо конечно неопределяемое, либо конечно определяемое. Множество конечно неопределяемых чисел не пусто. Только и всего.

Ох. Вот очень зря ты им пользуешься.
Очень было бы неплохо, если бы ты потратил денёк-другой и прочитал хорошую книжку про Гёделевскую теорему о неполноте (а заодно и про теорему о полноте, которую часто незаслуженно забывают).
Потому что насколько я могу судить, там внутри, в основах, такая банька с пауками, что вопрос об обоснованности аксиомы выбора кажется детским лепетом, так что если ты хочешь именно о нём говорить, использовать такие "очевидные" вещи нельзя ни в коем случае.

svetik5623190

Я ж и не обсуждаю вопрос об обоснованности аксиомы выбора. Я показываю, что её верность не является очевидной.
А про то, что есть математики, не приемлющие принцип исключённого третьего, я знаю. Что и говорить - математики относятся к математическим логикам примерно так, как физики - к математикам :)
Кстати, а теорем Гёделя о неполноте, кажется, вообще две.

svetik5623190

там внутри, в основах, такая банька с пауками,
Спору нет. Я и не говорю, что мой пример - весь айсберг. Просто часть вершины. Но школьники-то вообще о существовании айсберга не в курсе, потому и надо показать им хоть что-то. Будет классно, если в показываемом не будет очевидных ляпов.
Вот я и спрашиваю - есть ли тут у меня ляпы?

natunchik

Хотя бы потому, что предъявить - значит описать с помощью конечного числа символов.
lol, u totally miss the point.
Вопрос в том, что значит "описать с помощью конечного числа символов". Когда ты требуешь от меня предъявить чайтиновскую константу, ты пользуешься одним определением, когда ты сам предъявляешь своё доказательство, ты пользуешься совершенно другим.
Вот, я даю тебе описание чайтиновской константы:
1) Фиксируем некий язык программирования, например, C++.
2) Перебираем все корректные (компилирующиеся) программы в лексикографическом порядке.
3) Считаем сумму: для каждой останавливающейся программы длины n добавляем к сумме 2**-n. Там есть некая техническая тонкость, связанная с тем, что никакая корректная программа не может являться префиксом другой корректной программы (для С++ без макросов это верно поэтому ряд сходится и сходится к числу от 0 до 1.
Есть описание? Если у тебя нет сомнений в том, что для каждой программы действительно существует однозначный ответ, останавливается она или нет, то и это число однозначно определено. Определено ровно в том же смысле, в каком определено твоё множество. Однако я могу доказать, что это число в твоё множество не входит, следовательно, оно является примером элемента его дополнения до R.
Конечно, я не могу его конструктивно сконструировать (и могу это доказать, в чём весь и понт). Но и ты своё множество не можешь конструктивно сконструировать, что как бы совершенно не мешает тебе его использовать в доказательстве того, что неконструктивные множества плохи, лол. (Прочитай, пожалуйста, предыдущее предложение два или три раза, или сколько потребуется, пока ты его не поймёшь).
Я не понимаю твоей реакции. Если у тебя вопрос состоит в том, можно ли твоё доказательство использовать для пропаганды среди нерюхающих физиков — да, конечно можно, если совесть позволяет. Если ты интересуешься, как оно смотрится для рюхающих чуваков (к коим я скромно себя причисляю то хреново смотрится, извини. На первый взгляд красивое, но потом обнаруживаются вот такие стрёмные вещи.

svetik5623190

Если ты интересуешься, как оно смотрится для рюхающих чуваков
Да.
то хреново смотрится, извини.
Спасибо за потраченное время, я ещё подумаю. Щас пойду покурю и может вернусь что-нить напишу, правда спать уже хочется сильно.

natunchik

Так покажи им теорему Банаха-Тарского!11одинодин
Она совершенно очевидна, доступна любому школьнику и корректна в любом смысле. В английской википедии прекрасный чёткий и детальный план доказательства, опущены только совсем уж несущественные технические детали.

natunchik

То есть я вот что хочу сказать!
Формально рассуждение корректно. Действительно, если принять твои определения, то получается множество (и очень большое из которого нельзя конструктивно выбрать ни одного элемента, а аксиома выбора это позволяет сделать.
Но эстетически — очень плохо выглядит. Потому что пытаясь показать, что аксиома выбора стрёмная, ты используешь несравнимо более стрёмное неперечислимое множество. Аксиому выбора принимают многие математики, ни один математик не принимает предположение о том, что halting problem можно игнорировать (точнее, Хофстадтер вроде бы исследовал surreal numbers — те, которые получаются, если в Гёделевском рассуждении добавить в качестве новой аксиомы не истинность, а ложность недоказуемого утверждения, но это как бы чистые игры разума, даже ему самому не очень интересные, и в интернетах я про это ничего не нашёл).

svetik5623190

Есть описание? Если у тебя нет сомнений в том, что для каждой программы действительно существует однозначный ответ, останавливается она или нет, то и это число однозначно определено. Определено ровно в том же смысле, в каком определено твоё множество. Однако я могу доказать, что это число в твоё множество не входит, следовательно, оно является примером элемента его дополнения до R.
По мягкому определению эта константа - конечно определяемое число, потому что действительно предъявлено его однозначное описание. С другой стороны, непонятно, как вычислить энную цифру этого числа, но это уже другой вопрос.
По жёсткому определнию хз. Не уверен, что можно на С++ написать прогу, которая бы вычисляла энную цифру этой константы.

svetik5623190

Так покажи им теорему Банаха-Тарского!11одинодин
Она совершенно очевидна, доступна любому школьнику и корректна в любом смысле. В английской википедии прекрасный чёткий и детальный план доказательства, опущены только совсем уж несущественные технические детали.
Спасибо за ссылку!

svetik5623190

используешь несравнимо более стрёмное неперечислимое множество
Что такое неперечислимое множество?
Какое стрёмное множество я использую?
Извини, если это глупые вопросы.

natunchik

Не уверен, что можно на С++ написать прогу, которая бы вычисляла энную цифру этой константы.
Её НЕЛЬЗЯ написать, именно поэтому константа не принадлежит множеству конечно определяемых чисел и может использоваться как representative element его дополнения.
Никакое "мягкое определение" ты использовать не можешь, потому что иначе возникают парадоксы с "минимальным числом, не описываемым менее чем девятью словами" (в этом описании восемь слов, что оно описывает?)
"Что такое неперечислимое множество?" - это множество, для которого невозможно предоставить процедуру его построения. Точно так же твоё твоё определение "не конечно определяемого числа" (их принято называть невычислимыми числами) говорит о числах, для которого невозможно предоставить процедуру построения.
Случаи множества вычислимых чисел (самого неперечислимого, о чём и речь) и константы Чайтина интересны тем, что можно доказать, что они оба не(пере/вы)числимы, то есть ты не просто не знаешь процедуры построения, а её не существует вовсе. Перечитай один из комментов выше, я там набросал доказательство неперечислимости твоего множества где-то.
Стрёмное - множество вычислимых чисел. Довольно часто приходится иметь дело с ситуацией, когда само множество перечислимо, а его дополнение - нет, неприятно, конечно, но что поделаешь (пример что-то в голову не приходит, извини). Ситуация, когда и само множество, и его дополнение неперечислимы (типа этой вызывает сильные сомнения относительно того, можно ли вообще в таком случае говорить о "существовании" в хоть сколько-нибудь интересном смысле.

natunchik

А самого-то главного я не написал.
Аксиома выбора позволяет неконструктивно строить некоторые множества (то есть говорить об их существовании невзирая на отсутствие (и даже невозможность!) предъявить способ построения). Но от неё можно отказаться и продолжать получать какие-то интересные результаты.
Вычислимость и невычислимость — это гораздо более глубокие вещи, по сути лежащие в основе представления о том, что такое математика. Что такое доказательство? Последовательность утверждений, корректность которых (то есть соответствие формальным правилам вывода одного утверждения из другого) можно алгоритмически (то есть вычислимо) проверить. От требования вычислимости отказаться нельзя.

lenmas

Весь функан к чёрту пойдёт.
Навряд ли. Леммы Цорна и аксиомы выбора возникают, когда начинаются вопросы типа: " а давайте-ка построим базис в любом линейном пространстве!" или "а рассмотрим-ка гильбертово пространство произвольной размерности" или, что еще хуже, "построим разрывную аддитивную функцию" :grin:
Все реальные пространства, используемые в практике, сепарабельные, тут можно строить и без всякий зауми, взяв на вооружение только принцип математической индукции (обычной, а не трансфинитной! :grin: )

Sergey79

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

Sergey79

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

svetik5623190

Спасибо большое за столь развёрнутые ответы. Буду думать. По ходу, придётся всё-таки погрузиться немного в не(вы/пере)числимость. Какие книги посоветуешь?

asseevdm

Я хоть не такой рюх, как , но логику сдавал...
1. По теме очень рекомендую
Н.К. Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов.
http://www.mccme.ru/free-books/
Часть 1. Начала теории множеств.
Часть 2. Языки и исчисления.
Часть 3. Вычислимые функции.
2.
По самому примеру. Во-первых, неопределяемые числа — вещь классная. Она показывает, что "существует" и "можно привести" — совершенно не одно и то же. Так что все написанное тобой рассуждение скорей показывает этот факт, чем неочевидность аксиомы.
Если есть непустое множество А, существует множество B, содержащее один элемент множества А. Всё. Ты же нарочно подменяешь "существует", на "можно привести пример".
Для аксиомы выбора лучший пример неочевидности — трюк с яблоками. В районе того же mccme.ru можно найти методичку для школьников, где этот трюк описан.
Для демонстрации различий "существует" и "можно привести пример" также очень хорошо подходит следующая задача: существует ли алгоритм, который по числу n возвращает 1, если в десятичной записи числа Пи есть по крайней мере n подряд идущих девяток, и возвращает 0 в противном случае.

svetik5623190

Если есть непустое множество А, существует множество B, содержащее один элемент множества А. Всё.
Да? а какой это элемент?
Ты же нарочно подменяешь "существует", на "можно привести пример".
Я не подменяю понятия, я рассуждаю так: Если можно явно указать пальцем на объект, то он уж точно существует. Если нельзя - то уже не очевидно. что он существует. А теперь приведём пример ситуации, в которой указать пальцем на объект затруднительно. И именно из-за этой затруднительности мы и привлекаем аксиому выбора для того чтобы обосновать существование такого объекта. Объект - это способ выбора элемента из непустого множества в данном случае.

svetik5623190

Для демонстрации различий "существует" и "можно привести пример" также очень хорошо подходит следующая задача: существует ли алгоритм, который по числу n возвращает 1, если в десятичной записи числа Пи есть по крайней мере n подряд идущих девяток, и возвращает 0 в противном случае.
А в чём тут соль?

svetik5623190

1. По теме очень рекомендую
 Н.К. Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов.
http://www.mccme.ru/free-books/
Часть 1. Начала теории множеств.
Часть 2. Языки и исчисления.
 Часть 3. Вычислимые функции.
Спасибо! Первую из этих книг я пролистывал, о существовании остальных даже не знал.

asseevdm

Да, такой алгоритм существует.
Возможно, тот, который всегда возвращает 0. Может тот, который для n<2 дает 1, а для n>=2 — ноль.
А может тот, у которого пороговое значение для n не 2, а какое-то другое натуральное число. Ну или наконец тот, который всегда возвращает 1. В общем, один из этого счетного набора точно является искомым. Какой именно — сказать затруднительно, но этого в задаче не требуется.

asseevdm

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

kalliopa

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

asseevdm

физика ограничивается рациональными числами и лишь из соображений математического удобства пользуется более широкими классами чисел
Для удобства, буду считать число Пи равным трем (С) :grin:
Это я к тому, что ни от Pi, ни от e никуды физики не денутся.

svetik5623190

Возможно, тот, который всегда возвращает 0. Может тот, который для n<2 дает 1, а для n>=2 — ноль.
А может тот, у которого пороговое значение для n не 2, а какое-то другое натуральное число. Ну или наконец тот, который всегда возвращает 1. В общем, один из этого счетного набора точно является искомым. Какой именно — сказать затруднительно, но этого в задаче не требуется.
Так и не понял, в чём тут соль, то есть почему этот алгоритм имеет отношение к теме разговора.
 
Способ построения твоего множества, из которого ты хочешь выбрать одноэлементоное подмножество неочевиден. То есть, на множество описываемых чисел тоже нельзя "ткнуть пальцем". Поэтому странно на его основе строить пример другой неочивдности.

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

svetik5623190

Это я к тому, что ни от Pi, ни от e никуды физики не денутся.
Оба эти числа - конечно определяемые.

svetik5623190

Поэтому мне кажется странным считать, что твои конечно неопределимые числа имеют хоть какое-то отношение к физической реальности. Если для них аксиома выбора не очевидна или даже не работает — это проблемы неопределимых чисел, а не функана и тем более не физики.
Минуточку. Ещё раз уточню пропагандируемую мной в этом примере идеологию.
1. Физики пользуются в своих построениях математическими теоремами как фактами. Представить современную физику, например, без аппарата функана - невозможно.
2. Многие математические теоремы не доказать, если рассматривать только лишь рациональные или даже только лишь конечно определяемые числа, и вообще - если рассматривать лишь то, что можно пощупать, а существование того, что пощупать нельзя - отрицать или не принимать во внимание.
3. Чтобы работать с иррациональными и конечно неопределяемыми числами, а так же с другими объектами более сложной природы, математикам приходится принимать некоторые предположения (аксиомы) о свойствах этих объектов
4. Физикам, использующим математику, неплохо бы знать, что некоторые из этих предположений (аксиом) лишь кажутся очевидными (для не сложных объектов а на самом (в общем случае) деле таковыми не являются.
То же самое, но более кратко: физики сейчас (хотят они того или нет) на кажом шагу для познания физической реальности используют инструменты, к физической реальности отношения (быть может) не имеющие. Неплохо бы при этом знать, что инструменты эти имеют свою сложную внутреннюю структуру и не так примитивны, как может казаться на первый взгляд.

asseevdm

Ну да. Тут афтор вообще сказал, что рациональных достаточно

asseevdm

Соль, с моей точки зрения, в том, что эта задача хорошо иллюстрирует разницу в "существует" И "можно привести". Алгоритм существует, а можно ли его привести — неочевидно.
Пример хороший. Ошибок ты можешь еще наделать, когда придашь математическую строгость опеределениям определимости. Твой соус — аксиома выбора — мне не нравится.

svetik5623190

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

asseevdm

Млин, а! написал(а по моему мнению, ересь. Я на это ответил сатирой. Ему (ей) ответил. С тобой я тут не спорю. Я и сам знаю, что рациональных чисел маловато будет. Не надо мне это доказывать.

svetik5623190

Ошибок ты можешь еще наделать, когда придашь математическую строгость опеределениям определимости.
Я не буду этого делать по двум причинам:
1. Я не специалист в логике
2. Чем больше строгости, тем (как правило) меньше доступности для школьников.
Твой соус — аксиома выбора — мне не нравится.
Согласен, не самый лучший соус. Надо видимо делать так:
1. Описываем множество конечно неопределяемых чисел, показываем, что оно не пусто.
2. Замечаем, что множество обладает интересными свойствами:
во-первых, затруднительно указать хоть один его элемент.
Во-вторых, по аксиоме выбора можно образовать одноэлементное подмножество этого множества. Но аксиома выбора не даёт нам указание, какое это подмножество и как его образовать, она лишь утверждает, что одноэлементное подмножество существует. Этим подчёркивается то, что аксиома выбора не даёт конкретики, а говорит лишь о существовании.

svetik5623190

Млин, а! написал(а по моему мнению, ересь.
Эта ересь очень распространена среди физиков. Правда.
Я на это ответил сатирой. Ему (ей) ответил. С тобой я тут не спорю. Я и сам знаю, что рациональных чисел маловато будет. Не надо мне это доказывать.
Ок-ок, не горячись, я понял :)

kalliopa

> Представить современную физику, например, без аппарата функана - невозможно.
прекрасно возможно. Ты имеешь в виду, что есть отдельные области физики (хотя тебе, как математику, они лучше всего известны где функан позарез как нужен. А я хочу сказать, что:
а) большинство разделов физики (как по номенклатуре, так и по количеству занятых исследователей, объему грантов и так далее) не используют функан или используют на уровне квантов для студентов 4 курса физфака или мехмата - вроде бы используют, но настолько неспецифично, что сами не знают об этом;
б) физика в идеале базируется не на математике, а на практике (хотя на самом деле всякое бывает). Если функан в применении к физике будет работать на практике, а математики докажут, что он внутренне противоречив - физики от функана не откажутся. Ну, если не найдут столь же эффективного, но более "математичного" рецепта.

svetik5623190

Если функан в применении к физике будет работать на практике,
При построении первой ядерной бомбы в США люди численно (приближённо) вычисляли континуальные интегралы.
В GPS-навигаторах используются поправки, возникающие из ОТО, а в формуле лоренцевского сокращения есть значок квадратного корня, делающий иногда из рациональных чисел не рациональные.
Язык самой модной сейчас физической теории - теории струн - это функциональный анализ.
Мне кажется, куда уж дальше продолжать.

svetik5623190

Я имею в виду, что нет сомнений в том, что абстракции вроде иррациональных чисел и функана УЖЕ вовсю работают на практике.

kalliopa

> При построении первой ядерной бомбы в США люди численно (приближённо) вычисляли континуальные интегралы.
Сомневаюсь. Слышал, что это поветрие в физику привнес Фейнман, хотя в истории физики не силен. Как физик, пользовавшийся методом континуальных интегралов в своих задачах и ботавший Фейнмана и Кляйнерта, смею утверждать, что для применения этого метода можно вовсе не иметь представления о функане. Кстати, пример могу привести: производные дробных размерностей (fractional calculus, не знаю русского термина) и метод реплик (replica trick) начали применяться в физике задолго до того, как были строго обоснованы математически (не уверен, что их вообще обосновали на настоящий момент). Работают - значит, можно применять.
> а в формуле лоренцевского сокращения есть значок квадратного корня, делающий иногда из рациональных чисел не рациональные.
Мог бы проще сказать: формула для диагонали квадрата содержит квадратный корень. И что? Скорость, равно как и длина диагонали, продолжают быть рациональными (строго говоря, в философском смысле они могут быть и иррациональными, но в эксперименте мы можем получить только рациональные значения. По самой сути любого измерения. Получить в результате измерения иррациональное число в принципе невозможно).
> Язык самой модной сейчас физической теории - теории струн - это функциональный анализ.
Ну я же говорил: ты математик, тебе кажется, что вся современная физика или хотя бы современная теоретическая физика сводится к струнам или к разным теориям полей. На самом деле, эти области составляют лишь часть - и вряд ли бОльшую - физики.

Sergey79

Кстати, пример могу привести: производные дробных размерностей (fractional calculus, не знаю русского термина) и метод реплик (replica trick) начали применяться в физике задолго до того, как были строго обоснованы математически
абсолютно верно подмечено: зачастую физики пользуются заведомо необоснованными математическими приемами. Лишь бы под ответ (известный на практике или предполгагаемый исходя из физического смысла) подгонялось стабильно. Например та же дельта-функция.
Это происходит потому, что
- в математике теории должны быть "абсолютно" верными
- в физике теории заведомо верны лишь в ограниченной области
потому физиков совсен не шокирует, если функан окажется не "абсолютно" верным - лишь бы он был верен в ограниченной области для физических задач. Для физиков подобная ситуация как с теоремой выбора абсолютно естественна.

amarchenkov

Я не школьник, но поняла текст методички (не весь) только с третьего прочтения, и то благодаря комментариям дал , так же нам рассказывали на матане в универе. По-моему, идеальное для школьников объяснение.
Второе определение (про C++) вообще не подходит, привёл пример конечно неопределяемого (с помощью C++) числа ("чайтиновской константы"). Кстати, к первому определению она не подходит, потому что описывается символами "чайтиновская константа". Школьники вряд ли придумают такой пример, в этом и обман.
То, что школьникам даётся определение через C++, вообще не комментирую.

natunchik

Лишь бы под ответ (известный на практике или предполгагаемый исходя из физического смысла) подгонялось стабильно.
А вот объясни-ка мне тогда одну вещь, пожалуйста.
Я могу всё путать, если так, то скажи, тоже.
Можно рассмотреть КМ-модель с двумя потенциальными ямами и частицей. У неё есть базисные решения двух типов, когда частица спокойно сидит в одной яме, и когда осциллирует между ними. Я правильно понимаю, что если бы решения второго типа были отброшены как не имеющие физического смысла (потенциальный барьер же! то мы бы сейчас не могли вести эту высокоинтеллектуальную беседу, потому что транзисторы никогда не были бы изобретены? Подчеркну, это не ЭПР-пары, в которых теория делает вполне однозначное предсказание, это абсолютно рядовой случай, в других похожих задачах (частица, набигающая на барьер, например) левые решения отбрасываются абсолютно спокойно.

svetik5623190

Я не школьник, но поняла текст методички (не весь) только с третьего прочтения, и то благодаря комментариям и .
Два определения конечно неопределяемых чисел не эквивалентны.
Определение "нельзя описать конечным числом символов" более понятно дал , так же нам рассказывали на матане в универе. По-моему, идеальное для школьников объяснение.
Второе определение (про C++) вообще не подходит, привёл пример конечно неопределяемого (с помощью C++) числа ("чайтиновской константы"). Кстати, к первому определению она не подходит, потому что описывается символами "чайтиновская константа". Школьники вряд ли придумают такой пример, в этом и обман.
То, что школьникам даётся определение через C++, вообще не комментирую.
1. Защищать свой педагогический подход не буду. Отмечу лишь, что школьники реально продвинутые, С++ знают на уровне простых функций, а обсуждаемый пример входит в необязательную часть курса, на экзамене не спрашивался, и даже на лекциях был затронут очень вскользь, мол, аксиома выбора - штука не очевидная если множества состоят из многих элементов, кто хочет подробностей - смотрите пособие: там написано.
2. дал определение немного других чисел. И вообще, для меня является открытым вопрос о том, является ли множеством введённый "[класс] элементов, которые человек не может указать явно [конечным числом символов]". Да которые может, если честно, тоже - если не фиксирован набор символов.
3. Два определения, конечно, не эквивалентны, но каждое представляет некоторый интерес. Любое число, являющееся конечно определяемым по жёсткому определению, является таковым и по мягкому. Такое ощущение, что есть числа, конечно определяемые в мягком, но не в жёстком смысле. Похоже, что такова как раз чайтиновская константа.
Имхо запись "Наименьшее натуральное число, которое нельзя записать с помощью 1000 знаков" не задаёт конечно определяемое число в смысле мягкого определения, потому что эта комбинация символов видимо не задаёт число однозначно: не то что каждую, даже последнюю цифру этого числа имхо нельзя никаким способом (с использованием программ на компе или любым другим, с бесконечным временем ожидания ответа или нет) выудить из этой записи. Можно было бы попробовать устроить перебор по всем конечным записям, однозначно определяющим натуральные числа, а потом выбрать среди этих чисел наименьшее. Но вот как сравнивать с остальными числами число, задаваемое записью "Наименьшее натуральное число, которое нельзя записать с помощью 1000 знаков", не понятно. Поэтому я и думаю, что эта запись вообще никакого числа однозначно не задаёт. Впрочем, мутный это вопрос. Если более компетентные товарищи просветят - буду рад :)
А чайтиновская константа (для какого-то конкретного языка программирования) не является конечно определяемым числом в смысле более жёсткого определения, потому что (если верить ) нельзя написать прогу, которая бы за конечное число шагов вычисляла энную цифру этого числа.
Вопрос о том, является ли чайтиновская константа конечно определяемым числом в смысле мягкого определения, мне кажется сейчас ясным: является. Будем искать энную цифру этого числа в двоичной записи. Для этого надо запустить на выполнение энную в лексикографическом порядке программу и подождать, пока она остановится или ждать ответа вечно и так его и не получить, но ни на секунду не терять надежды в том, что этот ответ в принципе получаем. Гарантии, что мы-таки найдём эту цифру за конечное время, нет. НО ответ на этот вопрос однозначен: либо остановится, либо нет. Поэтому чайтиновская константа задана однозначно, и, следовательно, является конечно определяемым числом по мягкому определению.
Вот :)
Жду конструктивных ответов :)

svetik5623190

Школьники вряд ли придумают такой пример, в этом и обман.
Обмана нет, потому что я нигде не говорю, что определения эквивалентны.

491593

Язык самой модной сейчас физической теории - теории струн - это функциональный анализ
хм.. ну это ОЧЕНЬ сильно притянутое за уши утверждение..
Это кто тебе сказал, если не секрет.. или где ты это прочитал.

svetik5623190

Моё личное некомпетентное мнение :grin:
Просто несколько конструкций (примеры уже не приведу - выветрились про которые спецы говорили "вот, это из области теории струн!" использовали в той или иной мере функан или по крйней мере слова, зародившиеся в функане. Сам я в теории струн понимаю мало, мой багаж в ней - это Брайан Грин "Элегантная вселенная" не до конца.
Да ладно, это - не ключевой момент в этом треде. Может по основному сабжу что скажешь?

amarchenkov

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

Так же фиксирован: "символы, известные человечеству". :grin: Всё равно их не более чем счётно.
Повторю, что меня эта вещь очаровала именно в простой и понятной (пусть и не самой строгой) формулировке.
3.
Имхо запись "Наименьшее натуральное число, которое нельзя записать с помощью 1000 знаков"

Это определение самопротиворечиво, в нём меньше 1000 знаков. Я настаиваю, что русские буквы понятны человечеству.
А чайтиновская константа (для какого-то конкретного языкапрограммирования) не является конечно определяемым числом в смыслеболее жёсткого определения

Ну вот.
Поэтому жёсткое определение плохое. В этом обман школьников. ;) В том, что говорите "такое число нельзя предъявить", а они верят, потому что не знают таких жутких примеров, как константа Чайтина.
Такое ощущение, что есть числа, конечно определяемые в мягком, но не вжёстком смысле. Похоже, что такова как раз чайтиновская константа.

Да, об этом я и говорила. Т.е. "словесное" определение лучше, чем "сиплюсплюсное".

svetik5623190

Так же фиксирован: "символы, известные человечеству". Всё равно их не более чем счётно.

Что-что? Ты утверждаешь, что "[класс] элементов, которые человек не может указать явно [конечным числом символов]" не только является множеством, но и не более, чем счётным множеством?.. Можно ли попросить тебя предъявить доказательство? ;)
Это определение самопротиворечиво, в нём меньше 1000 знаков.
Я в курсе. Потому его и привёл. В смысле, я не знаю, как с ним быть. Один из возможных видимых мной выходов такой: будем считать, что эта запись вообще никакого числа однозначно не определеяет. Но я не уверен, что так можно делать, хотелось бы услышать мнение компетентных товарищей. Кроме того, сама процедура выяснения по записи, задаёт ли она какое-то число и задаёт ли она его при этом однозначно, представляется туманной. Спасает меня то, что даже если процедура туманна, то каждая конкретная запись либо определеяет число однозначно, либо нет, и третьего не дано. Ситуация очень напоминает чайтиновскую константу, именно поэтому мне её и привёл, обо рюх, как и сам признаёт :)
Поэтому жёсткое определение плохое. В этом обман школьников. В том, что говорите "такое число нельзя предъявить", а они верят, потому что не знают таких жутких примеров, как константа Чайтина.

Ещё раз. Обмана нет, потому что я не говорю, что более мягкий вариант и более жёсткий вариант задают одно и то же понятие.
Да, об этом я и говорила. Т.е. "словесное" определение лучше, чем "сиплюсплюсное".
Каждое из этих определений в чём-то лучше, в чём-то хуже. Поясни плиз, что имеешь в виду.
ЗЫ: Никогда не обсуждал с Гулькой математику, но прям есть ощущение, как будто она сейчас с нми: тот же смайлик, стиль общения похожий даже...

asseevdm

Лавсан говорит о дополнении, о множестве тех чисел, которые человечество указать может. Набор "символов, известных человечеству" для этого фиксирован. Например, таблицей unicode :)
2. С этим определением быть как с парадоксом лжеца. "Я лгу" - не утверждение. "Минимальное число, не описываемое 9 словами" — не число (нет алгоритма выписать его цифры).
3. В методичке с педагогической точки зрения вынос мозга действительно есть. И по формализму, и по стилю, и по типографии. Так что набор символов unicode — это ирония на C++.
4. Гулька — персональный тренер Лавсан по флуду.

svetik5623190

1. Лавсан говорит о дополнении, о множестве тех чисел, которые человечество указать может. Набор "символов, известных человечеству" для этого фиксирован. Например, таблицей unicode
А я-то подумал, что она говорит об одной из действительно интересных вещей:
1. Класс , то есть класс всех тех элементов (=предметов, =вещей, =объектов которые человечество не может описать с помощью заданного конечного набора символов.
2. Класс всех тех элементов, которые человечество может описать с помощью символов (любых).
Я не знаю даже, является ли хоть один из этих классов множеством. Первый как-то очень похож на класс Рассела, а второй - на класс всех классов. Слово "класс" я употребляю в общепринятом смысле - то есть так, как оно вводится, например, в добавлении к книге Джона Келли "Общая топология".
2. С этим определением быть как с парадоксом лжеца. "Я лгу" - не утверждение. "Минимальное число, не описываемое 9 словами" — не число (нет алгоритма выписать его цифры).
Не понимаю. Поясни и обоснуй, пожалуйста. Это - как раз моя точка зрения (см. по треду выше будет здорово, если ты подведёшь под неё какую-то базу.
3. В методичке с педагогической точки зрения вынос мозга действительно есть. И по формализму, и по стилю, и по типографии. Так что набор символов unicode — это ирония на C++.
Согласен :D Материал сырой. Ссылку надо заменить на явное указание процедуры Кантора и т.п.

asseevdm

Придет Лавсан, сама напишет, чего она имеет в виду.
Про минимальное число. Надо определиться, что значит, "описать". Самое логичное "можно описать" = "существует алгоритм, дающий все это число" (мы тут о натуральных числах, число цифр конечно). Если предположить, что такой алгоритм есть, получаем парадокс (то бишь противоречие). Значит, предположение не верно, такого алгоритма нет.
Кроме того, все это "описание" — всего навсего переформулировка парадокса лжеца, разрешение которого как раз в том, что "я лгу" — не утверждение.

svetik5623190

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

asseevdm

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

svetik5623190

А алгоритм-то где?

asseevdm

Еще раз.
"Я лгу". Если это истина, то это ложь. Если это ложь, то это истина. Парадокс. Самое нормальное разрешение этого парадокса, признать, что "я лгу" — не утверждение и не может быть истинно или ложно. Например, "слон" — не истина и не ложь, а просто тварь с хоботом.
"Минимальное натуральное число, которое нельзя описать за 9 слов" — если его нельзя описать, мы его только что описали. Если его можно описать, то противоречие с тем, что его нельзя описать. Тот же парадокс лжеца, только переформулированный. Поэтому самое правильное разрешение этого парадокса, признать, что "минимальное натуральное число, которое нельзя описать за 9 слов" — не описание числа. Чтобы более глубоко разобраться в этом парадоксе, следует уточнить, что значит "можно описать".
Пример более строгого определения описания.
Описание числа — это алгоритм его записи. Тогда "минимальное число, которое нельзя описать..." — это не алгоритм ни в каком понимании. Если бы это был алгоритм, то тогда бы можно было бы выписать это число. А это противоречит тому, что число описать за 9 слов нельзя. Значит, это не алгоритм.

svetik5623190

Спасибо за подробность. Когда говоришь о таких вещах, она, имхо, необходима.
Теперь становится понятна разница между жёстким и мягким определением конечно определяемых чисел, которые вводятся в первом посте. Переформулирую их с учётом произошедшей дискуссии, но не меняя (надеюсь) самой сути понятий.
Определение 1. Число называется (мягко) конечно определяемым, если существует алгоритм (записанный с помощью конечного числа символов из кодовой таблицы который (за конечное или бесконечное время) позволяет записать это число в какой-нибудь эм-ичной системе счисления, для определённости - в десятичной.
То есть существует записанная конечным числом символов инструкция, которая говорит, что надо делать, чтобы получить число. Причём исполнение инструкции может быть быстрым, медленным, трудным, лёгким, более того - вопрос о том, вечно ли придётся трудиться над исполнением инструкции или не вечно может быть очень сложным и т.п. Главное, чтобы исполнение инструкции не было гарантировано невозможным. То есть чтобы из текста инструкции однозначно следовало, какова каждая цифра нашего числа. При этом допускается, что процедура ответа на вопрос "ну и какова же эта цифра" может оказаться долгой или трудной или требующей бесконечного времени ожидания. Если же даже такой инструкции в принципе нет - всё, привет, число не мягко конечно определяемое.
Мощность множества мягко конечно определяемых числел - счётная.
Определение 2. Число называется (жёстко) конечно определяемым, если для любого натурального эн существует записанный с помощью конечного числа символов алгоритм, который вычисляет за конечное время энную цифру этого числа в записи в позиционной системе счисления (например, в десятичной).
Определение 2. Число называется (жёстко) конечно определяемым, если существует записанный с помощью конечного числа символов алгоритм, который для любого натурального эн вычисляет за конечное время энную цифру этого числа в записи в позиционной системе счисления (например, в десятичной).
Мощность множества жёстко конечно определяемых числел - счётная.
Интересное положение занимает следующее
Определение 3. Число называется (совсем жёстко) конечно определяемым, если существует записанный с помощью конечного числа символов алгоритм, который вычисляет за конечное время это число полностью (все цифры).
Мощность множества совсем жёстко конечно определяемых чисел - тоже счётная. Более того, это множество объединение по всем натуральным d совсем жёстко конечно определяемых в d-ичной системе счисления чисел совпадает с [math] $\mathbb{Q}$[/math].
Видно, что все совсем жёстко определяемые числа являются рациональными. В совсем жёстко конечно определяемом числе должно быть конечное число цифр, значит оно рациональное.
Обратное тоже верно: если число рационально, то оно представляет собой дробь z/n, записать эту дробь в n-ичной системы счисления за конечное число шагов проблем никаких.
 

491593

Может по основному сабжу что скажешь?
ну, имхо, сабж даже в науке интересен относительно малому числу людей..

svetik5623190

То есть тебе посрать на аксиому выбора вообще, а уж на то, как её лучше продемонстрировать детям - и подавно посрать?

asseevdm

Определение 1 — фигня какая-то.
Нет такого понятия, что число записывается за бесконечное время.
Можно его ввести по аналогии с пределом: любая цифра в некоторой момент времени будет выписана. Но тогда число подпадает под идею определения 2.
Определение 2 должно быть такое: для любого натурального n алгоритм выдаст n-ую цифру (за конечное время). У твоем определении ошибка, потому что алгоритм должен существовать для всего числа в целом. У тебя же для каждой n-цифры свой алгоритм. Очевидно, что для каждой n-ой цифры такой алгоритм будет (либо тот, который дает 1, либо тот, который дает 2, либо и так далее, один из 10 искомый).
Определение 3 неинтересное, из него следует, что число выписывается конечным числом символов. А это (в зависимости от допустимых символов) даже не Q, а все десятичные дроби.
В общем, пересдача тебе :)

svetik5623190

Имхо ты не понял написанного мной. Щас попробую пояснить получше.

svetik5623190

Определение 1 — фигня какая-то.
Нет такого понятия, что число записывается за бесконечное время.
А как же константа Чайтина? У нас нет уверенности, что не то что всё число, а даже что какая-то его цифра будет получена за конечное время. Потому что нельзя сказать за конечное время, что такая-то программа остановится за конечное время.
Определение 2 должно быть такое: для любого натурального n алгоритм выдаст n-ую цифру (за конечное время). У твоем определении ошибка, потому что алгоритм должен существовать для всего числа в целом. У тебя же для каждой n-цифры свой алгоритм. Очевидно, что для каждой n-ой цифры такой алгоритм будет (либо тот, который дает 1, либо тот, который дает 2, либо и так далее, один из 10 искомый).
Точно, ты прав. Вопрос не в том, существует ли конечный алгоритм для каждой цифры, а существует ли конечный алгоритм для всех цифр разом. Согласен, спасибо: тут я облажался. Поправляю определение.
Определение 3 неинтересное, из него следует, что число выписывается конечным числом символов. А это (в зависимости от допустимых символов) даже не Q, а все десятичные дроби.
И тут ты прав.
В общем, вышло так, что это я тебя плохо понял, а не ты меня. Я сейчас внёс в пост соответствующие поправки. Спасибо.

natunchik

Извините, что вмешиваюсь...
Dage! Или кто ещё из околоквантовых физиков!
Ответьте, пожалуйста, на мой вопрос!
А вот объясни-ка мне тогда одну вещь, пожалуйста.
Я могу всё путать, если так, то скажи, тоже.
Можно рассмотреть КМ-модель с двумя потенциальными ямами и частицей. У неё есть базисные решения двух типов, когда частица спокойно сидит в одной яме, и когда осциллирует между ними. Я правильно понимаю, что если бы решения второго типа были отброшены как не имеющие физического смысла (потенциальный барьер же! то мы бы сейчас не могли вести эту высокоинтеллектуальную беседу, потому что транзисторы никогда не были бы изобретены? Подчеркну, это не ЭПР-пары, в которых теория делает вполне однозначное предсказание, это абсолютно рядовой случай, в других похожих задачах (частица, набигающая на барьер, например) левые решения отбрасываются абсолютно спокойно.

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

asseevdm

Стало быть, ты хочешь определить "описание" в таком смысле, чтобы константа Чайтина была "описана". Ок, я сначала не понял, к чему вообще определение 1, теперь понял.
Все равно совершенно непонятно, что значит, что алгоритм что-то записывает за бесконечное время.
Если посмотреть строго, то под бесконечностью почти всегда понимается предел. Иногда другие строгие математические конструкции. Но никогда бесконечность не является начальным понятием. Так что определи, что такое "результат за бесконечное время".
Да, незачем писать про алгоритмы, что они конечнозаписаны. Может, в каком-то неклассическом смысле рассматривают какие-то другие алгоритмы (я не знаю но алгоритмы всегда сами конечны.

vovatroff

Можно рассмотреть КМ-модель с двумя потенциальными ямами и частицей. У неё есть базисные решения двух типов, когда частица спокойно сидит в одной яме, и когда осциллирует между ними. Я правильно понимаю, что если бы решения второго типа были отброшены как не имеющие физического смысла (потенциальный барьер же! то мы бы сейчас не могли вести эту высокоинтеллектуальную беседу, потому что транзисторы никогда не были бы изобретены?
А я (тоже извиняюсь, что вмешиваюсь) немножко не понял сам вопрос.
В задачке с двуямным потенциалом вид стационарных решений зависит
от энергии частицы.
Если она ниже вершины барьера - то они локализованы (более-менее)
в той или иной яме. Если энергия выше барьера - то делокализованы.
Они вместе образуют полную систему, у них у всех есть физический смысл,
и отбрасывать их вообще-то не полагается. В чем вопрос?
А транзистор требует еще и приложения внешнего поля, разности потенциалов.
Качественно - это все равно как прибавить линейную функцию (-E*x) к графику
двуямного потенциала c вершиной барьера в нуле. Одно дно станет выше, другое
ниже, высота барьера изменится.

natunchik

Да, незачем писать про алгоритмы, что они конечнозаписаны. Может, в каком-то неклассическом смысле рассматривают какие-то другие алгоритмы (я не знаю но алгоритмы всегда сами конечны.
Э нет, я, например, умею решать проблему останова бесконечным алгоритмом. Ну, в котором для каждой программы записано, останавливается она или нет. Тогда за О(2**(длина изучаемой программы я нахожу ответ в своей бесконечной таблице ответов прямым перебором (если мы о машине Тьюринга говорим). Причём, насколько я понимаю, это довольно корректно, то, что я только что сказал. Поэтому указывать конечность алгоритма нужно.

natunchik

Если она ниже вершины барьера - то они локализованы (более-менее)
в той или иной яме.

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

asseevdm

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

svetik5623190

Да нет же! Есть и осциллирующие между ямами!
Гм... А частота осцилляций от чего зависеть будет?..

svetik5623190

если взять сеттинг того эксперимента
Что такое сеттинг? Многократное повторение?

tatra

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

svetik5623190

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

Sergey79

Да нет же! Есть и осциллирующие между ямами!
я просто отвлекся от треда. То, что ты описал не очень поощрялось до конца 19 века. А после того как у Максвелла а затем и у отцов-квантовиков подобные фичи прокатили, это наоборот вошло в моду. Напомню, что как Калуца ввел в физике лишние измерения, так они сейчас везде процветают в 90% теорий. Но до сих пор за почти 80 лет их не открыли экспериментально. Но это и подобные вещи не противоречат физическому смылу.
На твоем примере: уравнения дают необычные решения. А затем подбирается физический смысл к необычным решениям. Вот так получились транзисторы. А нефизический смысл это всякие плохие асимптотики, расходимости и т.п. Т.е. если бы мы вместо тунелирования обнаружили что частица приобретает бесконечную массу на ровном месте - это было бы нефизично.

svetik5623190

Аксиома выбора не утверждает, что ее применение к одному и тому же семейству множеств даст одно и то же результирующее множество.
Аксиома выбора не утверждает, что ее применение к одному и тому же семейству множеств даст хоть одно множество. То есть аксиома выбора НЕ ДАЁТ множество, она лишь утверждает, что множество существует. В этом вся фишка аксиомы выбора: она говорит, что есть на Земле такая девушка, что если на ней женишься, то всю жизнь проживёшь счастливо. Но она даже не намекает на то, как такую девушку найти. Не уверен, что пример корректен, но идея, думаю, ясна: аксиома выбора по сути своей неконструктивна.
Поэтому число, выбранное из конечно-неопределяемых чисел согласно акс. выбора, не становится конечно-определяемым. Все ок.
Нет такого вполне себе определённого элемента, который бы аксиома выбора выбирала из более чем одноэлементного множества. Аксиома выбора лишь утверждает, что его можно выбрать, то есть она разрешает считать верным утверждение о том, что пытаться искать девушку своей мечты не бесполезно: способ найти её существует. Она даёт надежду на счастье, но не говорит, как его искать. И вот как раз так и получается, что современная математика (а вместе с ней и физика) без этой самой надежды на счастье уже никак не может обойтись.
Очень поэтичные метафоры получились :)

asseevdm

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

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

natunchik

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

svetik5623190

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

tatra

То есть аксиома выбора НЕ ДАЁТ множество, она лишь утверждает, что множество существует
это утверждение стилистически как-то плохо звучит. Существует - это как раз дает (хотя и не конструктивно).
А то как-то стремно работать с базисом Шаудера, который существует, но мне его не дали.

lenmas

А то как-то стремно работать с базисом Шаудера, который существует, но мне его не дали.
В каждом конкретном случае его легко предъявить. Ну а если хочешь произвольные пространства рассматривать, как математики, тогда уж извини...

tatra

Если можешь, выделяй плиз при редактировании поста (опечатки не в счёт) вновь дописанное другим шрифтом, а то я, например, запутываюсь когда старые посты редактируют.
Я его правил, до того, как ты ответил, думал что ты еще не прочитал. И смысла не менял, а уточнял. Прошу прощения.

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

lenmas

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

svetik5623190

Правильно ли я понял?
Определение 1. Назовем число конечно определенным, если существует алгоритм, который выдаст каждую его цифру за конечное время. При этом алгоритм умеет атомарно определять, остановится ли программа или нет.
Другими словами, ты хочешь расширить машину Тьюринга (или любой другой вычислитель) операцией определения, остановится программа или нет, и вот для этого расширенного вычислителя составлять алгоритм.
Не-не-не-не-не, Дэвид Блейн! :)
Я говорю, что корректная программа для машины Тьюринга, или алгоритм, или словесное описание, в общем - конечная строка символов (как текст) является сама по себе однозначно декодируемой записью сразу всех цифр числа. Например, в записанном на бумажке методе Ньютона, позволяюшем найти корень из двух с любой заданной точностью, заключена польностью вся информация о том, каково число "корень из двух".
Если такая однозначно определяющая конечная строка символов существует, то я называю число конечно-определяемым в мягком смысле.
А уж какой способ декодирования - то есть выуживания из текста этой информации - применяется, и с какими трудностями сопряжён этот способ - это уж другое дело. Главное чтоб информация в тексте была зашита, и вполне конкретная. А если её нельзя за конечное время извлечь - не беда.
Главное, чтоб для любого икс одно из двух утверждений "икс равно нашему числу" и "икс не равно нашему числу" было верно. А уж механизм проверки по данному икс, какое верно, а какое неверно, может быть сложным.
Не уверен, что это так уж нужно совсем строго формализовывать. Не уверен, что смогу формализовать удачно. Но попробую.
Твоя формализация
Определение 1. Назовем число конечно определенным, если существует алгоритм, который выдаст каждую его цифру за конечное время. При этом алгоритм умеет атомарно определять, остановится ли программа или нет.
Другими словами, ты хочешь расширить машину Тьюринга (или любой другой вычислитель) операцией определения, остановится программа или нет, и вот для этого расширенного вычислителя составлять алгоритм.

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

svetik5623190

А то как-то стремно работать с базисом Шаудера, который существует, но мне его не дали.
Базис Шаудера как раз тем и хорош, что он, в отличие от базиса Гамеля, всегда даётся явно.
В вещественном гильбертовом (=линейном бесконечномерном полном относительно порождённой скалярным произведением нормы сепарабельном) пространстве базис Шаудера - это набор единичных ортов. Вполне конкретная вещь. Если гильбертово пространство реализовано как пространство функций, то эти орты - это вполне конкретные функции.
А вот базис Гамеля в гильбертовом пространстве хотя и существует (следствие аксиомы выбора но как-то прилично описать его элементы не удаётся.

tatra

И вообще Аксиома выбора нужна только для бесконечных последовательностей множеств. Выбор элемента из единственного множества проблем создавать не должен. И возможность такого выбора должна быть в Аксиоматике теории множеств. (Эта статья из вики, такой аксиомы не содержит, но в ней встречаются кванторы \exists и \forall, которые уже подразумевают возможность неконструктивно выбирать. Более подробно наверно есть в уже упомянутой книге Верещагина.).
Так что у тебя претензии скорее не к аксиоме выбора, а к аксиоматике теории множеств.

Sergey79

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

Я честно не понимаю, в чем затыка? Физический смысл это не консерватизм, а иррационально обузданная интуиция. Ты хочешь, чтобы я формализовал когда и как применяется физический смысл? Это по определению не формализуемо в такой степени.
Критерй Бора: "достаточно ли безумна новая теория?"
Паскаль: "Если уравнение красиво, значит оно верно"
На примере тунелирования мы видим красивое и в меру безумное решение. Потому физический смысл не восстает.

svetik5623190

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

svetik5623190

Он под конструктивностью понимает "без аксиомы выбора", а не как обычно без закона исключенного третьего.
Я сразу предупредил, что в логике я чайник и что при написании методички использовался творческий метод Литлвуда со всеми вытекающими последствиями типа путаницы в терминах. Этот метод состоит в том, чтобы, приходя в новую для себя область, не читать много умных книг, а попробовать всё придумать самому. Тогда ты либо всё придумаешь сам, либо поймёшь, в чём имеются трудности, и тебе потом будет легче читать умные книги, поскольку будет ясно, над какой проблемой люди бьются.

svetik5623190

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

svetik5623190

Физики! Ответьте плиз на мой вопрос:

asseevdm

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

svetik5623190

В общем, я понял, что ты хочешь. Не знаю, является такое расширенное понимание алгоритма (или описания) интересным. Либо является (тогда оно наверняка уже изучено либо не является (непонятно, почему).
Ок. Если появятся мысли по теме - велком. Я буду иногда посматривать в этот тред. Спасибо за обсуждение!

svetik5623190

Вот ещё пример ситуации, когда информация о структуре множества помогает выбрать элемент даже из очень мощного множества. Пример построен моим другом Вовой Филимоновым, по образованию он радиофизик, я его просил читать некоторые куски моей методички и мы многое с ним обсуждали.
Обозначим натуральный ряд буквой N. Его мощность - счётная.
Обозначим множество всех подмножеств N символом P(N). Его мощность - континуум.
Множество всех подмножеств этого множества обозначим P(P(N. Его мощность - гиперконтинуум.
Множество всех подмножеств множества P(P(N обозначим P(P(P(N. Его мощность, насколько мне известно, специального названия не имеет.
Ну и так далее.
Если принять аксиому выбора и континуум-гипотезу, то мощность ЛЮБОГО множества (не буду здесь это доказывать, ладно? Доказательство знаю.) равна мощности одного из этих множеств либо конечна.
Из конечного подмножества множества N выбрать элемент проблем нет: берём наименьший элемент в естественном порядке натуральных чисел.
Из множества N выберем элемент 1.
Из множества P(N) выберем элемент {1}.
Из множества P(P(N выберем элемент {{1}}.
Из множества P(P(P(N выберем элемент {{{1}}}.
И так далее.
То есть как бы получается, что из "эталонного" множества любой возможной в природе мощности выбрать элемент проблемы нет.
А вот как выбрать элемент из произвольного множества, не понятно. Но как-то выбрать можно - по аксиоме выбора способ выбора существует.

vizier

Отличное обсуждение, очень понравилось )
Позвольте мне внести толику иррациональности в обсуждение, пользуясь методом Литлвуда ;)
Где-то на второй странице я пришел к мысли, которую сформулировал Григ, а именно, что определение "конечно неопределяемого" множества эквивалентно утверждению "я лгу". С точки зрения формальной логики оно бессмысленно. Однако оно допустимо грамматически. Грамматика в известной степени есть отражение способа мышления. Того самого мышления которое создало и математику. Поэтому нет ничего удивительного в том, что складывая, как вам кажется, два и два, вы получаете пять. Вам _кажется_ что вы четко задали правила игры, дали внутренне непротиворечивое утверждение. На деле это fuzzy logic. Еще раз, утверждение "я лгу" демонстрирует что ваш разум играет с вами и вовсе не по придуманными вами правилами. С другой стороны, это значит что всегда есть пространство для выбора и совершенствования инструментов анализа.
По-поводу замечания . В задаче про двухъямный потенциал стационарное решение есть линейная комбинация решений для изолированных ям. Если ямы находятся на конечном расстоянии, оба линейных коэффициента не нулевые, т.е. частица делокализована. Осцилляции наблюдаются в нестационарной задаче. Так что транзисторы у нас были бы. Но в целом мысль ясна. Моя точка зрения все так же иррациональна: прятаться за физическим смыслом или нет - вопрос интуиции. Но решает здесь именно ваш внутренний fuzzy logic, а не только математика. Не надо полагать, что математика придумала все абстракции, а физикам осталось складывать два и два. Примеров того, что физика принесла новое в математику достаточно.

svetik5623190

Судя по тому, что у тебя мало постов на этом форуме, ты можешь не знать о слоях. В настройках "my home" надо поставить "show all posts with garbage". В этом треде на данный момент 200 сообщений, из них довольно большая часть - в оффтопном и мусорном слое, которые не видны, если не включить их показ в настройках.
Если просматривать эту тему из интернета, не логинясь на форуме, то тоже не увидишь эти "кулуарные" части дискуссии.

svetik5623190

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

kalliopa

Ты почему-то рассматриваешь физиков как единый механизм. Хотя каждый отдельный физик пробует разные приемы. Один шарит в таких-то разделах математики, другой в таких-то, третий изобретает велосипед, четвертый краем уха слышал о матметоде и хочет его применить, не вдаваясь в детали. Кстати, последних большинство, по-моему. Отдельный физик может попробовать применить что-то. Например, если обнаружит, что аксиома выбора в каком-то случае "проваливается" (относительно здравого смысла он может попробовать ради интереса довести физическое решение до этого "провала" и посмотреть, кто был прав: аксиома или здравый смысл.
Это все даже не на уровне людей, а, скорее, на уровне лабораторий, научных микрошкол и даже школ. Успешные приемы привлекают внимание других лабораторий, неуспешные плавно лишаются своих создателей. Поэтому в целом в масштабе всей физики строгая и абсолютная применимость математических аксиом и модусов не важна, хотя в каждый момент каждая группа может на основании своих математических представлений пробовать применять тот или иной прием, выбирая, разумеется, из более логически обоснованных.

svetik5623190

Мне кажется, ты не прав. Даже (стандартный пример) в обобщенных функцияхсеквенциальный подход эквивалентен обычному (топологическому как доказывается при предположении аксиомы выбора.
В топологических пространствах секвенциальные замкнутость и непрерывность (если память меня не подводит) эквивалентны обычным при довольно слабых предположениях (нет учебника под рукой чтобы посмотреть): требуется вроде бы аксиома отделимости Т1 (о том, что одноточечное множество замкнуто; эквивалентная формулировка: для любой пары точек существует окрестность каждой из точек пары, не содержащая другую точку) и первая аксиома счётности (о том, что существует счётная база топологии в каждой точке). А может быть, достаточно и вовсе одной только Т1, не помню.
Так что на практике аксиома выбора не так уж и нужна в случае обобщённых функций, наверное.
Так что ситуация скорее всего такая же, как и с конструктивизмом (статья Колмогорова) - что с аксиомой выбора, что без нее - все одно и то же, лишь бы не рассматривать придуманные объекты типа множества всех множеств.
Кстати аксиома отделимости Т0 носит имя Колмогорова: в топологическом пространстве из двух точек по крайней мере одна обладает окрестностью, не содержащей другую точку. Так что может он и ругал всякие хитрые пространства за бесполезность, но ему можно: он сам изучал их свойства ;)
Колмогоров вообще не был (есть мнение) супер-специалист конкретно в области обобщённых функций. В учебнике Колмогоров-Фомин топология на пространстве D вообще определена не правильно. См. бо этом замечание размером в абзац в статье Богачёв В.И., Смолянов О.Г., "`Обобщённые функции, полученные регуляризацией неинтегрируемых функций"', Докл. РАН, 2008, т. 419, №6, стр 1-4.
Приведу ещё кусочек моей дипломной работы, чтобы ясность по поводу того, какая топология на D правильная, стала полной.
[math]Поскольку книга А.Н. Колмогорова и С.В. Фомина \cite{KF} до сих пор по праву является стандартным учебником по функциональному анализу, будет не лишним указать на одну не слишком известную неточность, имеющуюся в ней.[/math]
[math]Для простоты записи рассмотрим одномерный случай (в многомерном случае ситуация идейно та же). На прямой на данный момент считается общепринятым определять $$\mathcal{D}(\mathbb{R}^1)=\injlim\limits_n \ \projlim\limits_k\ C^k ([-n,n]$$ в то время как в \cite{KF} авторами указывается для $\mathcal{D}$ более слабая топология, а именно, в \cite{KF} полагается $$\mathcal{D}(\mathbb{R}^1)=\projlim\limits_k\ \injlim\limits_n\ C^k ([-n,n]).$$ По запасу элементов и свойствам сходимости последовательностей эти два определения пространства $\mathcal{D}$ не отличаются.[/math]
Так что у меня такое стойкое убеждение, что в реальности не встречаются такие странные примеры, как ты приводишь, а все это только от излишнего бурбакизма.
Во-первых, даже если ты и прав, это не уменьшает педагогическую ценность примера. Согласись, хоть раз одним глазком надо взглянуть на то, чего не бывает, особенно в школьные годы ;)
Во-вторых, мне лично мой опыт кажется недостаточным для того, чтобы утверждать такие вещи, что мол на практике то-то и то-то не встречается. Маловато ещё (лично у меня) этой практики.

Sergey79

Такое ощущение, что ты или тред прочитал не полностью, или не видел то, что написано в мусорном и оффтопном слоях.
НУ строго говоря аксакалы форума знают о такой настройке как количество постов на страницу. Согласно легенде у Ер-Суб это число равно 99. Что вполне соответствует двухстраничному треду.

vizier

Судя по тому, что у тебя мало постов на этом форуме, ты можешь не знать о слоях. В настройках "my home" надо поставить "show all posts with garbage". В этом треде на данный момент 200 сообщений, из них довольно большая часть - в оффтопном и мусорном слое, которые не видны, если не включить их показ в настройках.
Про слои, Ваня, я знаю и тред прочел весь ; )
Все эти переформулировки с алгоритмами, как мне кажется, не в силах устранить парадоксальность определения "конечно неопределяемых" чисел. Переформулировав утверждение "я лгу" ты не избавишься от парадоксальности.
Вообще, что находится в фундаменте математики? Есть ли глобальное обоснование всех этих абстракций? По большому счету это обоснование состоит в том же, в чем состоит обоснование закона сохранения энергии. Они работают. Чтобы понять работает ли что-то его нужно попробовать применить для чего-нибудь. Если его нельзя применить, это вещь в себе, бесполезная для любых постороений. Возможно я ошибаюсь относительно конечно неопределяемых чисел, но тогда приведи пример для чего их можно использовать.
зы
Возможно с аксиомой выбора есть более удачный пример, демонстрирующий ее нетривиальность. тоже было бы интересно услышать.
зыы
и если не сложно, возрази на мой предыдущий пост. мне кажется я сказал не глупую вещь. во всяком случае я думаю, что математика не так уж монолитна, как многоие склонны думать. Она не есть что-то отдельное от человека и потому идеальное.

svetik5623190

НУ строго говоря аксакалы форума знают о такой настройке как количество постов на страницу. Согласно легенде у Ер-Суб это число равно 99.
Ерсуб - не аксакал, а саксаул форума.
К тому же, она у меня в игноре.

svetik5623190

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

Поясни плиз. В каком смысле эквивалентно и в каком - бессмысленно? Пока это лишь мнение, а не доказывающее что-то рассуждение.
Вам _кажется_ что вы четко задали правила игры, дали внутренне непротиворечивое утверждение. На деле это fuzzy logic.
Я не стал возражать, потому с одной тороны, эта тема, мягко говоря, не нова, сиречь боян, с другой - я не специалист в этой области. Ещё Гильберт говорил о том, что математика - бессмысленная формальная игра в символы на бумаге. Мой товарищ Андрей Горшков считает, что математика должна быть реализована с помощью идей Гильберта на компе. То есть написанное на специальном языке утверждение верно, если комп его откомпилировал (не нашёл грамматических ошибок) и потом выполнил как программу. Есть ещё куча других точек зрения. Есть, как уже отмечалось в треде, интуиционализм, конструктивизм и т.п. (что значат эти слова - я не знаю).
В общем, говорить об этом можно много. Но мне лично в данном треде интересно не это, а другое: изъяны моего примера.

svetik5623190

зыы
То есть ззы?

toxin

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

svetik5623190

Все эти переформулировки с алгоритмами, как мне кажется, не в силах устранить парадоксальность определения "конечно неопределяемых" чисел.
Предъяви, пожалуйста, парадокс, возникающий из определения жёстко или мягко конечно неопределяемых чисел. Или хотя бы доказательство того, что он существует.
Парадоксально-опасные объекты имхо вот они:
 
1. Класс , то есть класс всех тех элементов (=предметов, =вещей, =объектов которые человечество не может описать с помощью заданного конечного набора символов.
2. Класс всех тех элементов, которые человечество может описать с помощью символов (любых).
  

Я писал об этом здесь:
Да и то, если аккуратно обращаться со словами "класс" и "множество", то можно не попасть впросак.
А у меня - числа, у меня всё ок вроде бы - то есть по крайней мере уж парадокс типа Рассела у меня не возникает, потому что множество конечно неопределяемых (и мягко, и жёстко) чисел - это подмножество класса, который является множеством, то есть настоящим множеством.
Если я ошибаюсь - прошу указать на ошибки.

svetik5623190

Более удачный пример - множесто непустых подмножеств вещественных чисел (они пересекаются, но их можно развести, рассмотрев декартово произведения множества вещественных чисел и множества всех его непустых подмножеств). Попробуй выбрать из каждого по элементу - ни алгоритмически, ни математически это не получится.
Спасибо! Хоть кто-то привел пример, который считает более удачным, а то мой пример все только ругают, а альтернативы не дают.
Чем этот пример существенно лучше? Множество конечно неопределяемых чисел - тоже непустое подмножество [math]$\mathbb{R}$ [/math], то есть твой пример уж никак не проще моего, потому что у меня выбор надо делать из одного множества, а у тебя - из системы множеств, одно из которых - моё. Или он лучше тем, что ещё проще как-то можно показать, что выбор сделать затруднительно?
Попробуй выбрать из каждого по элементу - ни алгоритмически, ни математически это не получится.
Обоснование?
И можно, пожалуйста, привести ещё какие-нибудь пояснения по поводу того, в чём соль этого примера? Честно говоря, не уловил. Не очень понял этот пример.

vizier

Предъяви, пожалуйста, парадокс
ок. не совсем парадокс, скорее тавтология:
ты говоришь: я хочу продемонстрировать что аксиома выбора не работает на некотором множестве. возьмем множество X, состоящее из элементов, которые мы никак не можем указать. Попробуем применить к нему аксиому выбора. Нам нужно множество из одного элемента, пересекающееся с X. Укажем этот элемент. Опаньки! А ни одного элемента X мы указать и не можем. ЧТД.
Масло масляное короче. Ну или триглицериды масляные.

asseevdm

Можно поподробнее?

svetik5623190

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

svetik5623190

Масло масляное короче. Ну или триглицериды масляные.
Мой пример скорее говорит, что масло (если прогоркнет) сильно воняет масляной кислотой.

vizier

То есть тем самым демонстрируется, что аксиома выбора существенно неконструктивна: она может утверждать существование объектов, которые конструктивно конечным числом символов описать нельзя.
вполне очевидно, что на вопрос "как мне выбрать из хз чего?", ты получаешь ответ "хз как". Это я о том, что аксиому выбора видимо нет смысла формулировать для множества "хз чего". Хотя грамматически все верно.

svetik5623190

вполне очевидно, что на вопрос "как мне выбрать из хз чего?", ты получаешь ответ "хз как". Это я о том, что аксиому выбора видимо нет смысла формулировать для множества "хз чего". Хотя грамматически все верно.
Ещё раз. Существование одноэлементых подмножеств у хз чего не очевидно. А аксиома выбора говорит, что они есть.

vizier

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

svetik5623190

Ты пытаешься применить аксиому выбора к несуществующему объекту. формально не существующему. объект нельзя определить, сказав "это не то не то и не то". видимо это вызывает затруднения.
Что-что?
Вещественные числа существуют. Конечно-определяемые числа существуют. Дополнение множества конечно-определяемых чисел до множества вещественных чисел это по определению множество конечно неопределяемых чисел. Простые мощностные рассуждения (см первый пост треда) показывают, что оно не пусто.

svetik5623190

Конечно не определяемые числа существуют по второй аксиоме аксиоматики Цермело-Френкеля - по аксиоме выделения.

svetik5623190

Вещественные числа существуют. Конечно-определяемые числа существуют.
Причёи существуют не просто так, аксиоматически, а в правильном смысле существуют - есть модели и того, и другого.
Моделей вещественных чисел полно - не буду пересказывать бояны.
Модель жёстко конечно определяемых чисел - множество программ на С++, получающих на вход натуральное n и выдающих за конечное число часов в качестве результата одно из двух чисел: 0 или 1. Эти 0 или 1 трактуются как n-я цифра числа, моделируемого программой.
Причём если две программы выдают на каждое n один и тот же результат, то они моделируют одно и то же конечно определяемое число.

vizier

оно не пусто, но ты уверен, что определил это понятие достаточно, для того, чтобы оперировать им и применять к нему аксиому выбора?
дело в том, что ты сейчас _говоришь_.
грамматически все верно.
проблема в том, что "я лгу".
; )

svetik5623190

оно не пусто, но ты уверен, что определил это понятие достаточно, для того, чтобы оперировать им и применять к нему аксиому выбора?
Полную уверенность даст только строгая формальная запись определения конечно-определяемого числа в соответствии с правилами аксиоматики Ц-Ф или какой-нибудь другой.
Я уверен, что это возможно для жёстко конечно определяемых чисел. Проводить эту формализацию мне не хочется, да и не хватит, скорее всего, квалификации. Кроме того, похоже, что жёстко конечно определяемые числа уже известны в математике под названием вычислимых (да поправят меня специалисты если вру так что наверняка полчища логиков уже провели эту формализацию во всех популярных аксиоматиках.
Это уже не вопрос возможности или невозможности, а вопрос того, какую долю бурбакизма в нашем общении мы считаем приемлемой.
После того, как конечно определяемые вещественные числа строго описаны, аксиома выделения говорит, что существует множество элементов, которые являются вещественными числами, но не являются конечно-определяемыми вещественными числами. После этого из соображений мощности следует, что это множество не равно пустому множеству.
По-моему, тут всё прозрачно.

svetik5623190

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

vizier

Полную уверенность даст только строгая формальная запись определения конечно-определяемого числа в соответствии с правилами аксиоматики Ц-Ф или какой-нибудь другой.
в ход пошла тяжелая артиллерия ).
ок, ты наверное прав.
ответь еще на один вопрос: а для чего еще можно использовать множество конечно не определяемых чисел, кроме демонстрации нетривиальности аксиомы выбора?

svetik5623190

ответь еще на один вопрос: а для чего еще можно использовать множество конечно не определяемых чисел, кроме демонстрации нетривиальности аксиомы выбора?
ХЗ. Я его придумал именно для этой цели.

vizier

То есть тем самым демонстрируется, что аксиома выбора существенно неконструктивна
...
ответь еще на один вопрос: а для чего еще можно использовать множество конечно не определяемых чисел, кроме демонстрации нетривиальности аксиомы выбора?
ХЗ. Я его придумал именно для этой цели.
то есть ты демонстрируешь неконструктивность аксиомы выбора на объекте, используя который, видимо, никаких конструктивных построений сделать нельзя. что это доказывает?

svetik5623190

  КЛЮЧЕВОЙ МОМЕНТ В ДИСКУССИИ!
 

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

Пожалуй, вот в этих твоих словах и выражена вкратце вся критика моего примера форумчанами на протяжении всего треда. Ты лучше всех сформулировал. Спасибо.
Попробую ещё раз пояснить свою педагогическую мысль - для тебя и для всех.
Построенный пример не доказывает ничего. Но показывает (демонстрирует что аксиома выбора может работать с такими объектами. А раз она может, то она не может быть конструктивной - то есть в принципе сама по себе аксиома выбора не даёт способа выбора.
Хотя в некоторых конкретных случаях способ выбора очевиден. Но тогда и аксиома выбора не нужна. Поэтому хочется сказать, что она очевидна и не нужна ВООБЩЕ. Но пример говорит - нет, брат, шалишь: существование одноэлементных подмножеств и возможность явно указать хоть одно одноэлементное подмножество - очень разные вещи. И аксиома выбора именно утверждает их существование.
Утверждать существование объекта можно и тогда, когда подтверждение его существования путём предъявления его за конечное число шагов затруднительно (жёстко конечно неопределяемые действительные числа) или даже вовсе невозможно (мягко конечно неопределяемые действительные числа) . В этом соль аксиомы выбора.
Этим же заодно демонстрируется и то, что вместо аксиомы выбора можно принять её отрицание, и всё равно противоречия не возникнет с остальными аксиомами теории множеств. То есть можно принять за аксиому утверждение "Существует набор непересекающихся непустых множеств такой, что не существует множества, содержащего по одной точке в каждом из множеств этого набора".
Действительно, поскольку в приведённом примере такое множество всё равно человек предъявить за конечное число шагов не может, то он имеет моральное право с равной степенью обоснованности верить в то, что оно существует, и в то, что оно не существует, либо игнорировать вопрос о его существовании. То есть принимать аксиому выбора, либо принимать её отрицание, либо не использовать в своих построениях в качестве аксиомы ни то, ни другое.
Опыт математической работы показывает, что жить легче, если аксиому выбора принимать. Но это вынуждает мириться с тем, что появляется возможность помимо всяких полезных вещей доказывать и странные вещи типа теоремы Банаха-Тарского об удвоении шара.
Что ж поделать, так устроен мир.

vizier

ок. это было интересно : )

svetik5623190

ок. это было интересно : )
Спасибо. Что именно тебе больше всего понравилось? :)
ЗЫ: Можешь поставить плюс посту, если он тебе показался интересным :)

vizier

напряжение мозгов ; )
зы поставил

svetik5623190

напряжение мозгов ; )
Мехмат - сила! ;)
ЗЫ: На этой позитивной ноте я иду спать :)

lena1978

И аксиома выбора именно утверждает их существование.
т.е. без аксиомы выбора совсем не очевидно, что множество состоит из своих элементов? :confused:
мне казалось, что неочевидность аксиомы выбора заключается в неочевидности возможности выбора по одному элементу из бесконечной совокупности бесконечных подможеств, а не из одного бесконечного множества.
а вообще все это хуйня ;)

svetik5623190

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

Sergey79

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

svetik5623190

имхо все твои рассуждения страдают неаксиоматичностью очевидности выбора
После всего этого треда ты по-прежнему считаешь аксиому выбора очевидно верным утверждением?

Sergey79

я скажу так: данная аксиома есть научно оформленное мое понимание слова "выбрать".
Например, у нас есть два множества A и B, состоящие из "не пойми чего". Тогда согласно аксиоме выбора я имею множество C из двух элементов, один из которых - это C_a="какой-то элемент из множества А", а другой элемент - это C_b="какой-то элемент из множества B".
И меня совершенно не смущает, что множества А и В не предоставляют "доступа ко всем свойствам своего элемента" при помощи конечного алгоритма.
Если А и В - это множества нормальные, то и С будет нормальным множеством. А если А и В - это множества типа как из твоего примера, то и С будет таким же множеством. И для меня тот факт, что на выходе аксиомы выбора мы получили неочевидное множество означает, что на вход были поданы неочевидные множества, а не потому, что аксиома выбора неочевидная.

svetik5623190

скажу так: данная аксиома есть научно оформленное мое понимание слова "выбрать".
Например, у нас есть два множества A и B, состоящие из "не пойми чего". Тогда согласно аксиоме выбора я имею множество C из двух элементов, один из которых - это C_a="какой-то элемент из множества А", а другой элемент - это C_b="какой-то элемент из множества B".

Да.
Если А и В - это множества нормальные, то и С будет нормальным множеством. А если А и В - это множества типа как из твоего примера, то С
не факт что существует.

Sergey79

не факт что существует.
не факт, а аксиома (мне очевидная)!

svetik5623190

А утверждение "Существует набор непересекающихся непустых множеств такой, что не существует множества, содержащего по одной точке в каждом из множеств этого набора" как тебе - верным интуитивно представляется или нет?
Это читал?

Sergey79

это читал, но имхо там все то же самое
что касается утверждения "<...>" то оно слишком сложное для моего понимания. Кроме того, я так и не понял что ты понимаешь под "множеством".

stm7543347

верность аксиомы выбора не очевидна
показывает (демонстрирует что аксиома выбора может работать с такими объектами. А раз она может, то она не может быть конструктивной - то есть в принципе сама по себе аксиома выбора не даёт способа выбора.
У меня сегодня что-то не то с равносильностями?
Напоминает, как мне в интернетах попалась "статья", выглядевшая примерно так: теорема Котельникова (Шеннона и кто там еще ее формулировал...) неверна, потому что наши инженеры не могут сделать идеальный ЦАП.

svetik5623190

что касается утверждения "<...>" то оно слишком сложное для моего понимания.
Извини.
Кроме того, я так и не понял что ты понимаешь под "множеством".
То же, что и все математики.
Как допишу книжку - дам ссылку, посмотришь - там много про это написано.

svetik5623190

Что ты имеешь в виду?

stm7543347

Мне все кажется, что "неочевидная верность" и "неконструктивность" есть несколько разные свойства.
Или уже провели реформы, и я безнадежно устарел?
ЗЫ. "Верность аксиомы" - это что? :ooo:

svetik5623190

Мне все кажется, что "неочевидная верность" и "неконструктивность" есть несколько разные свойства.
Да.
ЗЫ. "Верность аксиомы" - это что?
Философский вопрос, друг мой. Не знаю, что на него ответить. Но факт (доказанный Коэном, Гёделем и ещё Бог знает кем - глянь в Википедии) состоит в том, что аксиома выбора (равно как и её отрицание) не могут быть доказаны в системе аксиом теории множеств Ц-Ф. То есть аксиома выбора логически независима от аксиоматики Ц-Ф. Более того, если Ц-Ф непротиворечива, то и "ЦФ + аксиома выбора", а так же "ЦФ + отрицание аксиомы выбора" непротиворечивы. Есть даже специальное сокращение для "Система аксиом Цермело-Френкеля + аксиома выбора", оно такое: ZFC.
То же самое имеет место в отношении континуум-гипотезы. Кстати, обобщённая континуум-гипотеза влечёт аксиому выбора. Подробности в Википедии.

stm7543347

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

svetik5623190

В этом как бы и есть смысл аксиом (ты их либо принимаешь, либо нет, либо принимаешь им противоречащие
Да, так.
В чём вопрос-то? :)

stm7543347

В чём вопрос-то? :)
Какая будет погода на выходных?

svetik5623190

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

kravecnata

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

vvasilevskiy

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

natunchik

Что-то я давно не читал этот тред.

Я честно не понимаю, в чем затыка? Физический смысл это не консерватизм, а иррационально обузданная интуиция. Ты хочешь, чтобы я формализовал когда и как применяется физический смысл?
Обесняю. Если бы применение "физического смысла" было ограничено только тем, что кажется очевидным физику, то транзисторов и вообще ничего нового у нас бы не было по определению. Было бы только то, что казалось очевидным физикам того времени, когда эта деструктивная концепция распространилась.
Оно, конечно, этим не ограничено в нашей реальности. Я как раз говорю о том, чем оно _должно_ быть ограничено.
Это ведь вопрос доверия к математике, ещё раз повторяю. Если ты считаешь, что она периодически несёт фигню, то у тебя есть большие шансы пропустить реальное открытие. Если ты знаешь, что она имеет обыкновение нести фигню в таких-то и таких-то местах, то шансы пропустить открытие многократно уменьшаются, потому что когда ты натыкаешься на математическую фигню, в которой никаких левых аксиом не использовалось, ты обязан проверить, что действительно в реальности такого быть не может, и результат проверки может тебя озадачить до конца жизни (а потомкам дать много полезного). Вот и всё.
: То, что аксиома выбора позволяет работать со смутными объектами, никак её не компрометирует. Ты с вещественными числами работаешь? А среди них чуть менее чем все иррациональны. Иррациональность ведь это почти твоя конечная неопределяемость, не видишь разве? Замени С++ на любой достаточно мощный не-тьюринг полный язык и получишь иррациональные числа в качестве множества неопределяемых чисел.
Тем не менее ты замечательно ищешь пределы, интегрируешь на отрезке и всё такое. Тебе было бы очень тяжело интегрировать, если бы ты интегрировал только по рациональным числам, потому что у них как бы плотность, она, знаешь ли, ха ха, смешно себя ведёт. Иррационально, фактически.
Короче, моя личная претензия — нельзя демонстрировать стрёмность аксиомы выбора, используя несопоставимо более стрёмное невычислимое множество — остаётся в силе.
Настойчиво рекомендую: прочитай http://en.wikipedia.org/wiki/Banach%96Tarski_paradox
Он очень, очень простой. Его можно рассказывать восьмиклассникам, на самом деле, и они практически всё поймут. Ну, тем, кому уже рассказывали про натуральные, рациональные и вещественные числа, всё, больше там ничего не нужно.

svetik5623190

Короче, моя личная претензия — нельзя демонстрировать стрёмность аксиомы выбора, используя несопоставимо более стрёмное невычислимое множество — остаётся в силе.
Имхо на неё исчерпывающе отвечает этот пост
За ссылку спасибо большое, равно как и вообще за участие в треде.

natunchik

Охохо!
То, что аксиома выбора позволяет работать со смутными объектами, никак её не компрометирует. Ты с вещественными числами работаешь? А среди них чуть менее чем все иррациональны. Иррациональность ведь это почти твоя конечная неопределяемость, не видишь разве?
Так что не вполне отвечает.
Заодно подчёркивается стрёмность требования "доказывать существование объекта путём предоставления алгоритма его построения", раз уж ничего конструктивного в общем на этом требовании построить нельзя, только конструктивные частные случаи. Прикинь, да!
Неее, ты кажется совершенно не понял, во что влип, когда начал размышлять про аксиому выбора и обоснованность её использования. Основания математики дичайше стремны, там никакой обоснованности нет вообще нигде!
Ну реально, если ты не хочешь, чтобы тебя глодало осознание того, что ты детей в чём-то наебал, расскажи им лучше про Банаха-Тарского. Там всё сравнительно чисто.

svetik5623190

Спасибо, ещё подумаю. А то ночью что-то голова плохо варит: спать пора.

natunchik

Когда проснёшься, прочитай ещё раз внимательно. Я даже готов дать определение достаточно мощного не-(тьюринг полного) языка: это язык, в котором вычисления гарантированно завершаются для любых входных данных. Например, рекурсивно перечислимый (http://en.wikipedia.org/wiki/Recursively_enumerable_language там есть примеры, кстати). Любой язык, в котором любое утверждение позволяет провести индуктивное доказательство. Язык пропозиционального исчисления (которое логика без предикатов).
Все они позволяют описать рациональные чилса, ни один из них не позволят описать ни одно иррациональное число.
Если тебе влом углубляться в весь этот ужас, тогда просто поверь, что лучше рассказать детям Банаха-Тарского, чем довольно красивую (окей, мы оценили, этого достаточно?) но глючную в своей основе эту твою демонстрацию.

svetik5623190

Всем спасибо за обсуждение. Кажется, я въехал.
Как верно заметил (в устной беседе) , существование одноэлементных подмножеств у любого множества следует (без всякой аксиомы выбора!) из аксиоматики ЦФ, а точнее, по аксиоме выделения [math]$ \forall y\in X \  \exists\ \{x\in X: x=y \} $[/math].
Решил пример в книжку не включать.

mtk79

Мой учитель, легендарный* поэт Виктор Фершняго писал по поводу аксиомы выбора:
Не всяк, кто выбрать смог в комке палёвой жижи пенной,
Стоит по жизни покрутей, чем буриданов тот осёл,
Что ради доказательства тождественности сена
Пастера раньше, над собою на эксперимент пошёл.
Прошли тысячелетья — пролетели, точно птицы,
Но не забыло человечество, о ослик, подвиг твой:
И вот открылись нам элементарные частицы,
Которые, как электрон — одна тождественней другой.
* Легенды о Викторе Фершняго выходят за рамки тематики этого раздела

svetik5623190

Решил пример в книжку не включать.
Имеется в виду --- пример, описанный в первом посте этого треда.
Оставить комментарий
Имя или ник:
Комментарий: