Простейшие свойства натуральных чисел

       Свойство 1. Если элементы различны, то и следующие за ними различны, то есть

a ¹ b => а ' ¹ b'

       Доказательство осуществляется методом от противного: предположим, что а ' = b', тогда (по А₃) a = b, что противоречит условию теоремы.

Свойство 2. Если элементы различны, то и предшествующие им (если они существуют) различны, то есть а ' ¹ b', => a ¹ b.

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

Предположим, что a = b, тогда, согласно А₂, имеем а ' = b', что противоречит условию теоремы.

       Свойство 3. Никакое натуральное число не равно следующему за ним.

      Свойство 4. Для любого натурального числа отличного от 1 существует предшествующее ему число.

Принцип полной математической индукции.

Теорема индукции. Пусть некоторое утверждение Р(n) сформулировано для всех натуральных чисел, и

 1) Р(1) – истинно,

2) из того, что Р(k) истинно, следует, что Р(k') также истинно.

 Тогда утверждение Р(n) истинно для всех натуральных чисел.

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

Рассмотрим множество М таких натуральных чисел n  (М Í N), для которых утверждение Р(n) истинно. Воспользуемся аксиомой A₄, то есть попытаемся доказать, что:

1) 1 Î М;

2) k Î M => k ' Î M.

Если нам это удастся, то, согласно аксиоме А₄, мы сможем сделать вывод, что M = N, то есть P(n) истинно для всех натуральных чисел.

1) По условию 1) теоремы, Р(1) истинно, следовательно, 1 Î М.

2) Если некоторое k Î М, то (по построению М) Р(k) – истинно. По условию 2) теоремы, это влечёт за собой истинность Р(k'), а значит k' Î М. 

Следовательно, по аксиоме индукции (А₄) М = N, а значит Р(n) истинно для всех натуральных чисел.

 Таким образом, аксиома индукции позволяет создать метод доказательства теорем «по индукции». Данный метод играет ключевую роль при доказательстве основных теорем арифметики, касающихся натуральных чисел. Он состоит в следующем:

1) проверяется справедливость утверждения для n =1 (база индукции),

2) предполагается справедливость этого утверждения для n = k, где k – произвольное натуральное число (индуктивное предположение), и с учётом этого предположения устанавливается справедливость утверждения для n = k' = k +1 (индукционный шаг).

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

Пример 1. Доказать,  что при  число  четное.

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

1°. Проверим истинность утверждения при n =1

число четное

2°. Предположим, что число является четным при n = k, т.е.

Проверим, будет ли четным это число при n = k +1.

Число, записанное в скобках, является четным по предположению, а число 2 k также является четным. Значит,  – четное число.

Итак, все условия теоремы математической индукции выполняются, значит, (  четно при всех натуральных значениях   n.

Пример 2.

Доказать, что при  справедливо равенство

Обозначим

1°. Проверим выполнимость равенства при n =1

Преобразуем правую часть, воспользовавшись формулами сокращенного умножения:

следовательно, равенство верно при n=1.

2°. Предположим, что равенство верно при n=k, т.е.

Докажем тогда, что что равенство верно при n=k+ 1, т.е.

 .

В самом деле,

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

Пример 3.

Доказать, что при любом натуральном n число 11  делится на 133.

Решение:

1. Проверим справедливость утверждения при n = 1: ∶133

2. Предположим, что при n=k 11  делится на 133.

Докажем, что при n=k+1 11  делится на 133:

11 +133

Первое слагаемое делится на 133 по индуктивному предположению, второе по определению делимости.

Следовательно, сумма делится на 133.

Все условия теоремы математической индукции выполняются. Значит, при любом натуральном n  делится на 133.

Рассмотрим различные виды доказательств по индукции.

Сформулируем принцип полной математической индукции, в котором делается более сильное индуктивное предположение.

Теорема (усиленный принцип полной математической индукции):

Предложение Р(n), зависящее от натуральной переменной n, верно для любого натурального числа, если выполнены следующие условия:

1) это утверждение верно для n =1, т.е. Р (1) истинно;

2) каково бы ни было натуральное число m, из предположения о том, что Р (n) истинно для всех

n < m, следует, что оно верно и для m, т.е. Р (m) истинно.

Иногда истинность утверждения Р (n) нужно доказать для всех натуральных чисел, начиная с некоторого натурального числа a. Тогда используется следующая теорема.

Теорема (обобщенный принцип полной математической индукции):

Пусть а   N. Предложение Р(n) верно для любого натурального числа n≥а, если выполнены следующие условия:

1) предложение Р (n) верно для n = а, т.е. Р (а) истинно;

2) каково бы ни было натуральное число n≥ а, из предположения о том, что Р (n) истинно, следует, что Р (n ') истинно.

Теорема (обобщенный усиленный принцип полной математической индукции):

Пусть а   N. Предложение Р(n) верно для любого натурального числа n≥а, если выполнены следующие условия:

1) предложение Р (n) верно для n = а, т.е. Р (а) истинно;

