?

Log in

No account? Create an account
 
 
16 August 2010 @ 01:00 am
конструктивный ультрафильтр  
Навеяно вот этим: terrytao.wordpress.com/2010/03/19/a-computational-perspective-on-set-theory/

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

Теперь представим, что мы имеем право задавать только конечное (хоть и сколь угодно большое) число вопросов. Тогда ситуация меняется. Вот пример конструктивного "ультрафильтра" на натуральных числах:

1. У нас есть переменная S; сначала S --- это все множество натуральных чисел; S всегда будет бесконечным.
2. При каждом вопросе мы смотрим, с каким из элементов разбиения S пересекается по бесконечному множеству (если таких несколько, выбираем, например, элемент разбиения, содержащий наименьшее число).
3. Заменяем S на пересечение и возвращаем выбранный элемент разбиения.

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

Эта конструкция, в частности, показывает, что аксиома о существовании ультрафильтра совместима с ZF (без аксиомы выбора). Действительно, любое доказательство противоречия содержит лишь конечное число шагов. Аккуратная запись этой идеи приводит к методу форсинга, при помощи которого, в частности, Коэн доказал независимость гипотезы континуума.
 
 
 
(Deleted comment)
viktorpetrov on December 7th, 2010 01:44 pm (UTC)
Не знаю, я не специалист. Есть классическая книжка Йеха "Теория множеств и метод форсинга", но ее сложно читать.
Сергей Ларинsergeylarin on February 29th, 2012 06:49 am (UTC)
Весьма рад знакомству! По работе загруз поэтому временно не могу ответить своим оппонентам.Низкий поклон!
viktorpetrov on March 2nd, 2012 12:23 pm (UTC)
Я тоже очень рад! На Ваш журнал вышел по ссылке о мытарствах некоторое время назад, сейчас вот решился зафрендить :)