пусть A и B - два непустых множества. пусть есть отображение f : A → B
отображение f иньективно (мономорфно), если для любых x,y∈A из x ≠ y следует f(x) ≠ f(y) что означает, что каждый элемент домена отображается в отличный от других элемент кодомена. говорят, что А вкладывается в В
отображение f cюрьективно (эпиморфно), если для каждого y∈B существует x∈A, такой что f(x) = y сие означает, что диапазон покрыт полностью. говорят, что А накрывает В
отображение f биективно (изоморфно), если оно одновременно иньективно и сюрьективно
примером изоморфизма служит изоморфизм двух картезианских произведений множеств:
* * *
вот возьмём что-то простое - множество. у множества свойств не очень много - ну что там, сами элементы назвать, да ещё их количество можно посчитать
наделим наше множество определённой структурой, а именно: скажем, что помимо прочего на множестве определена операция, которая двум элементам множества сопоставляет элемент этого множества. пока не очень интересно
добавим некоторые свойства для этой операции: пусть она ассоциативна (какое-то слово), пусть существует выделенный относительно неё элемент нашего множества - выделен он так, что… (тут мы пишем про единицу и про обратный элемент). мы получили нечто, что называется группой. это множество, на котором ещё сверху стоит какая-то пристройка
можно строить дальше - пусть группа оснащена ещё одной дополнительной структурой (и тут мы пишем аксиомы кольца) - получаем кольцо
структура представляет собой
структура с пустым набором отношений называется "универсальной алгеброй"
структура с пустым набором операций называется "моделью"
заданные на наборе бинарные операции определяют некоторые интересные структуры на данном наборе: при этом, как частные случаи, структура может быть полугруппой, недогруппой, группой, полукольцом, недокольцом, кольцом, телом или полем, а также (если она сетоид) полурешеткой или решеткой
моноид - это категория с одним обьектом и с эндоморфизмами
Def: сетоидом (setoid, E-set, Bishop set) называется структура, снабженная отношением эквивалентности
если мы определим "отношение эквивалентости на множестве" - мы тут же получим классы конгруэнтности на нем (рассматривая "эквивалентность" как "равенство")
например: пусть X - непустое множество и A ⊂ X. введем отношение эквивалентности ∼ на X :
x ∼ y ⇐⇒ x = y | (x∈A & y∈A)эта операция называется стягиванием A в точку
сетоиды нужны тогда, когда различие между идентичностью (identity) и сопоставимостью (equivalence) должны быть явны
Def: полугруппа (semigroup) - структура, для элементов которой определена (замкнутая) бинарная операция. нейтрального элемента (а следовательно и инверсий) не требуется
примером полугруппы является структура с тремя элементами и с такой вот таблицей Кэли для операции:
| камень коса платок -------+---------------------------- камень | камень камень платок коса | камень коса коса платок | платок коса платокнейтрального элемента здесь не выбрать в принципе
докажем математическую корректность реализации и сгенерим код этой игры для Ocaml с помощью Coq (btw, так пишется код для аэронавтики и реакторов)
любые отображения множества на себя (автоморфизмы) можно выполнять последовательно, поэтому они (отображения) естественным образом образуют полугруппу с операцией композиция отображений
другим примером полугруппы являются нормали ко всем элементам любого выпуклого множества точек двумерной сферы вместе с операцией умножения (например - inner-product в прямоугольной системе координат, связанной с центром сферы)
полугруппа является магмой - категорией с бинарной операцией без аксиом, а только с таблицей Кэли. магма, это структура с бинарной операцией, у которой нет коммутативности, нет обратного элемента, нет нейтрали и нет ассоциативности ;-) ну это шутка. а если строго по определению, это просто синоним замкнутой бинарной операции, без каких-либо дополнительных свойств
пример магмы с неассоциативной и некоммутативной операцией:
| i j k --+------------- i | i j j j | k k j k | j i k i ∙ j = j ≠ k = j ∙ i (i ∙ j) ∙ j = k ≠ j = i ∙ (j ∙ j)нет нейтрали, а значит и нет обратных элементов. вуаля!
еще один пример неассоциативности и некоммутативности в магме
| i j --+---------- i | j i j | j i (i ∙ j) ∙ i = j i ∙ (j ∙ i) = i i ∙ j = i ≠ j = j ∙ i
Def: недогруппа - это структура, для обьектов которой определена замкнутая бинарная операция c нейтральным элементом. инверсий не требуется
элемент e ∈ X называется левым нейтральным, если
примерами недогруппы служат: натуральные числа, дополненные нулем - для операции сложения, и целые числа - для операции умножения
другим примером недогруппы служит структура с образующими {0,1}, с бинарной операцией Λ и c нейтралью 1
Λ | 0 1 --+----- 0 | 0 0 1 | 0 1
очень похожим примером недогруппы служит структура с образующими {0,1}, с бинарной операцией V и c нейтралью 0
V | 0 1 --+----- 0 | 0 1 1 | 1 1сразу видно, что инверсий (соответственно - нуля и единицы) в таких таблицах не получить
Def : группа - структура, для элементов которой определена замкнутая бинарная операция (пусть будет ∙
), нейтраль и инверсии
групповая операция ∙
должна быть ассоциативна
Def : если групповая операция коммутативна, то группа называется абелевой
Def : элемент x ∈ G называется обратимым слева, если существует элемент y ∈ G такой, что
(x⁻)⁻ = x
(x ∙ y)⁻ = y⁻ ∙ x⁻ и для некоммутативного случая важен порядок операндов
в группе разрешимы все уравнения вида g ∙ x = h, достаточно умножить обе части этого равенства слева на g⁻, что дает
с другой стороны, решением уравнения y ∙ g = h является y = h ∙ g⁻
если g и h не коммутируют, то эти два решения не совпадают, так что в неабелевых группах нужно различать левое частное
можно сокращать на любой элемент справа и слева. возможность левого сокращения означает, что равенство
Def : порядком конечной группы называется число ее элементов
примерами самой маленькой группы является группа { 1 } по умножению и изоморфная ей группа { 0 } по сложению
чуть больше размером группа с двумя элементами { 1 , a } со следующей таблицей Кэли:
| 1 a --+-------- 1 | 1 a a | a 1
и еще чуть больше группа с тремя элементами { 1 , a, b } со следующей таблицей Кэли:
| 1 a b ---+---------- 1 | 1 a b a | a b 1 b | b 1 a
примером группы являются множество целых чисел ℤ для операции сложения (c нейтралью 0)
множества ℚ, ℝ, ℂ образуют группы по сложению
множества
группами явлются "движения прямой" (Transfer, Simmetry, Id) и "движения окружности" (Rotation, Symmetry, Id) по отношению к операции "композиции движений" ∘
:
∘ | Id T S ∘ | Id R S ---+------------- ---+------------ Id | Id T S Id | Id R S T | T T S R | R R S S | S S T S | S S RId - тривиальное отображение - является нейтральным элементом этих двух групп
множество T комплексных чисел модуля 1 представляет собой группу по умножению. впрочем, операция в этой группе (группе "поворотов эвклидовой плоскости" или "группе углов") обычно записывается аддитивно, что согласуется со следующей ее интерпретацией: группа T истолковывается как аддитивная группа вещественных чисел ℝ₊ по модулю 2πℤ ("целые кратные 2π"). иными словами, T представляется как полуинтервал [0,2π), операция сложения ⊕ на котором определяется следующим образом:
если x + y < 2π, то x ⊕ y = x + y, если x + y ≥ 2π, то x ⊕ y = x + y − 2πв действительности, конечно, операция в T записывается обычным знаком + ("сложение углов")
множество 2Xподмножеств в X является группой относительно симметрической разности ("булевой суммы") ∆. нейтральный элемент этой операции равен ∅, а поскольку Y ∆ Y = ∅, то каждый элемент является симметричным сам себе
Def: элементы группы, замкнутые относительно групповой операции и имеющие среди себя единицу группы называются подгруппой
или
Def: пoдмножество H ⊆ G называется подгруппой в G, если оно само является группой относительно групповой операции G
иными словами, для того, чтобы H было подгруппой, необходимо выполнение следующих трех условий:
i) h , g ∈ H ⇒ h . g ∈ H ii) h ∈ H ⇒ h⁻ ∈ H iii) e ∈ H
или
Def : H ⊂ G, являющееся группой относительно операции группы G, называется подгруппой G и обозначается как
для конечных групп достаточно убедиться что в подгруппе групповая операция попарно дает элемент подгруппы же, и тогда обратный и единичный будут там уже автоматически
четные числа являются подгруппой натуральных
положительные целые являются подгруппой целых (как для операции "сложение" так и для операции "умножение")
для группы "движений прямой" подгруппой является
Def: полукольцо (rig) - это множество элементов со структурой недогруппы по сложению и недогруппы по умножению. сложение коммутативно, а умножение дистрибутивно над ним
отсутствие инверсий (negate) отражается в отсутсвии буковки n в слове "rig"
Def: недокольцо (rng) - это множество элементов со структурой группы по сложению и полугруппы по умножению (кольцо без единицы по умножению и следовательно - без инверсий). тот факт, что negate есть, а единицы (I) по умножению - нет, отражается в отсутствии буковки i в слове "rng"
Def: кольцо (ring) - это множество элементов со структурами: группы по сложению и недогруппы по умножению. операции сложения и умножения должны быть связаны законами дистрибутивности слева и справа. если операция умножения ∙
коммутативна
Def: непустое множество R с двумя бинарными операциями, сложением +
и умножением ∙
, называется кольцом, если R образует абелеву группу по сложению и умножение двусторонне-дистрибутивно относительно сложения
иными словами, предполагается, что выполнены следующие четыре аксиомы, относящиеся к сложению:
A1: ∀ x, y, z ∈ R, (x + y) + z = x + (y + z) A2: ∃ 0 ∈ R, ∀ x ∈ R, x + 0 = x = 0 + x A3: ∀ x ∈ R, ∃ −x ∈ R, x + (− x) = 0 = (− x) + x A4: ∀ x, y ∈ R, x + y = y + x
через R⁺ обозначается аддитивная группа кольца R, которая получается, когда мы забываем о том, что на R задано умножение. однако в действительности умножение в кольце есть и оно связано со сложением следующими двумя аксиомами дистрибутивности:
D1: ∀ x, y, z ∈ R, x∙
(y + z) = (x∙
y) + (x∙
z) (правая дистрибутивность) D2: ∀ x, y, z ∈ R, (x + y)∙
z = (x∙
z) + (y∙
z) (левая дистрибутивность)
Def: R - ассоциативное кольцо с единицей, если R образует моноид по умножению, т.е. если дополнительно к A1-A4, D1, D2 выполнены две следующие аксиомы:
M1: ∀ x, y, z ∈ R, (x∙
y)∙
z = x∙
(y∙
z) M2: ∃ 1 ∈ R, ∀ x ∈ R, x∙
1 = x = 1∙
x
если, кроме того, умножение коммутативно, т.е
M3: ∀ x, y ∈ R, xто кольцо R будет называться коммутативным∙
y = y∙
x
Def : подкольцо кольца K - это пара (R,φ), где R - кольцо, а
подкольцо кольца K рассматривается как подмножество R ⊂ K, замкнутое относительно операций из основного кольца K
например, кольцо целых чисел ℤ является подкольцом поля вещественных чисел ℝ и подкольцом кольца полиномов ℤ[x]
Def: тело (skew-field) - структура, для элементов которой определены ассоциативные операции: сложения с инверсиями, умножения c инверсиями (кроме умножения для нуля). коммутативных свойств по умножению не требуется
примером тела является тело кватернионов:
ℍ = { ( z w _ _ -w z ) | z , w ∈ ℂ } c базисом ±( 1 0 ±( i 0 ±( 0 1 ±( 0 i 0 1 ) 0 -i ) -1 0 ) i 0 )
Def: поле (field) - структура, для элементов которой определены ассоциативные и коммутативные операции сложения-умножения c инверсиями (кроме инверсии умножения для нуля - "делить на ноль нельзя")
другими словами, поле - это структура со свойствами
любое поле является телом
Def : пусть F ⊂ K - два поля. F называют подполем (subfield) K, и K называют расширением (extension) F
число x ∈ K называется алгебраическим над F если x является корнем нетривиального полинома с коэффициентами в F. сумма и произведение алгебраических чисел - тоже алгебраическое число
в аддитивной группе поля единица порождает циклическую подгруппу
⟨1⟩ = { 1, 1 + 1, 1 + 1 + 1, ... }если данная группа - конечна и содержит n элементов, то говорят, что характеристика поля равна n. если циклическая группа ⟨1⟩ бесконечна, то говорят, что характеристика поля - нулевая
если у поля F характеристика равна n > 0, то n - простое число. действительно, если n - непростое, то n=m*k, и значит в поле F сумма m единиц (не равная нулю), умноженная на сумму k единиц (не равную нулю) равна нулю. значит, в поле имеются делители нуля, что невозможно для поля по определению
в поле с характеристикой p > 0 выполняется правило "детских биномиальных коэффициентов" :
(x + y)n= xn+ yn
в поле с характеристикой 0 выполняется правило "биноминальных коэффициентов":
n (x + y)n= Σ (n, k) * xn-k* yk k=0
поле ⊂ коммутативное кольцо ∩ ∩ тело ⊂ кольцо
* * *
все вместе определенное на Haskell
* * *
Def: решётка (lattice) - частично упорядоченное множество, в котором каждое двухэлементное подмножество имеет как точную верхнюю (sup), так и точную нижнюю (inf) грани
решётка может быть определена как алгебра с двумя бинарными операциями (они обозначаются + и ∙
), удовлетворяющая следующим тождествам:
a + b = sup (a , b) a∙
b = inf (a , b) a + a = a a∙
a = a идемпотентность a + b = b + a a∙
b = b∙
a коммутативность a + (b + c) = (a + b) + c a∙
(b∙
c) = (a∙
b)∙
c ассоциативность a∙
(a + b) = a a + (a∙
b) = a поглощение
эквивалентны следующие утверждения:
a ≤ b
a ∙
b = a
a + b = b
отображение f : L → M одной решетки в другую называется гомоморфизмом, если оно сохраняет операции
f (X * Y) = f (X) * f (Y) и f (X + Y) = f (X) + f (Y)для любых X,Y ∈ L
отображение f : L → M одной решетки в другую называется дуальным гомоморфизмом, если оно переставляет операции, т.е.
f (Xдля любых X,Y ∈ L∙
Y) = f (X) + f (Y) и f (X + Y) = f (X)∙
f (Y)
появление понятия "решётка" относится к середине XIX века. чётко его сформулировал Дедекинд в работах 1894 и 1897 годов. сам термин "lattice" был введён Биркгофом в 1933 году
важная роль теории решёток объясняется тем, что многие факты, касающиеся множества идеалов и множества нормальных подгрупп, выглядят аналогично и могут быть доказаны в рамках теории решёток
фильтр - подмножество решётки, удовлетворяющее определённым условиям
Def : подмножество F элементов решётки L называется фильтром, если ∀ a,b ∈ F
a ∙
b ∈ F
а также если ∀ a ∈ F и b : a ≤ bb ∈ F
Def : фильтр F решетки L называется собственным, если F ≠ L
Def : собственный фильтр такой, что не существует других собственных фильтров, его содержащих, называется ультрафильтром
Def : фильтр F называется простым, если ∀ a,b ∈ L выполняется:
a + b ∈ F => (a ∈ F) \/ (b ∈ F)
Def : минимальный фильтр, содержащий данный элемент x, называется главным фильтром, сгенерированным элементом x
ультрафильтр на конечном множестве всегда является главным. каждый фильтр содержится в ультрафильтре
фильтр - это понятие, сродни идеалу. если F фильтр, то L/F является идеалом
фильтр не может быть топологией, а топология не может быть фильтром, поскольку фильтр не может содержать в себе пустого множества, а любая топология обязана содержать в себе пустое множество