contents next

1. ВВЕДЕНИЕ.

Слово "Алгебра" ввел в обращение арабский математик IX века Ал Харизми.
Крупнейшим алгебраистом средневековья считается французский математик Франсуа Виет (XVI век).
В XVII - XVIII веках алгебраическую теорию развивали Эйлер, Ньютон, Лагранж, Декарт, Ферма и др. Вплоть до XIX века основной задачей алгебры считалость отыскание решений уравнения $$a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0=0,$$ при произвольных действительных $a_0,\ldots,{a}_n$.
Для случая $n=1,2$ задача была решена в IX веке Ал Харезми.
Для случая $n=3,4$ задача была решена в XVI веке итальянскими математиками Кардано, Тарталья, Феррари.
В 1799 году итальянский математик Руффини опубликовал работу в которой доказывал, что при $n\geq5$ уравнение не разрешимо в радикалах.
В 1824 году Нильс Абель устранил неточности в доказательстве Руффини.
Основоположником современной алгебры считается французский математик Эварист Галуа (1811 - 1832).
В XIX веке алгебра начинает рассматриваться как наука о множествах с операциями и развивается многими видными математиками, среди которых российские Лобачевский, Чебышев, Шмидт.

Список литературы:
  1. Рыбников К. А "История матетатики."
  2. Глухов М. М, Елизаров В. П., Нечаев А. А. "Алгебра."
  3. Кострикин А. И "Сборник задач по алгебре."
  4. Проскуряков И. В "Сборник задач по линейной алгебре."
  5. Фадеев Д. К., Саминский И. С. "Сборник задач по высшей алгебре."
Обозначения:
  1. $\mathbb{R}$ - множество действительных чисел
  2. $\mathbb{N}$ - множество натуральных чисел
  3. $\mathbb{N}_0$ - множество неотрицательных целых чисел
  4. $\mathbb{Z}$ - множество целых чисел
  5. $\mathbb{Q}$ - множество рациональных чисел

