НГУ

Форумы НГУ
Текущее время: Вс авг 25, 2019 9:17 pm

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 75 ]  На страницу Пред.  1, 2, 3, 4, 5  След.
Автор Сообщение
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 30, 2006 6:37 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
AGu писал(а):
Pavel E. Alaev писал(а):
существует многочлен с целыми коэффициентами (от нескольких переменных) такой, что у него нет натуральных корней, но в ZFC невозможно это доказать.

Если имелось в виду существование такого диофантова уравнения,
что в ZFC не доказуемы ни наличие у него решений, ни их отсутствие, то -- зач0т! :)
Цитата:
Это легко выводится из отрицательного решения 10-й проблемы Гильберта

Не подскажете, как бы это сделать попроще?

Уравнение с целыми коэффициентами приводится к виду
t(x1,...,xn)=t'(x1,...,xn),
где t,t' - полиномы с натуральными коэффициентами. Решение 10-й проблемы говорит, что не существует общего алгоритма, который по наборам этих коэффициентов определяет, существуют ли у уравнения натуральные корни.

Каждому уравнению
t(x1,...,xn)=t'(x1,...,xn)
можно естественным образом сопоставить формулу, выражающую в ZFC, что у него есть корни. Если мы добавим в язык ZFC константу 0 и операцию s(x)=x+{x}, то она будет просто иметь вид
\exists x1 ... \exists xn [t(x1,...,xn)=t'(x1,...,xn) & nat(x1) & ... & nat(xn)].
Если у уравнения корни действительно существуют, то она, очевидно, выводима в ZFC, поскольку будет выводима формула
t('x1',...,'xn')=t'('x1',...,'xn')
для соответствующих конкретных термов 'xi'.

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

_________________
Не беги от снайпера - умрёшь усталым


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс окт 01, 2006 6:25 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
Красиво. Спасибо, что нашли время подсказать!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс окт 01, 2006 7:09 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
AGu писал(а):
Красиво. Спасибо, что нашли время подсказать!

Да вот что-то суета всякая мешает быстро отвечать.

AGu писал(а):
Pavel E. Alaev писал(а):
в любой модели ZFC число классов эквивалентности "конечных" множеств будет ровно столько же, сколько "натуральных" чисел.

Повторюсь: мы ведь имеем дело с теорией множеств, а не каких-нибудь там классов каких-нибудь там фон Нейманов, Гёделей или Бернайсов. Что такое "число один" согласно тому определению? (Не где-нибудь, а именно в ZFC.)
Из каких элементов это чудовище состоит? :-)

Мне кажется, что в рамках ZFC у нас по умолчанию есть некоторая "полунаивная" теория классов, основанная на постулатах:
(1) любой класс - некоторая совокупность множеств
(2) класс однозначно определяется своими элементами
(3) если x - множество и B(x,y) - некоторая формула, то совокупность
{y - множество | B(x,y)}
является классом. Она постоянная используется на практике - когда говорят о классе всех множеств, классе конечных множеств, о совпадении двух классов и т.д. Мы просто заводим для каждой формулой соответствующий класс. В частности, классом является совокупность всех множеств y, равномощных данному множеству x.

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

_________________
Не беги от снайпера - умрёшь усталым


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс окт 01, 2006 9:22 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
OK, не буду упорствовать и лишь выскажу явно то, что я имел в виду с самого начала: если притворяться занудой и не кривить теорией :) (в том числе, не привлекать упомянутое "полунаивное" расширение, которое при желании, конечно же, можно строго формализовать, вырвавшись за рамки ZFC), то, приняв определение натурального числа как класса эквивалентности конечных множеств, можно согласиться с существованием лишь одного натурального числа -- нуля.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт окт 05, 2006 9:40 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Мне кажется, что попытки размышлять над этими проблемами так или иначе приводят нас к вопросу о природе множеств. Они, очевидно нематериальны: объяснить неискушённому слушателю, чем отличаются объекты 0 и {0}, непросто. Есть, кажется, две основные точки зрения: объективный мир множеств и множества как воображаемые объекты.

Первая предполагает, что множества, с которыми имеют дело математики, где-то существуют, а те их просто исследуют. Такой подход хорош, в частности, тем, что проблему совокупности всех множеств можно решить, просто объявив, что в том загадочном мире такого множества "нет". Вариант, при котором в этом мире множеств нет и множества истинно-натуральных чисел
{0, 1, 2, ...},
нужно с отвращением отбросить - это была бы слишком жестокая шутка Творца над математиками. Если же оно там есть, то ZFC-формула nat(x) в точности определяет это множество, и может быть рассмотрена как определение натуральных чисел.

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

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

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

AGu писал(а):
Одной лишь апелляцией к интуитивной очевидности таких понятий, как конечное множество и функция, на мой взгляд, не обойтись. Без "высшей инстанции" (роль которой до сих пор играла метамодель с ее интуитивным понятием конечного доказательства) мы ведь запросто подеремся: один будет утверждать, что построил множество за конечное число шагов, другой возразит, что хоть это число и конечное, но оно бесконечно большое, третий скажет, что тут все, конечно же, конечно, но он не признает вот эту функцию, так как для нее не приведено построение, а лишь доказано, что она существует, тут снова вмешается второй и отвергнет это доказательство, ибо оно, на его взгляд, бесконечно длинное, четвертый заявит, что о функциях из N в N вообще нельзя говорить, так как их существование опирается на бесконечные последовательности выборов, а что такое бесконечная последовательность, мы интуитивно не чувствуем, (n+1)-й введет неопределяемое понятие бесконечного выбора, (n+2)-й скажет, что (n+1)-й погорячился и что бесконечные последовательности тоже можно строить за конечное число шагов, тут опять вылезет второй и объявит дискуссию логически необоснованной, так как число ее участников стало бесконечно большим.

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

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

