Помощь по Теле2, тарифы, вопросы

Открытые и замкнутые множества

Приложение 1 . Открытые и замкнутые множества

Множество M на прямой называется открытым , если каждая его точка сожержится в этом множестве вместе с некоторым интервалом. Замкнутым называется множество, содержащее все свои предельные точки (т. е. такие, что любой интервал, содержащий эту точку, пересекается со множеством еще хотя бы по одной точке). Например, отрезок является замкнутым множеством, но не является открытым, а интервал, наоборот, является открытым множеством, но не является замкнутым. Бывают множества, которые не являются ни открытыми, ни замкнутыми (например, полуинтервал). Существуют два множества, которые одновременно и замкнутые, и открытые – это пустое и все Z (докажите, что других нет). Легко видеть, что если M открыто, то [` M ] (или Z \ M – дополнение к множеству M до Z ) замкнуто. Действительно, если [` M ] не замкнуто, то оно не содержит какую-то свою предельную точку m . Но тогда m О M , причем каждый интервал, содержащий m , пересекается с множеством [` M ], т. е. имеет точку, не лежащую в M , а это противоречит тому, что M – открытое. Аналогично, тоже прямо из определения, доказывается, что если M замкнуто, то [` M ] открыто (проверьте!).

Теперь докажем следующую важную теорему.

Теорема. Любое открытое множество M можно представить в виде объединения интервалов с рациональными концами (т. е. с концами в рациональных точках).

Доказательство . Рассмотрим объединение U всех интервалов с рациональными концами, являющихся подмножествами нашего множества. Докажем, что это объединение совпадает со всем множеством. Действительно, если m – какая-то точка из M , то существует интервал (m 1 , m 2) М M , содержащий m (это следует из того, что M – открытое). На любом интервале можно найти рациональную точку. Пусть на (m 1 , m ) – это m 3 , на (m , m 2) – это m 4 . Тогда точка m покрыта объединением U , а именно, интервалом (m 3 , m 4). Таким образом, мы доказали, что каждая точка m из M покрыта объединением U . Кроме того, как очевидно следует из построения U , никакая точка, не содержащаяся в M , не покрыта U . Значит, U и M совпадают.

Важным следствием из этой теоремы является тот факт, что любое открытое множество есть счетное объединение интервалов.

Нигде не~плотные множества и~множества меры~ноль. Канторово множество>

Приложение 2 . Нигде не плотные множества и множества меры ноль. Канторово множество

Множество A называется нигде не плотным , если для любых различных точек a и b найдется отрезок [c , d ] М [a , b ], не пересекающийся с A . Например, множество точек последовательности a n = [ 1/(n )] является нигде не плотным, а множество рациональных чисел – нет.

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

Доказательство . Предположим, что существует последовательность A k нигде не плотных множеств, таких что И i A i = [a , b ]. Построим следующую последовательность отрезков. Пусть I 1 – какой-нибудь отрезок, вложенный в [a , b ] и не пересекающийся с A 1 . По определению нигде не плотного множества на отрезке I 1 найдется отрезок, не пересекающийся с множеством A 2 . Назовем его I 2 . Далее, на отрезке I 2 возьмем аналогичным образом отрезок I 3 , не пересекающийся с A 3 , и т. д. У последовательности I k вложенных отрезков есть общая точка (это одно из основных свойств действительных чисел). Эта точка по построению не лежит ни в одном из множеств A k , значит, эти множества не покрывают весь отрезок [a , b ].

Назовем множество M имеющим меру ноль , если для любого положительного e найдется последовательность I k интервалов с суммарной длиной меньше e , покрывающая M . Очевидно, что любое счетное множество имеет меру ноль. Однако бывают и несчетные множества, имеющие меру ноль. Построим одно такое, очень известное, называемое канторовым.