1.1 О методах математических доказательств.

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

    Пример 1.1:
    Докажем, что $(a+b)(a-b)=a^2-b^2$.
    Доказательство: $(a+b)(a-b)=a^2-ab+ba-b^2=a^2-b^2$.

  2. Метод доказательства от противного.
    Для доказательства этим методом некоторого утверждения $A$ допускают, что $A$ - ложно, т. е. истинно его отрицание $\bar{A}$. Далее с использованием утверждения $\bar{A}$ доказывается некоторое заведомо ложное утверждение $F$ и из этого делают вывод, что сделанное предположение о ложности $A$ - неверно и поэтому $A$ - истинно.

    Пример 1.2:
    Докажем, что $\sqrt{2}$ иррациональное число (то есть не рациональное).
    Доказательство: обозначим доказываемое утверждение $A$, предположим что верно $\bar{A}$, то есть $\sqrt{2}$ рационально, тогда существуют $p,q\in\mathbb{N}$ такие, что $\sqrt{2}=\frac{p}{q}$ - несократимая дробь. Тогда $\frac{p^2}{q^2}=2$, то есть $p^2$ - четное, следовательно, и $p$ - четное. Тогда существует $t\in\mathbb{N}$ такое, что $p=2t$ и $q^2=\frac{(2t)^2}{2}=2t^2$, то есть $q^2$ - четное, следовательно, и $q$ - четное. Тогда дробь $\frac{p}{q}$ сокращается на 2, что противоречит утверждению $\bar{A}$, следовательно утверждение $A$ истинно.
    Если утверждение имеет вид $A\Rightarrow{B}$ и утверждение $A$ истинно в доказательстве методом от противного допускают, что верно утверждение $\bar{B}$, и из $A$ и $\bar{B}$ выводят некоторое ложное утверждение $F$. Отсюда делают вывод, что из истинности $A$ следует истинность $B$.

    Пример 1.3:
    Докажем, что $$\forall{a},b\in\mathbb{R}((a\neq0\wedge{b}\neq0)\Rightarrow{a}b\neq0).$$ Пусть $ab=0$ и $a\neq0$, $b\neq{0}$, тогда $$a\neq0\Rightarrow\exists{a}^{-1}\in\mathbb{R}\Rightarrow{b}={a}^{-1}ab=a^{-1}0=0,$$ что противоречит утверждениею $b\neq0$, следовательно, утверждение $A\Rightarrow{B}$ истинно.

  3. Полная математическая индукция.
    Этот метод применяется для доказательства таких утверждений, в которых участвует числовой параметр $n$, принимающий все значения из множества $\mathbb{N}$ натуральных чисел.
    Если $A(n)$ доказываемое утверждение $n\in\mathbb{N}$, то
    1. База индукции.Доказываем, что $A(1)$ - истинно.
    2. Шаг индукции.Доказываем, что $$\forall{m}\in\mathbb{N}(\forall{n}\leq{m}(A(n))\Rightarrow{A}(m+1)).$$
    Отсюда делается вывод, что $A(n)$ истинно для любого $n\in\mathbb{N}$.

    Пример 1.4:
    Докажем, что $$\forall{n}\in\mathbb{N}\left(1+2+\cdots+n:=\sum_{k=1}^nk=\frac{n(n+1)}{2}\right).$$ Доказательство:

    1. При $n=1$ $1=\frac{1(1+1)}{2}$.
    2. Пусть для некоторого $m\in\mathbb{N}$ для любого $n\leq{m}$ верно $A(n)$, то есть $\sum_{k=1}^nk=\frac{n(n+1)}{2}$, тогда $$\sum_{k=1}^{m+1}k=\sum_{k=1}^mk+(m+1)=\frac{m(m+1)}{2}+(m+1)=\frac{m(m+1)+2(m+1)}{2}=\frac{(m+1)(m+2)}{2},$$ то есть $A(m+1)$ - истинно. Таким образом формула $A(n)$ верна для любого $n\in\mathbb{N}$.
    В данном примере для доказательства шага индукции достаточно было предположить, что $A(m)$ истинно, но не всегда этого бывает достаточно.
    Параметр $n$ может принимать значения из $\mathbb{N}$ только начиная с некоторого числа $n_0$, тогда в базе индукции необходимо доказать истинность $A(n_0)$, a шаг индукции доказывается для $m\geq{n}_0$.

    Пример 1.5:
    Докажем, что для любого $n\in\mathbb{N}$ такого, что $n\geq2$ $n$ либо простое число, либо раскладывается в произведение простых чисел.
    Доказательство:

    1. Так как $2$ - простое число, то $A(2)$ - истинно.
    2. Пусть для некоторого $m\in\mathbb{N}$ такого, что $m\geq2$ для любого $n$ такого, что $2\leq{n}\leq{m}$ верно $A(n)$, тогда если $m+1$ - простое число, то доказано, если $m+1$ не простое, то существуют $n_1,n_2\in\mathbb{N}$ такие, что $m+1=n_1n_2$ и $1<n_1<m+1$, $1<n_2<m+1$. Тогда по предположению индукции существуют простые числа $p_1,\ldots,p_s,p_{s+1},\ldots,p_{s+t}$ такие, что $n_1=p_1\cdots{p}_s$, $n_2=p_{s+1}\cdots{p}_{s+t}$, следовательно, $m+1=n_1n_2=p_1\cdots{p}_{s+t}$.
    В отличии от предыдущего примера здесь для доказательства шага индукции недостаточно предположения, что $A(m)$ истинно, необходима истинности $A(n)$ для любых $2\leq{n}\leq{m}$.
    Для доказательства верности утверждения $A(n)$ для всех $n\in\mathbb{Z}$ начиная с некоторго $n_0\in\mathbb{Z}$ применяют аналогичный метод
    1. База индукции. Доказываем, что $A(n_0)$ - истинно.
    2. Шаг индукции. Для любого $m\in\mathbb{Z}$ такого, что $m\geq{n}_0$ доказываем, что из истинности $A(n)$ для всех $n\in\mathbb{Z}$ таких, что $n_0\leq{n}\leq{m}$ следует истинность $A(m+1)$.

1.2 Бином Ньютона.

Определение 1.1:
Для любых $n,k\in\mathbb{N}_0$ таких, что $k\leq{n}$ число $$\binom{n}k:=\frac{n!}{k!(n-k)!}$$ называется биномиальным коэффициентом из $n$ по $k$.

