Ø1=0
х + 1= y + Þx = y
x + 0 = x
x + (y + 1) = (x + y) + 1
x×0 = 0
x×(y + 1) = x×y + x
Øx < 0
x < y + 1 Û x < y Ú x = y
p íx, 0ýÚ"(pÞíx, x + 1ý)Þ p
Здесь при записи аксиом использованы ранее перечисленные соглашения о компактизации изложения и известное соглашение о том, что знак умножения связывает сильнее знака сложения. Если такие соглашения не принимать, то к примеру первую аксиому следовало бы записать в виде Ø(g
Пример определяющих аксиом для новых нульместных функциональных знаков 2, 3, 4, 5 и новых двухместных предикатных знаков >, £,³,¹ :
2 = 1 + 1 | c1>c2 Ûc2<c1 |
3 = 2 + 1 | c1£c2Ûc1<c2 Úc1 = c2 |
4 = 3 + 1 | c1³c2Ûc1>c2 Úc1 = c2 |
5 = 4 + 1 | c1¹c2ÛØc1 = c2 |
Заметим, что знак < можно было бы не включать в перечень исходных знаков формальной арифметики, а ввести его с помощью определяющей аксиомы c1<c2 Û$c3(Øc3 = 0 Ùc1+ c3 = c2).
Пример доказательного текста в формальной арифметике (k = 3, е = 6, m = 1, n = 3):
1 | ¦ | Константа |
2 | ¦ | Константа |
3 | c1-------------------------------------------------- | Переменная |
4 | g | Предикат от 2,1 |
5 | Ø(g | Отрицание 4 |
6 | g | Предикат от 3,1 |
7 | Ø(g | Отрицание 6 |
8 | $c1(g | Подтверждение 7 по c1 |
9 | (Ø(g | Импликация 5,8 |
10 | Ø(g | 5: аксиома |
11 | (Ø( g | 9: пр. подт. 7, c1, 2 |
12 | Ø(g | 5: аксиома 10 |
13 | $c1(Ø( g | 8: пр. отделения для 12, 11 |
Компактизированный текст:
11 | Ø1 = 0 Þ$c1Øc1 = 0------------------------- | Правило подтверждения |
12 | Ø1 = 0-------------------------------------------- | Аксиома |
13 | $c1Øc1 = 0-------------------------------------- | Правило отд. для 12, 11 |
Словесный вариант: «Если единица не равна нулю, то тем самым существует не равное нулю число. Но единица не равна нулю. Следовательно, существует число, не равное нулю».
Тема 7. Множества и функции.
В этой теме A, B, C, D, E, F, G, X, Y, Z, X1, Z1,…, Xn, Yn, Zn обозначают попарно различные переменные. Множество – это совокупность различных объектов, мыслимая как единый новый объект. Различные объекты, из которых составлено множество, называются его элементами. Соотношение xÎA означает, что объект х есть элемент множества A. Отрицание соотношения xÎA записывается в виде xÏA. Соотношение АÌВ означает, что А есть подмножество множества В, т.е. что каждый элемент множества А является элементом множества В. Отрицание соотношения АÌВ записывается в виде АËВ. Множество, элементами которого являются все те и только те объекты вида а, для которых истинно соотношение p, обозначается через {a|p}. Множество {x|"A(xÏA)} называется пустым множеством и обозначается символом Ø. Множество {x|x = x1Ú…Úx = xn} обозначается через {x1,…,xn}. Множество {x|xÎAÚxÎB} называется объединением множеств А, В и обозначается через АÈВ. Множество {x|xÎAÙxÎB} называется пересечением множеств А, В и обозначается через АÇВ. Множество {x|xÎAÙxÏB} называется дополнением множества В относительно А или результатом удаления из множества А элементов множества В и обозначается через А\В.
Простейшиетеоремы: 3Ï{9, 7, 3}, {x+5|x2 = 4} = {3, 7], AÏA, AÌA, …
Обозначения для некоторых множеств:
N - множество натуральных чисел
Z - множество целых чисел
R - множество действительных чисел
Упорядоченная n-ка объектов x1,…,xn обозначается через (x1,…,xn) и определяется так: (x1) = x1
(x1, x2) = {{x1}, { x1, x2}}
(x1, x2, x3) = ((x1, x2), x3)
(x1, x2, x3,x4) = ((x1, x2, x3), x4)
………………………………..
Упорядоченная n-ка называется еще n-мерным упорядоченным набором, вектором, точкой, кортежем. Объект x1 называется k-той компонентой или координатой n-мерного набора (x1,…,xn) и обозначается через koor
Простейшие теоремы: (x1,…,xn) = (y1,…,yn)Û x1= y1Ù…Ùxn= yn, (9, 9, 9)¹ (9, 9), p
Функцией называется множество, любой элемент которого есть упорядоченная двойка. Множество π