Приложение 3. Задачи / Парадоксы теории множеств

Иван Ященко

Приложение 3. Задачи

Набор задач этого раздела взят из листков, предлагавшихся учащимся выпуска 2002 года школы № 57 г. Москвы в 8-м, 10-м и 11-м классах.

Операции над множествами

Множества $A$ и $B$ называются равными, если каждый элемент множества $A$ принадлежит множеству $B$ , и наоборот. Обозначение: $A = B$ .

Множество $A$ называется подмножеством множества $B$ , если каждый элемент множества $A$ принадлежит множеству $B$ . Обозначение: $A \subset B$ .

1. Для каждых двух из следующих множеств указать, является ли одно из них подмножеством другого:

$\{1\},\ \{1,2\},\ \{1,2,3\},\ \{\{1\},2,3\},\ \{\{1,2\},3\},\ \{3,2,1\},\ \{\{2,1\}\}$ .

2. Докажите, что множество $A$ тогда и только тогда является подмножеством множества $B$ , когда каждый элемент, не принадлежащий $B$ , не принадлежит $A$ .

3. Докажите, что для произвольных множеств $A$ , $B$ и $C$

а) $A \subset A$ ;
б) если $A \subset B$ и $B \subset C$ , то $A \subset C$ ; в) $A = B$ , если и только если $A \subset B$ и $B \subset A$ .

Множество называется пустым, если оно не содержит ни одного элемента. Обозначение: $\varnothing$ .

4. Сколько элементов у каждого из следующих множеств?

$\varnothing,\ \{1\},\ \{1,2\},\ \{1,2,3\},\ \{\{1\},2,3\},\ \{\{1,2\},3\},\ \{\varnothing\},\ \{\{2,1\}\}$

5. Сколько подмножеств у множества из трех элементов?

6. Может ли у множества быть ровно а) $0$ ; б*) $7$ ; в) $16$ подмножеств?

Объединением множеств $A$ и $B$ называется множество, состоящее из таких $x$ , что $x \in A$ или $x \in B$ . Обозначение: $A \cup B$ .

Пересечением множеств $A$ и $B$ называется множество, состоящее из таких $x$ , что $x \in A$ и $x \in B$ . Обозначение: $A \cap B$ .

Разностью множеств $A$ и $B$ называется множество, состоящее из таких $x$ , что $x \in A$ и $x \notin B$ . Обозначение: $A \setminus B$ .

7. Даны множества $A = \{1,3,7,137\},\ B = \{3,7,23\},\ C = \{0,1,3, 23\},\ D = \{0,7,23,1998\}$ . Найдите множества:

а) $A \cup B$ ;

б) $A \cap B$ ;

в) $(A \cap B)\cup D$ ;

г) $C\cap(D\cap B)$ ;

д) $(A \cup B)\cap(C\cup D)$ ;

е) $(A\cup(B\cap C))\cap D$ ;

ж) $(C\cap A)\cup((A\cup(C\cap D))\cap B)$ ;

з) $(A \cup B) \setminus (C\cap D)$ ;

и) $A \setminus (B \setminus (C \setminus D))$ ;

к) $((A \setminus (B\cup D)) \setminus C)\cup B$ .

8. Пусть $A$ — множество четных чисел, а $B$ — множество чисел, делящихся на 3. Найдите $A \cap B$ .

9. Докажите, что для любых множеств $A$ , $B$ , $C$

а) $A \cup B = B \cup A$ , $A \cap B = B \cap A$ ;

б) $A\cup(B\cup C) = (A \cup B)\cup C$ , $A\cap(B\cap C) = (A \cap B)\cap C$ ;

в) $A\cap(B\cup C) = (A \cap B)\cup(A\cap C)$ , $A\cup(B\cap C) = (A \cup B)\cap(A\cup C)$ ;

г) $A \setminus (B\cup C) = (A \setminus B)\cap(A \setminus C)$ ,

$A \setminus (B\cap C) = (A \setminus B)\cup(A \setminus C)$ .

