2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Сходящаяся последовательность множеств
Сообщение29.12.2015, 17:46 
Аватара пользователя
Застрял на простой задаче.

Пусть дано произвольное множество $A_1$ и определенная на нем функция $f$. Доказать или опровергнуть, что для бесконечной последовательности множеств
$A_1 \supset A_2 \supset A_3 \supset... $ и множества $A = \cap A_i$ верно
$f(A_1) \supset f(A_2) \supset f(A_3) \supset... $ и $f(A) = \cap f(A_i)$.
Это легко доказывается в конечном случае, а вот на бесконечном я застрял. То есть то, что $f(A_1) \supset f(A_2) \supset f(A_3) \supset... $, доказывается как раз рассмотрением произвольного конечного случая, а вот как доказать $f(A) = \cap f(A_i)$? Легко показать, что $f(A) \subset \cap f(A_i)$, это так для любого пересечения множеств. А вот с $f(A) \supset \cap f(A_i)$ затык. Для произвольной последовательности $\{A_i\}$ это не так, значит, надо использовать монотонное включение. Как его использовать? С другой стороны, и контрпример построить не получается, да и интуиция вопиет, что контрпримера быть не может.

Дайте мне пинка, что ли, в нужном направлении.

 
 
 
 Re: Сходящаяся последовательность множеств
Сообщение29.12.2015, 18:07 
Аватара пользователя
Это, конечно, неверно. Рассмотрите, например, последовательность с пустым пересечением и сделайте так, чтобы пересечение образов было непустым.

 
 
 
 Re: Сходящаяся последовательность множеств
Сообщение29.12.2015, 18:28 
Аватара пользователя
А! Очень просто. Рассмотрим константу $1$ как функцию на числовой прямой: $f(x) \equiv 1$. Рассмотрим последовательность $\{A_i\}$ такую, что $A_i = [i, \infty)$. Dixi. Что у меня за талант такой - не замечать очевидных контрпримеров?

-- 29.12.2015, 18:33 --

Но вот интересно - с непустым пересечением получится или нет?

 
 
 
 Re: Сходящаяся последовательность множеств
Сообщение29.12.2015, 18:43 
Аватара пользователя
Anton_Peplov в сообщении #1086844 писал(а):
Но вот интересно - с непустым пересечением получится или нет?
Ну можно добавить непустое пересечение, которое переходит в другое значение.

 
 
 
 Re: Сходящаяся последовательность множеств
Сообщение29.12.2015, 20:28 
Аватара пользователя
Xaositect в сообщении #1086846 писал(а):
Ну можно добавить непустое пересечение, которое переходит в другое значение.

Не понял этой фразы. Можно пример?

 
 
 
 Re: Сходящаяся последовательность множеств
Сообщение29.12.2015, 20:53 
Аватара пользователя
Anton_Peplov
В вашем примере добавьте в каждое множество элемент $0$ и положите $f(0)=0$

 
 
 
 Re: Сходящаяся последовательность множеств
Сообщение29.12.2015, 20:59 
Аватара пользователя
Ах, вот оно что. Действительно, образ каждого $A_i$ равен $\{0, 1\}$, поэтому и пересечение всех образов равно $\{0, 1\}$. Спасибо.

 
 
 
 Re: Сходящаяся последовательность множеств
Сообщение23.01.2016, 17:23 
Аватара пользователя
Пусть дано произвольное множество $A_1$ и определенная на нем функция $f$. Скажем, что функция стройная, если для бесконечной последовательности множеств
$A_1 \supset A_2 \supset A_3 \supset... $ и множества $A = \cap A_i$ верно
$f(A_1) \supset f(A_2) \supset f(A_3) \supset... $ и $f(A) = \cap f(A_i)$ (для чего, очевидно, необходимо и достаточно, чтобы $\cap f(A_i) \subset f(A)$).

Утверждение 1. Инъекция - стройная функция.
В самом деле, рассмотрим любую точку $y \in $\cap f(A_i)$. Поскольку функция инъективна, прообраз $y$ состоит из единственной точки $x$. Поскольку $f(x)$ входит в каждое $f(A_i)$, $x$ входит в каждое $A_i$, т.е. $x \in \cap A_i = A$, а потому $f(x) \in f(A)$. Итак, $\forall y \in \cap f(A_i) \ y \in f(A)$, чего и хотелось.

Но инъективность, являясь достаточным условием стройности, не является необходимым, ибо очевидно утверждение 2.

Утверждение 2. Функция с конечной областью определения - стройная.

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