Лемма 1.1:

  1. $\forall{n},k\in\mathbb{N}_0\left(k\leq{n}\Rightarrow\binom{n}k=\binom{n}{n-k}\right)$,
  2. $\forall{n},k\in\mathbb{N}\left(k\leq{n}\Rightarrow\binom{n}k=\binom{n-1}k+\binom{n-1}{k-1}\right)$.

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

  1. $\binom{n}k=\frac{n!}{k!(n-k)!}=\frac{n!}{(n-k)!(n-(n-k))!}=\binom{n}{n-k}.$
  2. $\binom{n-1}{k}+\binom{n-1}{k-1}=\frac{(n-1)!}{k!(n-1-k)!}+\frac{(n-1)!}{(k-1)!(n-1-k+1)!} =\frac{(n-1)!(n-k)+(n-1)!k}{k!(n-k)!}=\frac{(n-1)!n}{k!(n-k)!}=\frac{n!}{k!(n-k)!}=\binom{n}k.$

Теорема 1.1: Бином Ньютона.
$$ \forall{a},b\in\mathbb{R}\,\forall{n}\in\mathbb{N}\left((a+b)^n=\binom{n}0a^n+\binom{n}1a^{n-1}b+\cdots +\binom{n}ka^{n-k}b^k+\cdots+\binom{n}{n-1}ab^{n-1}+\binom{n}nb^n=\sum_{k=0}^n\binom{n}ka^{n-k}b^k\right). $$

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

Докажем методом математической индукции по параметру $n$.

  1. При $n=1$ $a+b=\binom{1}0a+\binom{1}1b$.
  2. Для любого $m\in\mathbb{N}$ докажем, что из справедливости утверждения при $n=m$ следует его справедливость при $n=m+1$. Дейстительно $$(a+b)^{m+1}=(a+b)^m(a+b)=\sum_{k=0}^m\binom{m}ka^{m-k+1}b^k+\sum_{k=0}^n\binom{m}ka^{m-k}b^{k+1} =\binom{m}0a^{m+1}+\sum_{k=1}^{m}\binom{m}{k}a^{m-(k-1)}b^k+\sum_{k=1}^{m+1}\binom{m}{k-1}a^{m-(k-1)}b^k=$$ $$=\binom{m+1}0a^{m+1}+\sum_{k=1}^m\left(\binom{m}{k}+\binom{m}{k-1}\right)a^{(m+1)-k}b^k+\binom{m}{m}b^{m+1}= \sum_{k=0}^{m+1}\binom{m+1}{k}a^{(m+1)-k}b^k,$$ где последнее равенство верно в силу леммы 1.2.1 и того, что для любого $m\in\mathbb{N}$ $\binom{m}m=\binom{m+1}{m+1}=1$.

Следствие 1.1:

  1. $\sum_{k=0}^n\binom{n}k=2^n$,
  2. $\sum_{k=0}^n(-1)^k\binom{n}k=0$,
  3. ${S}_1:=\binom{n}0+\binom{n}2+\binom{n}4+\cdots:=\sum_{t\in\mathbb{N}_0:2t\leq{n}}\binom{n}{2t}=2^{n-1}$
    ${S}_2:=\binom{n}1+\binom{n}{3}+\binom{n}{5}+\cdots:=\sum_{t\in\mathbb{N}_0:2t+1\leq{n}}\binom{n}{2t+1}=2^{n-1}$.

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

  1. По теореме 1.1 $\sum_{k=0}^n\binom{n}{k}=(1+1)^n=2^n$.
  2. По теореме 1.1 $\sum_{k=0}^n\binom{n}{k}(-1)^k=(1-1)^n=0$.
  3. По пункту 2 $S_1-S_2=0$, следовательно, $S_1=S_2$. По пункту 1 ${S_1+S_2=2^n}$, следовательно, $S_1=S_2=\frac{2^n}{2}=2^{n-1}$.

1.3 Сочетания, размещения и перестановки элементов конечных множеств.

В данном разделе рассматривается множество $A:=\{a_1,\ldots,a_n\}$ из $|A|=n$ элементов; $n\in\mathbb{N}$, $k\in\mathbb{N}_0$, $k\leq{n}$.

