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

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

п.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

Для подготовки данной применялись материалы сети Интернет из общего доступа

Группы. Примеры групп. Простейшие свойства групп. Гомоморфизмы и изоморфизмы групп. Подгруппы

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

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

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

- ассоциативно, то есть .

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

Аксиома существования правого обратного элемента: , - правый обратный элемент к .

Определение. Группа называется коммутативной (абелевой), если операция коммутативна, то есть .

Определение. Порядком группы называется число элементов в множестве , если - конечное множество. Если - бесконечное множество, то группа называется бесконечной.

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

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

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

существование правого нейтрального элемента, то есть

существование правого противоположного элемента, то есть

Определение. Группа называется абелевой, если операция - коммутативная операция, то есть .

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

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

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

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

Аксиома существования правого обратного элемента: .

Определение. Группа называется коммутативной, если операция - коммутативна, то есть .

п.2. Примеры групп.

Аддитивные группы.

1) Рассмотрим множество натуральных чисел и операции . - бинарная операция на множестве (сумма двух натуральных чисел – натуральное число), - не является унарной операцией на множестве , - не является алгеброй не группа.

2) . - бинарная операция на множестве , - унарная операция на множестве , является алгеброй. Проверим аксиомы аддитивной группы:

- выполняется по свойствам целых чисел.

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

3) . - бинарная операция, - унарная операция, является алгеброй.

- выполняется по свойствам действительных чисел.

выполняется по свойствам действительных чисел.

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

4) . не является алгеброй не является группой.

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

1) . -бинарная операция на множестве , - не является унарной операцией на множестве , не является алгеброй не является группой.

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

3) . - бинарная операция на множестве , - не является унарной операцией не является алгеброй не является группой.

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

5) . - бинарная операция на множестве , - не является унарной операцией на множестве , не алгебра не группа.

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

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

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

свойство

свойство обратной функции - группа.

Если множество - конечное множество, то группа - конечная группа и её порядок равен . Если множество - бесконечное, то - бесконечная группа. Если в множестве элементов, то группа коммутативна. Группа называется симметричной группой множества .

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

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

Под вращением треугольника понимается поворот, который вершины переводит в вершины.

тождественное вращение.

Составим таблицу умножения (роль умножения выполняет композиция)

Из таблицы видим, что композиция элементов множества множеству , значит композиция – бинарная операция.

унарная операция на множестве .

Тождественное вращение с , тогда является алгеброй.

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

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

по свойству тождественной функции.

по свойству обратной функции.

Значит, является группой, это конечная группа третьего порядка, коммутативная группа (таблица симметрична относительно главной диагонали).

II – группа вращений и симметрии правильного треугольника.

Рассмотрим множество

Рассмотрим

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

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

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

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

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

Конечная группа шестого порядка называется группой вращения и симметрии правильного треугольника.

п.3. Простейшие свойства групп.

Пусть мультипликативная группа.

Свойства.

, то есть правый обратный элемент является левым обратным элементом к .

Доказательство. Левая часть равна равна правой части.

то есть правый единичный является левым единичным элементом.

Доказательство. Левая часть равна равна правой части.

, если

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

если

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

I способ:

II способ:

I способ:

II способ:

правый

То есть существует и единственен правый, существует и единственен левый обратный элементы.

если

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

а)

б)

То есть существует и единственен правый, существует и единственен левый единичные элементы.

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

, имеют в группе единственное решение.

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

а) Проверим, что решение уравнения

Левая часть равна равна правой части.

Проверим, что решение единственно: пусть и - решения уравнения . Имеем

б) Проверим что - решение уравнения . Левая часть равна равна правой части.

Проверим, что решение уравнения единственно: Пусть и - два решения уравнения . Имеем

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

п.4. Гомоморфизмы групп.

Определение. Гомоморфизмом группы в группу называется отображение такое, что:

То есть сохраняет операции в группе .

Определение. Гомоморфизмом группы в группу называется отображение такое, что:

Пример.

Пусть

Рассмотрим функцию ;

Проверим, что - гомоморфизм:

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

Пусть .

Рассмотрим функцию и .

Проверим:

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

Теорема. Пусть , - мультипликативные группы. Если и , то - гомоморфизм групп.

Доказательство. Проверим, что обладает тремя свойствами определения гомоморфизма. Одно свойство дано в условии. Докажем, что : .

Докажем, что :

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

п.5. Изоморфизмы групп.

Пусть - мультипликативные группы.

Определение. Отображение называется изоморфизмом групп, если обладает двумя свойствами: - биекция и - гомоморфизм групп.

Если существует изоморфизм группы на , то группы называются изоморфными.

п.6. Подгруппы.

Определение. Пусть - мультипликативная группа, , . Говорят, что множество - замкнуто относительно операции умножения, если .

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

Определение. Пусть - аддитивная группа, , .

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

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

Теорема. Пусть - мультипликативная группа, , .

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

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

Так как - замкнуто относительно бинарной операции и унарной операции , то - бинарная операция на множестве , а - унарная операция на множестве .

Проверим, что . Так как , то (так как операция - унарная операция). Имеем (так как - бинарная операция на множестве ) . Проверено, что - алгебра.

Проверим, что - группа.

Все аксиомы группы на множестве выполнены, так как . Поэтому - группа.

Пример.

Рассмотрим аддитивную группу целых чисел , найдём подгруппы этой группы. Из теории следует, что для того, чтобы найти подгруппу, необходимо найти , замкнутое относительно операций и .

Пусть ; - подгруппа.

- подгруппа (то есть сама группа является своей подгруппой)

- это множество не замкнуто относительно операции : - не образует подгруппу.

Рассмотрим множество - множество целых чётных чисел (делящихся на целое число 2). Множество - замкнуто - подгруппа аддитивной группы целых чисел.

Рассмотрим - множество целых чисел, кратных числу 3. Это множество замкнуто относительно операций и , значит - подгруппа аддитивной группы целых чисел.

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

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

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

Кострикин А.И. Введение в алгебру. Ч.1 Основы алгебры. – М.: Физмат лит-ра, 2000

Кострикин А.И. Введение в алгебру. Ч.2 Основы алгебры. – М.: Физмат лит-ра, 2000

Кострикин А.И. Введение в алгебру. Ч.3 Основные структуры алгебры. – М.: Физмат лит-ра, 2000

Кострикин А.И. Сборник задач по алгебре. Изд. третье – М.: Физмат лит-ра, 2001

Для подготовки данной применялись материалы сети Интернет из общего доступа