дискретная-математика — Доказать континуум
Докажите, что если A ∪ B имеет мощность континуум, то A или B имеет мощность континуум. ( Замечание. Никому неизвестно, существуют ли множества промежуточной мощности между счетными и континуальными.)
задан 15 Ноя ’21 23:08
Континуум — это не утверждение! Его нельзя доказать.
(15 Ноя ’21 23:19) falcao
Хорошо, что не решить континуум!
(15 Ноя ’21 23:59) mihailm
@mihailm: по-моему, это равноценные варианты 🙂
(16 Ноя ’21 0:13) falcao
2 ответа
Вопрос уже встречался, но я не нашёл ссылку.
По теореме Кантора, плоскость RxR имеет мощность континуума. Поэтому можно считать, что плоскость представлена в виде объединения двух множеств AUB. Достаточно доказать, что мощность A или B не менее чем континуальна. Тогда по теореме Кантора — Бернштейна оно будет континуально.
Рассмотрим семейство горизонтальных прямых вида y=c. Если на каждой из этих прямых есть хотя бы одна точка из A, то такие точки образуют в A подмножество мощности не менее континуума. В противном случае найдётся прямая без точек множества A. Она целиком содержится в B, и тогда мощность B не меньше континуума.
отвечен 15 Ноя ’21 23:23
falcao
300k ● 9 ● 38 ● 55
множества — Верно ли, что множество кoнтинyyм
Верно ли, чтo множество пpямыx нa плоскости кoнтинyyм?
Правильно ли я понимаю, что надо делать так:
уравнение прямой $%ax+by+c = 0$%, где $%a,b,c$% — $%R => (a;b;c) = R * R * R = R$% что и требовалось?
задан 5 Ноя ’14 2:08
Leva319
1.7k ● 1 ● 27 ● 135
77% принятых
Не совсем так, потому что здесь нет однозначности. Прямые с пропорциональными коэффициентами в уравнении будут одинаковыми, а тройки разными, поэтому это не биекция. Но сам факт, что прямых континуум, разумеется, верен.
(5 Ноя ’14 2:25) falcao
Спасибо, но как тогда избежать повторений и доказать правильно?
(5 Ноя ’14 2:27) Leva319
1 ответ
В тех случаях, когда непосредственное построение биекции связано с трудностями, желательно применять теорему Кантора — Бернштейна. То есть доказать, что прямых не больше континуума, но и не меньше. Второе очевидно, а для первого уже годится Ваша конструкция: прямых не больше, чем троек, а последних имеется континуум. Но тут можно и по-другому сделать. Прямые однозначно задаются либо упорядоченной парой $%(k;b)$%, если это $%y=kx+b$%, либо числом $%c$%, если это $%x=c$%. Множество пар $%\mathbb R^2$% равномощно $%\mathbb R$% (по Кантору), и тогда возникают две копии $%\mathbb R$%. Их биективно отобразить на $%\mathbb R$% можно многими способами.
отвечен 5 Ноя ’14 4:23
falcao
300k ● 9 ● 38 ● 55
Спасибо, вопрос по Вашему решению: прямую можно задать y = kx + b, если она не параллельна оси OY и x = c, если она параллельна оси OY. Т.е. мы имеем пару (k;b) и с, т.е. надо отразить (R*R V R) в R. Правильно я понимаю? Как это сделать?
(5 Ноя ’14 22:32) Leva319
@Leva319: да, правильно. Доказать это дело легко, но надо оговорить, на что мы опираемся. Я предлагаю считать известными теорему Кантора — Бернштейна, а также то, что прямая и плоскость равномощны. Это всё равно используется в других задачах, поэтому можно применить, чтобы не говорить лишних слов. Тогда получается, что мощность множества, которое мы рассматриваем, не больше континуума. Плоскость равномощна прямой, а две прямые (это будет $%\mathbb R\cup\mathbb R$% в виде двух разных копий) помещаются на плоскости. Значит, наше множество не более чем континуально. Так проще всего.
(5 Ноя ’14 22:45) falcao
Т.е. R * R V R переходит в R V R, т.к. R * R —> R (плоскость, равномощна прямой). В итоге имеем R V R.
Далее Вы пишите, что R V R помещается на плоскости. Что это значит? Что R V R < R * R?
Затем Вы пишите, что множество не более, чем континуально, т.е. R V R
(5 Ноя ’14 22:55) Leva319
@Leva319: тут всё просто. Было множество прямых. Мы их закодировали в виде множества пар и чисел (по отдельности). Потом множество пар $%\mathbb R$% превратили в равномощное ему множество $%\mathbb R$%. Получилось две копии множества $%\mathbb R$%. Каждая из них равномощна числовой прямой (это имелось в виду). Рисуем на плоскости два параллельные прямые. Отсюда следует, что мощность нашего множества не превосходит мощности множества точек плоскости, то есть не больше континуума.
Если $%A$% — часть $%B$%, не равная $%B$%, то отсюда не следует $%A < B$%. Верно лишь $%A\le B$% по мощности.
Соответствия
Соответствием g между множествами X и Y будем называть тройку объектов: Г = (Х, K,G), где X — область отправления соответствия, Y — область прибытия соответствия, G — график соответствия, причём G ⊆ X × Y.
Областью определения соответствия будем называть пр1G.
Областью значений соответствия будем называть пр2G.
Соответствие называется всюду определённым, если пр1 G = X.
Соответствие называется сюръективным, если np2G = Y.
Соответствие будем называть функциональным, или функцией, если его график не содержит пар с одинаковыми первыми и различными вторыми координатами.
Соответствие называется инъективным, если его график не содержит пар с одинаковыми вторыми и различными первыми координатами.
Соответствие называется отображением X в Y, если оно всюду определено и функционально.
Соответствие называется отображением X на Y, если оно всюду определено, функционально и сюръективно.
Соответствие называется взаимно однозначным, если оно функционально и инъективно.
Соответствие называется биекцией, если оно всюду определено, сюръективно, функционально и инъективно.
Образом множества А при данном соответствии называется множество Г(В) =
Прообразом множecmвa В при данном соответствии называется множество Г -1 (В) = .
Множества называются равномощными, если между ними можно установить биекцию.
Множество называется счётным, если оно равномощно множеству натуральных чисел.
Множество называется континуальным, если оно равномощно множеству действительных чисел отрезка [0,1].
Задание 1.3.1
- Изобразить соответствие в виде графа.
- Выяснить, какими из 4 основных свойств (всюду определённость, сюръективность, функциональность, инъективность) обладает Г.
- Найти образ множества А и прообраз множества В при данном соответствии.
- Построить соответствие между бесконечными множествами, обладающее тем же набором свойств, что и Г.
- Построить соответствие между конечными множествами, обладающее набором свойств, противоположным данному. Замечание. Для данного и построенных соответствий отметить случаи отображений, указать их тип, отметить случаи биекций.
Замечание. Для данного и постоенных соответствий отметить случаи отображений, указать их тип, отметить случаи биекций.
| № | X | Y | G | A | B |
| 1 | a,b,с,d,e | 1,2,3 | (a,2),(b,3),(c,l),(d,2),(e,l) | e,c | 2,3 |
| 2 | a,b,с,d | 1,2,3,4 | (a,4),(b,3),(c,2),(d,1) | a,b | 1,3 |
| 3 | a,b,с,d | 1,2,3,4,5 | (a,3),(b,5),(c,4),(d,1) | a,c | 1,4 |
| 4 | a,b,с,d,e | 1,2,3,4 | (d,1),(b,2),(e,4),(a,3) | b,c | 1,2 |
| 5 | a,b,с,d,e | 1,2,3 | (b,2),(c,1),(e,3),(a,3) | e,c | 3,1 |
| 6 | a,b,с,d | 1,2,3,4 | (a,2),(b,3),(c,1),(a,4) | a,b | 1,2 |
| 7 | a,b,с,d,e | 1,2,3,4,5 | (a,5),(b,3),(d,1),(e,2) | d,e | 1,3 |
| 8 | a,b,с,d | 1,2,3,4 | (a,3),(b,4),(c,3),(d,1) | a,c | 1,3 |
| 9 | a,b,с | 1,2,3,4,5 | (a,2),(b,1),(c,5),(a,3) | a,b | 3,4 |
| 10 | a,b,с | 1,2,3 | (a,1),(a,3),(b,2),(c,3) | a,c | 2,3 |
| 11 | a,b,с,d | 1,2,3,4,5 | (a,2),(c,1),(d,5),(c,3) | b,c | 1,2 |
| 12 | a,b,с,d,e | 1,2,3,4 | (b,1),(c,3),(d,2),(c,1) | a,c | 1,2 |
| 13 | a,b,с,d | 1,2,3 | (a,1),(b,1),(c,3),(b,2) | b,d | 1,3 |
| 14 | a,b,с,d | 1,2,3,4 | (a,4),(b,3),(b,2),(c,3),(d,4) | a,b | 3,4 |
| 15 | a,b,с,d | 1,2,3,4 | (a,4),(c,4),(b,2),(a,3) | a,b | 2,4 |
| 16 | a,b,с,d,e | 1,2,3 | (a,2),(b,1),(d,3),(e,1) | a,b | 1,2 |
| 17 | a,b,с,d | 1,2,3,4 | (b,3),(a,2),(c,2),(d,1) | a,c | 1,4 |
| 18 | a,b,с,d | 1,2,3,4 | (a,3),(c,2),(d,1),(c,4) | c,d | 2,3 |
| 19 | a,b,с | 1,2,3,4,5 | (a,2),(b,5),(c,4),(b,3) | a,b | 2,5 |
| 20 | a,b,с,d | 1,2,3,4 | (a,1),(b,3),(a,2),(c,4) | a,b | 2,3 |
| 21 | a,b,с,d | 1,2,3,4 | (a,1),(b,3),(a,2),(c,4) | a,b | 2,3 |
| 22 | a,b,с,d | 1,2,3 | (a,1),(b,3),(c,2),(a,2) | a,b | 2,3 |
| 23 | a,b,с,d | 1,2,3,4 | (a,3),(b,4),(c,1),(d,2) | a,b | 1,4 |
| 24 | a,b,с | 1,2,3,4 | (a,3),(b,1),(c,2),(c,1) | a,c | 4,2 |
| 25 | a,b,с,d,e | 1,2,3 | (c,2),(d,1),(a,3),(b,3) | a,d | 3,1 |
| 26 | a,b,с,d | 1,2,3,4 | (b,2),(c,3),(d,1),(b,4) | b,c | 1,2 |
| 27 | a,b,с,d,e | 1,2,3,4,5 | (b,5),(c,3),(e,1),(a,2) | a,e | 1,3 |
| 28 | a,b,с,d | 1,2,3,4 | (b,3),(c,4),(d,3),(a,1) | b,d | 3,1 |
| 29 | a,b,с | 1,2,3,4,5 | (b,3),(c,4),(d,3),(a,1) | b,d | 3,1 |
| 30 | a,b,с | 1,2,3 | (b,1),(b,3),(c,2),(a,3) | a,b | 2,3 |
Пример решения заданя 1.3.1
- Изобразим соответствие в виде графа (рис. 1.3.1, а).
- Выясним, какими из свойств обладает данное соответствие. α) Соответствие не всюду определено, так как npjG — Ф X. β) Соответствие не сюръективно, так как np2G = Ф Y. γ) Соответствие не функционально, так как его график содержит две пары (Ь,1)и (Ь,5) с одинаковыми первыми и различными вторыми координатами. δ) Соответствие инъективно, так как его график G не содержит пар с одинаковыми вторыми и различными первыми координатами.
- Найдём образ Г(А)и прообраз Г -1 (В). Г(А) = , так как А = и ⊆ G Г -1 (B) = , так как В = и только (d,4) ⊆ G.
- Построим соответствие между бесконечными множествами, обладающее тем же набором свойств, что и данное соответствие. Пусть Х=[0,2], У = (-оо,+оо), G = <(x,y)\x2 +у2=1 и х>0>. Покажем, что это соответст- вие (рис. 1.3.1, б) обладает тем же набором свойств, что и данное.
α) Построенное соответствие не всюду определено, так как nptG = [0,l]*X.
β) Построенное соответствие не сюръективно, так как np2G = [-l,l]*K.
γ) Построенное соответствие не функционально, т. к., например, (ОД)еС и (0,-1)eG.
δ) Соответствие инъективно, так как его график не содержит пар с различными первыми и одинаковыми вторыми координатами.
Построим соответствие между конечными множествами, чтобы оно было всюду определено, сюръективно, функционально и не инъективно, изобразим его в виде графа (рис. 1.3.1, в) и аналитически:
Покажем, что это соответствие обладает требуемым набором свойств, что и данное.
α) Действительно, это соответствие всюду определено, так как np1G = X = .
β) Соответствие сюръективно, так как np2G = = Y.
γ) Соответствие функционально, так как в его графике нет пар с одинаковыми первыми и различными вторыми координатами.
δ) Соответствие не инъективно, так как его график состоит из двух пар (u,w)и , (v,w) с различными первыми и одинаковыми вторыми координатами.
Так как построенное соответствие всюду определено, сюръективно и функционально, оно является отображением X на Y.
Задание 1.3.2
Для соответствия Г =(X,Y,G)
- Определить набор свойств, которыми обладает данное соответствие.
- Построить соответствие между конечными множествами с набором свойств, противоположным данному, изобразив соответствие аналитически и в виде графа.
Замечание. Отметить случаи отображений и биекций.
| № | X | Y | G |
| 1 | многочлены 2 степени от одной переменной с действительными коэффичентами | R | (многочлен, его корень) |
| 2 | множество кугов на плоскости | множество точек плоскости | (круг, его центр) |
| 3 | (0, + ∞) | [-1,1] | (x,y)|x 2 |
| 4 | N | R | (x, ± 1n x) |
| 5 | R | непрерывные на [a,b] функции |  |
| 6 | вузы вашего города | жители вышего города | (вуз; человек, окончивший этот вуз) |
| 7 | (0, + ∞) | отрезки на прямой | (x, отрезок длины x) |
| 8 | фамилии студентов вашей группы | (фамилия, число букв в фамилии) | |
| 9 | окружности на плоскости | Z | (окружность, ее длина) |
| 10 | функции, определенные на [0,1] | R | (функция, ордината ее точки максимума) |
| 11 | R 2 | N |  |
| 12 | Имена студентов вашей группы | буквы русского алфавита | (имя, буква из имени) |
| 13 | N | студенты вашего вуза | (n, человек с годом рождения n) |
| 14 | [0,1] | (x,f(x)), где  |
|
| 15 | R | R 10 | (maxai,(at,a2. a10)) 1≤i≤10 |
| 16 | окружности на плоскости | прямые на плоскости | (окружность, касательная к этой оружности) |
| 17 | [P(U)] 3 | P(U) | ((A,B,C),A⌒B⌒C) |
| 18 | [0,1] | R 2 | (x,(x,y)|x 2 + y 2 = 1) |
| 19 | R | функции, непрерывные на [0,1] |  |
| 20 | P(U) | [P(U)] 3 |  |
| 21 | N | (x,y)|x — остаток от деления y на 3 | |
| 22 | [1,3] | R+ | (x,y)|(x-2) 2 + (y-2) 2 ≤1 |
| 23 | пары окружностей на плоскости | R 2 | (пара окружностей, координаты точки пересечения этих окружностей) |
| 24 | множество книг в библиотеке вашего вуза | Z | (книга, число страниц в этой книге) |
| 25 | (-4,4) | [1,6] | (x,y)|y=|x-2|+1 |
| 26 | мужчины вашего города | женщины вашего города | (x,y)|x и y состоят или когда-либо состояли друг с другом в законном браке |
| 27 | [P(U)] 2 | P(U) | ((A,B),A\B) |
| 28 | политические партии вашего города | жители вашего города | ((партия), (человек, состоящий в этой партии) |
| 29 | P(U), где U = | N | (A,|A|), где A∈ P(U) |
| 30 | пары прямых на плоскости | R | (пара прямых, абцисса точки пересечения прямых) |
Пример решения задания 1.3.2
Решим задание 1.3.2 для соответствия Г = (X,Y,G), если X = N, Y — множество непрерывных на [а,Ь] функций, а график G задан так: G =.
1. Определим набор свойств, которым обладает данное соответствие.
α) Для любого натурального числа п можно рассмотреть непрерывную функцию f(x) =
Тогда, вычисляя определённый интеграл, будем иметь: 
Итак, доказано, что данное соответствие является всюду определённым.
β) Так как для некоторых непрерывных функций на [а,b] определённый интеграл не выражается натуральным числом, то данное соответствие не является сюръективным.
γ) Покажем, что две различные функции могут иметь на рассматриваемом промежутке одинаковое значение определённого интеграла. Для этого можно рассмотреть функции
Для f(x) определённый интеграл не отрезке [а,b], как мы уже выяснили, равен n. Найдём соответствующий интеграл для g(x):
Итак, доказано, что соответствие, описанное в условии задания, не является функциональным.
δ) Так как для каждой функции её определённый интеграл на данном промежутке находится однозначно, данное соответствие является инъективным.
2. Построим соответствие между конечными множествами, чтобы оно было не всюду определено, сюръективно, функционально и не инъективно.
Пусть Г = (,, (рис. 1.3.2). Покажем, что построенное соответствие обладает требуемым набором свойств.
α) Соответствие Г не всюду определено, так как элемент с, входящий в область отправления, не имеет образа при данном соответствии.
β) Соответствие Г сюръективно, так как его область прибытия совпадает с областью значений.
γ) Соответствие Г функционально, так как его график не содержит пар с равными первыми и различными вторыми координатами.
δ) Соответствие Г не инъективно. так как в его графике пары (а,1) и (b,1) имеют различные первые и одинаковые вторые координаты.
Задание 1.3.3
Установить биекцию между множествами
Доказательство континуальности
Доказательство теоремы
Здравствуйте. Объясните, пожалуйста, подробно доказательство следующей теоремы.
Доказательство тавтологии
Выясните, справедливы ли следующие утверждения (если утверждение несправедливо, то постарайтесь.
Доказательство от противного
Доказать что (A \ (A \ B)) \ (A пересекает B) = пустое множество,методом от противного?
Доказательство выражения
Дорогие друзья. Помогите,пожалуйста,доказать это выражение: А->В, В->С |— A->С Я вот думаю.
4162 / 3034 / 914
Регистрация: 19.11.2012
Сообщений: 6,178
Сообщение было отмечено danyamatv как решение
Решение
Сообщение от danyamatv 
континуально
Никаких проблем с этой буквой. Возьмем, например, прямую, образующую угол 30 градусов с осью х-ов, и каждой точке на этой прямой поставим в соответствие буку L, вершина угла которой совпадает с этой точкой.