Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2023
Просмотров: 430
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
{
√
2 + i
√
2},
X
22
= {z
1
, z
2
}
(z
1
, z
2
∈ Z),
X
23
= Z,
X
24
= Z ∪ {
.
ı},
X
25
= R∪ {
.
ı};
B
1
= hω; +i, B
2
= hZ; +i, B
3
= hZ; +, −i, B
4
= hZ; ·i, B
5
= hQ; +i, B
6
= hQ; ·i,
B
7
= hQ \ {0}; ·, :i, B
8
= hR;
3
√ i, B
9
= hC; +i, B
10
= hC; ·i, B
11
= hC; ·, 2i,
B
12
= hC; +, ·i. Для множеств X
i
⊆ B
j
построить подсистемы B
j
(X
i
),
i = 1, . . . , 25, j = 1 . . . , 12.
10. Рассмотрим алгебру A = h{a, b, c, d, e}; ·i, определенную следующей таблицей
Кэли:
·
a
b
c
d
e
a
c
d
a
b
e
b
d
c
b
b
e
c
a
a
b
a
c
d
b
a
a
b
d
e
a
b
e
e
c
Какое из следующих разбиений образует конгруэнцию на алгебре A:
а) {{a, b, c}, {d, e}}; б) {{a, b}, {c, d}, {e}}?
Построить фактор-алгебру алгебры A по найденной конгруэнции.
11. Доказать, что любое л.у.м. является решеткой.
12. Доказать,
что в решетке максимальный элемент является наибольшим,
а минимальный — наименьшим.
13. Построить пример решетки с наибольшим элементом, но без наименьшего.
14. Построить булеву алгебру подмножеств трехэлементного (четырехэлемент- ного) множества.
15. Для терма x ∨ (y ∧ z) булевой алгебры найти соответствующий терм в буле- вом кольце.
Глава 3
ЧИСЛОВЫЕ СИСТЕМЫ
§ 3.1.
Бесконечные числовые системы
1.
Системы Дедекинда—Пеано
Как отмечалось в § 1.3, множество натуральных чисел можно определять двояко:
1) исходя из ∅ последовательно выражать натуральные числа как мно- жества, состоящие из предыдущих натуральных чисел;
2) задавать алгебраическую систему N = hN; 0,
0
i, удовлетворяющую си- стеме аксиом Дедекинда—Пеано. В дальнейшем мы будем рассматривать второй подход и называть такие системы системами Дедекинда—Пеано.
Теорема 3.1.1 (теорема Дедекинда—Пеано). Любые две системы Деде-
кинда—Пеано изоморфны. ¤
В § 1.3 показано, что по индукции в системе N однозначно определимы двухместные операции сложения и умножения. В дальнейшем через N будем обозначать систему Дедекинда—Пеано с этими операциями: hN; 0,
0
, +, ·i.
2.
Кольцо целых чисел
Определим с помощью системы N кольцо целых чисел Z = hZ; +, ·i.
Рассмотрим множество N
2
= {(a, b) | a, b ∈ N} и зададим отношение ∼
по следующему правилу:
(a, b) ∼ (c, d) ⇔ a + d = b + c.
3.1. БЕСКОНЕЧНЫЕ ЧИСЛОВЫЕ СИСТЕМЫ
77
Положим
(a, b) + (c, d) (a + c, b + d),
(a, b) · (c, d) (a · c + b · d, a · d + b · c).
Лемма 3.1.2. Отношение ∼ является конгруэнцией на алгебре
hN
2
; +, ·i.
Доказательство. Покажем сначала, что ∼ является отношением экви- валентности. Действительно, ∼ рефлексивно, так как из a+b = b+a следует
(a, b) ∼ (a, b). Из симметричности отношения равенства и (a, b) ∼ (c, d) сле- дует (c, d) ∼ (a, b), т. е. отношение ∼ симметрично. Установим теперь, что отношение ∼ транзитивно.
Предположим, что (a
1
, b
1
) ∼ (a
2
, b
2
) и (a
2
, b
2
) ∼ (a
3
, b
3
). Тогда по опреде- лению выполняются равенства a
1
+ b
2
= a
2
+ b
1
и a
2
+ b
3
= a
3
+ b
2
. Складывая равенства, имеем a
1
+ b
2
+ a
2
+ b
3
= a
2
+ b
1
+ a
3
+ b
2
, отсюда a
1
+ b
3
= a
3
+ b
1
,
т. е. (a
1
, b
1
) ∼ (a
3
, b
3
). Таким образом, ∼ — отношение эквивалентности.
Докажем, что отношение ∼ согласовано с операциями + и ·. Предполо- жим (a
1
, b
1
) ∼ (a
2
, b
2
) и (c
1
, d
1
) ∼ (c
2
, d
2
). Необходимо доказать:
1) (a
1
, b
1
) + (c
1
, d
1
) ∼ (a
2
, b
2
) + (c
2
, d
2
);
2) (a
1
, b
1
) · (c
1
, d
1
) ∼ (a
2
, b
2
) · (c
2
, d
2
).
Для доказательства свойства 1 нужно установить, что
(a
1
+ c
1
, b
1
+ d
1
) ∼ (a
2
+ c
2
, b
2
+ d
2
).
т. е.
(a
1
+ c
1
) + (b
2
+ d
2
) = (a
2
+ c
2
) + (b
1
+ d
1
).
По условию имеем
a
1
+ b
2
= a
2
+ b
1
и c
1
+ d
2
= c
2
+ d
1
.
(3.1)
Тогда
(a
1
+ b
2
) + (c
1
+ d
2
) = (a
2
+ b
1
) + (c
2
+ d
1
),
откуда получаем искомое равенство.
Для доказательства свойства 2 покажем, что
(a
1
c
1
+ b
1
d
1
, a
1
d
1
+ b
1
c
1
) ∼ (a
2
c
2
+ b
2
d
2
, a
2
d
2
+ b
2
c
2
),
78
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
т. е.
(a
1
c
1
+ b
1
d
1
) + (a
2
d
2
+ b
2
c
2
) = (a
2
c
2
+ b
2
d
2
) + (a
1
d
1
+ b
1
c
1
).
Умножая поочередно первое равенство из (3.1) на c
1
, d
1
, c
2
, d
2
, получаем
a
1
c
1
+ b
2
c
1
= a
2
c
1
+ b
1
c
1
, b
1
d
1
+ a
2
d
1
= a
1
d
1
+ b
2
d
1
,
a
1
c
2
+ b
2
c
2
= a
2
c
2
+ b
1
c
2
, b
1
d
2
+ a
2
d
2
= a
1
d
2
+ b
2
d
2
.
Аналогично, умножая поочередно второе равенство из (3.1) на a
1
, b
1
, a
2
, b
2
,
имеем
a
1
c
1
+ a
1
d
2
= a
1
c
2
+ a
1
d
1
, b
1
c
1
+ b
1
d
2
= b
1
c
2
+ b
1
d
1
,
a
2
c
1
+ a
2
d
2
= a
2
c
2
+ a
2
d
1
, b
2
c
1
+ b
2
d
2
= b
2
c
2
+ b
2
d
1
.
Складывая эти четыре равенства, после приведения подобных и деления пополам получаем искомое равенство. ¤
В дальнейшем носитель алгебры N будет также обозначаться через N.
Определим фактор-алгебру A = hN
2
/ ∼; +, ·i.
Лемма 3.1.3. Алгебра A является коммутативным ассоциативным
кольцом с единицей.
Доказательство. Проверка законов ассоциативности, коммутативно- сти и дистрибутивности для операций сложения и умножения осуществля- ется непосредственно. Нулевым элементом в A является класс ∼ (0, 0), еди- ничным элементом — ∼ (1, 0). Для произвольного элемента α = ∼ (a, b) про- тивоположный элемент −α равен ∼ (b, a). ¤
Множество N
2
/ ∼ разобьем на три части: 1) {∼ (a, b) | a > b},
2) {∼ (a, b) | a = b}, 3) {∼ (a, b) | a < b}. В первом случае класс ∼ (a, b) содер- жит пару (k, 0), где a = b + k. Такие классы можно интерпретировать как положительные натуральные числа k = ∼ (k, 0). Второе множество содер- жит всего один класс, который играет роль нуля в A: 0 = ∼ (0, 0). Каждый класс ∼ (a, b) из третьего множества содержит пару (0, k), где b = a + k. Эти классы интерпретируются как отрицательные числа: −k ∼ (0, k). Введен- ные обозначения позволяют рассматривать алгебру A как кольцо целых чи-
сел h{. . . , −n, . . . , −2, −1, 0, 1, 2, . . . , n, . . .}; +, ·i, которое в дальнейшем будем обозначать через hZ; +, ·i или просто Z. При этом ∼-классы будем называть
целыми числами.
3.1. БЕСКОНЕЧНЫЕ ЧИСЛОВЫЕ СИСТЕМЫ
79 3.
Поле рациональных чисел
Рассмотрим множество Z × (N \ {0}). Пару (m, n) из этого множества можно представить в виде дроби
m
n
. Если рассматривать дроби как раци- ональные числа, то некоторые из них считаются равными, например
1 2
и
2 4
, хотя записываются они по-разному. Чтобы отождествить эти записи,
определим отношение эквивалентности ∼ следующим образом:
(m
1
, n
1
) ∼ (m
2
, n
2
) ⇔ m
1
· n
2
= m
2
· n
1
.
Классы эквивалентности по отношению ∼ называются рациональными
числами, а множество всех классов эквивалентности образует множество
рациональных чисел Q =
¡
Z × (N \ {0})
¢
/ ∼.
Рассмотрим алгебру B = hZ × (N \ {0}); +, ·i, в которой операции сложе- ния и умножения определены так:
(m
1
, n
1
) + (m
2
, n
2
) (m
1
· n
2
+ m
2
· n
1
, n
1
· n
2
),
(m
1
, n
1
) · (m
2
, n
2
) (m
1
· m
2
, n
1
· n
2
)
для любых (m
1
, n
1
), (m
2
, n
2
) ∈ Z × (N \ {0}). Эти операции можно представ- лять и виде сложения и умножения дробей. Проверим, что отношение ∼
согласовано с операциями алгебры B.
Лемма 3.1.4. Отношение ∼ является конгруэнцией на алгебре B.
Доказательство. Пусть (m
1
, n
1
), (m
2
, n
2
), (m
0
1
, n
0
1
), (m
0
2
, n
0
2
) — пары из Z × (N \ {0}) с условиями
(m
1
, n
1
) ∼ (m
0
1
, n
0
1
) и (m
2
, n
2
) ∼ (m
0
2
, n
0
2
).
(3.2)
Требуется доказать, что:
1) ((m
1
, n
1
) + (m
2
, n
2
)) ∼ ((m
0
1
, n
0
1
) + (m
0
2
, n
0
2
));
2) ((m
1
, n
1
) · (m
2
, n
2
)) ∼ ((m
0
1
, n
0
1
) · (m
0
2
, n
0
2
)).
Для проверки свойства 1 имеем
(m
1
, n
1
) + (m
2
, n
2
) = (m
1
· n
2
+ m
2
· n
1
, n
1
· n
2
),
(m
0
1
, n
0
1
) + (m
0
2
, n
0
2
) = (m
0
1
· n
0
2
+ m
0
2
· n
0
1
, n
0
1
· n
0
2
).
80
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
Нужно установить, что
(m
1
· n
2
+ m
2
· n
1
) · (n
0
1
· n
0
2
) = (m
0
1
· n
0
2
+ m
0
2
· n
0
1
) · (n
1
· n
2
).
(3.3)
Зная из (3.2), что
m
1
· n
0
1
= m
0
1
· n
1
и m
2
· n
0
2
= m
0
2
· n
2
,
(3.4)
имеем
(m
1
· n
2
+ m
2
· n
1
) · (n
0
1
· n
0
2
) = (m
1
· n
2
) · (n
0
1
· n
0
2
) + (m
2
· n
1
) · (n
0
1
· n
0
2
) =
= (m
1
· n
0
1
) · (n
2
· n
0
2
) + (m
2
· n
0
2
) · (n
1
· n
0
1
) = {в силу (3.4)} =
= (m
0
1
· n
1
) · (n
2
· n
0
2
) + (m
0
2
· n
2
) · (n
1
· n
0
1
) =
= (m
0
1
· n
0
2
) · (n
1
· n
2
) + (m
0
2
· n
0
1
) · (n
1
· n
2
) = ((m
0
1
· n
0
2
) + (m
0
2
· n
0
1
)) · (n
1
· n
2
),
и тем самым равенство (3.3) установлено.
Проверка свойства 2 проводится аналогично и оставляется читателю в ка- честве упражнения. ¤
Таким образом, отношение ∼ — конгруэнция, и фактор-алгебра B/ ∼
образует множество рациональных чисел Q с обычными операциями сложе- ния и умножения: B/ ∼ = hQ; +, ·i. В полученной алгебре выполняются все аксиомы поля. Нулевым рациональным числом является класс ∼ (0, 1), еди- ницей — класс ∼ (1, 1), числом, противоположным числу ∼ (m, n), является число −(∼ (m, n)) ∼ (−m, n), обратным ненулевому числу ∼ (m, n) — чис- ло (∼ (m, n))
−1
∼ (±n, ±m), где знак плюс берется при m > 0 и минус —
при m < 0.
4.
Поле действительных чисел
Последовательность (x
n
)
n∈ω
рациональных чисел называется фундамен-
тальной, если для любого рационального числа ε > 0 существует такое n
0
,
что |x
p
−x
q
| < ε для всех p и q, больших n
0
. Фундаментальные последователь- ности (x
n
)
n∈ω
и (y
n
)
n∈ω
называются эквивалентными: (x
n
) ∼ (y
n
), если для любого рационального числа ε > 0 существует такое n
0
, что |x
p
− y
q
| < ε для всех p и q, больших n
0
. Классы эквивалентности фундаментальных после- довательностей ∼ (x
n
) называются действительными или вещественными
3.1. БЕСКОНЕЧНЫЕ ЧИСЛОВЫЕ СИСТЕМЫ
81
числами. Таким образом, множество R действительных чисел является фактор-множеством X/ ∼, где
X = {(x
n
) | (x
n
) — фундаментальная последовательность}.
На множестве R определим основные арифметические операции.
Для этого рассмотрим алгебру X = hX; +, ·i со следующими операциями:
(x
n
) + (y
n
) (x
n
+ y
n
), (x
n
) · (y
n
) (
x
n
· y
n
). Легко проверяется, что от- ношение ∼ является конгруэнцией алгебры X. Фактор-алгебра X/∼ обра- зует множество действительных чисел с обычными операциями сложения и умножения. В алгебре hR; +, ·i выполняются все аксиомы поля. Нулевым элементом является класс ∼ (0); единицей — класс ∼ (1); противоположным классу ∼ (x
n
) является класс −(∼ (x
n
)) ∼ (−x
n
); обратным ненулевому классу ∼ (x
n
), где (x
n
) является последовательностью без нулевых элемен- тов, — класс (∼ (x
n
))
−1
∼ ((x
n
)
−1
).
Отметим, что каждый класс ∼ (x
n
) содержит единственную последова- тельность (x
0
n
), такую, что
x
0
n
= ±(a
k
10
k
+ a
k−1 10
k−1
+ . . . + a
1 10 1
+ a
0 10 0
+
+a
−1 10
−1
+ a
−2 10
−2
+ . . . + a
−n
10
−n
),
где a
i
∈ {0, 1, . . . , 9} и не существует n с условием a
−i
= 9 при i > n. Поэтому для обозначения действительных чисел используются следующие записи,
называемые (бесконечными) десятичными дробями:
±a
k
a
k−1
. . . a
1
a
0
.a
−1
a
−2
. . . a
−n
. . . .
Каждая фундаментальная последовательность (x
n
) может иметь или не иметь предел в множестве рациональных чисел. В первом случае любая последовательность из класса ∼ (x
n
) сходится к одному и тому же рацио- нальному числу q, и поэтому такие классы удобно называть рациональными
числами. Во втором случае, когда предела в Q не существует, класс ∼ (x
n
)
называется иррациональным числом.
Десятичная дробь N.a
1
a
2
. . . a
n
. . ., где N ∈ Z, называется периодиче-
ской, если существуют такие натуральные числа p, q, что a
k+p
= a
k
для всех k > q. Для обозначения периодической дроби используется запись
N.a
1
a
2
. . . a
q
(a
q+1
a
q+2
. . . a
q+p
), где совокупность цифр a
q+1
a
q+2
. . . a
q+p
назы- вается периодом дроби.
82
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
Предложение 3.1.5. Бесконечная десятичная дробь тогда и только
тогда является рациональным числом, когда она периодична. ¤
Поскольку для любого конечного алфавита A множество слов W (A) счет- но, а множество действительных чисел континуально, справедливо следую- щее предложение.
Предложение 3.1.6. Не существует конечного алфавита, при помо-
щи слов которого можно обозначить все действительные числа. ¤
5.
Поле комплексных чисел
Множество C комплексных чисел строится из множества действительных чисел по правилу C = R
2
. Операции сложения и умножения определяются по следующим правилам: (a
1
, b
1
)+(a
2
, b
2
) (a
1
+a
2
, b
1
+b
2
), (a
1
, b
1
)·(a
2
, b
2
)
(a
1
a
2
− b
1
b
2
, a
1
b
2
+ a
2
b
1
). Алгебра hC; +, ·i удовлетворяет всем аксиомам поля.
Естественным образом определяются мономорфизмы, позволяющие вло- жить алгебру hN; +, ·i в алгебру hZ; +, ·i, алгебру hZ; +, ·i — в алгебру
hQ; +, ·i, алгебру hQ; +, ·i — в алгебру hR; +, ·i, алгебру hR; +, ·i — в алгебру
hC; +, ·i. Поэтому с точностью до изоморфизма можно считать, что каж- дая из этих алгебр является подалгеброй каждой из последующих алгебр и имеют место включения N ⊂ Z ⊂ Q ⊂ R ⊂ C.
Приведенные конструкции позволяют проследить процесс образования числовых систем с помощью основных теоретико-множественных операций исходя из пустого множества.
§ 3.2.
Системы счисления
1.
Позиционные системы счисления
В современных компьютерах любая информация представляется в ви- де двоичных кодов, т. е. упорядоченных наборов двух различных символов,
которые обычно обозначаются через 0 и 1. В связи с этим часто прихо- дится использовать системы счисления, отличные от привычной десятичной системы счисления. При этом в основном используются позиционные систе- мы счисления, которые строятся по тем же принципам, что и десятичная система.
√
2 + i
√
2},
X
22
= {z
1
, z
2
}
(z
1
, z
2
∈ Z),
X
23
= Z,
X
24
= Z ∪ {
.
ı},
X
25
= R∪ {
.
ı};
B
1
= hω; +i, B
2
= hZ; +i, B
3
= hZ; +, −i, B
4
= hZ; ·i, B
5
= hQ; +i, B
6
= hQ; ·i,
B
7
= hQ \ {0}; ·, :i, B
8
= hR;
3
√ i, B
9
= hC; +i, B
10
= hC; ·i, B
11
= hC; ·, 2i,
B
12
= hC; +, ·i. Для множеств X
i
⊆ B
j
построить подсистемы B
j
(X
i
),
i = 1, . . . , 25, j = 1 . . . , 12.
10. Рассмотрим алгебру A = h{a, b, c, d, e}; ·i, определенную следующей таблицей
Кэли:
·
a
b
c
d
e
a
c
d
a
b
e
b
d
c
b
b
e
c
a
a
b
a
c
d
b
a
a
b
d
e
a
b
e
e
c
Какое из следующих разбиений образует конгруэнцию на алгебре A:
а) {{a, b, c}, {d, e}}; б) {{a, b}, {c, d}, {e}}?
Построить фактор-алгебру алгебры A по найденной конгруэнции.
11. Доказать, что любое л.у.м. является решеткой.
12. Доказать,
что в решетке максимальный элемент является наибольшим,
а минимальный — наименьшим.
13. Построить пример решетки с наибольшим элементом, но без наименьшего.
14. Построить булеву алгебру подмножеств трехэлементного (четырехэлемент- ного) множества.
15. Для терма x ∨ (y ∧ z) булевой алгебры найти соответствующий терм в буле- вом кольце.
Глава 3
ЧИСЛОВЫЕ СИСТЕМЫ
§ 3.1.
Бесконечные числовые системы
1.
Системы Дедекинда—Пеано
Как отмечалось в § 1.3, множество натуральных чисел можно определять двояко:
1) исходя из ∅ последовательно выражать натуральные числа как мно- жества, состоящие из предыдущих натуральных чисел;
2) задавать алгебраическую систему N = hN; 0,
0
i, удовлетворяющую си- стеме аксиом Дедекинда—Пеано. В дальнейшем мы будем рассматривать второй подход и называть такие системы системами Дедекинда—Пеано.
Теорема 3.1.1 (теорема Дедекинда—Пеано). Любые две системы Деде-
кинда—Пеано изоморфны. ¤
В § 1.3 показано, что по индукции в системе N однозначно определимы двухместные операции сложения и умножения. В дальнейшем через N будем обозначать систему Дедекинда—Пеано с этими операциями: hN; 0,
0
, +, ·i.
2.
Кольцо целых чисел
Определим с помощью системы N кольцо целых чисел Z = hZ; +, ·i.
Рассмотрим множество N
2
= {(a, b) | a, b ∈ N} и зададим отношение ∼
по следующему правилу:
(a, b) ∼ (c, d) ⇔ a + d = b + c.
3.1. БЕСКОНЕЧНЫЕ ЧИСЛОВЫЕ СИСТЕМЫ
77
Положим
(a, b) + (c, d) (a + c, b + d),
(a, b) · (c, d) (a · c + b · d, a · d + b · c).
Лемма 3.1.2. Отношение ∼ является конгруэнцией на алгебре
hN
2
; +, ·i.
Доказательство. Покажем сначала, что ∼ является отношением экви- валентности. Действительно, ∼ рефлексивно, так как из a+b = b+a следует
(a, b) ∼ (a, b). Из симметричности отношения равенства и (a, b) ∼ (c, d) сле- дует (c, d) ∼ (a, b), т. е. отношение ∼ симметрично. Установим теперь, что отношение ∼ транзитивно.
Предположим, что (a
1
, b
1
) ∼ (a
2
, b
2
) и (a
2
, b
2
) ∼ (a
3
, b
3
). Тогда по опреде- лению выполняются равенства a
1
+ b
2
= a
2
+ b
1
и a
2
+ b
3
= a
3
+ b
2
. Складывая равенства, имеем a
1
+ b
2
+ a
2
+ b
3
= a
2
+ b
1
+ a
3
+ b
2
, отсюда a
1
+ b
3
= a
3
+ b
1
,
т. е. (a
1
, b
1
) ∼ (a
3
, b
3
). Таким образом, ∼ — отношение эквивалентности.
Докажем, что отношение ∼ согласовано с операциями + и ·. Предполо- жим (a
1
, b
1
) ∼ (a
2
, b
2
) и (c
1
, d
1
) ∼ (c
2
, d
2
). Необходимо доказать:
1) (a
1
, b
1
) + (c
1
, d
1
) ∼ (a
2
, b
2
) + (c
2
, d
2
);
2) (a
1
, b
1
) · (c
1
, d
1
) ∼ (a
2
, b
2
) · (c
2
, d
2
).
Для доказательства свойства 1 нужно установить, что
(a
1
+ c
1
, b
1
+ d
1
) ∼ (a
2
+ c
2
, b
2
+ d
2
).
т. е.
(a
1
+ c
1
) + (b
2
+ d
2
) = (a
2
+ c
2
) + (b
1
+ d
1
).
По условию имеем
a
1
+ b
2
= a
2
+ b
1
и c
1
+ d
2
= c
2
+ d
1
.
(3.1)
Тогда
(a
1
+ b
2
) + (c
1
+ d
2
) = (a
2
+ b
1
) + (c
2
+ d
1
),
откуда получаем искомое равенство.
Для доказательства свойства 2 покажем, что
(a
1
c
1
+ b
1
d
1
, a
1
d
1
+ b
1
c
1
) ∼ (a
2
c
2
+ b
2
d
2
, a
2
d
2
+ b
2
c
2
),
78
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
т. е.
(a
1
c
1
+ b
1
d
1
) + (a
2
d
2
+ b
2
c
2
) = (a
2
c
2
+ b
2
d
2
) + (a
1
d
1
+ b
1
c
1
).
Умножая поочередно первое равенство из (3.1) на c
1
, d
1
, c
2
, d
2
, получаем
a
1
c
1
+ b
2
c
1
= a
2
c
1
+ b
1
c
1
, b
1
d
1
+ a
2
d
1
= a
1
d
1
+ b
2
d
1
,
a
1
c
2
+ b
2
c
2
= a
2
c
2
+ b
1
c
2
, b
1
d
2
+ a
2
d
2
= a
1
d
2
+ b
2
d
2
.
Аналогично, умножая поочередно второе равенство из (3.1) на a
1
, b
1
, a
2
, b
2
,
имеем
a
1
c
1
+ a
1
d
2
= a
1
c
2
+ a
1
d
1
, b
1
c
1
+ b
1
d
2
= b
1
c
2
+ b
1
d
1
,
a
2
c
1
+ a
2
d
2
= a
2
c
2
+ a
2
d
1
, b
2
c
1
+ b
2
d
2
= b
2
c
2
+ b
2
d
1
.
Складывая эти четыре равенства, после приведения подобных и деления пополам получаем искомое равенство. ¤
В дальнейшем носитель алгебры N будет также обозначаться через N.
Определим фактор-алгебру A = hN
2
/ ∼; +, ·i.
Лемма 3.1.3. Алгебра A является коммутативным ассоциативным
кольцом с единицей.
Доказательство. Проверка законов ассоциативности, коммутативно- сти и дистрибутивности для операций сложения и умножения осуществля- ется непосредственно. Нулевым элементом в A является класс ∼ (0, 0), еди- ничным элементом — ∼ (1, 0). Для произвольного элемента α = ∼ (a, b) про- тивоположный элемент −α равен ∼ (b, a). ¤
Множество N
2
/ ∼ разобьем на три части: 1) {∼ (a, b) | a > b},
2) {∼ (a, b) | a = b}, 3) {∼ (a, b) | a < b}. В первом случае класс ∼ (a, b) содер- жит пару (k, 0), где a = b + k. Такие классы можно интерпретировать как положительные натуральные числа k = ∼ (k, 0). Второе множество содер- жит всего один класс, который играет роль нуля в A: 0 = ∼ (0, 0). Каждый класс ∼ (a, b) из третьего множества содержит пару (0, k), где b = a + k. Эти классы интерпретируются как отрицательные числа: −k ∼ (0, k). Введен- ные обозначения позволяют рассматривать алгебру A как кольцо целых чи-
сел h{. . . , −n, . . . , −2, −1, 0, 1, 2, . . . , n, . . .}; +, ·i, которое в дальнейшем будем обозначать через hZ; +, ·i или просто Z. При этом ∼-классы будем называть
целыми числами.
3.1. БЕСКОНЕЧНЫЕ ЧИСЛОВЫЕ СИСТЕМЫ
79 3.
Поле рациональных чисел
Рассмотрим множество Z × (N \ {0}). Пару (m, n) из этого множества можно представить в виде дроби
m
n
. Если рассматривать дроби как раци- ональные числа, то некоторые из них считаются равными, например
1 2
и
2 4
, хотя записываются они по-разному. Чтобы отождествить эти записи,
определим отношение эквивалентности ∼ следующим образом:
(m
1
, n
1
) ∼ (m
2
, n
2
) ⇔ m
1
· n
2
= m
2
· n
1
.
Классы эквивалентности по отношению ∼ называются рациональными
числами, а множество всех классов эквивалентности образует множество
рациональных чисел Q =
¡
Z × (N \ {0})
¢
/ ∼.
Рассмотрим алгебру B = hZ × (N \ {0}); +, ·i, в которой операции сложе- ния и умножения определены так:
(m
1
, n
1
) + (m
2
, n
2
) (m
1
· n
2
+ m
2
· n
1
, n
1
· n
2
),
(m
1
, n
1
) · (m
2
, n
2
) (m
1
· m
2
, n
1
· n
2
)
для любых (m
1
, n
1
), (m
2
, n
2
) ∈ Z × (N \ {0}). Эти операции можно представ- лять и виде сложения и умножения дробей. Проверим, что отношение ∼
согласовано с операциями алгебры B.
Лемма 3.1.4. Отношение ∼ является конгруэнцией на алгебре B.
Доказательство. Пусть (m
1
, n
1
), (m
2
, n
2
), (m
0
1
, n
0
1
), (m
0
2
, n
0
2
) — пары из Z × (N \ {0}) с условиями
(m
1
, n
1
) ∼ (m
0
1
, n
0
1
) и (m
2
, n
2
) ∼ (m
0
2
, n
0
2
).
(3.2)
Требуется доказать, что:
1) ((m
1
, n
1
) + (m
2
, n
2
)) ∼ ((m
0
1
, n
0
1
) + (m
0
2
, n
0
2
));
2) ((m
1
, n
1
) · (m
2
, n
2
)) ∼ ((m
0
1
, n
0
1
) · (m
0
2
, n
0
2
)).
Для проверки свойства 1 имеем
(m
1
, n
1
) + (m
2
, n
2
) = (m
1
· n
2
+ m
2
· n
1
, n
1
· n
2
),
(m
0
1
, n
0
1
) + (m
0
2
, n
0
2
) = (m
0
1
· n
0
2
+ m
0
2
· n
0
1
, n
0
1
· n
0
2
).
80
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
Нужно установить, что
(m
1
· n
2
+ m
2
· n
1
) · (n
0
1
· n
0
2
) = (m
0
1
· n
0
2
+ m
0
2
· n
0
1
) · (n
1
· n
2
).
(3.3)
Зная из (3.2), что
m
1
· n
0
1
= m
0
1
· n
1
и m
2
· n
0
2
= m
0
2
· n
2
,
(3.4)
имеем
(m
1
· n
2
+ m
2
· n
1
) · (n
0
1
· n
0
2
) = (m
1
· n
2
) · (n
0
1
· n
0
2
) + (m
2
· n
1
) · (n
0
1
· n
0
2
) =
= (m
1
· n
0
1
) · (n
2
· n
0
2
) + (m
2
· n
0
2
) · (n
1
· n
0
1
) = {в силу (3.4)} =
= (m
0
1
· n
1
) · (n
2
· n
0
2
) + (m
0
2
· n
2
) · (n
1
· n
0
1
) =
= (m
0
1
· n
0
2
) · (n
1
· n
2
) + (m
0
2
· n
0
1
) · (n
1
· n
2
) = ((m
0
1
· n
0
2
) + (m
0
2
· n
0
1
)) · (n
1
· n
2
),
и тем самым равенство (3.3) установлено.
Проверка свойства 2 проводится аналогично и оставляется читателю в ка- честве упражнения. ¤
Таким образом, отношение ∼ — конгруэнция, и фактор-алгебра B/ ∼
образует множество рациональных чисел Q с обычными операциями сложе- ния и умножения: B/ ∼ = hQ; +, ·i. В полученной алгебре выполняются все аксиомы поля. Нулевым рациональным числом является класс ∼ (0, 1), еди- ницей — класс ∼ (1, 1), числом, противоположным числу ∼ (m, n), является число −(∼ (m, n)) ∼ (−m, n), обратным ненулевому числу ∼ (m, n) — чис- ло (∼ (m, n))
−1
∼ (±n, ±m), где знак плюс берется при m > 0 и минус —
при m < 0.
4.
Поле действительных чисел
Последовательность (x
n
)
n∈ω
рациональных чисел называется фундамен-
тальной, если для любого рационального числа ε > 0 существует такое n
0
,
что |x
p
−x
q
| < ε для всех p и q, больших n
0
. Фундаментальные последователь- ности (x
n
)
n∈ω
и (y
n
)
n∈ω
называются эквивалентными: (x
n
) ∼ (y
n
), если для любого рационального числа ε > 0 существует такое n
0
, что |x
p
− y
q
| < ε для всех p и q, больших n
0
. Классы эквивалентности фундаментальных после- довательностей ∼ (x
n
) называются действительными или вещественными
3.1. БЕСКОНЕЧНЫЕ ЧИСЛОВЫЕ СИСТЕМЫ
81
числами. Таким образом, множество R действительных чисел является фактор-множеством X/ ∼, где
X = {(x
n
) | (x
n
) — фундаментальная последовательность}.
На множестве R определим основные арифметические операции.
Для этого рассмотрим алгебру X = hX; +, ·i со следующими операциями:
(x
n
) + (y
n
) (x
n
+ y
n
), (x
n
) · (y
n
) (
1 ... 5 6 7 8 9 10 11 12 ... 29
x
n
· y
n
). Легко проверяется, что от- ношение ∼ является конгруэнцией алгебры X. Фактор-алгебра X/∼ обра- зует множество действительных чисел с обычными операциями сложения и умножения. В алгебре hR; +, ·i выполняются все аксиомы поля. Нулевым элементом является класс ∼ (0); единицей — класс ∼ (1); противоположным классу ∼ (x
n
) является класс −(∼ (x
n
)) ∼ (−x
n
); обратным ненулевому классу ∼ (x
n
), где (x
n
) является последовательностью без нулевых элемен- тов, — класс (∼ (x
n
))
−1
∼ ((x
n
)
−1
).
Отметим, что каждый класс ∼ (x
n
) содержит единственную последова- тельность (x
0
n
), такую, что
x
0
n
= ±(a
k
10
k
+ a
k−1 10
k−1
+ . . . + a
1 10 1
+ a
0 10 0
+
+a
−1 10
−1
+ a
−2 10
−2
+ . . . + a
−n
10
−n
),
где a
i
∈ {0, 1, . . . , 9} и не существует n с условием a
−i
= 9 при i > n. Поэтому для обозначения действительных чисел используются следующие записи,
называемые (бесконечными) десятичными дробями:
±a
k
a
k−1
. . . a
1
a
0
.a
−1
a
−2
. . . a
−n
. . . .
Каждая фундаментальная последовательность (x
n
) может иметь или не иметь предел в множестве рациональных чисел. В первом случае любая последовательность из класса ∼ (x
n
) сходится к одному и тому же рацио- нальному числу q, и поэтому такие классы удобно называть рациональными
числами. Во втором случае, когда предела в Q не существует, класс ∼ (x
n
)
называется иррациональным числом.
Десятичная дробь N.a
1
a
2
. . . a
n
. . ., где N ∈ Z, называется периодиче-
ской, если существуют такие натуральные числа p, q, что a
k+p
= a
k
для всех k > q. Для обозначения периодической дроби используется запись
N.a
1
a
2
. . . a
q
(a
q+1
a
q+2
. . . a
q+p
), где совокупность цифр a
q+1
a
q+2
. . . a
q+p
назы- вается периодом дроби.
82
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
Предложение 3.1.5. Бесконечная десятичная дробь тогда и только
тогда является рациональным числом, когда она периодична. ¤
Поскольку для любого конечного алфавита A множество слов W (A) счет- но, а множество действительных чисел континуально, справедливо следую- щее предложение.
Предложение 3.1.6. Не существует конечного алфавита, при помо-
щи слов которого можно обозначить все действительные числа. ¤
5.
Поле комплексных чисел
Множество C комплексных чисел строится из множества действительных чисел по правилу C = R
2
. Операции сложения и умножения определяются по следующим правилам: (a
1
, b
1
)+(a
2
, b
2
) (a
1
+a
2
, b
1
+b
2
), (a
1
, b
1
)·(a
2
, b
2
)
(a
1
a
2
− b
1
b
2
, a
1
b
2
+ a
2
b
1
). Алгебра hC; +, ·i удовлетворяет всем аксиомам поля.
Естественным образом определяются мономорфизмы, позволяющие вло- жить алгебру hN; +, ·i в алгебру hZ; +, ·i, алгебру hZ; +, ·i — в алгебру
hQ; +, ·i, алгебру hQ; +, ·i — в алгебру hR; +, ·i, алгебру hR; +, ·i — в алгебру
hC; +, ·i. Поэтому с точностью до изоморфизма можно считать, что каж- дая из этих алгебр является подалгеброй каждой из последующих алгебр и имеют место включения N ⊂ Z ⊂ Q ⊂ R ⊂ C.
Приведенные конструкции позволяют проследить процесс образования числовых систем с помощью основных теоретико-множественных операций исходя из пустого множества.
§ 3.2.
Системы счисления
1.
Позиционные системы счисления
В современных компьютерах любая информация представляется в ви- де двоичных кодов, т. е. упорядоченных наборов двух различных символов,
которые обычно обозначаются через 0 и 1. В связи с этим часто прихо- дится использовать системы счисления, отличные от привычной десятичной системы счисления. При этом в основном используются позиционные систе- мы счисления, которые строятся по тем же принципам, что и десятичная система.