Утверждение 3. Если в области значения функции есть элемент с бесконечным прообразом, она не стройная.
В самом деле, пусть прообраз элемента $y$ - бесконечное множество. Выделим из него счетное подмножество $\{x_1, x_2, x_3...\}$ и обозначим его $A_1$. Построим
$A_2 = A_1 \setminus \{x_1\}$
$A_3 = A_1 \setminus \{x_1, x_2\}$,
...
Получим, что для каждого $i$ $f(A_i) = \{y\}$, в то время как пересечение всех $A_i$ пусто (как в примере Xaositect).

Вопрос. Достаточно ли для стройности функции, чтобы прообраз каждого элемента области значения был конечен?

 
 
 
 Re: Сходящаяся последовательность множеств
Сообщение23.01.2016, 20:19 
Аватара пользователя
Достаточно. Пусть прообраз точки $y\in f(A_1)$ конечен:
$f^{-1}y=X$
Тогда одно из двух:
или есть такое $x\in X$, которое принадлежит всем $A_i$,
или множества $A_i$, начиная с некоторого $i_0$, не содержат ни одного $x\in X$.

В первом случае $x\in\cap A_i \Rightarrow f(x)\in f(\cap A_i) \Rightarrow f(x)\in \cap f(A_i)$
Во втором случае $f(x)\notin f(A_{i_0})\Rightarrow f(x)\notin \cap f(A_i)\Rightarrow f(x)\notin f(\cap A_i)$
А чтобы функция не была стройной, должна существовать такая точка $y$, что
$y\notin f(\cap A_i)$, но $y\in \cap f(A_i)$

 
 
 
 Re: Сходящаяся последовательность множеств
Сообщение23.01.2016, 23:58 
Аватара пользователя
Спасибо!
Я чуть переформулирую в более понятные мне слова.
Пусть прообраз каждого элемента $Y$ конечен. Докажем, что тогда $\cap f(A_i) \subset f(A)$.
Рассмотрим произвольную точку $y \in \cap f(A_i)$. Т.к. точка $y$ лежит в образе каждого $A_i$, в каждом $A_i$ должна быть хоть одна точка ее прообраза. Но по условию прообраз конечен, а значит, в нем должна быть хоть одна точка $x$, лежащая в бесконечном множестве различных $A_i$. Но по условию $A_1 \supset A_2 \supset A_3 \supset... $, а значит, точка, лежащая в бесконечном множестве различных $A_i$, лежит во всех $A_i$. Значит, она лежит в $A = \cap A_i$. А коли $x \in A$, то $f(x) = y \in f(A)$. Таким образом, для любого $y \in \cap f(A_i)$ верно $y \in f(A)$. Теорема доказана.

P.S. Интересно, а есть ли у стройных функций какое-нибудь общепринятое название? Или на всем белом свете только я ими интересуюсь?

-- 24.01.2016, 00:10 --

Anton_Peplov в сообщении #1093674 писал(а):
Но по условию $A_1 \supset A_2 \supset A_3 \supset... $, а значит, точка, лежащая в бесконечном множестве различных $A_i$, лежит во всех $A_i$.

Вот это звено мне не дает покоя. Чувствую здесь скользкое место, как и в аналогичном утверждении "$\mathbb{N}$ нельзя разбить на два бесконечных множества $A$ и $B$ так, чтобы $\forall a \in A, b \in B \ a<b$". Это вроде бы и верно, и через аксиому Архимеда вроде бы даже доказывается, но что-то я здесь чувствую...

 
 
 
 Re: Сходящаяся последовательность множеств
Сообщение24.01.2016, 01:28 
Аватара пользователя
Anton_Peplov
Я себя убедил здесь таким образом. Излагаю подробно, чтобы уж никаких сомнений.

Прообраз точки $y\in\cap f(A_i)$ конечен. Пусть он содержит $n$ элементов $x_1, ... , x_n$. Подходим к каждому элементу $x_k$ и спрашиваем его: «Ты принадлежишь каждому $A_i$ или нет?». Если элемент отвечает «нет», мы спрашиваем его: «Начиная с какого номера $i$ множества $A_i$ тебя уже не содержат?».

Допустим, каждый элемент прообраза $x_k$ признался, что принадлежит не всем $A_i$, и назвал номер, начиная с которого он отсутствует. Тогда мы берём максимальный из названных номеров (это возможно, так как их конечное количество), обозначим его $i_{\max}$. И делаем вывод, что множество $A_{i_{\max}}$ (и последующие) не содержит ни одну из точек прообраза $y$. Но тогда точка $y$ не содержится в $f(A_{i_{\max}})$. И, стало быть, $y$ не содержится в $\cap f(A_i)$. Противоречие.

