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.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, следующие условия эквивалентны:

5. m Ј n,

6. m < n или m = n,

7. 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,	(2)
m · (n + 1) = (m · n) + m.

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 если

1. a О A и

2. s(x) О A всегда, когда x О A,

тогда A = W.

Используя это определение, аксиомы 1–3 можно сформулировать кратко, сказав, что тройка <w, 0, s₀>, где s₀ обозначает функцию следования, является системой Пеано.

1.39 Определите систему Пеано <W, a, s> такую, что W = w \ {0}.

1.40 Найдите изоморфизм между системой Пеано <w, 0, s₀> и системой Пеано, построенной в решении задачи 1.39.

1.41 Для любой системы Пеано <W, a, s> существует изоморфизм между <w, 0, s₀> и <W, a, s>. Ошибка! Недопустимый объект гиперссылки.

Таким образом, любая система Пеано изоморфна системе натуральных чисел. В этом смысле аксиомы 1–3 дают полную характеризацию натуральных чисел.

4.7. Логика высказываний

Для понятия ``высказывание'' иногда используют термин ``пропозиция'', что является калькой с английского. Мы этот термин не используем, но говорим ``пропозициональный'' в смысле относящийся к логике высказываний. Центральными понятиями данной части являются пропозициональные формулы и пропозициональный вывод.

Объектный язык и метаязык

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

Пропозициональные формулы будут определены как конечные последовательности символов, взятых из определенного алфавита. Можно развить теорию конечных последовательностей на строго аксиоматической основе, но мы не будем здесь делать это. В доказательствах метатеорем мы будем свободны использовать любые хорошо известные свойства натуральных чисел которые нам могут потребоваться, не доказывая их на основе аксиом арифметики (из части 1).

Пропозициональные формулы

Пропозициональная сигнатура – это множество символов, называемых атомами. Символы ¬ (отрицание), & (конъюнкция), Ъ (дизъюнкция) и Й (импликация) называются пропозициональными связками; ¬ – унарная связка, а другие – бинарные.

Возьмём непустую пропозициональную сигнатуру s , которая не содержит ни пропозициональных связок, ни скобки (, ). Алфавит пропозициональной логики состоит из атомов сигнатуры s, пропозициональных связок и скобок. Под строкой мы понимаем конечную последовательность (строку) символов в этом алфавите.

Чтобы определить понятие пропозициональной формулы, нам требуется следующее вспомогательное определение.

Определение 7. Множество X строк замкнуто относительно правил построения (для логики высказываний), если

• каждый атом принадлежит X,

• для любой строки F, если F принадлежит X, то ¬F тоже принадлежит,

• для любых строк F, G и любой бинарной связки Д, если F и G принадлежат X, то также принадлежит (F Д G).