MandelbrotK писал(а):Source of the post Для конечных множеств A и B, доказать:
1) |A x B|=|A||B|
2)
![$$ |A \setminus B|=|A|-|A\cap B| 3) |2^A|=2^{|A|}$$ $$ |A \setminus B|=|A|-|A\cap B| 3) |2^A|=2^{|A|}$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20%7CA%20%5Csetminus%20B%7C%3D%7CA%7C-%7CA%5Ccap%20B%7C%203%29%20%7C2%5EA%7C%3D2%5E%7B%7CA%7C%7D%24%24)
Ещё не понятно вот что:
![$$ f: X\to Y, A,B\subset X$$ $$ f: X\to Y, A,B\subset X$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%3A%20X%5Cto%20Y%2C%20A%2CB%5Csubset%20X%24%24)
![$$f(A\cap B) \subset f(A)\cap f(B)$$ $$f(A\cap B) \subset f(A)\cap f(B)$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24f%28A%5Ccap%20B%29%20%5Csubset%20f%28A%29%5Ccap%20f%28B%29%24%24)
выплняется всегда, a равенство
![$$f(A\cap B) = f(A)\cap f(B)$$ $$f(A\cap B) = f(A)\cap f(B)$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24f%28A%5Ccap%20B%29%20%3D%20f%28A%29%5Ccap%20f%28B%29%24%24)
только, когда f - инъекция, как это нормально объяснить?
Спасибо
1), 2) Это следует из определений соответствующих операций.
3) Пусть
![$$ A = \{ a_1, a_2, \ldots, a_n \} $$ $$ A = \{ a_1, a_2, \ldots, a_n \} $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20A%20%3D%20%5C%7B%20a_1%2C%20a_2%2C%20%5Cldots%2C%20a_n%20%5C%7D%20%24%24)
. Так как подмножество однозначно определяется входящими в него элементами, то каждому подмножеству B множества A можно сопоставить строку из нулей и единиц следующим образом: на i-м месте строки стоит единица, если элемент
![$$ a_i \in B $$ $$ a_i \in B $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20a_i%20%5Cin%20B%20%24%24)
. Число таких строк -
![$$ 2^n $$ $$ 2^n $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%202%5En%20%24%24)
.
Можно эту задачу решить и методом индукции.
4.1) Если
![$$ x \in A \cup B $$ $$ x \in A \cup B $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20x%20%5Cin%20A%20%5Ccup%20B%20%24%24)
, то
![$$ x \in A $$ $$ x \in A $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20x%20%5Cin%20A%20%24%24)
или
![$$ x \in B $$ $$ x \in B $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20x%20%5Cin%20B%20%24%24)
. B таком случае
![$$ f(x) \in f(A) $$ $$ f(x) \in f(A) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%28x%29%20%5Cin%20f%28A%29%20%24%24)
или
![$$ f(x) \in f(B) $$ $$ f(x) \in f(B) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%28x%29%20%5Cin%20f%28B%29%20%24%24)
, то есть
![$$ f(x) \in f(A) \cup f(B) $$ $$ f(x) \in f(A) \cup f(B) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%28x%29%20%5Cin%20f%28A%29%20%5Ccup%20f%28B%29%20%24%24)
. Значит выполняется включение
![$$ f(A \cup B) \subseteq f(A) \cup f(B) $$ $$ f(A \cup B) \subseteq f(A) \cup f(B) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%28A%20%5Ccup%20B%29%20%5Csubseteq%20f%28A%29%20%5Ccup%20f%28B%29%20%24%24)
.
Обратно, если
![$$ y \in f(A) \cup f(B) $$ $$ y \in f(A) \cup f(B) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20y%20%5Cin%20f%28A%29%20%5Ccup%20f%28B%29%20%24%24)
, то
![$$ y \in f(A) $$ $$ y \in f(A) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20y%20%5Cin%20f%28A%29%20%24%24)
или
![$$ y \in f(B) $$ $$ y \in f(B) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20y%20%5Cin%20f%28B%29%20%24%24)
. Для определенности, пусть
![$$ y \in f(A) $$ $$ y \in f(A) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20y%20%5Cin%20f%28A%29%20%24%24)
. Тогда существует такой
![$$ x \in A $$ $$ x \in A $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20x%20%5Cin%20A%20%24%24)
, что
![$$ f(x) = y $$ $$ f(x) = y $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%28x%29%20%3D%20y%20%24%24)
. Следовательно,
![$$ x \in A \cup B $$ $$ x \in A \cup B $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20x%20%5Cin%20A%20%5Ccup%20B%20%24%24)
, откуда следует, что
![$$ y = f(x) \in f(A \cup B) $$ $$ y = f(x) \in f(A \cup B) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20y%20%3D%20f%28x%29%20%5Cin%20f%28A%20%5Ccup%20B%29%20%24%24)
, то есть выполнено включение
![$$ f(A) \cup f(B) \subseteq f(A \cup B) $$ $$ f(A) \cup f(B) \subseteq f(A \cup B) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%28A%29%20%5Ccup%20f%28B%29%20%5Csubseteq%20f%28A%20%5Ccup%20B%29%20%24%24)
. Из двух включений следует равенство.
4.2) Если
![$$ x \in A \cap B $$ $$ x \in A \cap B $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20x%20%5Cin%20A%20%5Ccap%20B%20%24%24)
, то
![$$ x \in A $$ $$ x \in A $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20x%20%5Cin%20A%20%24%24)
и одновременно
![$$ x \in B $$ $$ x \in B $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20x%20%5Cin%20B%20%24%24)
. B таком случае
![$$ f(x) \in f(A) $$ $$ f(x) \in f(A) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%28x%29%20%5Cin%20f%28A%29%20%24%24)
и одновременно
![$$ f(x) \in f(B) $$ $$ f(x) \in f(B) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%28x%29%20%5Cin%20f%28B%29%20%24%24)
. Значит
![$$ f(x) \in f(A) \cap f(B) $$ $$ f(x) \in f(A) \cap f(B) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%28x%29%20%5Cin%20f%28A%29%20%5Ccap%20f%28B%29%20%24%24)
, то есть
![$$ f(A \cap B) \subseteq f(A) \cap f(B) $$ $$ f(A \cap B) \subseteq f(A) \cap f(B) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%28A%20%5Ccap%20B%29%20%5Csubseteq%20f%28A%29%20%5Ccap%20f%28B%29%20%24%24)
.
Пусть теперь
![$$ y \in f(A) \cap f(B) $$ $$ y \in f(A) \cap f(B) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20y%20%5Cin%20f%28A%29%20%5Ccap%20f%28B%29%20%24%24)
. Это означает, что
![$$ y \in f(A) $$ $$ y \in f(A) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20y%20%5Cin%20f%28A%29%20%24%24)
и одновременно
![$$ y \in f(B) $$ $$ y \in f(B) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20y%20%5Cin%20f%28B%29%20%24%24)
. Если отображение
![$$ f $$ $$ f $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%20%24%24)
инъективно, то существует единственный элемент
![$$ x $$ $$ x $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20x%20%24%24)
, такой, что
![$$ f(x) = y $$ $$ f(x) = y $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%28x%29%20%3D%20y%20%24%24)
и можно показать, что выполняется включение
![$$ f(A) \cap f(B) \subseteq f(A \cap B) $$ $$ f(A) \cap f(B) \subseteq f(A \cap B) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%28A%29%20%5Ccap%20f%28B%29%20%5Csubseteq%20f%28A%20%5Ccap%20B%29%20%24%24)
.
Однако, если отображение не инъективно, то могут существовать два различных элемента
![$$ x_1, x_2 $$ $$ x_1, x_2 $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20x_1%2C%20x_2%20%24%24)
множества X, таких, что
![$$ f(x_1) = f(x_2) = y $$ $$ f(x_1) = f(x_2) = y $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%28x_1%29%20%3D%20f%28x_2%29%20%3D%20y%20%24%24)
. Тогда если
![$$ x_1 \in A,\ x_2 \in B $$ $$ x_1 \in A,\ x_2 \in B $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20x_1%20%5Cin%20A%2C%5C%20x_2%20%5Cin%20B%20%24%24)
, но
![$$ x_1 \neq B,\ x_2 \neq A $$ $$ x_1 \neq B,\ x_2 \neq A $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20x_1%20%5Cneq%20B%2C%5C%20x_2%20%5Cneq%20A%20%24%24)
, то на
![$$ x_1 $$ $$ x_1 $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20x_1%20%24%24)
, ни
![$$ x_2 $$ $$ x_2 $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20x_2%20%24%24)
не содержатся в
![$$ A \cap B $$ $$ A \cap B $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20A%20%5Ccap%20B%20%24%24)
.
Как пример, пусть
![$$ X = \{ x_1, x_2, x_3 \} $$ $$ X = \{ x_1, x_2, x_3 \} $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20X%20%3D%20%5C%7B%20x_1%2C%20x_2%2C%20x_3%20%5C%7D%20%24%24)
,
![$$ Y = \{ y_1, y_2 \} $$ $$ Y = \{ y_1, y_2 \} $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20Y%20%3D%20%5C%7B%20y_1%2C%20y_2%20%5C%7D%20%24%24)
. Зададим отображение f следующим образом:
![$$ f(x_1) = y_1,\ f(x_2) = y_2,\ f(x_3) = y_2 $$ $$ f(x_1) = y_1,\ f(x_2) = y_2,\ f(x_3) = y_2 $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%28x_1%29%20%3D%20y_1%2C%5C%20f%28x_2%29%20%3D%20y_2%2C%5C%20f%28x_3%29%20%3D%20y_2%20%24%24)
Пусть теперь
![$$ A = \{ x_1, x_2 \} $$ $$ A = \{ x_1, x_2 \} $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20A%20%3D%20%5C%7B%20x_1%2C%20x_2%20%5C%7D%20%24%24)
,
![$$ B = \{ x_1, x_3 \} $$ $$ B = \{ x_1, x_3 \} $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20B%20%3D%20%5C%7B%20x_1%2C%20x_3%20%5C%7D%20%24%24)
. Тогда
![$$ A \cap B = \{ x_1 \} $$ $$ A \cap B = \{ x_1 \} $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20A%20%5Ccap%20B%20%3D%20%5C%7B%20x_1%20%5C%7D%20%24%24)
и
![$$ f(A \cap B) = y_1 $$ $$ f(A \cap B) = y_1 $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%28A%20%5Ccap%20B%29%20%3D%20y_1%20%24%24)
.
Однако,
![$$ f(A) = Y = f(B) $$ $$ f(A) = Y = f(B) $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%28A%29%20%3D%20Y%20%3D%20f%28B%29%20%24%24)
, то есть
![$$ f(A) \cap f(B) = Y = \{ y_1, y_2 \} $$ $$ f(A) \cap f(B) = Y = \{ y_1, y_2 \} $$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%20f%28A%29%20%5Ccap%20f%28B%29%20%3D%20Y%20%3D%20%5C%7B%20y_1%2C%20y_2%20%5C%7D%20%24%24)
.