10. Верно ли, что для любых множеств $A$ , $B$ , $C$

а) $A\cap\varnothing = \varnothing$ , $A\cup\varnothing = A$ ;

б) $A \cup A = A$ , $A \cap A = A$ ;

в) $A \cap B = A \Leftrightarrow A \subset B$ ;

г) $(A \setminus B)\cup B = A$ ;

д) $A \setminus (A \setminus B) = A \cap B$ ;

е) $A \setminus (B \setminus C) = (A \setminus B)\cup(A\cap C)$ ;

ж) $(A \setminus B)\cup(B \setminus A) = A \cup B$ ?

Отображения множеств

Если каждому элементу $x$ множества $X$ поставлен в соотвествие ровно один элемент $f(x)$ множества $Y$ , то говорят, что задано отображение $f$ из множества $X$ в множество $Y$ . При этом, если $f(x) = y$ , то элемент $y$ называется образом элемента $x$ при отображении $f$ , а элемент $x$ называется прообразом элемента $y$ при отображении $f$ . Обозначение: $f\colon X \to Y$ .

11. Нарисуйте всевозможные отображения из множества $\{7,8,9\}$ в множество $\{0,1\}$ .

Пусть $f\colon X \to Y$ , $y \in Y$ , $A \subset X$ , $B \subset Y$ . Полным прообразом элемента $y$ при отображении $f$ называется множество $\{x \in X \mid f(x) = y\}$ . Обозначение: $f^{-1}(y)$ . Образом множества $A \subset X$ при отображении $f$ называется множество $\{f(x) \mid x \in A\}$ . Обозначение: $f(A)$ . Прообразом множества $B \subset Y$ называется множество $\{x \in X \mid f(x) \in B\}$ . Обозначение: $f^{-1}(B)$ .

12. Для отображения $f\colon \{0,1,3,4\} \to \{2,5,7,18\}$ , заданного картинкой, найдите $f(\{0,3\})$ , $f(\{1,3,4\})$ , $f^{-1}(2)$ , $f^{-1}(\{2,5\})$ , $f^{-1}(\{5,18\})$ .

13. Пусть $f\colon X \to Y$ , $A_1, A_2 \subset X$ , $B_1, B_2 \subset Y$ . Всегда ли верно, что

а) $f(X) = Y$ ;

б) $f^{-1}((Y) = X$ ;

в) $f(A_1\cup A_2) = f(A_1)\cup f(A_2)$ ;

г) $f(A_1\cap A_2) = f(A_1)\cap f(A_2)$ ;

д) $f^{-1}(B_1\cup B_2) = f^{-1}(B_1)\cup f^{-1}(B_2)$ ;

е) $f^{-1}(B_1\cap B_2) = f^{-1}(B_1)\cap f^{-1}(B_2)$ ;

ж) если $f(A_1) \subset f(A_2)$ , то $A_1 \subset A_2$ ;

з) если $f^{-1}(B_1) \subset f^{-1}(B_2)$ , то $B_1 \subset B_2$ ?

Композицией отображений $f\colon X \to Y$ и $g\colon Y \to Z$ называется отображение, сопоставляющее элементу $x$ множества $X$ элемент $g(f(x))$ множества $Z$ . Обозначение: $g\circ f$ .

14. Докажите, что для произвольных отображений $f\colon X \to Y$ , $g\colon Y \to Z$ и $h\colon Z \to W$ выполняется следующее: $h\circ(g\circ f) = (h\circ g)\circ f$ .

15. Пусть $f\colon \{1,2,3,5\} \to \{0,1,2\}$ , $g\colon \{0,1,2\} \to \{3,7,37,137\}$ , $h\colon \{3,7,37,137\} \to \{1,2,3,5\}$ — отображения, показанные на рисунке:

Нарисуйте картинки для следующих отображений:

а) $g\circ f$ ;

б) $h\circ g$ ;

в) $f\circ h\circ g$ ;

г) $g\circ h\circ f$ .

Отображение $f\colon X \to Y$ называется биективным, если для каждого $y \in Y$ найдется ровно один $x \in X$ такой, что $f(x) = y$ .

