Принцип математичної індукції. 
Підстановки. 
Основні алгебраїчні структури (реферат)

Реферат на тему:

Принцип математичної індукції. Підстановки. Основні алгебраїчні структури.

§ 1. Принцип математичної індукції.

Аксіома математичної індукції

Нехай, А — множина натуральних чисел, яка має такі властивості:

1. 1. $$1A\text{.}$$.

2. 2.Якщо натуральне число k належить до А, то й наcтупне число $$k^{\text{'}}$$ належить до А.

Тоді до, А належать всі натуральні числа.

Принцип математичної індукції (основна форма).

Якщо деяке твердження Т правильне для числа 1 і якщо із припущення, що воно правильне для натурального числа k, випливає його правильність і для наступного числа $$k^{\text{'}}$$, то твердження Т правильне для будь-якого натурального числа n.

Доведення.

Дійсно, нехай, А — множина всіх натуральних чисел, для кожного із яких твердження Т правильне. За умовою теореми $$1A$$, і якщо $$kA$$, то і наступне число $$k^{\text{'}}A$$. Отже, згідно аксіоми індукції множина, А збігається з множиною всіх натуральних чисел. Таким чином, твердження Т виконується для будь-якого натурального числа. div>

Отже, щоб довести справедливість якогось твердження для довільного натурального числа п методом математичної індукції, треба:

1) довести, що це твердження справедливе для п=1;

2) припустивши справедливість даного твердження для n=k, довести його справедливість для $$n=k^{\text{'}}=k+1\text{.}$$.

Іноді розглядуване твердження не має змісту, або неправильне при п=1, але стає справедливим при $$n>=2$$, або взагалі при $$n>=n_0$$. В цьому випадку використовується інша форма принципу математичної індукції.

Узагальнення основної форми принципу математичної індукції.

Якщо деяке твердження Т правильне для певного натурального числа $$n_0$$ і якщо з припущення, що воно правильне для натурального числа $$k>=n_0$$, випливає його правильність і для наступного числа $$k^{\text{'}}$$, то твердження Т правильне для будь-якого натурального числа n.

Друга форма принципу математичної індукції.

Якщо деяке твердження Т правильне для 1 і якщо з припущення, що воно правильне для всіх натуральних чисел, менших ніж k, випливає його правильність і для числа k, то твердження Т правильне для будь-якого натурального числа п.

Узагальнення другої форми принципу математичної індукції

Якщо деяке твердження Т правильне для натурального числа $$n_0$$ і якщо з припущення, що воно правильне для всіх натуральних чисел, менших k, випливає його правильність і для числа k, то твердження Т правильне для будь-якого натурального числа.

§ 2. Підстановки а) Перестановки.

Всяке розташування чисел 1,2,…, n в деякому визначеному порядку називається перестановкою із n чисел (чи n символів).

Якщо в деякій перестановці поміняти місцями якісь два символи (необов'язково сусідні), а всі решту символи залишити на місці, то отримається нова перестановка. Таке перетворення перестановки називається транспозицією.

Вважається, що числа i та j утворюють в даній перестановці інверсію, якщо i>j, але i знаходиться в цій перестановці раніше за j. Перестановка називається парною, якщо її символи утворюють парну кількість інверсій, і непарною — в протилежному випадку. Наприклад, перестановка (2,3,1,4,5) є парною (дві інверсії), а (2,3,1,5,4) — непарною (три інверсії).

Властивості:

1. 1.Кількість різних перестановок із n символів дорівнює добутку 1· 2·…·n = n!

Дійсно, загальний вигляд перестановки із n символів є i1, i2,…, in, де кожне із ik є одним із чисел 1,2,…, n, причому жодне з чисел не зустрічається двічі. В ролі i1 можна взяти довільне із чисел 1,2,…, n. Це дасть n різних варіантів. Якщо ж i1 вже вибрано, то в ролі i2 можна взяти тільки n-1 із чисел, що залишилися. Тоді кількість різних способів вибрати символи i1 та i2 дорівнюватиме n (n-1). Далі аналогічні міркування. >

1. 2.Від довільної перестановки із n символів можна перейти до будь-якої іншої перестановки із тих же елементів з допомогою декількох транспозицій.

Ця властивість, очевидно, випливає із того, що всі n! перестановок із символів можна розмістити в такому порядку, що кожна наступна отримана із попередньої однією транспозицією, причому починати можна з довільної перестановки. >

1. 3.Кожна транспозиція змінює парність перестановки.

Якщо транспоновані символи i та j є сусідніми, тобто перестановка має вигляд …, i, j,…, то в результаті транспозиції отримаємо перестановку …, j, i,…,.

в якій символи i та j утворюють із нерухомими символами ті ж інверсії, що й у попередній. Від переставляння символів i та j кількість інверсій зміниться на одну (якщо інверсії не було, то з’явиться, якщо ж була, то зникне), що і змінить парність перестановки.

Якщо ж між транспонованими символами i та j розміщені s символів, тобто перестановка має вигляд …, i, k1,k2,…, ks, j,…, то транспозицію символів i та j можна отримати в результаті 2s+1 транспозицій сусідніх елементів (s для переміщення i на місце ks, 1 для переставлення місцями і та j, s для переміщення j з позиції ks на місце i), після чого утвориться перестановка …, j, k1,k2,…, ks, i,…, яка матиме протилежну парність до початкової.

1. 4.При nкількість парних перестановок із n символів дорівнює кількості непарних, тобто дорівнює $$\frac{1}{2}$$ n!

Дійсно, якщо впорядкувати усі перестановки із n символів так, що кожна отримується із попередньої однією транспозицією, то сусідні перестановки матимуть протилежні парності, а число n! парне.

б) Підстановки Дві перестановки із n символів, записані одна під одною, визначають деяке взаємно однозначне відображення множини перших n натуральних чисел на себе.

Довільне взаємно однозначне відображення, А множини перших n натуральних чисел на себе називається підстановкою n-го степеня. Символічний запис:

$$A=\left(\begin{array}{c}{i}_1\\ {}_{i_1}\end{array}\begin{array}{c}{i}_2\\ {}_{i_2}\end{array}\begin{array}{c}\text{.}\text{.}\text{.}\\ \text{.}\text{.}\text{.}\end{array}\begin{array}{c}{i}_k\\ {}_{i_k}\end{array}\right)$$.

Тут число, в яке при перестановці А переходить число i, і=1,2,…, n. Читають так: при підстановці А число і1 переходить в $${}_{i_1}$$, і2 — в $${}_{i_2}$$ ,…, іn — в $${}_{i_n}$$ .

Від одного запису підстановки, А до іншого можна перейти з допомогою декількох транспозицій стовпчиків.

Приклад.

$$\left(\begin{array}{ccccc}2& 5& 1& 4& 3\\ 1& 2& 3& 4& 5\end{array}\right)$$, $$\left(\begin{array}{ccccc}2& 1& 5& 3& 4\\ 1& 3& 2& 5& 4\end{array}\right)$$, $$\left(\begin{array}{ccccc}1& 5& 2& 4& 3\\ 3& 2& 1& 4& 5\end{array}\right)$$ .

При цьому можна отримати запис вигляду $$\left(\begin{array}{cccc}1& 2& \text{.}\text{.}\text{.}& n\\ {}_1& {}_2& \text{.}\text{.}\text{.}& {}_n\end{array}\right)$$ (2.1),.

при якому різні підстановки відрізняються одна від одної тільки нижніми перестановками, звідки випливає, що кількість підстановок n-го степеня дорівнює кількості перестановок із n символів, тобто дорівнює n! Підстановка $$E=\left(\begin{array}{cccc}1& 2& \text{.}\text{.}\text{.}& n\\ 1& 2& \text{.}\text{.}\text{.}& n\end{array}\right)$$ називається тотожньою або одиничною.

Підстановка називається парною, якщо парності верхньої і нижньої її перестановок співпадають або сума інверсій у верхній і нижній перестановках є парною. В іншому випадку підстановка непарна.

Кількість непарних підстановок n-го степеня дорівнює кількості парних, тобто дорівнює $$\frac{1}{2}$$ n! Цей висновок випливає із можливості запису довільної перестановки у вигляді (2.1) і властивості 4 перестановок з n елементів.

Добутком двох підстановок n-го степеня називається підстановка n-го степеня, отримана в результаті послідовного виконання даних підстановок.

Приклад.

$$\left(\begin{array}{cccc}1& 2& 3& 4\\ 1& 3& 4& 2\end{array}\right)$$ $$\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 2& 4& 1\end{array}\right)$$ = $$\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 4& 1& 2\end{array}\right)$$. $$$$.

Множення підстановок n-го степеня при n $$$$ 3 некомутативне.

Приклад.

$$\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 2& 4& 1\end{array}\right)$$ $$\left(\begin{array}{cccc}1& 2& 3& 4\\ 1& 3& 4& 2\end{array}\right)$$ = $$\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 3& 2& 1\end{array}\right)$$.

(порівняти з попереднім).

Множення підстановок асоціативне, тобто (АВ)С=А (ВС). Дійсно, якщо символ і1 при підстановці А переходить в і2, символ і2 при підстановці В переходить в і3, а і3 при підстановці С переходить в і4, то при підстановці АВ символ і1 переходить в і3, при підстановці ВС символ і2 переходить в і4, тому при обох підстановках (АВ)С та А (ВС) символ і1 переходить в символ і4.

Ясно, що для будь-якої підстановки А: АЕ=ЕА=А.

Оберненою для підстановки, А називається така підстановка А-1 того ж степеня, що АА-1 = А-1А = Е.

Очевидним є те, що оберненою для підстановки A= $$\left(\begin{array}{cccc}1& 2& \text{.}\text{.}\text{.}& n\\ {}_1& {}_2& \text{.}\text{.}\text{.}& {}_n\end{array}\right)$$ $$$$ є підстановка А-1= $$\left(\begin{array}{cccc}{}_1& {}_2& \text{.}\text{.}\text{.}& {}_n\\ 1& 2& \text{.}\text{.}\text{.}& n\end{array}\right)$$, отримана із, А переставленням нижнього і верхнього рядків.

Циклічною підстановкою або циклом довжиною k називається така підстановка, при повторенні якої k разів кожен з її символів переходить в себе.

Приклад.

підстановка 8-го степеня $$\left(\begin{array}{cccccccc}1& 2& 3& 4& 5& 6& 7& 8\\ 1& 8& 6& 4& 5& 2& 7& 3\end{array}\right)$$ має цикл (2836) довжиною 4.

§ 3.Основні алгебраїчні структури а) Група.

Непорожня множина із визначеною в ній бінарною операцією $$$$, називається групоїдом. Групоїд, в якому визначена асоціативна операція, називається півгрупою. Півгрупа, в якій існує одиничний (нейтральний) елемент, називається моноїдом. Одиничний елемент позначають е: для будь-якого g $$$$ G [g $$$$ e = e $$$$ g = g]. Моноїд, кожен елемент якого оборотний, називається групою. Оборотним називається такий елемент множини, для якого в цій множині існує обернений. Оберненим до елемента g $$$$ G називається такий елемент g-1 цієї ж множини, для якого g $$$$ g-1= g-1 $$$$ g = e.

Повне означення групи.

Непорожня множина G, на якій визначено бінарну операцію $$$$, називається групою, якщо виконуються наступні умови:

1. 1)операція $$$$ асоціативна;

2. 2)в множині G існує одиничний елемент ;

