индекс

  • моноид
  • сетоид
  • полугруппа
  • недогруппа
  • группа
  • подгруппа
  • полукольцо
  • недокольцо
  • кольцо
  • подкольцо
  • тело
  • поле
  • решетки
  • фильтры

  • пусть 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 биективно (изоморфно), если оно одновременно иньективно и сюрьективно
    примером изоморфизма служит изоморфизм двух картезианских произведений множеств: A ⨯ B ≅ B ⨯ A

    * * *

    вот возьмём что-то простое - множество. у множества свойств не очень много - ну что там, сами элементы назвать, да ещё их количество можно посчитать
    наделим наше множество определённой структурой, а именно: скажем, что помимо прочего на множестве определена операция, которая двум элементам множества сопоставляет элемент этого множества. пока не очень интересно
    добавим некоторые свойства для этой операции: пусть она ассоциативна (какое-то слово), пусть существует выделенный относительно неё элемент нашего множества - выделен он так, что… (тут мы пишем про единицу и про обратный элемент). мы получили нечто, что называется группой. это множество, на котором ещё сверху стоит какая-то пристройка
    можно строить дальше - пусть группа оснащена ещё одной дополнительной структурой (и тут мы пишем аксиомы кольца) - получаем кольцо

    структуры

    структура представляет собой

    структура с пустым набором отношений называется "универсальной алгеброй"

    структура с пустым набором операций называется "моделью"

    NB: алгебраисты всегда называют алгеброй лишь свободный модуль над кольцом (линейное пространство), а просто структуру с сигнатурой они называют алгебраической системой

    заданные на наборе бинарные операции определяют некоторые интересные структуры на данном наборе: при этом, как частные случаи, структура может быть полугруппой, недогруппой, группой, полукольцом, недокольцом, кольцом, телом или полем, а также (если она сетоид) полурешеткой или решеткой


    моноид

    моноид - это категория с одним обьектом и с эндоморфизмами

    Coq

    сетоид

    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 называется левым нейтральным, если e ∙ x = x для всех x ∈ X и правым нейтральным, если x ∙ 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 такой, что y ∙ x = e. элемент y называется левым обратным к x ; x называется обратимым справа, если существует элемент z ∈ G такой, что x ∙ z = e. элемент z называется правым обратным к x ; если у элемента x существуют и левый обратный k и правый обратный t, то k = t

    (x⁻)⁻ = x
    (x ∙ y)⁻ = y⁻ ∙ x⁻ и для некоммутативного случая важен порядок операндов

    в группе разрешимы все уравнения вида g ∙ x = h, достаточно умножить обе части этого равенства слева на g⁻, что дает x = g⁻ ∙ h
    с другой стороны, решением уравнения y ∙ g = h является y = h ∙ g⁻
    если g и h не коммутируют, то эти два решения не совпадают, так что в неабелевых группах нужно различать левое частное g⁻ ∙ h от правого частного h ∙ g⁻

    можно сокращать на любой элемент справа и слева. возможность левого сокращения означает, что равенство g ∙ x = g ∙ y влечет x = y. возможность правого сокращения означает, что если x ∙ g = y ∙ g, то x = y

    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)

    множества ℚ, ℝ, ℂ образуют группы по сложению

    множества ℚ₊ = { x ∈ ℚ | x > 0 } и ℝ₊ = { x ∈ ℝ | x > 0 } положительных рациональных и положительных вещественных чисел представляют собой группы по умножению (с нейтралью 1)

    группами явлются "движения прямой" (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   R
    Id - тривиальное отображение - является нейтральным элементом этих двух групп

    группа углов (circle group)

    множество 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 и обозначается как H ◁ G. по определению H ◁ G тогда и только тогда, когда:

    для конечных групп достаточно убедиться что в подгруппе групповая операция попарно дает элемент подгруппы же, и тогда обратный и единичный будут там уже автоматически

    примеры

    четные числа являются подгруппой натуральных

    положительные целые являются подгруппой целых (как для операции "сложение" так и для операции "умножение")

    для группы "движений прямой" подгруппой является


    полукольцо

    Def: полукольцо (rig) - это множество элементов со структурой недогруппы по сложению и недогруппы по умножению. сложение коммутативно, а умножение дистрибутивно над ним

    отсутствие инверсий (negate) отражается в отсутсвии буковки n в слове "rig"

    Coq

    недокольцо

    Def: недокольцо (rng) - это множество элементов со структурой группы по сложению и полугруппы по умножению (кольцо без единицы по умножению и следовательно - без инверсий). тот факт, что negate есть, а единицы (I) по умножению - нет, отражается в отсутствии буковки i в слове "rng"

    Coq

    кольцо

    Def: кольцо (ring) - это множество элементов со структурами: группы по сложению и недогруппы по умножению. операции сложения и умножения должны быть связаны законами дистрибутивности слева и справа. если операция умножения коммутативна ( a ∙ b = b ∙ a ), то кольцо называется коммутативным, но в общем случае этого не требуется

    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  y = y  x
    то кольцо R будет называться коммутативным

    Coq

    подкольцо

    Def : подкольцо кольца K - это пара (R,φ), где R - кольцо, а φ :R → K есть мономорфизм (вложение) колец

    подкольцо кольца 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  Y) = f (X) + f (Y)
    и
         f (X + Y) = f (X)  f (Y)
    для любых X,Y ∈ L

    появление понятия "решётка" относится к середине XIX века. чётко его сформулировал Дедекинд в работах 1894 и 1897 годов. сам термин "lattice" был введён Биркгофом в 1933 году

    важная роль теории решёток объясняется тем, что многие факты, касающиеся множества идеалов и множества нормальных подгрупп, выглядят аналогично и могут быть доказаны в рамках теории решёток

    фильтры

    фильтр - подмножество решётки, удовлетворяющее определённым условиям

    Def : подмножество F элементов решётки L называется фильтром, если ∀ a,b ∈ F

        a  b ∈ F
    а также если ∀ a ∈ F и b : a ≤ b
        b ∈ 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 является идеалом

    фильтр не может быть топологией, а топология не может быть фильтром, поскольку фильтр не может содержать в себе пустого множества, а любая топология обязана содержать в себе пустое множество


    индекс