16. Пусть $f\colon X \to Y$ , $g\colon Y \to Z$ . Верно ли, что если $f$ и $g$ биективны, то и $g \circ f$ биективно?

17. Пусть $f\colon \{1,2,3\} \to \{1,2,3\}$ , $g\colon \{1,2,3\} \to \{1,2,3\}$ , — отображения, изображенные на рисунке:

Нарисуйте картинки для следующих отображений:

а) $g\circ f\circ g$ ;

б) $f\circ g\circ f$ ;

в) $f\circ g\circ f\circ g\circ f\circ g$ .

18. Про каждые два из следующих множеств выясните, существует ли биекция из первого во второе (надлежит считать, что ноль — натуральное число):

а) множество натуральных чисел;

б) множество четных натуральных чисел;

в) множество натуральных чисел без числа 3.

Отображение $g \colon Y \to X$ называется обратным к отображению $f\colon X \to Y$ , если $g(f(x))=x$ и $f(g(y))=y$ для любых $x\in X$ и $y\in Y$ .

19. Каким должно быть отображение, чтобы у него

а) не было обратного;

б) было ровно одно обратное;

в) было более одного обратного.

Мощность множеств

Два множества $X$ и $Y$ называются равномощными, если существует биекция $f\colon X \to Y$ . Обозначение: $|X|=|Y|$ .

20. Докажите, что

а) $|A|=|A|$ ;

б) $|A|=|B|$ тогда и только тогда, когда $|B|=|A|$ ;

в) если $|A|=|B|$ и $|B|=|C|$ , то $|A|=|C|$ .

21. Докажите, что следующие множества равномощны:

а) любые два отрезка;

б) интервал и полуокружность без концов;

в) интервал и прямая;

г) квадрат и круг;

д) действительные числа и неотрицательные действительные числа;

е) интервал и отрезок;

ж*) отрезок и квадрат.

Множество называется счётным, если оно равномощно множеству натуральных чисел.

22. Докажите, что счётны

а) конечное объединение счётных множеств;

б) счётное объединение счётных множеств;

в) произвольное пересечение счётных множеств, не являющееся конечным множеством.

23. Докажите, что следующие множества счётны:

а) множество рациональных чисел;

б) множество конечных последовательностей нулей и единиц;

в) множество непересекающихся кругов на плоскости;

г*) множество непересекающихся букв T на плоскости.

24. Докажите, что следующие множества несчётны:

а) множество всех подмножеств натуральных чисел;

б) множество бесконечных последовательностей нулей и единиц;

в) множество всех биекций из множества натуральных чисел в себя;

г) все перечисленные множества равномощны.

25*. Множество действительных чисел равномощно множествам из предыдущей задачи.

26. Докажите, что:

а) в любом бесконечном множестве найдётся счётное подмножество;

б) множество бесконечно тогда и только тогда, когда оно равномощно некоторому своему собственному (отличному от самого себя) подмножеству;

в) при объединении бесконечного мнoжества с множеством, которое конечно или счётно, получается множество, равномощное исходному.

Метрические пространства и непрерывные отображения

Метрическим пространством называется множетсво $X$ с заданной метрикой $\rho: X\times X \to \mathbb{R}$ , удовлетворяющее следующим аксиомам:

1) $\forall x,y \in X\ \rho(x,y) \ge 0$ , причем $\rho(x,y) = 0$ , если и только если $x = y$ (неотрицательность);

2) $\forall x,y \in X\ \rho(x,y) = \rho(y,x)$ (симметричность);

3) $\forall x,y,z \in X\ \rho(x,y) + \rho(y,z) \ge \rho(x,z)$ (неравенство треугольника).

27. Докажите, что следующие пары $(X,\rho)$ являются метрическими пространствами:

а) $X=\mathbb{R},\ \rho(x,y)=|x-y|$ ;

б) $X=\mathbb{R}^2,\ \rho_2((x_1,y_1),(x_2,y_2))=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ ;