Возьмем отрезок . Поделим его на три равные части. Средний отрезок выкинем (рис. 11, а ). Останется два отрезка суммарной длины [ 2/3]. С каждым из них проделаем точно такую же операцию (рис. 11, б ). Останется четыре отрезка суммарной длины [ 4/9] = ([ 2/3]) \ B 2 . Продолжая так далее (рис. 11, в –е ) до бесконечности, получаем множество, которое имеет меру меньше любой наперед заданной положительной, т. е. меру ноль. Можно установить взаимно однозначное соответствие между точками этого множества и бесконечными последовательностями нулей и единиц. Если при первом "выкидывании" наша точка попала в правый отрезок, поставим в начале последовательности 1, если в левый – 0 (рис. 11, а ). Далее, после первого "выкидывания", получаем маленькую копию большого отрезка, с которой поступаем точно так же: если наша точка после выкидывания попала в правый отрезок, поставим 1, если в левый – 0, и т. д. (проверьте взаимную однозначность), рис. 11, б , в . Поскольку множество последовательностей нулей и единиц имеет мощность континуум, канторово множество также имеет мощность континуум. Кроме того, несложно доказать, что оно нигде не плотно. Однако неверно, что оно имеет строгую меру ноль (см. определение строгой меры). Идея доказательства этого факта в следующем: возьмем последовательность a n , очень быстро стремящуюся к нулю. Для этого подойдет, например, последовательность a n = [ 1/(2 2 n )]. После чего докажем, что этой последовательностью нельзя покрыть канторово множество (проделайте это!).

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

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

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

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

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

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

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

а) A М A ; б) если A М B и B М C , то A М C ;

в) A = B , если и только если A М B и B М A .

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

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

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

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

Объединением множеств A и B x , что x О A или x О B . Обозначение: A И B .

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

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

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

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

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

а) A И B = B И A , A З B = B З A ;

б) A И (B И C ) = (A И B )И C , A З (B З C ) = (A З B )З C ;

в) A З (B И C ) = (A З B )И (A З C ), A И (B З C ) = (A И B )З (A И C );

г) A \ (B И C ) = (A \ B )З (A \ C ), A \ (B З C ) = (A \ B )И (A \ C ).

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

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

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

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

Пусть f : X ® Y , y О Y , A М X , B М Y . Полным прообразом элемента y при отображении f называется множество {x О X | f (x ) = y }. Обозначение: f - 1 (y ). Образом множества A М X при отображении f называется множество {f (x ) | x О A }. Обозначение: f (A ). Прообразом множества B М Y называется множество {x О X | f (x ) О B }. Обозначение: f - 1 (B ).

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

13. Пусть f : X ® Y , A 1 , A 2 М X , B 1 , B 2 М Y . Всегда ли верно, что

а) f (X ) = Y ;

б) f - 1 (Y ) = X ;

в) f (A 1 И A 2) = f (A 1)И f (A 2);

г) f (A 1 З A 2) = f (A 1)З f (A 2);

д) f - 1 (B 1 И B 2) = f - 1 (B 1)И f - 1 (B 2);

е) f - 1 (B 1 З B 2) = f - 1 (B 1)З f - 1 (B 2);

ж) если f (A 1) М f (A 2), то A 1 М A 2 ;

з) если f - 1 (B 1) М f - 1 (B 2), то B 1 М B 2 ?

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

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

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

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

а) g ° f ; б) h ° g ; в) f ° h ° g ; г) g ° h ° f .

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

16. Пусть f : X ® Y , g : Y ® Z . Верно ли, что если f и g биективны, то и g ° f биективно?

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

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

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

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

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

Метрическим пространством называется множетсво X с заданной метрикой r : X ×X ® Z

1) " x ,y О X r (x ,y ) і 0, причем r (x ,y ) = 0, если и только если x = y (неотрицательность ); 2) " x ,y О X r (x ,y ) = r (y ,x ) (симметричность ); 3) " x ,y ,z О X r (x ,y ) + r (y ,z ) і r (x ,z ) (неравенство треугольника ). 19 19. X

а) X = Z , r (x ,y ) = | x - y | ;

б) X = Z 2 , r 2 ((x 1 ,y 1),(x 2 ,y 2)) = Ц {(x 1 - x 2) 2 + (y 1 - y 2) 2 };

в) X = C [a ,b a ,b ] функций,

Открытым (соответственно, замкнутым ) шаром радиуса r в пространстве X с центром в точке x называется множество U r (x ) = {y О x : r (x ,y ) < r } (соответственно, B r (x ) = {y О X : r (x ,y ) Ј r }).

Внутренней точкой множества U М X U

открытым окрестностью этой точки.

Предельной точкой множества F М X F .

замкнутым

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

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

б) объединение множества A замыкание A

Отображение f : X ® Y называется непрерывным