Значит, существует такой элемент прообраза, который принадлежит всем $A_i$.

 
 
 
 Re: Сходящаяся последовательность множеств
Сообщение24.01.2016, 02:17 
Аватара пользователя
svv в сообщении #1093703 писал(а):
Если элемент отвечает «нет», мы спрашиваем его: «Начиная с какого номера $i$ множества $A_i$ тебя уже не содержат?».

Anton_Peplov в сообщении #1093674 писал(а):
Но по условию $A_1 \supset A_2 \supset A_3 \supset... $, а значит, точка, лежащая в бесконечном множестве различных $A_i$, лежит во всех $A_i$. Значит, она лежит в $A = \cap A_i$.

Это одно и то же. Мы говорим, что раз последовательность монотонна по включению, то не может быть такого, чтобы $x$ принадлежал, скажем, всем $A_i$ с четными и только четными номерами. Или, скажем, тем и только тем $A_i$, номера которых - степени числа $2$. Или всем $A_i$ с простыми номерами и только им. Нет, говорим мы, раз уж последовательность монотонна по включению, то $x$ принадлежит либо конечному числу ее элементов, либо всем.
Это правильно. И все же чем-то это меня беспокоит. Паранойя у меня, наверное.

 
 
 
 Re: Сходящаяся последовательность множеств
Сообщение24.01.2016, 03:44 
Аватара пользователя
Придумал, как сказать это "на финитном языке".
Если в последовательности $A_1 \supset A_2 \supset A_3 \supset... $ точка $x$ лежит в множестве $A_k$, то она лежит во всех множествах $A_1...A_{k-1}$. Пусть теперь точка $x$ лежит в бесконечном числе разных $A_i$. Обозначим множество их номеров как $M$.
Рассмотрим произвольный элемент последовательности $A_k$. Т.к. $M$ бесконечно, в нем найдется номер $m > k$. Значит, точка $x$ лежит во всех множествах $A_1...A_{m-1}$, в том числе и в $A_k$. Таким образом, для любого $A_k$ верно $x \in A_k$, т.е. $x$ лежит во всех элементах последовательности.

Вот теперь все красиво, как Давид у Микеланджело.

 
 
 
 Re: Сходящаяся последовательность множеств
Сообщение24.01.2016, 13:39 
Аватара пользователя
С моей точки зрения — OK. :P
Anton_Peplov в сообщении #1093718 писал(а):
И все же чем-то это меня беспокоит. Паранойя у меня, наверное.
Давайте назовём это «аберрация». Аберрации есть у всех (ну, или почти у всех). У меня их куча, вот одна. Скажите, а вот в таком варианте сомнение снимается?:

Подходим к каждому элементу $x_k$ и спрашиваем его: «Существует ли какое-то $A_i$, которому ты не принадлежишь?». Если элемент отвечает «да», мы просим его: «Номер назови, да?» :-) .

Если каждый элемент прообраза ответил «существует» и назвал номер $i_k$, мы берём из них максимальный, обозначим его $i_{\max}$, и делаем вывод, что ни один из $x_k$ не принадлежит $A_{i_{\max}}$. В противном случае, если бы какой-то $x_k\in A_{i_{\max}}$, то также $x_k\in A_{i_k}$, ведь $A_{i_k}\supset A_{i_{\max}}$.

Значит, $y\notin f(A_{i_{\max}})$ (только одному множеству!). И этого достаточно, чтобы $y\notin \cap f(A_{i_{\max}})$

 
 
 
 Re: Сходящаяся последовательность множеств
Сообщение24.01.2016, 14:56 
Аватара пользователя
svv в сообщении #1093805 писал(а):
Скажите, а вот в таком варианте сомнение снимается?:

Оно снялось моим предыдущим сообщением, вот этим:
Anton_Peplov в сообщении #1093730 писал(а):
Придумал, как сказать это "на финитном языке"....
Меня беспокоило, что я не мог подробно доказать лемму "Дана последовательность $A_1 \supset A_2 \supset A_3 \supset... $. Если точка $x$ лежит в бесконечном числе элементов этой последовательности, то она лежит во всех ее элементах." Вместо доказательства у меня выходило "ей-Богу, так!", а таким аргументам я давно и прочно отучен доверять, тем более когда речь идет о бесконечности.
Теперь мне удалось подробно расписать доказательство этой леммы, и чувство сомнения ушло. Теперь все в порядке, спасибо Вам за участие.

 
 
 [ Сообщений: 15 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group