Измеримость натурального ряда

[Dave]

Существует ли функция $f \colon 2^{\mathbb N} \to \{0,1\}$, такая, что:

1. $\forall n \in \mathbb N \colon f(\{n\})=0$ ;
2. $f(\mathbb N)=1$ ;
3. $\forall \, A,B \subseteq \mathbb N, \; A \cap B=\varnothing \colon f(A \cup B)=f(A)+f(B)$ ?

[Sonic86]

del

[lena7]

del

[g______d]

По-моему, все такие функции в точности соответствуют неглавным ультрафильтрам. Соответственно, существование зависит от леммы Цорна.

[Dave]

g______d в сообщении #749800 писал(а):

По-моему, все такие функции в точности соответствуют неглавным ультрафильтрам.

Ультрафильтры - это, конечно, хорошо, но хотелось бы увидеть какое-нибудь доказательство. В крайнем случае - ссылку на теорему, что ли.

g______d в сообщении #749800 писал(а):

Соответственно, существование зависит от леммы Цорна.

Будем считать, что аксиома выбора, как и лемма Цорна, у нас в кармане.

[g______d]

Dave в сообщении #750010 писал(а):

Ультрафильтры - это, конечно, хорошо, но хотелось бы увидеть какое-нибудь доказательство. В крайнем случае - ссылку на теорему, что ли.

Статья в википедии под названием "ультрафильтр".

Можно еще так: рассмотрим множество всех функций из $\mathbb N$ в $\mathbb Z/2\mathbb Z$. Оно биективно отображается на $2^{\mathbb N}$ (характеристическая функция подмножества).

Введем на этом множестве операции сложения и умножения (как сложение и умножение функций). Тогда это будет кольцом. Рассмотрим множество всех функций, отличных от нуля только в конечном количестве точек. Это идеал. Он содержится в некотором максимальном (лемма Цорна). Следовательно, фактор по нему – поле, причем из двух элементов (т. к. там всегда верно $x^2=x$, т. е. $x(x-1)=0$). Отображение в фактор, ядром которого будет этот идеал, и есть искомое.

[lena7]

С какой стороны ни подходи, все равно получается ультрафильтр.

Определим $f(A)=0$, если $A$ конечно и $f(A)=1$, если дополнение $A$ конечно. Для всех остальных разбиений $\mathbb N$ на две (уже бесконечные) части определим $f$ на одной части единице, на другой --- нулю, произвольным образом.

Хотя бы похоже на правду?

[iifat]

Не похоже. Сумма мер всех чётных и всех нечётных получается 2.
Возьмём $\{A|f(A)=1\}$.
Тогда $f(\varnothing)=0$
$A\subset B\Rightarrow f(B)=f(A)+f(B\setminus A)=1$
$f(A)+f({\mathbb N}\setminus A)=1$
Осталось доказать $f(A)=f(B)=1 \Rightarrow f(AB)=1$

[g______d]

lena7 в сообщении #750063 писал(а):

С какой стороны ни подходи, все равно получается ультрафильтр.

Потому что функции, описываемые в задаче, – это и есть в точности (неглавные) ультрафильтры.

Кстати, можно еще здесь посмотреть: http://en.wikipedia.org/wiki/Stone%E2%8 ... tification

lena7 в сообщении #750063 писал(а):

Для всех остальных разбиений $\mathbb N$ на две (уже бесконечные) части определим $f$ на одной части единице, на другой --- нулю, произвольным образом.

Произвольным – нельзя. Нужно сохранять условие монотонности ($A\subset B$ влечет $f(A)\leqslant f(B)$).

[Dave]

g______d в сообщении #750057 писал(а):

Статья в википедии под названием "ультрафильтр".

И что? Где там хоть одно доказательство? Или хотя бы ссылка на статью или монографию?
Я, например, строил необходимую конструкцию самостоятельно, без привлечения понятий "ультрафильтр" и "идеал".

[g______d]

Dave в сообщении #750250 писал(а):

Где там хоть одно доказательство? Или хотя бы ссылка на статью или монографию?

http://en.wikipedia.org/wiki/Ultrafilter#References

Dave в сообщении #750250 писал(а):

Я, например, строил необходимую конструкцию самостоятельно, без привлечения понятий "ультрафильтр" и "идеал".

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