22.

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

F (x ) = inf y О F r (x ,y

F .

24. Пусть f : X ® Y – . Верно ли, что обратное к нему непрерывно?

Непрерывное взаимно однозначное отображение f : X ® Y гомеоморфизмом . Пространства X , Y гомеоморфными .

25.

26. Для каких пар X , Y f : X ® Y , которое не склеивает точки (т. е. f (x ) № f (y ) при x № y вложениями )?

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

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

Метрическим пространством называется множетсво X с заданной метрикой r : X ×X ® Z , удовлетворяющее следующим аксиомам:

1) " x ,y О X r (x ,y ) і 0, причем r (x ,y ) = 0, если и только если x = y (неотрицательность ); 2) " x ,y О X r (x ,y ) = r (y ,x ) (симметричность ); 3) " x ,y ,z О X r (x ,y ) + r (y ,z ) і r (x ,z ) (неравенство треугольника ). 28. Докажите, что следующие пары (X ,r ) являются метрическими пространствами:

а) X = Z , r (x ,y ) = | x - y | ;

б) X = Z 2 , r 2 ((x 1 ,y 1),(x 2 ,y 2)) = Ц {(x 1 - x 2) 2 + (y 1 - y 2) 2 };

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

Открытым (соответственно, замкнутым ) шаром радиуса r в пространстве X с центром в точке x называется множество U r (x ) = {y О x : r (x ,y ) < r } (соответственно, B r (x ) = {y О X : r (x ,y ) Ј r }).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

а) расстояние до множества r F (x ) = inf y О F r (x ,y ) является непрерывной функцией;

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

33. Пусть f : X ® Y

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

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

35. Для каких пар X , Y пространств из предыдущей задачи существует непрерывное отображение f : X ® Y , которое не склеивает точки (т. е. f (x ) № f (y ) при x № y – такие отображения называют вложениями )?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

45. а) Пусть a , b , a , b О Z и a < a < b < b . Докажите, что множество непрерывных функций на [a ,b ], монотонных на , нигде не плотно в пространстве всех непрерывных функций на [a ,b ] c равномерной метрикой.

б) Пусть a , b , c , e О Z и a < b , c > 0, e > 0. Тогда множество непрерывных функций на [a ,b ], таких что

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

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

48*. Пусть f – дифференцируемая функция на отрезке . Докажите, что ее производная непрерывна на всюду плотном множестве точек. Это определение лебеговой меры ноль. Если счетное число интервалов заменить на конечное, то получится определение жордановой меры ноль.

Результат операции “*” определяется как и в таблице Пифагора. Например, “произведение” 3 * 4 равно числу, стоящему на пересечении строки с номером 3 и столбца с номером 4. В нашем случае это число равно 2. Следовательно, 3 * 4 = 2. Как вы думаете, по какому правилу была заполнена эта таблица?

Заметим, что результат выполнения операции “*” над числами из множества {0, 1, 2, ..., 9} является числом из этого же множества. В таких случаях говорят, что множество замкнуто относительно операции, а операция называется алгебраической .

Вы, наверное, уже обратили внимание на то, что таблица симметрична относительно диагонали
(0, 1, 4, 9, 6, 5, 6, . . .). Это говорит о том, что операция “*” обладает свойством коммутативности , то есть для любых чисел a и b из множества {0, 1, 2, ..., 9} выполняется равенство: a * b = b * a .

Используя таблицу, вы сможете убедиться, что выполняется равенство (2 * 3) * 4 = 2 * (3 * 4). Набравшись терпения и перебрав все упорядоченные тройки чисел, вы убедитесь, что новая операция обладает свойством ассоциативности , то есть для любых чисел a , b , c из множества {0, 1, 2, ..., 9} выполняется равенство: (a * b ) * c = a * (b * c ).

Проверьте, будет ли множество {0, 1, 2, ..., 9} замкнуто относительно умножения, задаваемого таблицей Пифагора.

Р ассмотренные примеры могут создать у вас впечатление, что как бы вы ни вводили операцию над числами, она всегда будет коммутативной и ассоциативной. Не будем спешить с выводом.

Рассмотрим еще одну операцию. Обозначим ее через “o” и назовем операцией “Круг”. Она определяется таблицей:

Попытайтесь найти закономерность, по которой составлена данная таблица. Опираясь на эту закономерность, впишите в таблицу пропущенные результаты. Будет ли операция “o” алгебраической? Докажите, что операция “o” коммутативна . Однако эта операция не ассоциативна ! Чтобы убедиться в этом, подберите три числа m , n и k , для которых m o (n o k ) ¹ (m o n ) o k .

П редставим вам еще одну операцию: -.

Введем ее на множестве натуральных чисел так: m - n = m n .

Например, 2 - 3 = 2 3 = 8; 3 - 2 = 3 2 = 9.

Будет ли операция “-” алгебраической? Рассмотренного выше примера достаточно, чтобы убедиться, что новая операция не коммутативна .

Вычислите результат выполнения операции
2 - (1 - 3), а затем проверьте равенство 2 - (1 - 3) =
= (2 - 1) - 3. Если вы все сделаете правильно, то сможете сказать, что операция “-” не ассоциативна .

1. Являются ли алгебраическими операции сложения и умножения на множестве:

а) четных чисел; б) нечетных чисел?

2. Является ли алгебраической операция вычитания на множестве:

а) натуральных чисел; б) целых чисел?

3. Является ли алгебраической операция деления на множестве:

а) ненулевых целых чисел;

б) ненулевых рациональных чисел?

4. Покажите, что операция

x D y = x + y – 3

5. Покажите, что операция

x Ñ y = x + y – xy

является алгебраической на множестве всех целых чисел. Будет ли эта операция ассоциативной и/или коммутативной?

6. По аналогии с таблицей Пифагора составьте свою таблицу, определяющую операцию “à” над числами {0, 1, 2, 3, 4}. Результат m à n операции над числами m и n в этой таблице должен равняться остатку от деления на 5 обычного произведения mn .

Будет ли операция “à” алгебраической? Если да, то будет ли она ассоциативной и/или коммутативной?

7. Придумайте несколько своих примеров операций над числами.

Какие из них будут алгебраическими? Какие из ваших алгебраических операций будут ассоциативными и/или коммутативными?

Для тех, кто хочет вести секретную переписку с друзьями

О днажды Фома получил от одного из своих друзей телеграмму.

Кто такой Фома? О! Это личность весьма примечательная. Ничему на слово не верит, все пытается делать по-своему. Любит, с одной стороны, находить новое решение старых проблем и, с другой стороны, использовать старые знания для преодоления новых трудностей. Любит читать самые разные математические книги, разыскивать в них нестандартные ситуации и находить из них выход. А больше всего любит сам такие ситуации создавать.

Так вот, телеграмма была какой-то странной. Вот что в ней было написано:

“йажзеирпончорсмедж”.

Сможете ли вы “прочитать” этот текст? Фома же, немного подумав, понял секрет этой телеграммы. В ней было приглашение в гости. Он решил ответить в том же духе. Сочинил ответную телеграмму и зашифровал ее таким же способом. Получилась запись из двух строк: “приеду в субботу встречайте”, “етйачертсвутоббусвудеирп”.

Однако Фоме захотелось придумать более интересную шифровку. Он разбил текст своей телеграммы на две равные части и каждую из них зашифровал по старому методу:

П осле окончания шифровки Фома захотел всю свою переписку с другом вести только зашифрованными текстами, меняя время от времени способ шифровки. Поэтому он рьяно взялся за разработку шифра.

Буквы исходного текста он решил заменять номерами позиций, которые занимают эти буквы. Вот какой список номеров получил Фома для телеграммы друга: (1, 2, 3, ..., 18).

Затем он заметил, что зашифрованный текст отличается от исходного только измененным порядком букв. Как изменяется порядок букв, легко увидеть с помощью тех же номеров позиций. Например, зашифрованный текст телеграммы друга Фома теперь смог представить в виде списка: (18, 17, 16, ..., 3, 2, 1).

Сопоставление этих двух списков дает ключ к шифровке текста:
.

Символьная запись читается так: “1 переходит в 18”. (Вместо нее часто используется другая запись: 1 ® 18.)

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

Если направление стрелок сменить на противоположное, то та же двустрочная таблица будет определять порядок расшифровки текста. Например, буква, стоящая в зашифрованном тексте в 18-й позиции, должна занять в расшифрованном тексте первую позицию.

