Отношение порядка на множестве натуральных чисел

Определение. Отношения >, <, ³, £, на множестве натуральных чисел определяются следующим образом:

- a > b означает, что существует число k такое, что a = b + k;

- a < b Û b > a;

- a ³ b Û a > b Ú a = b;

- a £ b Û a < b Ú a = b.

Теорема 1. Для любых натуральных чисел а и b имеет место одно и только одно из трех соотношений: a = b, a > b, a < b.

Доказательство. Теорема следует непосредственно из теоремы 1.2.5.

Теорема 2. Отношения >, <, ³, £ являются отношениями линейного порядка. Порядки > и < строгие, ³ и £ – нестрогие.

Доказательство. Отношение является отношением порядка, если оно транзитивно и антисимметрично. Проверяем транзитивность для отношения >:

a > b, b > c Þ a = b + k, b = c + m Þ a = (c + m)+ k = c + (m+ k)Þ a > c.

Из этого следует транзитивность для отношения <.

Для отношения ³ требуется проверить несколько случаев. Пусть a ³ b, b ³ c. Пусть это означает, например, что a > b, b = c. Тогда

a = b + k, b = c Þ a = с + k Þ a > c.

Остальные случаи проверяются аналогично или следуют из доказанного выше. Для отношения £ транзитивность следует из транзитивности отношения ³.

Проверим антисимметричность отношения >. Требуется проверить, что имеет место логическое следствие a > b, b > а Þ a = b. Но согласно теореме 1 посылки этого логического следствия не могут выполняться одновременно. Значит, это логическое следствие не может быть нарушено: не существует примера, в котором обе посылки истинны, а заключение ложно.

Проверим антисимметричность отношения ³. Требуется теперь проверить, что имеет место логическое следствие a ³ b, b ³ а Þ a = b. Но согласно теореме 1 посылки этого логического следствия могут выполняться одновременно, только если имеет место равенство в обоих случаях. Из этого следует заключение логического следствия.

Антисимметричность отношений < и £ следует из доказанного.

Доказано, что рассмотренные отношения являются отношениями порядка. Порядок f называется линейным, если для любых двух различных элементов а и b выполняется а fb или b fа. Для рассмотренных отношений выполнение этого следует из теоремы 1.

Порядок является строгим, если он антирефлексивен, то есть никакой элемент а не находится в отношении сам с собой. Для отношения > условие a > a не может выполняться в силу теоремы 1, так как выполняется а = а. Это же относится к отношению <. Порядок является нестрогим, если любой элемент находится в отношении сам с собой. Для отношения ³ (как и £ ) выполнение а ³ а следует из определения этого отношения. Теорема доказана.

Теорема 3. (Законы монотонности отношений порядка относительно сложения и умножения). Если а b, то

(1) a + c b + c;

(2) ac bc.

Доказательство. Пусть a > b. Тогда a = b + k, и, воспользовавшись коммутативностью и ассоциативностью сложения и умножения и дистрибутивностью, получаем

a + c = (b + k) + c = (b + c) + k Þ a + c > b + c;

ac = (b + k)c = bc + kc Þ ac > bc.

Для отношения «< » утверждение следует из доказанного, для «=» из однозначности сложения и умножения. Теорема доказана.

Теорема 4. (Законы сокращения для сложения и умножения). Из каждого из условий a + c b + c, ac bc следует а b.

Доказательство – в качестве упражнения.

Теорема 5. Единица – наименьшее натуральное число, то есть а ³ 1 для любого а.

Доказательство – в качестве упражнения.

Теорема 6. Любое непустое подмножество А множества натуральных чисел содержит наименьший элемент.

Доказательство. Пусть М – множество тех чисел а, которые не превосходят ни одного числа из А. 1Î М согласно теореме 5. Есть числа, не принадлежащие М. Действительно, если bÎ А, то b¢ > b, и b¢ Ï M. Значит, в М должно существовать число а такое, что а¢ Ï M. В противном случае по аксиоме индукции получили бы, что М = N. Число а принадлежит A, так как иначе a < b для всех bÎ A, и a¢ £ b для всех bÎ A. Это будет означать, что а¢ Î M. Таким образом, а – искомый наименьший элемент множества А. Теорема доказана.

Теперь можно строго доказать законность рекурсивных определений функций. Структура такого определения следующая. Для функции f(n) от натурального аргумента n первые k значений, то есть при n = 1, …, k, задаются непосредственно. Каждое следующее значение определяется через k предыдущих. Требуется доказать, что таким образом действительно определяется функция, причем единственная. О том, какие здесь имеются логические трудности, сказано в замечании, сделанном после определения операции сложения.

Здесь приводится только идея строгого доказательства. Оно опирается на понятие начального отрезка натурального ряда: отрезок – это множество чисел, не превосходящих n. Функция определяется последовательно для чисел отрезков , , , …, так что функция на каждом следующем отрезке продолжает предыдущую. Для таких отрезков нетрудно доказать по индукции существование и единственность определяемой функции. Затем это определение естественным образом распространяется на весь натуральный ряд.

1.5. Исследование аксиом системы натуральных
чисел

Как отмечалось в разделе 1.1, важнейшее требование к системе аксиом аксиоматической теории – ее непротиворечивость. Доказательство непротиворечивости осуществляется построением модели теории. Для приведенной аксиоматики можно предложить, например, следующую модель. Числа изображаются последовательностями палочек. Единица изображается одной палочкой. Число, следующее за данным, получается приписыванием к данному числу одной палочки. Ясно, что аксиомы для такой модели выполняются, но строго доказать это невозможно.