3. 3)кожний елемент g $$$$ G множини G оборотний.

Якщо операція $$$$, визначена в групі, є комутативною, то група G називається комутативною або абелевою.

Група G називається скінченною, якщо кількість її елементів (порядок групи) скінченна.

Приклади.

1. 1.Множини цілих, раціональних, дійсних чисел відносно додавання: (Z,+), (Q,+), (R,+).

2. 2.Множини всіх додатніх раціональних, дійсних чисел відносно множення: (Q+,•), (R+,•).

3. 3.Сукупність чисел 1 та -1 утворюють групу за множенням: ({1—1},•).

4. 4.Множина всіх підстановок n-го степеня відносно операції множення (симетрична група, позначають Sn).

5. 5.Множина всіх парних підстановок n-го степеня відносно множення (знакозмінна група, позначають Аn).

Групу за додаванням називають адитивною, за множенням — мультиплікативною.

Непорожню підмножину H групи G називають підгрупою цієї групи, якщо Н є групою відносно бінарної операції, визначеної в групі G.

Перевірка того, чи непорожня підмножина Н групи G є підгрупою групи G, включає:

1. 1)чи містить Н разом із будь-якими своїми елементами g1 та g2 і результат операції між ними, тобто елемент g1 $$$$ g2;

2. 2)чи містить Н разом із будь-яким своїм елементом g і обернений йому елемент g-1.