[Dave]

g______d в сообщении #750255 писал(а):

http://en.wikipedia.org/wiki/Ultrafilter#References

Так бы и говорили, что имелась ввиду английская Википедия. И какая конкретно теорема в какой монографии имелась ввиду?

g______d в сообщении #750255 писал(а):

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

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

[g______d]

Dave в сообщении #750267 писал(а):

g______d в сообщении #750255 писал(а):

http://en.wikipedia.org/wiki/Ultrafilter#References

Так бы и говорили, что имелась ввиду английская Википедия. И какая конкретно теорема в какой монографии имелась ввиду?

Если говорить о монографии Comfort, W. W.; Negrepontis, S. (1974), The theory of ultrafilters по ссылке, то существование неглавного ультрафильтра содержится в лемме 7.2.

Я признаю, что эта монография не подходит для первого или даже сколько-нибудь раннего чтения. Но я видел это доказательство в большом количестве мест. Например, я думаю, что это есть в начале любой книги по нестандартному анализу. И в более-менее любом задачнике по теории множеств. Например, Лавров–Максимова, задача 67. Или Верещагин–Шень, задача 123. Нужны еще ссылки? Могу поискать.

Я хочу сказать, что задача представляет собой эквивалентную переформулировку общеизвестной теоремы (судя по википедии, доказанной Тарским в 1930 году); это не значит, что задача плохая, но не понимаю, почему этого факта стоит избегать.

-- 29.07.2013, 20:47 --

Я знаю еще несколько решений, но они все эквивалентны.

На всякий случай, фильтр – это семейство подмножеств, не содержащее пустого множества, с любым множеством содержащее все его надмножества и с любой парой множеств содержащее их пересечение; ультрафильтр – то же, но еще для любого множества содержащий либо его, либо его дополнение. Главный ультрафильтр – ультрафильтр, состоящий ровно из множеств, содержащих фиксированный элемент. Легко показать, что если ультрафильтр содержит конечное множество, то он главный.

Если есть функция из условия, то семейство подмножеств, на которых она будет равна единице, будет ультрафильтром. Неглавным, потому что мы исключили случай $f(\{n\})=1$.

Одно решение – рассмотреть множество всех фильтров и частично упорядочить его по включению. По лемме Цорна всякий фильтр содержится в максимальном. Рассмотрим фильтр, состоящий из дополнений к конечным множествам (называется фильтром Фреше). Он будет содержаться в некотором максимальном фильтре, не содержащем конечных множеств. Покажем, что он будет ультрафильтром. Действительно, если какое-то множество $A$ в нем не содержится и его дополнение тоже, то добавим множество $A$, все его надмножества и все пересечения надмножеств $A$ с остальными множествами фильтра. Это тоже будет фильтром, что противоречит максимальности.

Можно, наверное, то же сказать на языке функций из условия: рассматривать функции, заданные не обязательно на всем $2^{\mathbb N}$ и ввести отношение порядка (одна является продолжением другой). Потом взять функцию, равную 1 на дополнениях к конечным множествам. У нее есть максимальное продолжение. И так же показать, что оно будет задано на всем $2^{\mathbb N}$.

В принципе, мне было бы интересно услышать решения, существенно отличающиеся от приведенных.

[Dave]

g______d в сообщении #750279 писал(а):

Одно решение – рассмотреть множество всех фильтров и частично упорядочить его по включению. По лемме Цорна всякий фильтр содержится в максимальном. Рассмотрим фильтр, состоящий из дополнений к конечным множествам (называется фильтром Фреше). Он будет содержаться в некотором максимальном фильтре, не содержащем конечных множеств. Покажем, что он будет ультрафильтром. Действительно, если какое-то множество $A$ в нем не содержится и его дополнение тоже, то добавим множество $A$, все его надмножества и все пересечения надмножеств $A$ с остальными множествами фильтра. Это тоже будет фильтром, что противоречит максимальности.

Моё решение как раз было похоже на это, но с той разницей, что не содержало слова "фильтр" (как и лемма Цорна, кстати). И я увеличивал набор множеств, на которых функция равна нулю, а не единице.

g______d в сообщении #750279 писал(а):

В принципе, мне было бы интересно услышать решения, существенно отличающиеся от приведенных.

Мне тоже .