В теории, построенной в согласии с аксиоматическим методом,
начинают с небольшого количества неопределяемых (первичных) понятий,
которые по предположению удовлетворяют определенным аксиомам. Прочие
понятия, изучаемые в теории, определяются через первичные, и из аксиом и
определений выводятся теоремы. Развитие математической теории в таком стиле
– это первый шаг по направлению к её формализации.
В этой части мы исследуем применение аксиоматического метода в арифметике.
Мы используем термин "натуральные числа" в смысле, отличающемся от обычного
– ноль мы тоже включаем в натуральные числа. Такое использование этого
термина обычно для зарубежных математиков. Мы пишем "натуральные числа"
только чтобы не писать каждый раз "целые неотрицательные числа".
Аксиомы натуральных чисел
Мы рассматриваем множество w
объектов называемых натуральными числами.
Одно из натуральных чисел называется нулём и обозначается
0 . Для любого натурального числа n одно из натуральных
чисел называется следующим за числом n и обозначается
n' .
Множество натуральных чисел таково, что удовлетворяет следующим аксиомам:
Аксиома 1. Для любого натурального числа n: n'№ 0.
Аксиома 2. Для любых натуральных чисел m и n: если m'=n',
то m = n.
Аксиома 3. Пусть A является подмножеством множества w со следующими свойствами:
-
0 О A;
для любого натурального числа n: если n О A, то n' О A.
Тогда A = w.
Эти аксиомы были введены Джузеппе Пеано в 1889 году.
Начальные задачи
Определения. 1 = 0', 2 = 1', 3 = 2', 4 = 3' .
В каждой из следующих задач получите данное утверждение из аксиом.
1.1 2 № 4.
см. Решение
1.2 n' № n.
Решение. Рассмотрим множество A натуральных чисел n таких, что n' № n.
Наша цель – показать, что A = w, и мы сделаем это, используя аксиому
3. Сначала нам надо проверить, что 0 О A, то есть 0' № 0. Это
следует из аксиомы 1. Теперь возьмём любое натуральное число n и
предположим, что n О A, то есть n' № n.
Нам надо вывести из этого предположения,
что n'О A – это значит, что n" № n'.
Предположим, что n"= n'. Тогда, по аксиоме 2, n'= n, а это
противоречит тому, что n' № n.
Это доказательство, разумеется, "доказательство по индукции".
Условия 1 и 2 аксиомы 3 являются "базисом" и "индуктивным шагом".
Аксиома 3, которая служит для
построения доказательств подобных этому, называется
аксиомой индукции.
1.3 Если n № 0, то существует натуральное число m такое, что n = m'.
1.4 Такое число m единственно.
Сложение
Чтобы определить сумму двух натуральных чисел, нам надо доказать корректность
хорошо известного рекурсивного определения сложения
(уравнения (1) ниже),
то есть существование и единственность функции,
удовлетворяющей этим уравнениям.
Эти факты сформулированы здесь как задачи 1.7 и 1.8.
1.5 Существует функция f из натуральных чисел в натуральные числа такая, что
f(0) = 3, |
f(n') = f (n)'.
|
1.6 Для любого m существует функция f из натуральных чисел в натуральные
числа такая, что
1.7 Существует функция g из w ґ w в w такая, что
g(m, 0) = m, |
g(m, n') = g(m, n).
|
1.8 Такая функция g единственна.
Определение 1 (Сумма).
Для этой функции g число g(m, n) называется суммой m
и n и обозначается m + n .
Так, для любых натуральных чисел m и n:
m + 0 = m, |
m + n'= (m + n)'.
|
| (1) |
Корректность определения сложения была выведена из
аксиом Пеано Лазло Кальмаром в 1929 году.
1.9 2 + 2 = 4.
1.10 n'= n + 1.
1.11 (k + m) + n = k + (m + n).
1.12 0 + n = n.
1.13 m'+ n = m + n'.
1.14 m + n = n + m.
1.15 Если k + m = k + n, то m = n.
Порядок
Определение 2 (Порядок).
Мы пишем m Ј n , если для некоторого k: n = m + k.
1.16 0 Ј n.
см. Решение 1.17 n Ј n.
1.18 n Ј n'.
1.19 n Ј 0 тогда и только тогда, когда n = 0.
1.20 Если k Ј m и m Ј n, то k Ј n.
1.21 Если m Ј n и n Ј m, то m = n.
1.22 Если m Ј n и m № n, то m'Ј n.
1.23 Для любых m и n: m Ј n или n Ј m.
1.24 k + m Ј k + n тогда и только тогда, когда m Ј n.
Определение 3. Мы пишем m < n , если m Ј n и m № n.
1.25 2 < 4.
1.26 Любые натуральные числа m и n удовлетворяют по крайней мере
одному из условий:
m = n, m < n, n < m.
1.27 Любые натуральные числа m и n удовлетворяют в точности
одному из этих условий.
1.28 Для любых натуральных чисел m и n, следующие условия эквивалентны:
- m
Ј n,
m < n или m = n,
m < n'.
Наименьший элемент
Определение 4 (Наименьший элемент).
Элемент n множества A натуральных чисел называется его наименьшим
элементом, если для любого элемента m из A
n Ј m.
1.29 Любое множество натуральных чисел имеет не более одного наименьшего элемента.
1.30 Для любого множества A натуральных чисел
если 0 О A, то 0 является наименьшим элементом A.
1.31 Для любого множества A натуральных чисел
если 1 О A, то A имеет наименьший элемент.
1.32 Любое непустое множество натуральных чисел имеет единственный наименьший элемент.
Умножение
1.33 Для любого m существует функция f из натуральных чисел в натуральные
числа такая, что
f(0) = 0, |
f(n + 1) = f(n) + m.
|
1.34 Существует функция g из w ґ w в w такая, что
g(m, 0) = 0, |
g(m, n + 1) = g(m, n) + m.
|
1.35 Такая функция g единственна.
Определение 5 (Произведение).
Для этой функции g число g(m, n) называется произведением
m и n и обозначается m · n .
Так, для любых натуральных чисел m и n
m · 0 = 0, |
m · (n + 1) = (m · n) + m.
|
| (2) |
1.36 2 · 2 = 4.
1.37 m · n = n · m.
1.38 m · n = 0 тогда и только тогда, когда m = 0 или n = 0.
Системы Пеано
Определение 6 (Система Пеано).
Тройка <W, a, s> ,
где W – множество, a – элемент из W, а s –
функция из W в W называется системой Пеано, если
- для любого x О W: s(x) № a,
- для любых x, y О W: если s(x) = s(y), то x = y,
- для любого подмножества A множества W если
- a О A и
- s(x) О A всегда, когда x О A,
тогда A = W.
Используя это определение, аксиомы 1–3 можно сформулировать кратко, сказав,
что тройка
<w, 0, s0>,
где s0 обозначает функцию следования,
является системой Пеано.
1.39 Определите систему Пеано <W, a, s> такую, что
W = w \ {0}.
1.40 Найдите
изоморфизм между системой Пеано
<w, 0, s0> и
системой Пеано, построенной в решении задачи 1.39.
1.41 Для любой системы Пеано <W, a, s> существует изоморфизм между
<w, 0, s0> и <W, a, s>.
Таким образом, любая система Пеано изоморфна системе натуральных чисел.
В этом смысле аксиомы 1–3 дают полную характеризацию натуральных
чисел.
Следующая часть: Логика высказываний
|