в) $X=C[a,b]$ — множество непрерывных на $[a,b]$ функций,

$\rho(f,g)=\sup_{x\in[a,b]}|f(x)-g(x)|$ .

г) $X = S^1$ — окружность с центром $O$ , $\rho(x,y)$ — величина центрального угла $xOy$ ;

д) $X$ — множестов движений плоскости,

$\rho(f,g)=\max_{x\in D}\rho_2(f(x),g(x))$ ,

где $D$ — круг единичного радиуса с центром в начале координат.

Открытым (соответственно, замкнутым) шаром радиуса $r$ в пространстве $X$ с центром в точке $x$ называется множество $U_r(x) = \{y \in x \colon \rho(x,y) < r\}$ (соответственно, $B_r(x) = \{y \in X \colon \rho(x,y) \le r\}$ ).

Внутренней точкой множества $U \subset X$ называется такая точка, которая содержится в $U$ вместе с некоторым шаром ненулевого радиуса.

Множество, все точки которого внутренние, называется открытым. Открытое множество, содержащее данную точку, называется окрестностью этой точки.

Предельной точкой множества $F \subset X$ называется такая точка, в любой окрестности которой содержится бесконечно много точек множества $F$ .

Множество, которое содержит все свои предельные точки, называется замкнутым (сравните это определение с тем, которое было дано в приложении 1).

28. Докажите, что

а) множество открыто тогда и только тогда, когда его дополнение замкнуто;

б) конечное объединение и счетное пересечение замкнутых множеств замкнуто;

в) счетное объединение и конечное пересечение открытых множеств открыто.

29. Докажите, что

а) множество предельных точек любого множества является замкнутым множеством;

б) объединение множества $A$ и множества его предельных точек (замыкание $A$ ) является замкнутым множеством.

Отображение $f\colon X \to Y$ называется непрерывным, если прообраз каждого открытого множества открыт.

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

31. Докажите, что

а) расстояние до множества $\rho_F(x)=\inf_{y\in F}\rho(x,y)$ является непрерывной функцией;

б) множество нулей функции пункта а) совпадает с замыканием $F$ .

32. Пусть $f\colon X \to Y$ — непрерывное взаимно однозначное отображение. Верно ли, что обратное к нему непрерывно?

Непрерывное взаимно однозначное отображение $f\colon X \to Y$ , обратное к которому также непрерывно, называется гомеоморфизмом. Пространства $X$ , $Y$ , для которых такое отображение существует, называются гомеоморфными.

33. Для каждой пары из следующих множеств установите, гомеоморфны ли они:

а) прямая;

б) отрезок;

в) окружность;

г) буква Т;

д) буква Ы;

е) круг;

ж) плоскость;

з) граница квадрата;

и) плоскость без начала координат.

34. Для каких пар $X$ , $Y$ пространств из предыдущей задачи существует непрерывное отображение $f\colon X \to Y$ , которое не склеивает точки (т. е. $f(x) \ne f(y)$ при $x \ne y$ — такие отображения называют вложениями)?

35*. Придумайте непрерывное отображение плоскости на тор, которое было бы локальным гомеоморфизмом (т. е. у каждой точки $x$ плоскости и $f(x)$ тора существуют такие окрестности $U$ и $V$ , что $f$ гомеоморфно отображает $U$ на $V$ ).

Полнота. Теорема Бэра

Пусть $X$ — метрическое пространство. Последовательность $x_n$ его элементов называется фундаментальной, если

$\forall \varepsilon>0\ \exists n\ \forall k,m>n\ \rho(x_k,x_m)<\varepsilon$

36. Докажите, что сходящаяся последовательность фундаментальна. Верно ли обратное утверждение?

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

37. Верно ли, что пространство, гомеоморфное полному, полно?

38. Докажите, что замкнутое подпространство полного пространства само полно; полное подпространство произвольного пространства замкнуто в нем.

39. Докажите, что в полном метрическом пространстве последовательность вложенных замкнутых шаров с радиусами, стремящимися к нулю, имеет общий элемент.

