Как мы доказывали в прошлом семестре, элементы обратной матрицы вычисляются по формулам 
. Однако если мы рассматриваем матрицы не над полем, а над кольцом, то деление на 
может оказаться невозможным, так как, в отличие от поля, не всякий элемент кольца обратим. Например, в 
обратимы только 1 и 
.
Матрица 
является обратимой над кольцом 
тогда и только тогда, когда является обратимым элементом в кольце .
Задача. Найдите матрицы, обратимые над кольцом целых чисел :
а) 
, б) 
, в) 
. г) 
д) 
Определители 1, 9, соответственно, поэтому обратимы матрицы в пунктах (а) и (в), не обратима в (б).
г) определитель равен , матрица обратима над .
д) определитель равен 2, матрица не обратима над .
Элементы теории множеств.
Задача 1. Дано: 
Ø, 
Ø. Возможно ли, что 
Ø?
Нет, 
но Ø, тогда 
.
= 
= 
, а про это множество в условии сказано, что оно непусто.
Задача 2. Доказать, что
1) 
= 
2) 
= 
(множество элементов, принадлежащих лишь одному из множеств).
2а) 
= 
n=2 очевидно: = при объединении, все элементы пересечения учтены 2 раза, их и нужно вычесть.
n=3: два разных подхода к образованию симметрической разности.
А) Если определять как множество элементов, принадлежащих только одному из множеств:
=
центральную часть прибавили 3 раза, вычли 6 раз, значит, нужно прибавить 3 раза, чтобы характеристическая функция приняла значение 0.
= 3, в симметрической разности тоже 3 точки.
Б) Если последовательно, то
=
В этом случае центральная часть присутствует, и её характеристическую функцию нужно прибавить 4 раза.
Задача 3. Доказать, что 
.
Идея решения: Множество всех подмножеств из k элементов, при всех k, как раз и составляет множество всех подмножеств.
Задача 4. Дано универсальное множество 
и множества 
, 
, 
.
1) Найти множество 
.
2) Записать булеан множества 
.
Решение.
1) 
.
= 
.
= 
.
2) Множество всех подмножеств 
.
Задача 5. Из 100 студентов факультета, в олимпиаде по математике участвовали 28, по физике 42, по информатике 30. Одновременно в двух олимпиадах участвовали: по математике и физике 10 студентов, по математике и информатике 8 студентов, по физике и информатике 5 человек. При этом во всех трёх олимпиадах приняли участие 3 человека. Сколько студентов не участвовали ни в одной олимпиаде?
Решение. По формуле включений и исключений,
= 
.
Найдём число студентов, которые участвовали хотя бы в одной олимпиаде. 
= 
.
Таким образом, 20 студентов не участвовали ни в одной олимпиаде.
Практика 3
Задача 6 (РП). На кафедре 13 человек знают иностранные языки. Причём каждый из них владеет хотя бы одним иностранным языком. 10 человек знают английский, 7 человек немецкий, 6 французский. При этом 5 человек знают английский и немецкий, 4 знают английский и французский, 3 знают немецкий и французский.
1) Сколько человек знают 3 языка?
2) Сколько человек знают только 2 языка?
3) Сколько человек знают только английский?
Решение.
По формуле включений и исключений,
= .
= 13. 
.
.
Тогда число людей, знающих все 3 языка, 
.
.
Англ+нем: всего 5 чел, из них 2 знают и третий язык, т.е. только англ+нем 3.
англ + фр 4, только англ + фр 2
нем + фр 3, только нем + фр 1.
Далее, англ 10, вычесть 3,2,2. Остаётся 3 - только англ.
Аналогично, нем 7, вычесть 3,1,2, осталось 1.
фр 6, вычесть 2,1,2, осталось 1.
1) Сколько человек знают 3 языка? 2
2) Сколько человек знают только 2 языка? 6
3) Сколько человек знают только английский? 3
Задача 7.
, 
, 
, 
.
Найти 
. В ответе указать сумму и произведение всех чисел этого множества, а также мощность множества.
Решение.
, 
. Учитываем элементы, которые есть только в одном или другом множестве. 3 и 4 есть в обоих множествах, поэтому в симметрическую разность они не входят.
.
, . Пересечение 
.
Ответ. , сумма чисел равна 7, произведение 10, мощность 2.
Задача 8.
, 
, 
, 
.
Найти 
.
Решение.
1) 
.
2) 
3) = 
.
Задача 9.
, 
, 
, 
.
Найти 
.
Решение.
Так как 
то 
= 
.
= 
.
Ответ. = .
Задача 9-А
, 
, 
, 
.
Найти 
.
Решение. 
.
= 
.
Перерыв
Задача 10. (Принцип индукции). Доказать, что 
делится на 6 для любого 
.
База индукции. 
. 
.
Индукционный шаг. Пусть верно для n, рассмотрим n+1.
= 
= 
.
Выделим старое выражение отдельным слагаемым, а также константу, которая точно делится на 6.
= 
. Осталось доказать, что последнее слагаемое делится на 6. Оно точно делится на 3, поэтому осталось доказать, что 
делится на 2.
= 
произведение соседних целых чисел, поэтому одно из них точно чётное, значит, 
, 
.
Задача 11. (Принцип индукции). Доказать, что при любом натуральном 
верно 
.
Решение.
Проверим при 
(база индукции).
. (При n=3: 16 < 20).
Если верно при n, докажем, что и при 
.
Составим выражение при и докажем, что левая часть умножается на меньший коэффициент, чем правая.
= 
(для левой).
= 
= 
= 
=
= 
= 
= 
(для правой).
Соотношение.
= 
= 
=
. В выражении 
числитель больше знаменателя. Тогда 
. Неравенство сохранится при переходе от n к n+1.
Если сократить ранее, то 
= 
= .
Задача 12. Доказать, что множества 
и 
равномощны. Построить биективное отображение.
Решение. 
биективно отображает на
. Тогда 
биекция на .
Задача 12-А. Доказать, что множества и 
равномощны. Построить биективное отображение.
Как и в прошлой задаче, но 
(прошлую функцию сжать в 2 раза и поднять на 0,5).
Задача 13 (РП). Доказать, что любые два интервала 
и 
на прямой равномощны.
Решение. 2 способа:
1) Построить биекцию.
, 
, 
.
Получится система уравнений 
Вычесть 1-е из 2-го 
, 
,
. Биективное отображение существует.
2) По теореме Кантора-Бернштейна.
Построить 2 инъективных отображения, в и в .
, 
. (малые коэфф, кратно меньше отношения длин интервалов). Каждое множество равномощно подмножеству второго, эти множества равномощны.
ПРАКТИКА 4. 20.2.2021.
Задача 13. Доказать, что множества и 
равномощны.
Решение. 
,
, 
.
Каждое множество отображается на часть второго с помощью инъективной функции.
По теореме Кантора-Бернштейна, они равномощны, континуум.
Задача 14. Доказать, что множества и 
равномощны.
Решение.
Два инъективных отображения: 
.
.
По теореме Кантора-Бернштейна, они равномощны.
Задача 15. Найти мощность множества корней уравнения 
.
Решение. 
, 
, 
.
Существует биективное отображение между множеством корней этого уравнения и 
, а это счётное множество.
Графики функций 
и 
выглядят так:
и 
Задача 16. Доказать, что если 
- множества корней многочленов 
соответственно, то 
- множество корней произведения многочленов 
.
Решение. = 0 тогда и только тогда, когда один или второй множитель равен 0, 
или 
, то есть 
.
Задача 17. На множестве 
задано бинарное отношение: 
. Представить с помощью графа и матрицы, выяснить свойства (рефлексивность, симметричность, транзитивность), является ли отношением эквивалентности или отношением порядка?
Решение.
Рефлексивность очевидна: для пары 
получается 
.
Симметричность: 
= 
=
, и здесь каждое делится на 3.
Транзитивность: пусть 
и 
делятся на 3, проверим это свойство для 
.
= 
= 
, здесь каждое делится на 3. Значит, отношение транзитивно.
Итак, это отношение эквивалентности (рефлексивно, симметрично, транзитивно).
Запишем сами эти числа вида
Укажем «1», где делится на 3:
Граф отношения:
Из строения матрицы видно, что отношение рефлексивно и симметрично. Отношение эквивалентности.
Классы эквивалентности 
видны на графе (множество распадается на 3 непересекающихся подмножества).
Подматрицы из 1,4 строки и 1,4 столбца,
2,5 строка и 2,5 столбец, 3 строка 3 столбец.
В 1,4 строках не содержится «1» нигде кроме этих же номеров столбцов.
- Перерыв -
Задача 18. Фундированные множества (задача с монетами).
Каждую минуту автомат меняет монету, выдавая любое количество любых монет, но меньшего достоинства (видов монет конечное число). Доказать, что рано или поздно у игрока не останется ни одной монеты.
Решение. Пусть есть k видов монет. Множество монет, имеющееся в определённый момент, можно описать набором чисел 
.
Отношение порядка введём следующим образом.
Если 
то 
,
Если 
то сравнение по 
номеру и так далее.
Набор при каждом действии уменьшается (в смысле введённого порядка). При этом множество 
фундировано (доказано в лекциях). Таким образом, процесс должен оборваться.
.
Задача 19. (РП). Пусть X и Y - два непересекающихся частично упорядоченных множества. На их объединении задан частичный порядок: внутри каждого множества элементы сравниваются как и прежде, а любой элемент 
по определению меньше любого элемента 
. Будет ли такой порядок линейным? Почему?
Частичный порядок, следовательно, 
или 
несравнимые в исходном множестве, и после объединения будут несравнимы.
Задача 20. Доказать, что 
можно вполне упорядочить.
Решение. (это не декартово произведение) 
, порядок: 
.
предельный элемент (не существует непосредственного предшествующего).
Линейный порядок был на каждом из множеств, линейный порядок на объединении. Кроме того, множество фундированное.
(1 есть наименьший элемент). Линейно упорядоченное и фундированное, значит, вполне упорядоченное.
Задача 21. Доказать методом математической индукции, что
.
Решение. База индукции. Можно непосредственно проверить на малых числах, например 1 или, если интересно, 2 (достаточно 1).
. 
.
. 
.
Индукционный шаг. Рассмотрим, следует ли из выполнения этого равенства для номера 
его выполнение для номера .
, 
=
.
С другой стороны, для выражение бы выглядело так: 
.
Мы должны убедиться, что:
= .
= 
, таким образом, остаётся сравнить 
и 
.
Сократим на 
сравнить 
и 
.
Справа и слева 
.
Задача 22. Доказать методом математической индукции, что
.
Решение. База индукции. . 
.
Индукционный шаг. Рассмотрим, следует ли из выполнения этого равенства для номера его выполнение для номера .
, 
.
С другой стороны, для выражение бы выглядело так:
.
Нужно сравнить 
и .
= 
.
Остаётся сравнить 
и 
.
Сократим 
. Остаётся сравнить: 
и 
оба равны 
.
Практика 5.
(из рабочей программы):