Желательное, но необязательное требование к системе аксиом – ее независимость. Это означает, что никакая аксиома не может быть выведена как следствие из других аксиом. Доказать независимость аксиомы от остальных можно построением модели, в которой эта аксиома не выполняется, а остальные выполняются.

Теорема 1. Система аксиом натуральных чисел, предложенная в разделе 1.1, независима.

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

Независимость аксиомы (N1). Пусть N = {1, 2, 3}. Операция следования задана на графе. Для этой модели аксиома (N1) не выполняется: у числа 1 есть предшествующее. Аксиома (N2) выполняется: у каждого числа одно предшествующее. Аксиома (N3) выполняется. Если в множество М включить 1 и вместе с каждым числом включить следующее за ним, то в М придется включить и 2, и 3. Значит, получим М = N.

Независимость аксиомы (N2). Пусть N = {1, 2, 3, 4}. Операция следования задана на графе. Для этой модели аксиома (N2) не выполняется, так как у числа 2 есть два предшествующих. Остальные аксиомы выполняются.

Независимость аксиомы (N3). В качестве модели возьмем два экземпляра обычного натурального ряда, объединив их в одну систему. Тогда аксиомы (N1) и (N2) выполняются. Аксиома (N3) не выполняется, так как в качестве М можно взять первый ряд. Для этого множества посылки аксиомы индукции выполняются, но М ¹ N.

Следующее требование к аксиоматической теории – ее полнота. В узком смысле это означает, что в теории можно доказать или опровергнуть любое утверждение, сформулированное на языке этой теории. Из результатов Гёделя следует, что в этом смысле формальная арифметика в принципе не может быть полной ни при какой аксиоматизации. Поэтому полноту понимают в широком смысле: аксиом достаточно, чтобы можно было доказывать теоремы, имеющие содержательный смысл. Это, конечно, не строгое определение.

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

Теорема 2. Теория натуральных чисел, предложенная в разделе 1.1, категорична.

Доказательство. Пусть N ₁ и N ₂ – две модели теории. Их элементы будем обозначать символами с индексами 1 и 2 соответственно. Установим соответствие
f: N ₁® N ₂, рекурсивно:

(1) f(1₁) = 1₂;

(2) f(a₁¢ ) = f(a₁)¢.

Законность рекурсивных определений уже установлена, значит, f – функция, определенная для всех элементов из N ₁. Она сохраняет операции (единица переводится в единицу, операция следования также сохраняется). Остается проверить, что отображение f взаимно однозначное, то есть у каждого элемента из N ₂ есть прообраз, причем единственный.

Пусть М – множество элементов из N ₂, имеющих единственный прообраз. Согласно (1) 1₂ имеет прообраз 1₁. Если еще f(a₁) = 1₂, где a₁ ¹ 1₁, то у a₁ есть предшествующий, a₁= b₁¢. Но согласно (2) f(a₁) = f(b₁¢ ) = f(b₁)¢ ¹ 1₂по аксиоме (N1). Значит, 1₂Î М.

Пусть теперь а₂Î М, и а₁ – единственный прообраз а₂. Тогда f(a₁¢ ) = f(а₁)¢ = а₂¢, то есть у а₂¢ есть прообраз a₁¢. Если b₁ – произвольный прообраз для a₂¢, то b₁ ¹ 1₁. Значит, b₁= с₁¢ для некоторого с₁. Тогда a₂¢ = f(b₁) = f(c₁¢ ) = f(c₁)¢, и по аксиоме (N2)
a₂ = f(c₁). А так как a₂ имеет единственный прообраз a₁, то с₁= а₁, b₁= с₁¢ = а₁¢. Это означает, что у а₂¢ есть единственный прообраз, и а₂¢ Î М. По аксиоме индукции
М = N, и теорема доказана.

Из курса математической логики известно, что теория, имеющая счетную модель, имеет и несчетную модель. Казалось бы, что это противоречит категоричности теории натуральных чисел. Но дело в том, что модели, о которых идет речь в логике, являются чисто формальными, соответствующие интерпретации не имеют содержательного смысла. В нашем же случае понятия, сформулированные в рамках теории, имеют совершенно определенный математический смысл. Именно при сохранении этого смысла имеет место категоричность теории.

Упражнения

Докажите тождества:

1. 1² + 2² +... + n² = .

2. 1³ + 2³ +... + n3 = .

Найдите сумму:

3. .

4. .

5. .

6. 1× 1! + 2× 2! +... + n× n!.

Докажите неравенства:

7. n² < 2n для n > 4.

8. 2ⁿ < n! для n ³ 4.

9. (1 + x)ⁿ ³ 1 + nx, где x > –1.

10. при n > 1.

11. при n > 1.

12. .

13. Найдите ошибку в доказательстве по индукции, что все числа равны между собой. Доказываем равносильное утверждение: в любом множестве из n чисел все числа равны между собой. При n = 1 утверждение верно. Пусть оно верно для n = k, докажем его для n = k + 1. Возьмем множество из произвольных
(k + 1) чисел. Удалим из него одно число а. Осталось k чисел, по индуктивному предположению они равны между собой. В частности, равны два числа b и с. Теперь удалим из множества число с и включим а. В получившемся множестве по-прежнему k чисел, значит, они тоже равны между собой. В частности, a = b. Значит, a = b = c, и все (k + 1) числа равны между собой. Индуктивный переход завершен, и утверждение доказано.

14. Докажите усиленный принцип математической индукции:

Пусть A(n) – предикат на множестве натуральных чисел. Пусть А(1) истинен и из истинности A(k) для всех чисел k < m следует истинность A(m). Тогда A(n) истинен для всех n.

⇐ Предыдущая 123 4 5 6 7 Следующая ⇒