Реферат на тему:
Принцип математичної індукції. Підстановки. Основні алгебраїчні
структури
§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, тобто збігається з однією із своїх
циклічних підгруп
групи
Приклади.
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
Нашли опечатку? Выделите и нажмите CTRL+Enter