Определение 1.2:

  1. Сочетанием из $n$ элеметнов множества $A$ по $k$ называется любое $k$-элементное подмножество $\{a_{i_1},\ldots,a_{i_k}\}$ множества $A$. Количество сочетаний из $n$ по $k$ обозначают $C_n^k$.
  2. Размещением из $n$ элементов множества $A$ по $k$ называют любой упорядоченный набор $(a_{i_1},\ldots,a_{i_k})$ из $k$ различных элементов множества $A$. Количество размещений из $n$ по $k$ обозначают $A_n^k$.
  3. Перестановкой элементов множества $A$ называют размещение из $n$ элементов множества $A$ по $n$. Множество перестановок элементов множества $A$ обозначают $\mathcal{P}(A)$, количество перестановок $n$-элементного множества обозначают $P_n$.

Так как количество сочетаний, размещений, перестановок элементов множества зависит только от количества элементов будем далее считать, что $A:=\overline{1,n}:=\{1,\ldots,n\}$

Теорема 1.2:
Для любых $k,n\in\mathbb{N}$ таких, что $k\leq{n}$ справедливы равенства

  1. $A_n^k=\frac{n!}{(n-k)!}$,
  2. $P_n=n!$,
  3. $C_n^k=\binom{n}k:=\frac{n!}{k!(n-k)!}$,

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

  1. Фиксируем $n\in\mathbb{N}$ и докажем утверждение индукцией по $k$
    1. При $k=1$, очевидно, $A_n^1=n=\frac{n!}{(n-1)!}$.
    2. Фиксируем $m<n$ и докажем, что из справедливости равенства при $1\leq{k}\leq{m}$ следует его справедливость при $k=m+1$. С этой целью укажем метод построения размещений из $n$ по $m+1$ используя размещения из $n$ по $m$.
      Обозначим $M_k:=\{(i_1,\ldots,i_k)\mid{i}_j\in{A},j\in\overline{1,k}\}$ - множество размещений из $n$ по $k$. Для любого размещения $s=(i_1,\ldots,i_m)\in{M}_m$ обозначим $M_{m+1}(s):=\{(i_1,\ldots,i_m,i_{m+1})\mid{i}_{m+1}\in{A}\backslash\{i_1,\ldots,i_m\}\}$.
      Для любого размещения $r\in{M}_{m+1}$ существует размещение ${s\in{M}_m}$ такое, что $r\in{M}_{m+1}(s)$, с другой стороны, для любого $s\in{M}_m$ $M_{m+1}(s)\subset{M}_{m+1}$, следовательно, $M_{m+1}=\bigcup_{s\in{M}_m}M_{m+1}(s)$. Так как для любых двух различных $s,s'\in{M}_m$ ${M_{m+1}(s)\cap{M}_{m+1}(s')=\varnothing}$, то $$A_n^{m+1}=|A_{m+1}|=\Bigl\lvert\bigcup_{s\in{M}_m}M_{m+1}(s)\Bigr\rvert=\sum_{s\in{M}_m}|M_{m+1}(s)| =(n-m)|M_m|=(n-m)A_n^m=\frac{(n-m)n!}{(n-m)!}=\frac{n!}{(n-(m+1))!}$$ где предпоследнее равенство по предположению индукции.
  2. $P_n=A_n^n=\frac{n!}{0!}=n!$.
  3. Обозначим $\tilde{M}_k:=\{B\subset{A}\mid|B|=k\}$ - множество сочетаний из $n$ по $k$, тогда очевидно, что $M_k=\bigcup_{B\in\tilde{M}_k}\mathcal{P}(B)$. Так как для любых двух различных $B,B'\in\tilde{M}_k$ $\mathcal{P}(B)\cap\mathcal{P}(B')=\varnothing$, то $$ A_n^k=|M_k|=\Bigl\lvert\bigcup_{B\in\tilde{M}_k}\mathcal{P}(B)\Bigr\rvert=\sum_{B\in\tilde{M}_k}|\mathcal{P}(B)|=\sum_{B\in\tilde{M}_k}P_k= k!|\tilde{M}_k|=k!C_n^k\Rightarrow{C}_n^k=\frac{A_n^k}{k!}=\frac{n!}{k!(n-k)!}=\binom{n}k. $$