Наконец, если первая строка будет всегда связана с исходным текстом, то отпадет необходимость в использовании стрелок. (При шифровке исходным текстом является шифруемый текст, а при расшифровке – зашифрованный.)

Поняв все это, Фома быстро записал ключ ко 2-ой шифровке своей телеграммы:

.

Осталось только сообщить каким-либо образом
этот ключ своему другу – и тайна переписки будет гарантирована!

Если идеи Фомы вы поняли, то вот вам его девиз в зашифрованном виде:

“водянойпероревряй”.

Оно зашифровано ключом:

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

.

Здесь в верхней строке стоят все натуральные числа от 1 до n в возрастающем порядке. Нижняя строка получается некоторой перестановкой чисел из верхней строки. Вся таблица в целом называется подстановкой порядка n .

В ернемся к Фоме. С помощью подстановки-ключа

он зашифровал сообщение, состоящее из одного слова, и отправил его другу. Нерасшифрованное сообщение тот зашифровал еще раз, но уже с помощью другого ключа:

.

Получившееся дважды зашифрованное сообщение он адресовал вам:

“сноас”.

Расшифруйте это сообщение.

Процесс расшифровки вы можете провести значительно быстрее, если будете знать, как над подстановками выполняется одна алгебраическая операция. Эта операция называется умножением подстановок . (При желании вы можете назвать ее по-другому, ибо она никак не связана с обычным умножением чисел.)

Рассмотрим на примере, как она выполняется. Умножим подстановки, с помощью которых шифровалось сообщение Фоме:

.

Процедура умножения сводится к последовательному проведению подстановок.

В первой подстановке (А ) 1 ® 5;

во второй подстановке (В ) 5 ® 1.

В итоге получаем: 1 ® 1.

Аналогично, из “2 ® 2” и “2 ® 3” следует: “2 ® 3”. Проведя еще три рассуждения такого типа, получим подстановку-произведение

.

Заметим, что произведение определено только для подстановок с одинаковым числом столбцов.

Используя подстановку AB как шифратор, вы можете теперь в один прием расшифровать сообщение Фомы “сноас”. Заодно проконтролируете себя.

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

Занимаясь расшифровкой сообщений, вы познакомились с алгебраической операцией над новыми объектами – подстановками.

Е сли кого-то из вас заинтересовали не только шифровки, но и сами по себе подстановки, то вы можете лучше познакомиться с ними, выполнив следующие задания.

1. Найдите произведения подстановок:

2. Найдите произведение ВА подстановок А и В , рассмотренных выше. Используя подстановку ВА как шифратор, расшифруйте еще раз сообщение “сноас”. Сравните расшифрованный текст с результатом предыдущей расшифровки.

Если вы выполните задание 2, то сможете сказать, обладает ли умножение подстановок свойством коммутативности .

Можно показать, что умножение подстановок обладает свойством ассоциативности .

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

Подстановка

называется тождественной . Ее обозначают через E .

Как вы сами легко установите, тождественная подстановка не меняет текста сообщения. В этом случае говорят, что сообщение идет открытым текстом.

Определение 19. МножествоЕ называетсяоткрытым , если все его точки являются внутренними, то есть если оно не содержит своих граничных точек.

Определение 20. МножествоЕ называетсязамкнутым , если оно содержит все свои предельные точки, то есть. (Иначе,
).

Пример 1. Любоеn -мерный интеграл – открытое множество. Любой отрезок – замкнутое множество.

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

Пример 2. Пустое множество следует считать замкнутым, хотя оно в то же время является и открытым. МножествоR действительных чисел одновременно является и замкнутым, и открытым.

Множество Q рациональных чисел ни замкнуто, ни открыто. Линейный полуинтервал - ни замкнутое, ни открытое множество.

Теорема 3. Любой шарS (a , r ) - открытое множество.

Доказательство:

Пусть . Возьмём
. Докажем, что шар
(это будет означать, что любая точка шара
- внутренняя, то есть
- открытое множество). Возьмём. Докажем, что
, для этого оценим расстояние
:

Следовательно,
, то есть
, то естьS (a , r ) - открытое множество.

Теорема 4. Производное множество
любого множестваE замкнуто.

Доказательство:

Пусть
. Тогдав любой окрестности
точкисуществует хотя бы одна точкамножества
, отличная от. Так как- предельная точка множестваE , то в любой её окрестности (в том числе сколь угодно малой, содержащейся в
) существует хотя бы одна точкамножестваE , отличная от точки. Таким образом, по определению точкаявляется предельной точкой для множестваE . Итак,
, что по определению означает замкнутость множестваE .

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

Свойства открытых и замкнутых множеств

Теорема 5. Объединение любого конечного числа замкнутых множеств является замкнутым множеством.

Доказательство:

Пусть
- замкнутые множества. Докажем, что
- замкнутое множество.

Пусть - предельная точка множества

. Тогда- предельная точка хотя бы одного из множеств
(доказывается от противного). Так как- замкнутое множество, то
. Но тогда
. Итак, любая предельная точка множества
ему принадлежит, то есть
замкнуто.

Теорема 6. Пересечение любого числа замкнутых множеств является замкнутым множеством.

Доказательство:

Пусть
- любая совокупность замкнутых множеств. Докажем, что
- замкнутое множество.

Пусть - предельная точка множества

. Тогда по теореме 1 в любой окрестности

. Но все точки множества
являются и точками множеств
. Следовательно, в
содержится бесконечно много точек из
. Но все множествазамкнуты, поэтому

и
, то есть
замкнуто.

Теорема 7. Если множествоF замкнуто, то его дополнениеCF открыто.

Доказательство:

Пусть . Так как
замкнуто, тоне является его предельной точкой (
). Но это означает, что существует окрестность
точки, не содержащая точек множестваF , то есть
. Тогда
и поэтому- внутренняя точка множества
. Так как- произвольная точка множестваCF , то все точки этого множества являются внутренними, то естьCF открыто.

Теорема 8. Если множествоG открыто, то его дополнениеCG замкнуто.

Доказательство:

Пусть вместе с некоторой окрестностью. Следовательно,не является предельной точкой множестваCG . Итак,
не является предельной точкой для
, то есть
содержит все свои предельные точки. По определению,
замкнуто.

Теорема 9. Объединение любого числа открытых множеств является открытым множеством.

Доказательство:

Пусть
- произвольная совокупность открытых множестви
. Докажем, что- открытое множество. Имеем:

.

Так как множества открыты
, то по теореме 8 множества
замкнуты
. Тогда по теореме 6 их пересечение

открыто.

Теорема 10. Пересечение любого конечного числа открытых множеств является открытым множеством.

Доказательство:

Пусть
- пересечение любого конечного числа открытых множеств
. Докажем, что- открытое множество. Имеем:

.

Так как множества открыты
, то по теореме 8 множества
замкнуты
. Тогда по теореме 5 их объединение

замкнуто. По теореме 7 множество
открыто.

Одна из основных задач теории точечных множеств - изучение свойств различных типов точечных множеств. Познакомимся с этой теорией на двух примерах и изучим свойства так называемых замкнутых и открытых множеств.

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

Приведем примеры замкнутых и открытых множеств .

Всякий отрезок есть замкнутое множество, а всякий интервал (a, b) - открытое множество. Несобственные полуинтервалы и замкнуты , а несобственные интервалы и открыты . Вся прямая является одновременно и замкнутым и открытым множеством. Удобно считать пустое множество тоже одновременно замкнутым и открытым. Любое конечное множество точек на прямой замкнуто, так как оно не имеет предельных точек.

Множество, состоящее из точек:

замкнуто; это множество имеет единственную предельную точку x=0, которая принадлежит множеству.

Основная задача состоит в том, чтобы выяснить, как устроено произвольное замкнутое или открытое множество. Для этого нам понадобится ряд вспомогательных фактов, которые мы примем без доказательства.

• 1. Пересечение любого числа замкнутых множеств замкнуто.
• 2. Сумма любого числа открытых множеств есть открытое множество.
• 3. Если замкнутое множество ограничено сверху, то оно содержит свою верхнюю грань. Аналогично, если замкнутое множество ограничено снизу, то оно содержит свою нижнюю грань.

Пусть E - произвольное множество точек на прямой. Назовем дополнением множества E и обозначим через CE множество всех точек па прямой, не принадлежащих множеству E. Ясно, что если x есть внешняя точка для E, то она является внутренней точкой для множества CE и обратно.

4. Если множество F замкнуто, то его дополнение CF открыто и обратно.