40. Можно ли в предыдущей задаче убрать условие полноты пространства или стремления к нулю радиусов шаров?

Отображение $f$ метрического пространства $X$ в себя называется сжимающим, если

$\exists c\ (0\le c<1)\colon\forall x,y\in X\ \rho(f(x),f(y))<c\rho(x,y)$

41. Докажите, что сжимающее отображение непрерывно.

42. а) Докажите, что сжимающее отображение полного метрического пространства в себя имеет ровно одну неподвижную точку.

б) На карту России масштаба 1:5 000 000 положили карту России масштаба 1:20 000 000. Докажите, что найдется точка, изображения которой на обеих картах совпадут.

43*. Существует ли неполное метрическое пространство, в котором верно утверждение задачи 15, а?

Подмножество метрического пространства называется всюду плотным, если его замыкание совпадает со всем пространством; нигде не плотным – если его замыкание не имеет непустых открытых подмножеств (сравните это определение с тем, которое было дано в приложениие 2).

44. а) Пусть $a, b, \alpha, \beta \in \mathbb{R}$ и $a < \alpha < \beta < b$ . Докажите, что множество непрерывных функций на $[a,b]$ , монотонных на $[\alpha, \beta]$ , нигде не плотно в пространстве всех непрерывных функций на $[a,b]$ c равномерной метрикой.

б) Пусть $a, b, c, \varepsilon \in \mathbb{R}$ и $a < b$ , $c > 0$ , $\varepsilon > 0$ . Тогда множество непрерывных функций на $[a,b]$ , таких что

$\exists x\in[a,b]\colon \forall y\,(0<|x-y|<\varepsilon) \Rightarrow \frac{|f(x)-f(y)|}{|x-y|}\le c$

нигде не плотно в пространстве всех непрерывных функций на $[a,b]$ c равномерной метрикой.

45. (Обобщенная теорема Бэра.) Докажите, что полное метрическое пространство нельзя представить в виде объединения счетного числа нигде не плотных множеств.

46. Докажите, что множество непрерывных, не монотонных ни на каком непустом интервале и нигде не дифференцируемых функций, определенных на отрезке $[0,1]$ , всюду плотно в пространстве всех непрерывных функций на $[0,1]$ с равномерной метрикой.

47*. Пусть $f$ — дифференцируемая функция на отрезке $[0,1]$ . Докажите, что ее производная непрерывна на всюду плотном множестве точек.

<<< |1|…|13|14|15|16|17|

Содержание

Комментарии: 0

Похожее

Парадоксы теории множеств и их философская интерпретация

Парадоксы являются следствием дихотомии языка и мышления, выражением глубоких диалектических (теорема Гёделя позволила проявить диалектику в процессе познания) и гносеологических трудностей, связанных с понятиями предмета и предметной области в формальной логике, множества (класса) в логике и теории множеств, с употреблением принципа абстракции, позволяющего вводить в рассмотрение новые (абстрактные) объекты (бесконечность), со способами определения абстрактных объектов в науке и т. п. Поэтому не может быть дано универсального способа устранения всех парадоксов.
А нужен ли выбор? (альтернатива аксиоме выбора в теории множеств)

Михаил Раскин

Современная математика в качестве своего основания использует теорию множеств. Традиционно при анализе теоретико-множественных тонкостей используется аксиоматика Цермело-Френкеля с аксиомой выбора, обозначаемая ZFC. На аксиому выбора опираются доказательства наличия базиса в любом векторном пространстве и существования неизмеримого множества в математическом анализе. К сожалению, теория множеств обязана работать и со множествами, которые не описываются достаточно подробно и конкретно, чтобы мы могли себе их представить. В курсе будет рассмотрен один пример, к чему это приводит. Оказывается, ценой ослабления аксиомы выбора можно получить теорию множеств, в которой любая ограниченная функция на отрезке интегрируема по Лебегу. То, что используется аксиома выбора, в каком-то смысле, произошло исторически. Курс основан на статье Р.М. Соловэя о построении теории множеств, в которой все множества вещественных чисел измеримы.
«Мы не можем ждать милостей от природы», или применение метода вынуждения в построении моделей теории множеств

