Операции на множествах и их свойства. Теорема о мощности декартова произведения конечных множеств. Теорема о счетности множества рациональных чисел. Изоморфизмы и автоморфизмы алгебр, страница 2

Билет №8. Алгебры с одной бинарной операцией: полугруппы, группы. Группа подстановок.

Отображение φ, хⁿ→Х называется n-местной операцией. При n=2 – бинарная операция φ:х²=х×х→х

(a,b) х²,  (a,b) →сХ

Множество А вместе с заданной на нем совокупностью операций, т.е.  называется алгеброй.

Типы алгебр:

1. Полугруппой называется алгебра с одной  операцией и свойством ассоциативности.

 a(bc)=(ab)c

В общем случае ab≠ba, если же умножение коммутативно, то полугруппа называется коммутативной. Если полугруппа содержит такой элемент е, что для любого а ае=еа=а, то е называется единицей. Единица в полугруппе всегда единственна.

Пример:

 2/3N не алгебра (операция не должна выходить за рамки основного множества.)

2. Группой называется непустое множество с одной бинарной алгебраической операцией, если выполняются следующие условия:

1) ассоциативность (ab)c=a(bc)

2) , т.е. еа=ае=а, аА

3)  аА а^-1А, аа^-1= а^-1а=е

Число элементов группы называется порядком группы.

Пример группы:

Группа подстановок.

Х – конечное множество, состоящее из n-элементов.

Взаимнооднозначное отображение Х в себя называется подстановкой.

, S_n- множество всех подстановок

;

(ab)c=a(bc)

Билет №9. Алгебры с двумя бинарными операциями: кольца, поля. Примеры колец и полей.

Алгебра  с двумя бинарными операциями называется кольцом, если

1.  коммутативная группа

2.  полугруппа

3. a(b+c)=ab+ac

    (b+c)a=ba+ca       дистрибутивность

Пример:

1.

1+2=2+1

2.

(1*2)*3=1*(2*3)

3. является кольцом.

Алгебра   называется полем, если

1.  коммутативная группа с единицей

2.  коммутативная группа

3. a(b+c)=ab+ac

Пример:

 - поле?

1.

1.1.

1.2. е=0

      

1.3.

2.

2.1

2.2 е=1

2.3

3. ;; 

   является полем

Билет №10. Изоморфизмы и автоморфизмы алгебр. Примеры.

Две алгебры  и  называются изоморфными, если существует биекция U:А→В такая, что

1.  U – взаимнооднозначна

2.  U(ab)=U(a)*U(b), a,bA,B(биекция сохраняет операцию).

Свойства изоморфизма:

1. Единичный элемент переходит в единичный.

2. обратный элемент переходит в обратный.

3. обратное отображение :G^’→G, также является изоморфизмом.

Пример:

обратное отображение

Определение:  существует биекция

, +→, →*

сопряжение – биекция с→с

Изоморфизм алгебры на себя называется автоморфизмом.

нужно показать, что

Билет №11. Системы линейных уравнений и многочлены над кольцом вычетов по модулю m.

Теорема 1. Если число корень многочлена f=a_nxⁿ+…+a₁x+a₀ с действительными коэффициентами a_i, то тоже корень многочлена f(x).

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

n=2; f(x)=ax²+bx+c

Подставим в многочлен вместо х  число z, получим:

, где M и N – выражения не содержащие i, т.к.  - корень многочлена, то , откуда .

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

Теорема 2. Любой многочлен нечетной степени с действительными коэффициентами имеет хотя бы один действительный корень.

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

n=3; корень f(x)

по теореме (1)  тоже корень f(x)

третий корень действительный.

Кольцо вычетов.

n – фиксированное число

Два целых числа n,n^’ называются сравнимыми по , если при делении на m они дают одинаковые остатки.

>1

, m-модуль сравнения.

m=2

1=3=5=7=9=11 (mod 2)

0=2=4=6=8=10 (mod 2)

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

по определению n и n^’ сравнимы по (mod m)

                          

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

Свойство: если два числа сравнимы по некоторому модулю, то все их натуральные степени также сравнимы по этому модудю.

Утверждение: Если n-простое число, то кольцо вычетов  поле, т.е  ненулевые элементы образуют группу.

 - группа

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

Билет №12. Выборки с повторениями и без повторений, перестановки. Их число.

r - выборкой  из множества А= называется набор  элементов из А длины r.

r-выборка называется упорядоченной, если в ней задан порядок следования элементов

1. r – выборки с повторениями  это упорядоченные r-выборки, элементы которых могут повторятся.

n^r – число всех r-выборок из множества А=.

Пример:

2. Если элементы упорядоченной r-выборки попарно различны, то она называетсяr – выборкой без повторений 

Теорема. Число всех упорядоченных подмножеств из множества А без повторений равно .

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

Будем последовательно выбирать элементы множества А и размещать их в определенном порядке на r местах. На первое место можно поставить любой из n элементов А. На второе место можно поставить любой из (n-1) оставшихся элементов А и т.д. На r место можно поставить (n-r+1) элемент. По правилу умножения (Если A и B - конечные множества и | A | = m, | B | = n, то мощность множества A x B равна m x n) получаем:

Пример:

Сколькими способами можно рассадить 5 студентов за 10-ю столами(по одному за стол)?

.

3. Перестановки.

Различные  n-элементные множества, которые отличаются лишь порядком элементов(т.е. могут быть получены из того же самого множества) называются перестановками этого множества. Перестановки отличаются лишь порядком следования элементов. Состав элементов не важен. Всякое множество можно упорядочить. Множество, содержащее более одного элемента можно упорядочить не единственным способом. Найдем число этих способов.

Теорема. Число перестановок n-элементного множества равно  (это r-выборка без повторений при n=r, т.е. ).

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

Число перестановок вычисляется по правилу произведения (если объект a может быть выбран m способами, и после этого объект b может быть выбран n способами, то выбор пары (a, b) может осуществляться m x n способами). Будем последовательно выбирать элементы множества А и располагать их в определенном порядке на n местах. На первое место можно поставить любой из n элементов. На второе место выбираем любой из (n-1) оставшихся элементов и т.д. на последнее n-ое место у нас останется один элемент. По правилу умножения все n мест можно заполнить  числом способов.

Пример:

 Сколькими способами можно расставить на полке 4 книги?
N=P₄ = 4!=24