Предложение 4 показывает, что между замкнутыми и открытыми множествами имеется весьма тесная связь: одни являются дополнениями других. В силу этого достаточно изучить одни замкнутые или одни открытые множества. Знание свойств множеств одного типа позволяет сразу выяснить свойства множеств другого типа. Например, всякое открытое множество получается путем удаления из прямой некоторого замкнутого множества.

Приступаем к изучению свойств замкнутых множеств. Введем одно определение. Пусть F - замкнутое множество. Интервал (a, b), обладающий тем свойством, что ни одна из его точек не принадлежит множеству F, а точки a и b принадлежат F, называется смежным интервалом множества F.

К числу смежных интервалов мы будем также относить несобственные интервалы или, если точка a или точка b принадлежит множеству F, а сами интервалы с F не пересекаются. Покажем, что если точка x не принадлежит замкнутому множеству F, то она принадлежит одному из его смежных интервалов.

Обозначим через часть множества F, расположенную правее точки x. Так как сама точка x не принадлежит множеству F, то можно представить в форме пересечения:

Каждое из множеств F и замкнуто. Поэтому, в силу предложения 1, множество замкнуто. Если множество пусто, то весь полуинтервал не принадлежит множеству F. Допустим теперь, что множество не пусто. Так как это множество целиком расположено на полуинтервале, то оно ограничено снизу. Обозначим через b его нижнюю грань. Согласно предложению 3, а значит. Далее, так как b есть нижняя грань множества, то полуинтервал (x, b), лежащий левее точки b, не содержит точек множества и, следовательно, не содержит точек множества F. Итак, мы построили полуинтервал (x, b), не содержащий точек множества F, причем либо, либо точка b принадлежит множеству F. Аналогично строится полуинтервал (a, x), не содержащий точек множества F, причем либо, либо. Теперь ясно, что интервал (a, b) содержит точку x и является смежным интервалом множества F. Легко видеть, что если и - два смежных интервала множества F, то эти интервалы либо совпадают, либо не пересекаются.

Из предыдущего следует, что всякое замкнутое множество на прямой получается путем удаления из прямой некоторого числа интервалов, а именно смежных интервалов множества F. Так как каждый интервал содержит по крайней мере одну рациональную точку, а всех рациональных точек на прямой - счетное множество, то легко убедиться, что число всех смежных интервалов не более чем счётно. Отсюда получаем окончательный вывод. Всякое замкнутое множество на прямой получается путем удаления из прямой не более чем счетного множества непересекающихся интервалов.

В силу предложения 4, отсюда сразу вытекает, что всякое открытое множество на прямой представляет собой не более чем счетную сумму непересекающихся интервалов. В силу предложений 1 и 2, ясно также, что всякое множество, устроенное, как указано выше, действительно является замкнутым (открытым).

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

Счетное множество- есть бесконечное множество элементы которого можно пронумеровать натуральными числами, или это множество, равномощное множеству натуральных чисел.

Иногда счётными называются множества равномощные любому подмножеству множества натуральных чисел, то есть все конечные множества тоже считаются счётными.

Счётное множество является «наименьшим» бесконечным множеством, то есть в любом бесконечном множестве найдётся счётное подмножество.

Свойства:

1.Любое подмножество счётного множества не более чем счётно.

2.Объединение конечного или счётного числа счётных множеств счётно.

3.Прямое произведение конечного числа счётных множеств счётно.

4.Множество всех конечных подмножеств счётного множества счётно.

5.Множество всех подмножеств счётного множества континуально и, в частности, не является счётным.

Примеры счетных множеств:

Простые числа Натуральные числа, Целые числа, Рациональные числа, Алгебраические числа, Кольцо периодов, Вычислимые числа, Арифметические числа.

Теория вещественных чисел.

(Вещественные = действительные – памятка для нас, пацаны.)

Множество R содержит рациональные и иррациональные числа.

Действительные числа, не являющиеся рациональными, называются иррациональными

Теорема: Не существует рационального числа, квадрат которого равен числу 2

Рациональные числа: ½, 1/3, 0.5, 0.333.

Иррациональные числа: корень из 2=1,4142356… , π=3.1415926…

Множество R действительных чисел обладает следующими свойствами:

1. Оно упорядоченное: для любых двух различных чисел a и b имеет место одно из двух соотношений a либо a>b