_________________
Не беги от снайпера - умрёшь усталым


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Сб окт 07, 2006 6:17 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
Pavel E. Alaev писал(а):
А можно ли найти конкретный пример утверждения,
которое вызвало бы спор между двумя математиками, одинаково уважающими ZFC,
но расходящимися в понимании "конечного числа шагов"
или "произвольной последовательности выборов"?

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

Выбор метамодели в определенной степени произволен
(или, если угодно, основан на "наивных" представлениях).
Возьмем в качестве метамодели ту модель ZFC, в которой
то самое диофантово уравнение (разрешимость которого
недоказуема и неопровержима в ZFC) имеет таки решение.
Спрашивается, конечно ли решение этого уравнения?
В разговор тут же вступают три математика -- A, B и C.
    A: "Оно конечно, как и всякое натуральное число."
    B: "Да, но ведь оно бесконечно большое!"
    C: "Этого числа вообще нет, так как его существование
      не подкрепляется конкретной конечной конструкцией."
    A: "Это число само является своей конструкцией."
    B: "Да, но эта конструкция бесконечно длинная!"
    C: "Этой конструкции нет, так как ее существование
      не подкрепляется конкретной конечной конструкцией."
И кто из них прав?
    A: Разумеется, я.
    B: Чушь, уж кто прав, так это я.
    C: Сам дурак.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: определение целого числа в ZF
СообщениеДобавлено: Пн окт 09, 2006 2:24 am 
Не в сети
Частый гость

Зарегистрирован: Вс май 21, 2006 2:30 am
Сообщения: 41
Откуда: Дорин Александр
Все-таки дайте опеделение целого числа в ZF формальным образом
без воды


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение целого числа в ZF
СообщениеДобавлено: Пн окт 09, 2006 3:49 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
alex_dorin писал(а):
Все-таки дайте опеделение целого числа в ZF формальным образом

Разве это не было сделано в самом первом посте? Вот еще один вариант: тот факт, что x является натуральным числом, записывается формулой
    \forall Y [0 \in Y & \forall y (y \in Y => y+1 \in Y)] => x \in Y,
где 0 -- сокращение для пустого множества, а y+1 -- сокращение для объединения y и {y}.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение целого числа в ZF
СообщениеДобавлено: Вт окт 10, 2006 10:16 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
AGu писал(а):
...тот факт, что x является натуральным числом, записывается формулой
    \forall Y [0 \in Y & \forall y (y \in Y => y+1 \in Y)] => x \in Y,
где 0 -- сокращение для пустого множества, а y+1 -- сокращение для объединения y и {y}.


Надо ещё дописать, что y --- наименьшее по включению с таким свойством.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: AGu: осталось определить y + 1
СообщениеДобавлено: Вт окт 10, 2006 4:35 pm 
Не в сети
Частый гость

Зарегистрирован: Вс май 21, 2006 2:30 am
Сообщения: 41
Откуда: Дорин Александр
AGu:

\forall Y [0 \in Y & \forall y (y \in Y => y+1 \in Y)] => x \in Y,

осталось определить y + 1


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение целого числа в ZF
СообщениеДобавлено: Вт окт 10, 2006 5:07 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
Коба писал(а):
Надо ещё дописать, что y --- наименьшее по включению с таким свойством.
Разве? Не, там все правильно, ничего дописывать не нужно.
alex_dorin писал(а):
осталось определить y + 1
Я же написал, что y+1 -- это объединение y и {y}.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: определение целого числа в ZF
СообщениеДобавлено: Чт окт 12, 2006 11:48 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
AGu писал(а):
Коба писал(а):
Надо ещё дописать, что y --- наименьшее по включению с таким свойством.
Разве? Не, там все правильно, ничего дописывать не нужно.


Да, написано, не разглядел сначала.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн окт 16, 2006 7:13 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
AGu писал(а):
Выбор метамодели в определенной степени произволен
(или, если угодно, основан на "наивных" представлениях).
Возьмем в качестве метамодели ту модель ZFC, в которой
то самое диофантово уравнение (разрешимость которого
недоказуема и неопровержима в ZFC) имеет таки решение. Спрашивается, конечно ли решение этого уравнения?

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

Ладно, достаём из-за пазухи следующий аргумент: само определение ZFC требует каких-то представлений о множестве конечных слов: некоторые её аксиомы определяются как зависящие от \phi, где \phi - произвольная формула с некоторыми ограничениями. Чтобы объяснить, что такое ZFC, надо сначала объяснить, что такое конечное слово. Так что всё равно без понятия конечности никуда.

_________________
Не беги от снайпера - умрёшь усталым


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Pavel E. Alaev: если можно, подробнее
СообщениеДобавлено: Пн окт 16, 2006 8:51 pm 
Не в сети
Частый гость

Зарегистрирован: Вс май 21, 2006 2:30 am
Сообщения: 41
Откуда: Дорин Александр
Если можно, подробнее прокомментируйте Ваше определение целого числа в ZF. Обычно это более громоздкие конструкции
Как Ваше определение соотносится с приведенными в литературе ?

С уважением
А. Дорин


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вт окт 17, 2006 1:45 pm 
Не в сети
Частый гость

Зарегистрирован: Вс май 21, 2006 2:30 am
Сообщения: 41
Откуда: Дорин Александр
Ваше определение целого числа x N(x) утверждает только то, что x является элементом бесконечного множества.
Этого не достаточно для того что бы Ваше определение было определением целого числа.
Может это розыграш типа содержания некоторых научных статей ?

С уважением
А. Дорин


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 75 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: Bing [Bot] и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB