Теория множеств

MandelbrotK · Сообщение **MandelbrotK** » 11 сен 2008, 16:01

Для конечных множеств A и B, доказать:

1) |A x B|=|A||B|
2) $|A \setminus B|=|A|-|A\cap B| 3) |2^A|=2^{|A|}$

Ещё не понятно вот что: $f: X\to Y, A,B\subset X$
$f(A\cap B) \subset f(A)\cap f(B)$ выплняется всегда, a равенство
$f(A\cap B) = f(A)\cap f(B)$ только, когда f - инъекция, как это нормально объяснить?

Спасибо

AV_77 · Сообщение **AV_77** » 11 сен 2008, 19:39

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|}$

Ещё не понятно вот что: $f: X\to Y, A,B\subset X$
$f(A\cap B) \subset f(A)\cap f(B)$ выплняется всегда, a равенство
$f(A\cap B) = f(A)\cap f(B)$ только, когда f - инъекция, как это нормально объяснить?

Спасибо

1), 2) Это следует из определений соответствующих операций.

3) Пусть $A = \{ a_1, a_2, \ldots, a_n \}$ . Так как подмножество однозначно определяется входящими в него элементами, то каждому подмножеству B множества A можно сопоставить строку из нулей и единиц следующим образом: на i-м месте строки стоит единица, если элемент $a_i \in B$ . Число таких строк - $$ 2^n $$

.
Можно эту задачу решить и методом индукции.

4.1) Если $x \in A \cup B$ , то $x \in A$ или $x \in B$ . B таком случае $f(x) \in f(A)$ или $f(x) \in f(B)$ , то есть $f(x) \in f(A) \cup f(B)$ . Значит выполняется включение $f(A \cup B) \subseteq f(A) \cup f(B)$ .
Обратно, если $y \in f(A) \cup f(B)$ , то $y \in f(A)$ или $y \in f(B)$ . Для определенности, пусть $y \in f(A)$ . Тогда существует такой $x \in A$ , что $$ f(x) = y $$

. Следовательно, $x \in A \cup B$ , откуда следует, что $y = f(x) \in f(A \cup B)$ , то есть выполнено включение $f(A) \cup f(B) \subseteq f(A \cup B)$ . Из двух включений следует равенство.

4.2) Если $x \in A \cap B$ , то $x \in A$ и одновременно $x \in B$ . B таком случае $f(x) \in f(A)$ и одновременно $f(x) \in f(B)$ . Значит $f(x) \in f(A) \cap f(B)$ , то есть $f(A \cap B) \subseteq f(A) \cap f(B)$ .
Пусть теперь $y \in f(A) \cap f(B)$ . Это означает, что $y \in f(A)$ и одновременно $y \in f(B)$ . Если отображение $$ f $$

инъективно, то существует единственный элемент $$ x $$

, такой, что $$ f(x) = y $$

и можно показать, что выполняется включение $f(A) \cap f(B) \subseteq f(A \cap B)$ .
Однако, если отображение не инъективно, то могут существовать два различных элемента $$ x_1, x_2 $$

множества X, таких, что $$ f(x_1) = f(x_2) = y $$

. Тогда если $x_1 \in A,\ x_2 \in B$ , но $x_1 \neq B,\ x_2 \neq A$ , то на $$ x_1 $$

, ни

не содержатся в $A \cap B$ .

Как пример, пусть $X = \{ x_1, x_2, x_3 \}$ , $Y = \{ y_1, y_2 \}$ . Зададим отображение f следующим образом:
$f(x_1) = y_1,\ f(x_2) = y_2,\ f(x_3) = y_2$
Пусть теперь $A = \{ x_1, x_2 \}$ , $B = \{ x_1, x_3 \}$ . Тогда $A \cap B = \{ x_1 \}$ и $f(A \cap B) = y_1$ .
Однако, $$ f(A) = Y = f(B) $$

, то есть $f(A) \cap f(B) = Y = \{ y_1, y_2 \}$ .

yourdomain.com