Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
d dx ® (где d dx — операция дифференцирова- ния) не является алгеброй, поскольку не всякая функция дифференцируема, 56 Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ но если рассмотреть множество A = {f (x) | f (x) дифференцируема беско- нечное число раз}, то отображение дифференцирования d dx : f 7→ df dx является операцией на A и пара A; d dx ® образует алгебру. ¤ Заметим, что частичную операцию f , отображающую A n в A, можно рассматривать как (n + 1)-местное отношение R f {(x 1 , x 2 , . . . , x n , y) | (x 1 , . . . , x n ) ∈ A n и y = f (x 1 , . . . , x n )}. Поэтому в последнем примере пару {f (x) | f : R → R}; d dx ® можно считать алгебраической системой, если рассматривать d dx как бинарное отношение © (f, g) | g = df dx ª Алгебра A сигнатуры Σ = {f }, где µ(f ) = 2, называется группоидом. Единственная здесь операция f обычно обозначается символом ·: A = hA; ·i. Если A — конечное множество, действия операции · можно задать квадрат- ной таблицей, в которой для каждой пары (a i , a j ) ∈ A 2 записан результат действия ·(a i , a j ). Такая таблица называется таблицей Кэли группоида A. Группоид A называется полугруппой, если · — ассоциативная операция, т. е. для всех элементов x, y, z ∈ A верно x · (y · z) = (x · y) · z. Полугруппа A на- зывается моноидом, если существует элемент e ∈ A, называемый единицей, такой, что e · x = x · e = x для всех x ∈ A. Полугруппы и моноиды имеют особое значение в теории языков при обработке слов. Пример 2.1.2. Пусть W (X) — множество слов алфавита X. Определим на W (X) операцию конкатенации ˆследующим образом: если α, β ∈ W (X), то αˆβ = αβ, т. е. результатом является слово, полученное соединением слов α и β (например, xyzˆzx = xyzzx). Операция ˆ ассоциативна, т. е. для лю- бых слов α, β, γ верно (αˆβ)ˆγ = αˆ(βˆγ). Следовательно, система hW (X);ˆi является полугруппой. Так как для всех α ∈ W (X) верно Λˆα = αˆΛ = α, где Λ — пустое слово, то Λ удовлетворяет свойству единицы. Таким образом, система hW (X);ˆi является моноидом. ¤ Моноид A = hA; ·i называется группой, если для любого элемента x ∈ A существует элемент x −1 ∈ A, называемый обратным к x, такой, что x · x −1 = x −1 · x = e. Группа A называется коммутативной или абелевой, если x · y = y · x для всех x, y ∈ A. Пример 2.1.3. 1. Если hK; +, ·i — кольцо, то hK; +i — абелева группа. 2. Система hGL n (K); ·i, где GL n (K) {A | A — матрица порядка n над полем K, и det A 6= 0} является группой, которая некоммутативна при n > 2. ¤ 2.2. МОРФИЗМЫ 57 § 2.2. Морфизмы Пусть даны алгебраические системы A = hA; Σi и B = hB; Σi. Отобра- жение ϕ: A → B называется гомоморфизмом системы A в систему B, если выполняются следующие условия: 1) для любого функционального символа f (n) ∈ Σ, соответствующих функций f A и f B в системах A и B и любых a 1 , a 2 , . . . , a n ∈ A выполня- ется ϕ(f A (a 1 , a 2 , . . . , a n )) = f B (ϕ(a 1 ), ϕ(a 2 ), . . . , ϕ(a n )); 2) для любого предикатного символа P (n) ∈ Σ, соответствующих преди- катов P A и P B в системах A и B и любых a 1 , a 2 , . . . , a n ∈ A выполняется (a 1 , a 2 , . . . , a n ) ∈ P A ⇒ (ϕ(a 1 ), ϕ(a 2 ), . . . , ϕ(a n )) ∈ P B . Если ϕ: A → B — гомоморфизм, то будем его обозначать через ϕ: A → B. При гомоморфизме сохраняются действия операций и отношения. Это позволяет переносить изучение свойств с одной системы на другую. Пример 2.2.1. Рассмотрим системы A = hZ; +, 6i и B = hZ 2 ; +, 6i, где в системе B сложение задается по правилу (a 1 , b 1 ) + (a 2 , b 2 ) = (a 1 + a 2 , b 1 + b 2 ), а отношение порядка — (a 1 , b 1 ) 6 (a 2 , b 2 ) ⇔ a 1 6 a 2 и b 1 6 b 2 . Отображение ϕ: Z → Z 2 , при котором ϕ(a) = (a, 0), является гомоморфиз- мом. Действительно, для любых a, b ∈ Z имеем ϕ(a + b) = (a + b, 0) = (a, 0) + (b, 0) = ϕ(a) + ϕ(b), и если a 6 b, то (a, 0) 6 (b, 0), т. е. ϕ(a) 6 ϕ(b). ¤ Гомоморфизм ϕ: A → B, являющийся инъекцией, называется мономор- физмом. Гомоморфизм ϕ: A → B, являющийся сюръекцией, называется эпиморфизмом, и при этом система B называется гомоморфным образом 58 Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ системы A. Гомоморфизм ϕ: A → A называется эндоморфизмом. Сюръек- тивный мономорфизм ϕ: A → B, для которого ϕ −1 — гомоморфизм, называ- ется изоморфизмом A на B и обозначается через ϕ: A ∼ → B. Если существует изоморфизм ϕ: A ∼ → B, то системы A и B называются изоморфными и обо- значается это так: A ' B. Таким образом, условие A ' B означает, что существует биекция ϕ: A ↔ B, удовлетворяющая следующим условиям: 1) для любого функционального символа f (n) ∈ Σ, соответствующих функций f A и f B в системах A и B и любых a 1 , a 2 , . . . , a n ∈ A выполня- ется ϕ(f A (a 1 , a 2 , . . . , a n )) = f B (ϕ(a 1 ), ϕ(a 2 ), . . . , ϕ(a n )); 2) для любого предикатного символа P (n) ∈ Σ, соответствующих преди- катов P A и P B в системах A и B и любых a 1 , a 2 , . . . , a n ∈ A выполняется (a 1 , a 2 , . . . , a n ) ∈ P A ⇔ (ϕ(a 1 ), ϕ(a 2 ), . . . , ϕ(a n )) ∈ P B . Изоморфизм ϕ: A ∼ → A называется автоморфизмом системы A. Заметим, что, поскольку изоморфизм ϕ: A ∼ → B является биекцией A ↔ B, изоморф- ные системы равномощны. Утверждение 2.2.1. 1. id A : A ∼ → A. 2. Если ϕ: A ∼ → B, то ϕ −1 : B ∼ → A. 3. Если ϕ: A 1 ∼ → A 2 и ψ: A 2 ∼ → A 3 , то ϕ ◦ ψ: A 1 ∼ → A 3 . ¤ Таким образом, отношение изоморфизма ' является эквивалентностью на любом множестве алгебраических систем (отметим, что класс всех алгеб- раических систем не является множеством, поскольку не существует множе- ства всех множеств). Это означает, что отношение изоморфизма разбивает множества алгебраических систем на классы эквивалентности, в каждом из которых содержатся системы, имеющие “одинаковое устройство”. Это да- ет возможность переносить изучение свойств с одной системы на другую, изоморфную ей. Так, используя факт изоморфизма геометрического вектор- ного пространства пространству строк, работу с геометрическими объекта- ми можно свести к действиям с наборами чисел, что позволяет применять компьютеры. Пример 2.2.2. 1. Рассмотрим множество векторов E 3 геометрическо- го векторного пространства с операциями сложения векторов и умножения 2.2. МОРФИЗМЫ 59 векторов на вещественные числа. Получим систему A = hE 3 ; +, {λ·} λ∈R i бес- конечной сигнатуры, где одноместные функции λ· ставят в соответствие век- тору a вектор λa. Рассмотрим также систему B = hR 3 ; +, {λ·} λ∈R i, носитель которой состоит из троек вещественных чисел (x, y, z), + — двухместная операция покоординатного сложения троек, а функция λ· — операция умно- жения троек на число λ для всех вещественных чисел λ. Системы A и B яв- ляются линейными пространствами над полем R. Отображение ϕ, ставящее в соответствие вектору a ∈ E 3 его координатную строку (x, y, z) в некотором фиксированном базисе e 1 , e 2 , e 3 , является биекцией (ϕ: E 3 ↔ R 3 ), при кото- рой сохраняются действия операций: ϕ(a+b) = ϕ(a)+ϕ(b) и ϕ(λ·a) = λ·ϕ(a). Таким образом, ϕ — изоморфизм линейных пространств A и B, и, следова- тельно, изучение геометрических векторов можно свести к изучению троек чисел и наоборот. 2. Рассмотрим два равномощных алфавита X, X 0 и алгебры A = hW (X);ˆi, B = hW (X 0 );ˆi (см. пример 2.1.2). Покажем, что A ' B. Так как |X| = |X 0 |, то существует биекция ϕ: X ↔ X 0 . Построим по ней би- екцию ψ: W (X) ↔ W (X 0 ), при которой слову α ∈ W (X) ставится в соответ- ствие слово β ∈ W (X 0 ), получающееся заменой каждого символа x в слове α на символ ϕ(x). Построенная биекция ψ дает искомый изоморфизм A на B, поскольку ψ(α 1 ˆα 2 ) = ψ(α 1 )ˆψ(α 2 ) для любых α 1 , α 2 ∈ W (X). 3. Для заданного множества U система hP(U); ∩, ∪, , 0, 1i изоморфна си- стеме hP(U); ∪, ∩, , 1, 0i с биекцией ϕ: A 7→ A. Действительно, по законам де Моргана ϕ(B ∩ C) = B ∩ C = B ∪ C = ϕ(B) ∪ ϕ(C) и ϕ(B ∪ C) = B ∪ C = B ∩ C = ϕ(B) ∩ ϕ(C) для любых B, C ∈ P(U). Кроме того, ϕ(A) = A = ϕ(A), ϕ(0) = 0 = 1 и ϕ(1) = 1 = 0. 4. Рассмотрим группы A = h(0, ∞); ·i, B = hR; +i и отображение ϕ: (0, ∞) → R по правилу ϕ(x) = log p (x) для некоторого фиксированно- го p ∈ (0, ∞), p 6= 1. Отображение ϕ является изоморфизмом систем A и B, называемым логарифмом (по основанию p). Это позволяет произво- дить умножение положительных чисел при помощи сложения вещественных чисел на основании тождества a · b = ϕ −1 (ϕ(a) + ϕ(b)), которое получается из равенства ϕ(a · b) = ϕ(a) + ϕ(b) применением отображения ϕ −1 к обеим частям. ¤ 60 Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ § 2.3. Подсистемы Алгебраическая система A = hA; Σi называется подсистемой системы B = hB; Σi (обозначается через A ⊆ B), если выполняются следующие условия: а) A ⊆ B; б) для любого функционального символа f (n) ∈ Σ, соответствующих функций f A и f B и любых элементов a 1 , a 2 , . . ., a n ∈ A выполняется равен- ство f A (a 1 , . . . , a n ) = f B (a 1 , . . . , a n ), т. е. интерпретации символа f действуют одинаково на элементах из A; в) для любого предикатного символа P (n) ∈ Σ, соответствующих пре- дикатов P A и P B справедливо равенство P A = P B ∩ A n , т. е. предикат P A содержит в точности те кортежи отношения P B , которые состоят из элемен- тов множества A. Если Σ — функциональная (предикатная) сигнатура, то подсистема A алгебры (модели) B называется подалгеброй (подмоделью). Пример 2.3.1. 1. Если V 0 — подпространство линейного пространства V , то V 0 — подсистема (подалгебра) системы V . 2. Если Σ = {P (1) }, B = hB; Σi — система, ∅ 6= A ⊆ B, то A = hA; Σi является подсистемой системы B тогда и только тогда, когда P A = P B ∩A. ¤ Теорема 2.3.1. Если B — алгебраическая система, X ⊆ B, X 6= ∅, то существует единственная подсистема B(X) ⊆ B с носителем B(X), такая, что X ⊆ B(X) и B(X) ⊆ A для любой подсистемы A ⊆ B с усло- вием X ⊆ A. Доказательство. В качестве B(X) рассмотрим пересечение носите- лей A всех подсистем A ⊆ B, содержащих X. Так как X ⊆ B(X), то B(X) 6= ∅. Единственность подсистемы B(X) очевидна. ¤ Подсистема B(X) из теоремы 2.3.1 называется подсистемой, порожден- ной множеством X в B. Она является наименьшей подсистемой системы B, содержащей множество X. Пример 2.3.2. Напомним, что если V — линейное пространство, S — некоторое непустое множество векторов пространства V , то линейная обо- лочка L(S) множества S в V состоит из всевозможных линейных комби- наций векторов из S. Алгебра L(S) является подалгеброй пространства V , порожденной множеством S. ¤ 2.3. ПОДСИСТЕМЫ 61 Для описания устройства подсистемы B(X) определим индукцией по по- строению понятие терма сигнатуры Σ: 1) переменные x, y, z, . . . и константные символы из Σ суть термы; 2) если f ∈ Σ — n-местный функциональный символ, t 1 , t 2 , . . ., t n — термы, то f (t 1 , . . . , t n ) — терм; 3) никаких термов, кроме построенных по пп. 1, 2, нет. Таким образом, термом является любое функциональное выражение, со- ставленное с помощью переменных и (или) сигнатурных функциональных символов. Множество всех термов сигнатуры Σ обозначается через T (Σ). Пример 2.3.3. 1. Термами сигнатуры Σ = {+, ·, 6, 0} будут, например, 0, x, x + y, z · (x + z) + 0 · y, а x + y 6 (0 + z) · x термом не является. 2. Если Σ = {f, g, h} — функциональная сигнатура, где µ(f ) = 3, µ(g) = 1, µ(h) = 2, то выражения h(f (x 1 , x 2 , x 3 ), g(x 2 )), g(f (h(x 1 , x 2 ), x 1 , g(x 2 )) — тер- мы, а h(x 1 , f (x 1 , x 3 )) не образует терма. 3. В сигнатуре Σ = {отец (1) , Иван (0) } терм отец(отец(Иван)) можно про- интерпретировать как “дедушка Ивана”. ¤ Пусть t(x 1 , x 2 , . . . , x k ) — терм из T (Σ), все переменные которого содер- жатся среди x 1 , x 2 , . . . , x k ; A = hA; Σi — алгебраическая система. Значение терма t при значениях a 1 , a 2 , . . . , a k ∈ A переменных x 1 , x 2 , . . . , x k (обозна- чается через t(a 1 , a 2 |