Михаил Раскин

В теории множеств есть несколько известных вопросов о том, следует ли из некоторых аксиом другая аксиома (или гипотеза; аксиома — это просто гипотеза, которой пользуется подавляющее большинство). Как и в других областях математики, недоказуемость можно продемонстрировать с помощью модели, в которой верны предположения, но не верна гипотеза. Для построения одного из самых известных таких примеров, модели теории множеств, в которой есть промежуточная мощность между мощностями натурального ряда и вещественной прямой, Коэн разработал метод вынуждения.
Теория множеств для начинающих

Виктор Викторов

Основные понятия, операции над множествами, тождества, свойства дополнения, правило Де Моргана, свойства симметрической разности; отображение (функция), факторотображение, отношение эквивалентности, парадокс брадобрея; упорядоченные множества, минимальный, наименьший, максимальный и наибольший элементы в упорядоченном множестве, мажоранта и миноранта; аксиома выбора, вполне упорядоченное множество.
Числа и многочлены

Проскуряков И. В.

Целью этой книги является строгое определение чисел, многочленов и алгебраических дробей и обоснование их свойств, уже известных из школы, а не ознакомление читателя с новыми свойствами. Поэтому читатель не найдет здесь новых для него фактов (за исключением, быть может, некоторых свойств, действительных и комплексных чисел), но узнает, как доказываются вещи, хорошо ему известные, начиная с «дважды два — четыре» и кончая правилами действий с многочленами и алгебраическими дробями. Зато читатель познакомится с рядом общих понятий, играющих в алгебре основную роль.
Математика на шахматной доске

Гик Е. Я.

В книге рассказывается о разнообразных связях, существующих между математикой и шахматами: о математических легендах о происхождении шахмат, об играющих машинах, о необычных играх на шахматной доске и т. д. Затронуты все известные типы математических задач и головоломок на шахматную тему: задачи о шахматной доске, о маршрутах, силе, расстановках и перестановках фигур на ней. Рассмотрены задачи «о ходе коня» и «о восьми ферзях», которыми занимались великие математики Эйлер и Гаусс. Дано математическое освещение некоторых чисто шахматных вопросов - геометрические свойства шахматной доски, математика шахматных турниров, система коэффициентов Эло.
Десять великих идей науки. Как устроен наш мир

Питер Эткинз

Эта книга предназначена для широкого круга читателей, желающих узнать больше об окружающем нас мире и о самих себе. Автор, известный ученый и популяризатор науки, с необычайной ясностью и глубиной объясняет устройство Вселенной, тайны квантового мира и генетики, эволюцию жизни и показывает важность математики для познания всей природы и человеческого разума в частности.
Алиса в Стране Смекалки

Смаллиан Рэймонд

В книге «Алиса в Стране Смекалки» кэрролловская Алиса из Страны Чудес и ее друзья раскрывают перед читателем нескончаемую вереницу задач-головоломок. Они доставят удовольствие всем любителям занимательной математики, а почитателям творчества Льюиса Кэрролла в особенности.
Математическое понимание природы

Владимир Арнольд

Сборник «Задачи для детей от 5 до 15 лет» вызвал много отзывов. И дети, и взрослые читатели часто сожалели, что там были только математические задачи, — ведь и все естествознание заслуживает столь же активного, творческого к себе отношения. Теперь я отвечаю на эти пожелания — следуя скорее Яну Амосу Каменскому, чем современным педагогам, то есть всегда стремясь быть понятным читателю, не имеющему предварительных знаний (но столь же любознательному, как большинство подростков).
Невероятные числа профессора Стюарта

Отрывок из книги «Невероятные числа профессора Стюарта» заслуженного профессора математики Уорикского университета, известного популяризатора науки Иэна Стюарта, посвященной роли чисел в истории человечества и актуальности их изучения в наше время.

Далее >>>

∀ x, y, z