Следствие 1.2:
Число подмножеств $n$-элементного множества равно $2^n$

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

Число подмножеств $n$-элементного множества равно $\sum_{k=1}^nC_n^k$. По теореме 1.2 и следствию 1.1 $\sum_{k=1}^nC_n^k=\sum_{k=1}^n\binom{n}k=2^n$.

Пример 1.6

  1. Число способов рассаживания на лавке $n$ человек равно $P_n=n!$.
  2. Число способов рассаживания на лавке $k$ человек из $n$ равно ${A_n^k=\frac{n!}{(n-k!)}}$.
  3. Число способов отправки в колхоз $k$ человек из $n$ равно $C_n^k=\frac{n!}{k!(n-k)!}$.
  4. Число способов отправки в колхоз какого-то количества человек из $n$ равно $\sum_{k=1}^nC_n^k=2^k$.
  5. Число способов рассаживания на лавке какого-то количества человек из $n$ равно $\sum_{k=1}^nA_n^k$.

1.4 Перестановки и их классификация.

Определение 1.3:
Пусть $M\subset\mathbb{N}_0$, $|M|=n$, $s=(i_1,\ldots,i_n)\in\mathcal{P}(M)$.
Говорят, что числа $i_k,i_m\in{M}$ образуют инверсию в перестановке $s$, если $i_k<i_m$ и $k>m$, либо $i_k>k_m$ и $k<m$.
Количество инверсий в перестановке $s$ обозначают $J(s)$.

Пример 1.7:
Пусть $s=(3,2,4,1,5)\in\mathcal{P}(\overline{1,5})$, тогда $J(s)=2+1+1+0+0=4$.

Определение 1.4:
Перестановка $s$ называется четной, если число инверсий в ней четно и не четной, если число инверсий в ней нечетно.
Функция $\delta(s)=(-1)^{J(s)}$ называется функцией четности перестановок.
Из определения в частности следует, что перестановки $s$ и $s'$ имеют разную четность тогда и только тогда, когда $\delta(s)=-\delta(s')$.

Определение 1.5:
Траспозицией называется преобразование перестановки заключающееся в перемене мест каких-либо двух ее элементов.

Теорема 1.3:
Если перестановка $s$ получена из перестановки $s'$ с помощью одной транспозиции, то перестановки $s$ и $s'$ разной четности.

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

Рассмотрим два случая.

  1. Пусть переставленные элементы стоят на соседних местах, то есть ${s'=(s_1,i,j,s_2)}$, ${s=(s_1,j,i,s_2)}$, где $s_1,s_2$ - некоторые перестановки. Тогда если $\{a,b\}\neq\{i,j\}$, то элементы $a$ и $b$ образуют инверсию в перестановке $s$ тогда и только тогда, когда они образуют инверсию в перестановке $s'$. Если $\{a,b\}=\{i,j\}$, то $a$ и $b$ образуют инверсию только в одной из перестановок $s$, $s'$. Таким образом либо $J(s)=J(s')+1$, либо $J(s)=J(s')-1$, то есть $\delta(s)=-\delta(s')$.
  2. Пусть теперь переставленные элементы не стоят на соседних местах, то есть $s'=(s_1,i,i_1,\ldots,i_k,j,s_2)$, $s=(s_1,j,i_1,\ldots,i_k,i,s_2)$, где $s_1,s_2$ - некоторые перестановки. Построим последовательность перестановок полученную транспозицией соседних элементов.
    $s'=(s_1,i,i_1,\ldots,i_k,j,s_2)$
    $s^{(1)}=(s_1,i_1,i,i_2,\ldots,i_k,j,s_2)$
    $s^{(2)}=(s_1,i_1,i_2,i,i_3,\ldots,i_k,j,s_2)$
    $\cdots$
    $s^{(k)}=(s_1,i_1,\ldots,i_k,i ,j,s_2)$
    $s^{(k+1)}=(s_1,i_1,\ldots,i_k,j,i,s_2)$
    далее аналоично сдвигаем элемент $j$ на $k$ позиций влево
    $s^{(2k+1)}=(s_1,j,i_1,\ldots,i_k,i,s_2)=s'$
    По доказанному в п. 1 при каждой транспозиции соседних элементов четность меняется. Мы поменяли четность $2k+1$ раз, следовательно, $\delta(s)=(-1)^{2k+1}\delta(s')=-\delta(s')$.

