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

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

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

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

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

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

належить до А.

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

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

, то твердження Т правильне для будь-якого натурального числа n.

Доведення.

. Отже, згідно аксіоми індукції множина А збігається з множиною всіх
натуральних чисел. Таким чином, твердження Т виконується для будь-якого
натурального числа.(

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

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

. В цьому випадку використовується інша форма принципу математичної
індукції.

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

, то твердження Т правильне для будь-якого натурального числа n.

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

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

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

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

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

а) Перестановки

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

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

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

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

Кількість різних перестановок із 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). Далі аналогічні
міркування. ?

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

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

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

Якщо транспоновані символи 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,… , яка матиме
протилежну парність до початкової.

n!

Дійсно, якщо впорядкувати усі перестановки із n символів так,
що кожна

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

б) Підстановки

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

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

.

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

Приклад.

.

(2.1),

називається тотожньою або одиничною.

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

n! Цей висновок випливає із можливості запису довільної перестановки у
вигляді (2.1) і властивості 4 перестановок з n елементів.

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

Приклад.

3 некомутативне.

Приклад.

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

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

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

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

, отримана із А переставленням нижнього і верхнього рядків.

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

Приклад.

має цикл (2836) довжиною 4.

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

а)Група

g = e.

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

, називається групою, якщо виконуються наступні умови:

асоціативна;

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

G множини G оборотний.

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

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

Приклади.

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

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

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

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

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

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

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

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

g2;

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

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

Н2 теж є підгрупою групи G.

Доведення.

Н2 – теж підгрупа групи G.?

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

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

Приклади.

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

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

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

b1 між елементами групи G1.

– в групі G1.

Приклади.

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

(R,+).

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

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

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

б) Кільце

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

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

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

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

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

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

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

Приклади.

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

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

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

?,

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

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

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

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

Приклади.

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

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

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

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

К1 сумі a+b відповідає сума a1+b1, добутку ab відповідає добуток a1b1.

в)Поле

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

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

Приклади.

(Q,+, •).

(R,+, •).

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

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

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

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

ке = ?.

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

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

PAGE

PAGE 8

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *