Система натуральних чисел. Принцип математичної індукції. Теореми математичної індукції

п.1. Аксіоматична система натуральних чисел.

Визначення. Системою натуральних чисел (системою Пеано) називається алгебра, де - бінарні операції, - унарний операція (Функція В«проходженняВ»), - виділений елемент в множині, для якої виконані наступні аксіоми:

Для, (елемент називається наступним за).

Для,,.

,.

Для,.

,.

Для,.

Аксіома індукції: Нехай. Якщо безліч задовольняє умовам:

а);

б) для,;

то.

Система аксіом Пеано володіє тим властивістю, що ні одна з аксіом системи не є наслідком інших аксіом.

Із системи аксіом Пеано можна вивести всі відомі нам властивості натуральних чисел.

п.2. Теореми математичної індукції.

Теорема 1. (Принцип повної математичної індукції). Нехай - одномісний предикат на, який задовольняє умовам:

- істина.

(- істина В® - істина).

Тоді предикат тотожно істинна на.

Доказ. Позначимо через множину всіх тих, для яких істина. Перевіримо, що задовольняє умовам аксіоми індукції.

Т.к. - Істина, то.

Якщо, то - істина і по другій умові теореми індукції - істина. Тому.

Безліч задовольняє умовам аксіоми індукції. Тому.

Позначення. Безліч цілих чисел складається з натуральних чисел, нуля і чисел протилежних натуральним.

Для позначимо.

Теорема 2. (Узагальнення принципу повної математичної індукції). Нехай - одномісний предикат на, де, який задовольняє умовам:

-

істина.

(- істина В® - істина).

Тоді предикат тотожно істинна на.

Теорема 3. (Сильна форма принципу повної математичної індукції). Нехай - одномісний предикат на, який задовольняє умовам:

- істина.

(- істини В® - істина).

Тоді предикат тотожно істинна на.

Теорема 4. (Узагальнення сильної форми принципу повної математичної індукції). Нехай - одномісний предикат на, де, який задовольняє умовам:

- істина.

(- істини В® - істина).

Тоді предикат тотожно істинна на.

Числа Фібоначчі

Визначення. Числа Фібоначчі, для, визначаються рекуррентно

(1),;

для всіх.

З визначення чисел Фібоначчі випливає, що

,,,,,,,,,,.

Для обчислення чисел Фібоначчі справедлива наступна формула Біне

(3),.

З (1) та (2) випливає, що індукційне припущення, при доказі формули Біне, повинно припускати справедливість (3) для і, і значить, початкові умови повинні вимагати виконання (3) для і. Тому доказ формули Біне може проводитися за наступною теоремою математичної індукції.

Теорема 5. Нехай - одномісний предикат на, який задовольняє умовам:

- істини.

(- істини В® - істина).

Тоді предикат тотожно істинна на.

Проведемо доказ формули Біне по теоремі 5.

Для і рівність (3) приймає вигляд

,.

Очевидно, що ці рівності вірні.

Припустимо, що рівність (3) істинно для чисел і. Тоді з (2) випливає, що

.

Після простих перетворень правій частині одержимо, що

За індукції формула Біне доведена.

Теорема 6. Нехай - одномісний предикат на, який задовольняє умовам:

- істина.

(- істини В® - істина).

Тоді предикат тотожно істинна на.

п.3. Основна властивість асоціативних операцій.

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

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

Для - очевидно, так як порядок виконання операцій единственен.

Для твір може бути обчислено двома способами: або. В силу асоціативності - ці твори рівні.

Припустимо, що теорема доведена для всіх чисел, де.

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

Список літератури

Е.Е. Маренич, А.С. Маренич. Вступний курс математики. Навчально-методичне посібник. 2002

В.Є. Маренич. Журнал В«АргументВ». Задачі з теорії груп.

Кострикін А.І. Введення в алгебру. Ч.1 Основи алгебри. - М.: фізмат літ-ра, 2000

Кострикін А.І. Введення в алгебру. Ч.2 Основи алгебри. - М.: фізмат літ-ра, 2000

Кострикін А.І. Введення в алгебру. Ч.3 Основні структури алгебри. - М.: фізмат літ-ра, 2000

Кострикін А.І. Збірник задач з алгебри. Вид. третє - М.: фізмат літ-ра, 2001

Для підготовки даної роботи були використані матеріали з сайту referat.ru/

Групи. Приклади груп. Найпростіші властивості груп. Гомоморфізму і ізоморфізми груп. Підгрупи

Дано визначення групи, абелевих, нескінченною, адитивної, мультиплікативної і комутативної груп, гомоморфізм та ізоморфізм груп, наведені приклади груп і їх найпростіші властивості з доказами.

п.1. Поняття групи.

Визначення. Алгебра, де - бінарна операція, - унарний операція, називається групою, якщо виконані 3 аксіоми:

- асоціативно, тобто.

Аксіома існування правого нейтрального елемента:

Аксіома існування правого зворотного елемента:, - правий зворотний елемент до.

Визначення. Група називається комутативною (Абелевих), якщо операція комутативна, тобто.

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

Адитивна форма запису групи.

Визначення. Алгебра, де - бінарна операція, - унарна операція, називається адитивної групою, якщо виконані аксіоми:

операція асоціативна, тобто

існування правого нейтрального елемента, тобто

існування правого протилежного елементу, то є

Визначення. Група називається абелева, якщо операція - комутативна операція, тобто.

Мультиплікативна форма записи групи.

Визначення. Алгебра, де - бінарна операція, - унарна, називається мультиплікативної групою, якщо виконуються наступні аксіоми:

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

Аксіома існування правого одиничного елемента:.

Аксіома існування правого зворотного елемента:.

Визначення. Група називається комутативною, якщо операція - коммутативна, тобто.

п.2. Приклади груп.

Адитивні групи.

1) Розглянемо безліч натуральних чисел і операції. - Бінарна операція на безлічі (сума двох натуральних чисел - натуральне число), - не є унарний операцією на множині, - Не є алгеброю не група.

2). - Бінарна операція на множині, - унарний операція на безлічі, є алгеброю. Перевіримо аксіоми адитивної групи:

- виконується за властивостями цілих чисел.

- виконується за властивостями цілих чисел.

- виконується за властивостями цілих чисел.

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

3). - Бінарна операція, - унарна операція, є алгеброю.

- виконується за властивостями дійсних чисел.

виконується за властивостями дійсних чисел.

.

Значить є групою, абелева група, , Нескінченна група називається адитивною групою дійсних чисел.

4). не є алгеброю не є групою.

Мультиплікативні групи.

1). -Бінарна операція н...а множині, - не є унарний операцією на безлічі, не є алгеброю не є групою.

2) не є алгеброю не є групою, так як не є унарний операцією.

3). - Бінарна операція на множині, - не є унарний операцією не є алгеброю не є групою.

4). - Бінарна операція на множині, - унарна операція на множині, є алгеброю є групою, так як аксіоми виконуються за властивостями раціональних чисел комутативна нескінченна група називається мультиплікативною групою не рівних раціональних чисел.

5). - Бінарна операція на множині, - не є унарний операцією на безлічі, не алгебра не група.

6) симетричної групи безлічі, де. Бієкція. Розглянемо, де - бінарна операція на безлічі (по визначенню Бієкція), - унарна операція на множині, (з визначення тотожної функції і Бієкція) є алгеброю.

Перевіримо аксіоми груп:

- асоціативна операція.

властивість

властивість зворотної функції - група.

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

7) Група обертань і симетрії правильного трикутника.

I - група обертань правильного трикутника.

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

тотожне обертання.

Складемо таблицю множення (роль множення виконує композиція)

З таблиці бачимо, що композиція елементів множини безлічі, значить композиція - бінарна операція.

унарний операція на множині.

Тотожне обертання с, тоді є алгеброю.

Перевіримо аксіоми групи:

Операція композиція асоціативна на твір множин, а значить, асоціативна на безлічі.

по властивості тотожною функції.

по властивості зворотної функції.

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

II - група обертань і симетрії правильного трикутника.

Розглянемо безліч

Розглянемо

Побудуємо таблицю множення (для операції композиції)

- бінарна операція.

унарний операція.

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

Операція композиція не коммутативна (не симетрична)

Кінцева група шостого порядку називається групою обертання і симетрії правильного трикутника.

п.3. Найпростіші властивості груп.

Нехай мультиплікативна група.

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

, тобто правий зворотний елемент є лівим зворотним елементом до.

Доказ. Ліва частина дорівнює дорівнює правій частині.

тобто правий одиничний є лівим одиничним елементом.

Доказ. Ліва частина дорівнює дорівнює правій частині.

, якщо

Доказ.

якщо

Доказ.

I спосіб:

II спосіб:

I спосіб:

II спосіб:

правий

Тобто існує і единственен правий, існує і единственен лівий зворотний елементи.

якщо

Доказ.

а)

б)

Тобто існує і единственен правий, існує і единственен лівий одиничні елементи.

Доказ.

, мають в групі єдине рішення.

Доказ.

а) Перевіримо, що рішення рівняння

Ліва частина дорівнює дорівнює правій частині.

Перевіримо, що рішення єдино: нехай і - рішення рівняння. Маємо

б) Перевіримо що - рішення рівняння. Ліва частина дорівнює дорівнює правій частини.

Перевіримо, що рішення рівняння єдино: Нехай і - два рішення рівняння. Маємо

Доказ.

п.4. Гомоморфізм груп.

Визначення. Гомоморфизмом групи в групу називається відображення таке, що:

Тобто зберігає операції в групі.

Визначення. Гомоморфизмом групи в групу називається відображення таке, що:

Визначення. Гомоморфизмом групи в групу називається відображення таке, що:

Визначення. Гомоморфизмом групи в групу називається відображення таке, що:

Приклад.

Нехай

Розглянемо функцію;

Перевіримо, що - гомоморфізм:

1.

2.

3.

Значить - гомоморфізм.

Нехай.

Розглянемо функцію і.

Перевіримо:

1)

2)

3)

Значить - гомоморфізм групи в групі.

Теорема. Нехай, - мультиплікативні групи. Якщо і, то - гомоморфізм груп.

Доказ. Перевіримо, що володіє трьома властивостями визначення гомоморфізму. Одна властивість дано в умові. Доведемо, що:.

Доведемо, що:

Значить - гомоморфізм груп.

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

Нехай - мультиплікативні групи.

Визначення. Відображення називається ізоморфізмом груп, якщо володіє двома властивостями: - Бієкція і - гомоморфізм груп.

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

п.6. Підгрупи.

Визначення. Нехай - мультиплікативна група,,. Кажуть, що безліч - замкнуто щодо операції множення, якщо.

Кажуть, що - замкнуто щодо операції, якщо.

Визначення. Нехай - адитивна група,,.

Кажуть, що - замкнуто щодо бінарної операції, якщо.

Кажуть, що - замкнуто щодо операції, якщо.

Теорема. Нехай - мультиплікативна група,,.

Якщо - замкнуто щодо бінарної операції та унарний операції, то - група, яка називається підгрупою групи.

Доказ.

Так як - замкнуто щодо бінарної операції та унарний операції, то - бінарна операція на множині, а - унарна операція на множині.

Перевіримо, що. Так як, то (так як операція - унарний операція). Маємо (так як - бінарна операція на безлічі). Перевірено, що - алгебра.

Перевіримо, що - група.

Всі аксіоми групи на безлічі виконані, так як. Тому - група.

Приклад.

Розглянемо адитивну групу цілих чисел, знайдемо підгрупи цієї групи. З теорії випливає, що для того, щоб знайти підгрупу, необхідно знайти, замкнуте щодо операцій і.

Нехай; - підгрупа.

- підгрупа (тобто сама група є своєї підгрупою)

- це безліч не замкнуто щодо операції: - не утворює підгрупу.

Розглянемо безліч - безліч цілих парних чисел (Делящихся на ціле число 2). Безліч - замкнуто - підгрупа адитивної групи цілих чисел.

Розглянемо - безліч цілих чисел, кратних числу 3. Це безліч замкнуто щодо операцій і, значить - підгрупа адитивної групи цілих чисел.

Список літератури

Е.Е. Маренич, А.С. Маренич. Вступний курс математики. Навчально-методичний посібник. 2002

В.Є. Маренич. Журнал В«АргументВ». Задачі з теорії груп.

Кострикін А.І. Введення в алгебру. Ч.1 Основи алгебри. - М.: фізмат літ-ра, 2000

Кострикін А.І. Введення в алгебру. Ч.2 Основи алгебри. - М.: фізмат літ-ра, 2000

Кострикін А.І. Введення в алгебру. Ч.3 Основні структури алгебри. - М.: фізмат літ-ра, 2000

Кострикін А.І. Збірник задач з алгебри. Вид. третє - М.: фізмат літ-ра, 2001

Для підготовки даної роботи були використані матеріали з сайту referat.ru/