2) каково бы ни было натуральное число m ≥ а, из предположения о том, что Р (n) истинно для всех натуральных n таких, что а≤ n< m, следует истинность Р (m).

СЛОЖЕНИЕ НАТУРАЛЬНЫХ ЧИСЕЛ

Сложением натуральных чисел называется бинарная операция, удовлетворяющая следующим двум аксиомам:

 

C 2:

Пример. Найдём на основании определения сумму 2 + 2:

2 + 2 = 2 + 1 ' = (2 + 1) ' = (2 ') ' = 3 ' = 4.

Теорема 1 (о существовании и единственности сложения). Каждой паре натуральных чисел а и b соответствует однозначно определённая сумма а + b, удовлетворяющая определению сложения (аксиомам С1 и С2).

Теорема 2. Для любых натуральных чисел а, b, c выполняется ассоциативный закон сложения: (a + b) + c = a + (b +c)

Доказательство (индукцией по с):

1) При с = 1 имеем: 

2) Предположим справедливость равенства при c=k: (a+b)+k = a+(b+k).

Согласно принципу индукции теперь требуется доказать, что

(a+b)+k^/  = a+(b+k^/). Докажем это.

Таким образом, для k^/  утверждение справедливо, следовательно, согласно теореме индукции, ассоциативный закон справедлив для любых натуральных чисел.

          Теорема 3. Для любых натуральных чисел выполняется коммутативный закон сложения a + b = b + a.

Доказательству теоремы предпошлём лемму.

Лемма 1. a + 1 = 1 + a (Л1)

Докажем её индукцией по а.

1) Проверим справедливость равенства при а=1: 1 + 1 = 1 + 1  (справедливо).

2) Предположим, что равенство справедливо при a = k: k + 1 = 1 + k.

Докажем, что равенство справедливо при a = k ': k ^' + 1 = 1 + k ^'.

.

Лемма доказана.

Пусть а – фиксированное постоянное число, докажем теорему индукцией по b.

1)  Для b = 1 утверждение теоремы истинно по лемме 1.

2) Предположим, что равенство справедливо при b = k: a + k = k + a.

Докажем, что равенство справедливо при b = k ':

.

Условия теоремы математической индукции выполняются, следовательно, коммутативный закон сложения справедлив при  " b Î N, а т.к. а – фиксированное постоянное число, то при " а, в Î N.

Теорема 4. Сумма двух чисел не равна ни одному из слагаемых: a + b ¹ b.

Теорема 5.  а = b => a + c = b + c.

Следствие 1. a + с ¹ b + с = > a ¹ b (доказательство проводится методом от противного).

Теорема 6. a + c = b + c => а = b.

Следствие 2. a ¹ b = > a + с ¹ b + с (доказательство методом от противного).

Решением уравнения а + х = b (а, b – натуральные числа, х – переменная) называется такое натуральное число с, при подстановке которого вместо х в уравнение, получается верное числовое равенство а + с = b

Теорема 7. Если уравнение а + х = b имеет решение, то это решение единственно.

УМНОЖЕНИЕ НАТУРАЛЬНЫХ ЧИСЕЛ

Умножением натуральных чисел называется бинарная операция, удовлетворяющая следующим двум аксиомам:

У1: а × 1 = а

У2:

Найдём на основании определения произведение 2×2:

Теорема 1. Для любых двух чисел а и b существует однозначно определённое произведение a×b, удовлетворяющее определению умножения.

Теорема 2. Для любых натуральных чисел а, b, c выполняется дистрибутивный закон:

(a + b)×c = a×с + b×c.

Теорема 3. Для любых натуральных чисел выполняется коммутативный закон умножения a × b = b × a.

Лемма 2. a × 1 = 1 × a (Л2)

Докажем её индукцией по а.

1) Проверим справедливость равенства при а=1: 1 (справедливо).

2) Предположим, что равенство справедливо при a = k: k  1 = 1 k.

Докажем, что равенство справедливо при a = k ': k ^'  1 = 1 k ^'.

.

Лемма доказана.

Пусть а – фиксированное постоянное число, докажем теорему индукцией по b.

1)  Для b = 1 утверждение теоремы истинно по лемме 1.

2) Предположим, что равенство справедливо при b = k: a × k = k × a.

Докажем, что равенство справедливо при b= k':

.

Условия теоремы математической индукции выполняются, следовательно, коммутативный закон умножения справедлив при  " b Î N, а т.к. а – фиксированное постоянное число, то при " а, в Î N.

В теореме 2 доказана одна из форм дистрибутивного закона. Теперь мы имеем возможность доказать и вторую форму дистрибутивного закона.

Теорема 4. Для любых натуральных а, b, c: a×(b + c) = a×b + a×c.

Теорема 5. Для любых натуральных чисел а, b, c выполняется ассоциативный закон умножения: (a × b) × c = a × (b × с)

Теорема 6. а = b => a × c = b × c.

Следствие 1. a × с ¹ b × с => a ¹ b (доказательство методом от противного).