Утверждение 1.1:
Пусть $s=(i_1,\ldots,i_n)\in\mathcal{P}(\overline{1,n})$ и таблица $A=\begin{pmatrix}j_1, & \ldots, & j_n \\ 1, & \ldots, & n\end{pmatrix}$ получена из таблицы $B=\begin{pmatrix}1, & \ldots, & n \\ i_1, & \ldots, & i_n\end{pmatrix}$ перестановкой столбцов. Тогда четность перестановки $(i_1,\ldots,i_n)$ равна четности перестановки $(j_1,\ldots,j_n)$, то есть $\delta(i_1,\ldots,i_n)=\delta(j_1,\ldots,j_n)$.

Доказательство:
Для любых перестановок $s_1=(r_1,\ldots,r_n)$, $s_2=(t_1,\ldots,t_n)$, $s_1,s_2\in\mathcal{P}(\overline{1,n})$, $C:=\begin{pmatrix}r_1, & \ldots, & r_n \\ t_1, & \ldots, & t_n\end{pmatrix}$ обозанчим $\Delta(C):=\delta(s_1)\delta(s_2)$. Пусть таблица $C':=\begin{pmatrix}r'_1, & \ldots, & r'_n \\ t'_1, & \ldots, & t'_n\end{pmatrix}$ получена из таблицы $C$ перестановкой двух столбцов, тогда если обозначить $s'_1:=(r'_n,\ldots,r'_n)$, $s'_2:=(t'_1,\ldots,t'_n)$, то $$\Delta(C')=\delta(s'_1)\delta(s'_2)=-\delta(s_1)(-\delta(s_2))=\Delta(C).$$ Следовательно, если $D$ получено из $C$ произвольным числом перестановок столбцов, то $\Delta(C)=\Delta(D)$. Тогда $\Delta(A)=\Delta(B)$ и так как $\delta(1,\ldots,n)=1$, то $\delta(i_1,\ldots,i_n)=\delta(j_1,\ldots,j_n)$.

Утверждение 1.2:
Пусть $s=(i_1,\ldots,i_n)\in\mathcal{P}(\overline{1,n})$, $k\in\overline{1,n-1}$, тогда $$\delta(s)=\delta(i_1,\ldots,i_k)\delta(i_{k+1},\ldots,i_n)(-1)^{(i_1+\cdots+i_k)-(1+\cdots+k)}$$

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

$J(s)=J(i_1,\ldots,i_k)+J(i_{k+1},\ldots,i_n)+r$, где r - число инверсий, которые образуют элементы множества $M_1:=\{i_1,\ldots,i_k\}$, с элементами множества $M_2:=\{i_{k+1},\ldots,i_n\}$. Пусть $a_1,\ldots,a_k\in\overline{1,n}$ такие, что $a_1<\cdots<a_k$ и $\{a_1,\ldots,a_k\}=\{i_1,\ldots,i_k\}$. Тогда $a_1=\min{M_1}$, следовательно, все числа от $1$ до $a_1-1$ содержатся в множестве $M_2$ и образуют инверсии с $a_1$, все числа от $1$ до $a_2-1$, кроме $a_1$, содержаться в множестве $M_2$ и образуют инверсии с $a_2$ и т. д. Таким образом $$r=(a_1-1)+(a_2-2)+\cdots+(a_k-k)=\\=(a_1+\cdots+a_k)-(1+\cdots+k)=(i_1+\cdots+i_k)-(1+\cdots+k),$$ следовательно $$\delta(s)=(-1)^{J(s)}=(-1)^{J(i_1,\ldots,i_k)}(-1)^{J(i_{k+1},\ldots,i_n)}(-1)^r= \delta(i_1,\ldots,i_k)\delta(i_{k+1},\ldots,i_n)(-1)^{(i_1+\cdots+i_k)-(1+\cdots+k)}.$$ contents next