Пусть заданы множества $latex X $ и $latex Y, $ тогда бинарным отношением $latex R $ из множества $latex X $ в множество $latex Y $ называется подмножество декартова произведения $latex X $ и $latex Y $:
$latex R \subset X \times Y $.
Напомним свойства отношений:
Спойлер
Пусть $latex R\subset A^2. $ Тогда отношение $latex R $ называется:
— рефлесивным, если $latex aRa $ для любого $latex a\in A $;
— антирефлексивным, если $latex a\overline R a $ для любого $latex a\in A; $
— симметричным, если из $latex aRb $ следует $latex bRa $ для любых $latex a\in A, $ $latex b\in A; $
-антисимметричным, если $latex a\not= b, $ то из $latex aRb $ следует $latex b\overline R $ для любых $latex a\in A, $ $latex b\in A; $
— транзитивным, если из $latex aRb $ и $latex bRc $ следует $latex aRc $ для любых $latex a\in A, $ $latex b\in A, $ $latex c\in A; $
[свернуть]
Примеры:
1. Пусть $latex A = \left\{1, 2, 7\right\}, $ $latex B = \left\{3, 9 \right\}. $
Прежде чем мы будем рассматривать теоремы о транспозиции, попытаемся сформулировать само понятие транспозиции. Транспозицией называется перемена местами двух элементов перестановки .
Теорема 1
Все $ n!$ перестановок длин $ n $ можно расположить одну за другой так, что каждая последующая получается из предыдущей $ 1 $ (одной) транспозицией, начинать можно с любой перестановки.
Доказательство
Доказательство будем проводить индукцией по $ n$ .
База индукции: $ n= 2$ , то получаем перестановки $ (1, 2), (2, 1)$ , тогда расположения будут иметь вид $ (1, 2, 2, 1)$ и $ (2, 1, 1, 2)$ , теорема справедлива.
Предположение индукции: $ n \le m,$ $ m \ge 2$ .
Шаг индукции: $ n= m+1$ $ (i_1, i_2,$ … $, i_{m+1})$ . Рассмотрим все перестановки, где на первом месте стоит $ i_1$ .
$(i_1, {i`}_2,$ …$, {i`}_{m+1})$ ;
$({i`}_2, i_1,$ …$, {i`}_{m+1})$ ;
$({i`}_2, {i`}_1,$ …$, {i«}_{m+1})$ ;
Таких $ m!(m+1)= (m+1)!$ перестановок.
Следствие:
Пусть $ n \ge 2 $ , тогда число $ \frac{n!}{2}$ чётных равно числу $ \frac{n!}{2}$ нечётных перестановок.
Рассмотрим перестановку …,$ i, j$ , …, где $ i$ и $ j$ транспонируемые символы, стоящие рядом. В результате транспозиции получим новую перестановку …, $j, i $ , …, при этом в данных перестановках каждый из символов $ i$ и $ j$ составит одинаковые инверсии с символами, остающимися на месте, количество таких инверсий $ n$ . В случае, если до этого $ i$ и $ j$ не составляли инверсий, то с новой перестановкой появится и новая инверсия (число инверсий будет равным $ n+1 $ ), в противном случае, число инверсий на $ 1 $ уменьшиться. И в том и в другом случаях чётность перестановки меняется.
Теперь рассмотрим вариант, когда между $ i$ , $ j$ расположено$ s$ символов $ (s>0) $ , т.е. перестановка имеет вид …$ i, k_1, k_2$ , …, $ k_s, j$ ,…. Транспозицию символов $ i$ , $ j$ получим последовательным выполнением $ 2s+1$ транспозиции элементов, стоящих рядом. В итоге, мы меняем четность перестановки нечетное число раз, и по-этому перестановки
…, $ i, k_1, k_2$ , …, $ k_s, j$ ,… и …, $ j, k_1, k_2$ , …, $ k_s, i$ ,… будут противоположной чётности.
Пример
$ (2,5,4,1,3)$ $ \Rightarrow$ $ (1,5,4,2,3)$ $ \Rightarrow$ $ (1,2,4,5,3)$ $ \Rightarrow$
$ (1,2,3,5,4)$ $ \Rightarrow$ $ (1,2,3,4,5)$ .
Здесь, перестановка $(2,5,4,1,3)$ приведена к начальной за $ 4 $ транспозиции и она четная, т.к. $ \tau(2,5,4,1,3)= 6$
Тест о теоремах о транспозиции
Лимит времени: 0
Навигация (только номера заданий)
0 из 6 заданий окончено
Вопросы:
1
2
3
4
5
6
Информация
Данный тест поможет проверить, как вы усвоили материал данной статьи
Вы уже проходили тест ранее. Вы не можете запустить его снова.
Тест загружается...
Вы должны войти или зарегистрироваться для того, чтобы начать тест.
Вы должны закончить следующие тесты, чтобы начать этот:
Результаты
Правильных ответов: 0 из 6
Ваше время:
Время вышло
Вы набрали 0 из 0 баллов (0)
Средний результат
Ваш результат
Рубрики
Нет рубрики0%
Алгебра0%
Ваш результат был записан в таблицу лидеров
Загрузка
максимум из 11 баллов
Место
Имя
Записано
Баллы
Результат
Таблица загружается
Нет данных
1
2
3
4
5
6
С ответом
С отметкой о просмотре
Задание 1 из 6
1.
За какое количество транспозиций перестановка (4, 2, 5, 1, 3) будет приведена к начальной?
Правильно
Неправильно
Задание 2 из 6
2.
По теореме о транспозиции
Любая транспозиция меняет (чётность перестановки)
Правильно
Неправильно
Задание 3 из 6
3.
Являются ли такое преобразования перестановок транспозицией ?
2679035418[latex]\Rightarrow[/latex]2479305618
Правильно
Неправильно
Задание 4 из 6
4.
Перестановка 38524671 является:
Правильно
Неправильно
Задание 5 из 6
5.
Сопоставить перестановки с числом содержащихся в них инверсий:
Элементы сортировки
7
10
4
( 1, 5, 8, 3, 2, 4)
( 6, 9, 5, 8, 7, 1)
(4, 1, 3, 2, 5, 6)
Правильно
Неправильно
Задание 6 из 6
6.
Этапы доказательства теоремы 1 (Все [latex] n![/latex] перестановок длин [latex] n[/latex] можно расположить одну за другой так, что каждая последующая получается из предыдущей [latex] 1 [/latex](одной) транспозицией, начинать можно с любой перестановки):
$n= 2$, то получаем перестановки $ (1, 2), (2, 1)$, тогда расположения будут иметь вид $ (1, 2, 2, 1)$ и $(2, 1, 1, 2)$, теорема справедлива;
$ n \in m,$ $m \ge 2$;
Рассмотрим все перестановки, где на первом месте стоит $i_1$.
Необходимость. Пусть система векторов [latex]S=<a_{1},a_{2},..,a_{n}>[/latex] линейно независима, но существуют числа [latex]\alpha_{1},…,\alpha_{n}[/latex], не все равные нулю, такие, что
Допустим, что [latex]\alpha_{k} \neq 0[/latex]. Тогда из этого равенства [latex]a_{k}[/latex] определяется как линейная комбинация остальных векторов из [latex]a_{1},…,a_{n}[/latex]. Это означает, что система векторов [latex]S=<a_{1},a_{2},..,a_{n}>[/latex], согласно определению, линейно зависима, что противоречит предположению.
Достаточность. Пусть теперь указанное выше равенство выполняется только тогда, когда все числа [latex]\alpha_{1},…,\alpha_{n}[/latex] равны нулю. Предположим, однако, что система векторов [latex]S=<a_{1},a_{2},..,a_{n}>[/latex] линейно зависима. Это означает, что один из векторов [latex]a_{k}[/latex] линейно выражается через остальные, т.е.
и не все коэффициенты этой линейной комбинации равны нулю, что противоречит условию. Поэтому система векторов [latex]S=<a_{1},a_{2},..,a_{n}>[/latex] линейно независима.
Пример
Проверить является ли система [latex]S=<(1,0,0),(0,1,0),(0,0,1)>[/latex] линейно независимой.
Т.е. система [latex]S=<(1,0,0),(0,1,0),(0,0,1)>[/latex] линейно независима по критерию ЛНЗ.
Теорема (первый критерий ЛЗ)
Система [latex]S=<a_{1},a_{2},..,a_{n}>[/latex] линейно зависима тогда и только тогда, когда существует линейная комбинация [latex]\alpha_{1} a_{1}+\alpha_{2}a_{2}+…+\alpha_{n}a_{n}=0[/latex] с ненулевым набором коэффициентов.
Пример
Проверить является ли система [latex]S=<(1,0,0),(0,2,0),(1,2,0)>[/latex] линейно независимой.
При [latex]\alpha_{1}=1[/latex] и [latex]\alpha_{3}=-1[/latex] линейная комбинация равна нулю, т.е. система линейно зависима по первому критерию.
Теорема (второй критерий ЛЗ)
Векторы [latex]a_{1},a_{2},…,a_{n}[/latex] линейно зависимы тогда и только тогда, когда либо [latex]a_{1}=0[/latex], либо некоторый вектор [latex]a_{k}[/latex], [latex]2\leq k\leq n[/latex], является линейной комбинацией предшествующих векторов.
Доказательство
Предположим, что векторы [latex]a_{1},a_{2},…,a_{n}[/latex] линейно зависимы. Тогда в линейной комбинации, составленной из этих векторов не все коэффициенты равны нулю. Пусть последний ненулевой коэффициент есть [latex]\alpha_{k}[/latex]. Если [latex]k=1[/latex], то это означает, что [latex]a_{1}=0[/latex]. Пусть теперь [latex]k>1[/latex]. Тогда из равенства [latex]\alpha_{1} a_{1}+\alpha_{2}a_{2}+…+\alpha_{n}a_{n}=0[/latex] находим, что
Этим доказана необходимость утверждения, сформулированного в теореме. Достаточность очевидна, поскольку и случай, когда [latex]a_{1}=0[/latex], и случай, когда вектор [latex]a_{k}[/latex] линейно выражается через предшествующие векторы, означает линейную зависимость первых векторов из [latex]a_{1},a_{2},…,a_{n}[/latex]. Но отсюда следует линейная зависимость и всей системы векторов.
Пример
Проверить является ли система [latex]S=<(1,0,0),(0,2,0),(1,4,0)>[/latex] линейно независимой.
Данная система является линейно зависимой по второму критерию, т.к. третий вектор является линейной комбинацией первых двух:
[latex](1,4,0)=(1,0,0)+2\cdot(0,2,0)[/latex]
Литература
Конспект лекций по линейной алгебре. Белозёров Г.С.
Если существует линейная комбинация [latex]\alpha_{1}a_{1}+\alpha_{2}a_{2}+…+\alpha_{n}a_{n}=0[/latex] с ненулевым набором коэффициентов, то система [latex]S=<a_{1},a_{2},..,a_{n}>[/latex] …
Правильно
Неправильно
Подсказка
Закончить утверждение
Задание 3 из 4
3.
Какое условие является необходимым и достаточным во втором критерии линейной зависимости?
Множества равны, если они содержат одни и те же элементы. Если $A$ есть множество $\left\{2,4,6\right\}$, а $B$ есть множество $\left\{x: x\ есть\ четное\ положительное\ целое\ число,\ которое\ меньше\ 7\right\},$ тогда $A$ и $B$ — равные множества. Таким образом мы приходим к следующему определению.
Пусть $A$ и $B$ — некоторые множества. Говорят, что $A$ равно $B$, и пишут $A=B$, если $\forall\ x : x\in\ A\Leftrightarrow\ x\in\ B$. Иначе говоря, $A=B\Leftrightarrow\ A\subseteq\ B \ и \ B\subseteq\ A$.
Литература:
Конспект лекций Г.С. Белозерова
Линейная алгебра. Воеводин В.В. М.: Наука. Главная редакция физико-математической литературы, 1980, с.9-13
Лекции по общей алгебре (издание второе). Курош А.Г. М.: Наука. Главная редакция физико-математической литературы, 1973, с.14-17
Тест
Лимит времени: 0
Навигация (только номера заданий)
0 из 9 заданий окончено
Вопросы:
1
2
3
4
5
6
7
8
9
Информация
В заданиях необходимо определить отношения включения множеств
Вы уже проходили тест ранее. Вы не можете запустить его снова.
Тест загружается...
Вы должны войти или зарегистрироваться для того, чтобы начать тест.
Вы должны закончить следующие тесты, чтобы начать этот:
Результаты
Правильных ответов: 0 из 9
Ваше время:
Время вышло
Вы набрали 0 из 0 баллов (0)
Средний результат
Ваш результат
Рубрики
Нет рубрики0%
Алгебра0%
Теория множеств0%
Ваш результат был записан в таблицу лидеров
Загрузка
1
2
3
4
5
6
7
8
9
С ответом
С отметкой о просмотре
Задание 1 из 9
1.
Как соотносятся между собой множества $A=\left\{1,2,4,6,8\right\}$ и $B=\left\{x:x\ есть\ четное\ положительное\ целое\ число,\ которое\ меньше\ 12\right\}$.
Правильно
Неправильно
Задание 2 из 9
2.
Как соотносятся между собой множества $A=\left\{2,4,6,8\right\}$ и $B=\left\{x:x\ есть\ четное\ положительное\ целое\ число,\ которое\ меньше\ 12\right\}.$
Правильно
Неправильно
Задание 3 из 9
3.
Как соотносятся между собой множества $A=\left\{1,3,5,7,9\right\}$ и $B=\left\{x:x\ есть\ нечетное\ положительное\ целое\ число,\ которое\ меньше\ 10\right\}$.
Дано множество $A=\left\{6, 12, 18\right\}$ и множество $B=\left\{x:x\ есть\ четное\ положительное\ число,\ меньшее\ 20\ и\ кратное\ 2\ и\ 3\right\}$.
Дано множество $A=\left\{6, 12, 18\right\}$ и множество $B=\left\{x:x\ есть\ положительное\ натуральное\ число\right\}$.
$A=\left\{a_{1}, a_{2}, a_{3}, ...\right\}$
Конечное множество
Равное множество
Подмножество
Бесконечное множество
Правильно
Неправильно
Задание 5 из 9
5.
Вставьте пропущенные слова.
Перечислением можно задать только (конечные множества).
Правильно
Неправильно
Задание 6 из 9
6.
Множества бывают двух типов:
Правильно
Неправильно
Задание 7 из 9
7.
Расположить множества $A$ и $B$ в следующем порядке: равные множества, одно множество есть подмножеством другого, счетное множество, несчетное множество
Множество $X$ называется подмножеством множества $Y$, если любой элемент множества $X\in\ Y$. Принято обозначать это следующим образом: $X\subseteq\ Y$.
Если необходимо указать, что $Y$ содержит и другие элементы, а не только элементы множества $X$, то принято использовать символ строгого включения $\subset\ : X\subset\ Y$.
Связь между символами строгого и не строгого включения ($\subset$ и $\subseteq$) показана выражением:
$$X\subset\ Y\Leftrightarrow\ X\subseteq\ Y \ и \ X\ne\ Y$$
Выделим некоторые свойства, которые вытекают из определения:
$X\subseteq\ X$ (рефлексивность);
$\left[X\subseteq\ Y \ и \ Y\subseteq\ Z\right] \Rightarrow\ X\subseteq\ Z$ (транзитивность);
$\varnothing\ \subseteq\ M$. Отметим, что пустое множество является подмножеством любого подмножества.
Начальное множество $A$ по отношению к его подмножествам является полным множеством и его принято обозначать $I$.
Собственное множество множества $A$ — это любое подмножество $A_i$ множества $A$.
Булеаном множества $X$ — называется множество, состоящее из всех подмножеств данного множества $X$ и пустого множества $\varnothing$. Принято обозначать как $\beta(X)$. Множество булеана $\left|\beta(X)\right|=2^n$.
Счетное множество — это множество $A$, которое совпадает по мощности с множеством натуральных чисел $N$. Другими словами — если множество, эквивалентно множеству натуральных чисел, то оно называется счетным множеством.
Множество $A$ называется несчётным, если оно бесконечно и не является счётным.
Описанием — указываются характерные свойства , которыми обладают все элементы множества.
Множество полностью определено своими элементами.
Конечные множества можно задать только перечислением их элементов (например, множество дней в месяце).
Для задания бесконечных множеств нужно описать свойства их элементов (например, множество рациональных чисел можно задать описанием $Q=\left\{n/m, \ m, \ n\in\ z, \ m\ne\ 0\right\}$.
Подмножеством множества $A$ можно рассматривать само множество $A$ и пустое множество $\varnothing$. Эти два подмножества называются несобственными. Остальные подмножества множества $A$ будут называться собственными.
Литература:
Конспект лекций Г.С. Белозерова
Линейная алгебра. Воеводин В.В. М.: Наука. Главная редакция физико-математической литературы, 1980, с.9-13
Лекции по общей алгебре (издание второе). Курош А.Г. М.: Наука. Главная редакция физико-математической литературы, 1973, с.14-17