конструктивный ультрафильтр

Aug 16, 2010 01:00

Навеяно вот этим: terrytao.wordpress.com/2010/03/19/a-computational-perspective-on-set-theory/

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

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

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

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

Эта конструкция, в частности, показывает, что аксиома о существовании ультрафильтра совместима с ZF (без аксиомы выбора). Действительно, любое доказательство противоречия содержит лишь конечное число шагов. Аккуратная запись этой идеи приводит к методу форсинга, при помощи которого, в частности, Коэн доказал независимость гипотезы континуума.
Previous post Next post
Up