Бинарные отношения на произвольных множествах.

Пусть заданы множества $latex X $ и $latex Y, $ тогда бинарным отношением $latex R $ из множества $latex X $ в множество  $latex Y $ называется подмножество декартова произведения $latex X $ и $latex Y $:

$latex R \subset X \times Y $.

Напомним свойства отношений:

Примеры:

1. Пусть $latex A = \left\{1, 2, 7\right\}, $ $latex B = \left\{3, 9 \right\}. $

Задаем отношения:

$latex R_1 = \left\{(1, 9), (2, 3), (2, 9), (7, 3)\right\} \subset A\times B; $

$latex R_2 = \left\{(1, 2), (2, 7), (7, 1), (7, 2), (7, 7)\right\}\subset A\times A; $

2. Пусть $latex R\subseteq \mathbb{R} $, $latex R=\left\{(x, y)\,|\, 2x \geq 3y \right\}, $ определить его свойства.

Решение:

— Не является рефлексивным, так как, например, $latex (1,1) \not \in R. $

— Не является антирефлексивным, так как, например, $latex (-1, -1) \in R. $

— Не является симметричным, так как можно привести контрпример: $latex (5, 1) \in R $, а $latex (1, 5)\not\in R. $

— Не является антисимметричным, так как нельзя подобрать такие $latex (x, y)\in R $ и $latex (y, x)\in R, $ что $latex y= x. $

— Не является транзитивным, так как можно привести контрпример:

$latex x=-1, y=-2, z=1, $ тогда $latex 2x\geq 3y, 2y \geq 3z \Rightarrow 2x\geq 3z $, но $latex -2 \leq 3. $

3. Пусть $latex R \subseteq \mathbb{N}^2, $

$latex R=\left\{(x, y)|\, x~\vdots~y = 0 \right\} $,

определить его свойства.

Решение:

— Является рефлексивным, так как $latex x~\vdots~x = 0 $.

— Не является антирефлексивным, так как уже рефлексивно.

— Не является симметричным, так как не обязательно, что $latex y~\vdots ~x = 0 $, например,

возьмем пару $latex (10, 2) $, $latex 10 $ делится на $latex 2 $, но $latex 2 $ не делится на $latex 10 $.

— Является антисимметричным, так как $latex x~\vdots~y= 0 $ и $latex y~\vdots~ x =0 $, когда $latex x= y $.

— Является транзитивным, так как $latex ~x\vdots ~y = 0, y~\vdots ~z= 0 \Rightarrow x~\vdots~ z =0 $.

Литература:

• Белозеров Г.С. Конспект лекций по алгебре и геометрии
• Федоровский С.В. Конспект лекций по математической логике
• Кострикин А.И. Введение в алгебру. М.: Наука, 1977, (Стр. 47-48)
• Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 1995

Теоремы о транспозиции

Прежде чем мы будем рассматривать теоремы о транспозиции, попытаемся сформулировать само понятие транспозиции. Транспозицией называется перемена местами двух элементов перестановки .

Теорема 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}$ нечётных перестановок.

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

Теорема 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$

Источники

1. Г.С.Белозеров.Конспект лекций
2. В.В.Воеводин. Линейная алгебра. Второе издание, физико-математическая литература, 1980. Стр. 122-124.
3. А.Г.Курош. Курс линейной алгебры. Издание тринадцатое, 2004. Стр.28-37.

Теорема (критерий ЛНЗ)

Система векторов [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](\alpha_{1}=\alpha_{2}=…=\alpha_{n}=0 )[/latex].

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

Необходимость. Пусть система векторов [latex]S=<a_{1},a_{2},..,a_{n}>[/latex]  линейно независима, но существуют числа [latex]\alpha_{1},…,\alpha_{n}[/latex], не все равные нулю, такие, что

[latex]\alpha_{1} a_{1}+\alpha_{2}a_{2}+…+\alpha_{n}a_{n}=0[/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]a_{k}=\alpha_{1}a_{1}+…+\alpha_{k-1}a_{k-1}+\alpha_{k+1}a_{k+1}+…+\alpha_{n}a_{n}[/latex]

Но тогда

[latex]\alpha_{1}a_{1}+…+\alpha_{k-1}a_{k-1}+(-1)a_{k}+\alpha_{k+1}a_{k+1}+…+\alpha_{n}a_{n}[/latex]

и не все коэффициенты этой линейной комбинации равны нулю, что противоречит условию. Поэтому система векторов [latex]S=<a_{1},a_{2},..,a_{n}>[/latex] линейно независима.

Пример

Проверить является ли система [latex]S=<(1,0,0),(0,1,0),(0,0,1)>[/latex] линейно независимой.

Составим линейную комбинацию из векторов системы:

[latex]\alpha_{1}(1,0,0)+\alpha_{2}(0,1,0)+\alpha_{3}(0,0,1)=0\Rightarrow[/latex]

[latex](\alpha_{1},0,0)+(0,\alpha_{2},0)+(0,0,\alpha_{3})=0\Rightarrow[/latex]

[latex](\alpha_{1},\alpha_{2},\alpha_{3})=0\Rightarrow \alpha_{1}=\alpha_{2}=\alpha_{3}=0[/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,0,0)+\alpha_{2}(0,2,0)+\alpha_{3}(1,2,0)=0\Rightarrow[/latex]

[latex](\alpha_{1},0,0)+(0,2\alpha_{2},0)+(\alpha_{3},2\alpha_{3},0)=0\Rightarrow[/latex]

[latex](\alpha_{1}+\alpha_{3},2\alpha_{2}+2\alpha_{3},0)=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_{k}=\left ( -\frac{\alpha_{1}}{\alpha_{k}}\right )a_{1}+\left ( -\frac{\alpha_{2}}{\alpha_{k}} \right )a_{k}+…+\left ( -\frac{\alpha_{k-1}}{\alpha_{k}} \right )a_{k-1}[/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]

 Литература

• Конспект лекций по линейной алгебре. Белозёров Г.С.
• Воеводин В.В. Линейная алгебра. М.: Наука, 1994 с. 44-47.
• Курош А.Г. Курс высшей алгебры. М.: Наука, 1968 c.63-70

Равенство множеств

Множества равны, если они содержат одни и те же элементы. Если $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

Тест

Подмножества. Отношение включения.
Множество $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$ называется несчётным, если оно бесконечно и не является счётным.

Существует 2 основных способа задания множеств.

• Перечислением$(X=\left\{a,b\right\}, Y=\left\{1\right\}, Z=\left\{1,2,…,8\right\}, M=\left\{m_{1},m_{2},m_{3},..,m_{n}\right\})$;
• Описанием — указываются характерные свойства , которыми обладают все элементы множества.

Множество полностью определено своими элементами.

Конечные множества можно задать только перечислением их элементов (например, множество дней в месяце).
Для задания бесконечных множеств нужно описать свойства их элементов (например, множество рациональных чисел можно задать описанием $Q=\left\{n/m, \ m, \ n\in\ z, \ m\ne\ 0\right\}$.

Подмножеством множества $A$ можно рассматривать само множество $A$ и пустое множество $\varnothing$. Эти два подмножества называются несобственными. Остальные подмножества множества $A$ будут называться собственными.

Литература:

• Конспект лекций Г.С. Белозерова
• Линейная алгебра. Воеводин В.В. М.: Наука. Главная редакция физико-математической литературы, 1980, с.9-13
• Лекции по общей алгебре (издание второе). Курош А.Г. М.: Наука. Главная редакция физико-математической литературы, 1973, с.14-17