Теорема (про перетин підгруп).

Якщо Н1 і Н2 — підгрупи групи G, то їх перетин Н1 $$$$ Н2 теж є підгрупою групи G.

Доведення.

Якщо елементи a i b належать перетину Н1 $$$$ Н2, то вони містяться в кожній з підгруп Н1 та Н2, тому елементи ab та a-1 теж містяться в кожній з підгруп, а тому і в їх перетині. Отже, Н1 $$$$ Н2 — теж підгрупа групи G. div>

Підгрупа, що складається з усіх степенів елемента g $$$$ G, називається циклічною підгрупою групи G, породженою елементом g. Позначається <g>.

Група G називається циклічною, якщо вона складається тільки зі степенів одного із своїх елементів g, тобто збігається з однією із своїх циклічних підгруп <g>. Елемент g називають твірним елементом циклічної групи <g>. Кожна циклічна група є абелевою.

Приклади.

1. Адитивна група Z цілих чисел — нескінченна циклічна група з твірним елементом 1 (можна -1).

2. Група за множенням, що складається з 1 та -1, є циклічною групою 2-го порядку з твірним елементом -1.

Ізоморфізм груп.

Групи G i G1 називаються ізоморфними, якщо між їх елементами можна встановити таку взаємно однозначну відповідність, що коли будь-яким елементам a, b $$$$ G відповідають елементи a1, b1 $$$$ G1, то результату операції a $$$$ b між елементами групи G відповідає результат операції a1 $$$$ b1 між елементами групи G1.

