Логика в Excel   теория и практика обработки информации   Математическая логика   экономическая информатика

Аксиоматический метод в математической логике

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

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

Аксиомы натуральных чисел

Мы рассматриваем множество w объектов называемых натуральными числами. Одно из натуральных чисел называется нулём и обозначается 0 . Для любого натурального числа n одно из натуральных чисел называется следующим за числом n и обозначается n' .

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

Аксиома 1. Для любого натурального числа n: n' 0.

Аксиома 2. Для любых натуральных чисел m и n: если m'=n', то m = n.

Аксиома 3. Пусть A является подмножеством множества w со следующими свойствами:

  1. 0 О A;
  2. для любого натурального числа 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 из натуральных чисел в натуральные числа такая, что

f(0) = m,
f(n') = f(n)'.

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

  1. m Ј n,
  2. m < n или m = n,
  3. 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 называется системой Пеано, если

Используя это определение, аксиомы 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 дают полную характеризацию натуральных чисел*.

Логика в Excel   теория и практика обработки информации   Математическая логика   экономическая информатика

Знаете ли Вы, низкочастотные электромагнитные волны частотой менее 100 КГц коренным образом отличаются от более высоких частот падением скорости электромагнитных волн пропорционально корню квадратному их частоты от 300 тыс. км/с при 100 кГц до примерно 7 тыс км/с при 50 Гц.

НОВОСТИ ФОРУМАФорум Рыцари теории эфира
Рыцари теории эфира
 20.10.2019 - 19:34: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> КОМПЬЮТЕРНО-СЕТЕВАЯ БЕЗОПАСНОСТЬ ДЛЯ ВСЕХ - Карим_Хайдаров.
20.10.2019 - 19:29: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> ЗА НАМИ БЛЮДЯТ - Карим_Хайдаров.
19.10.2019 - 18:18: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Марины Мелиховой - Карим_Хайдаров.
18.10.2019 - 14:00: ЭКОЛОГИЯ - Ecology -> Биохимия мозга от проф. С.В. Савельева и не только - Карим_Хайдаров.
18.10.2019 - 07:39: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> Проблема государственного терроризма - Карим_Хайдаров.
18.10.2019 - 07:34: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Вячеслава Осиевского - Карим_Хайдаров.
18.10.2019 - 07:26: ЭКОНОМИКА И ФИНАНСЫ - Economy and Finances -> КОЛЛАПС МИРОВОЙ ФИНАНСОВОЙ СИСТЕМЫ - Карим_Хайдаров.
17.10.2019 - 18:29: ЭКСПЕРИМЕНТАЛЬНАЯ ФИЗИКА - Experimental Physics -> Ядерные эксперименты - Карим_Хайдаров.
17.10.2019 - 06:01: ЭКОЛОГИЯ - Ecology -> ПРОБЛЕМЫ МЕДИЦИНЫ - Карим_Хайдаров.
16.10.2019 - 19:24: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Ю.Ю. Болдырева - Карим_Хайдаров.
13.10.2019 - 18:09: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Светланы Вислобоковой - Карим_Хайдаров.
13.10.2019 - 08:05: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Декларация Академической Свободы - Карим_Хайдаров.
Bourabai Research Institution home page

Bourabai Research - Технологии XXI века Bourabai Research Institution