Тут $$$$ — позначення операції в групі G, $$$$ — в групі G1.

Приклади.

1. Адитивна група Z цілих чисел ізоморфна адитивній групі G парних чисел (відображення k $$->$$ 2k, kєZ). (Z,+) $$$$ ({2k, kєZ},+).

2. Мультиплікативна група R+ додатних дійсних чисел ізоморфна адитивній групі R всіх дійсних чисел. (R+,•) $$$$ (R,+).

При ізоморфному відображенні груп G та G1:

1. 1)одиничний елемент групи G відображається в одиничний елемент групи G1;

2. 2)будь-яка пара взаємнообернених елементів g та g-1 групи G відображається в пару взаємнообернених елементів групи G1.

б) Кільце.

Непорожня множина К, на якій визначено операції додавання і множення, називається кільцем, якщо виконуються такі умови:

1. 1)множина К є адитивною абелевою групою;

2. 2)множина К є мультиплікативною півгрупою;

3. 3)операція множення дистрибутивна відносно додавання, тобто.

$$$$ a, b, cєK [(a+b)c = ac+bcc (a+b) = ca+cb].

Позначається (К,+, •).

Кільце називають комутативним, якщо операція множення в кільці комутативна.

Приклади.

1. 1.(Z,+, •), (Q,+, •), (R,+, •).

2. 2.({2k, kєZ},+,•).

Ненульове кільце, в якому є одиничний елемент е, називають кільцем з одиницею.

Елементи а, b кільця К називаються дільниками нуля, якщо, а $$$$ $$$$ div>

але ab = нульовий елемент кільця.

Комутативне кільце з одиницею, в якому немає дільників нуля, називається цілісним кільцем (областю цілісності).

Підмножина К1 кільця К називається підкільцем кільця К, якщо К1 є кільцем відносно операцій додавання і множення, визначених в кільці К.

Перевірка того, що дана підмножина кільця є його підкільцем, включає вияснення, чи різниця й добуток довільних двох елементів підмножини К1 належить до К1.

Приклади.

1. 1.Кільце парних чисел — підкільце кільця цілих чисел.

2. 2.Кільце цілих чисел — підкільце кільця раціональних чисел.

3. 3.Кільце раціональних чисел — підкільце кільця дійсних чисел.

Ізоморфізм кілець.

Кільця К і К1 називаються ізоморфними, якщо між їх елементами можна встановити таку взаємно однозначну відповідність, що для будь-яких елементів a, b $$$$ К і відповідних їм елементів a1, b1 $$$$ К1 сумі a+b відповідає сума a1+b1, добутку ab відповідає добуток a1b1.

в)Поле.

Комутативне кільце з одиницею, в якому кожен ненульовий елемент є оборотним, називається полем. Позначають (Р,+, •).

Поле (Р,+, •) являє собою поєднання в тій самій множині Р двох абелевих груп — адитивної (Р,+) та мультиплікативної (Р{0},•).

Приклади.

1. 1.(Q,+, •).

2. 2.(R,+, •).

Ясно, що ніяке поле не має дільників нуля.

Характеристикою поля Р називають:

• -.число нуль, якщо ne=ише при n=0;

• -. натуральне число р, якщо pe = немає такого кєN, меншого ніж р, що.

ке = >

Ясно, що ненульова характеристика р поля Р є числом простим.

Підмножину Р1 поля Р називають підполем цього поля, якщо вона сама є полем відносно бінарних операцій, визначених у полі Р. Поле Р при цьому називають розширенням поля Р1.

.

.

.